Difference between revisions of "Atomic Stack Assignment"

From CSE231 Wiki
Jump to navigation Jump to search
Line 73: Line 73:
 
The constructor
 
The constructor
  
  <nowiki>public DefaultNode(E value, Optional<Node<E>> nextNode)</node>
+
  <nowiki>public DefaultNode(E value, Optional<Node<E>> nextNode)</nowiki>
  
 
is passed a value and a nextNode.  Hang on to this data in instance variables.  As instances of DefaultNode are to be immutable, the instance variables should be marked as <code>final</code>.
 
is passed a value and a nextNode.  Hang on to this data in instance variables.  As instances of DefaultNode are to be immutable, the instance variables should be marked as <code>final</code>.
Line 93: Line 93:
 
Optional<E> pop();
 
Optional<E> pop();
 
}</nowiki>
 
}</nowiki>
 +
 
===NotThreadSafeStack===
 
===NotThreadSafeStack===
 
[https://www.javadoc.io/static/com.google.code.findbugs/jsr305/3.0.1/javax/annotation/concurrent/NotThreadSafe.html @NotThreadSafe]
 
[https://www.javadoc.io/static/com.google.code.findbugs/jsr305/3.0.1/javax/annotation/concurrent/NotThreadSafe.html @NotThreadSafe]

Revision as of 02:33, 10 November 2022

Background

Implicit Locks

synchronized methods

Atomics

AtomicReference<V>

get()
compareAndSet(expect, update)

Node and Stack Interfaces

interface Node

public interface Node<E> {
	E value();
	Optional<Node<E>> nextNode();
}

interface Stack

public interface Stack<E> {
	void push(E value);
	Optional<E> peek();
	Optional<E> pop();
}

Example

empty

Stack<String> stack = new NotThreadSafeStack<>(DefaultNode::new);

Stack empty.svg

In this state, stack.peek() will return Optional.empty() and stack.pop() will also return Optional.empty().

push A, B, C, D, E

Stack<String> stack = new NotThreadSafeStack<>(DefaultNode::new);
stack.push("A");
stack.push("B");
stack.push("C");
stack.push("D");
stack.push("E");

Stack edcba.svg

In this state, stack.peek() will return Optional.of("E").

push A, B, C, D, E, pop

Stack<String> stack = new NotThreadSafeStack<>(DefaultNode::new);
stack.push("A");
stack.push("B");
stack.push("C");
stack.push("D");
stack.push("E");
Optional<String> optOfE = stack.pop();

Stack dcba.svg

In this state, optOfE will hold Optional.of("E") and stack.peek() will return Optional.of("D").

Code To Implement

Node

public interface Node<E> {
	E value();

	Optional<Node<E>> nextNode();
}

DefaultNode

The mighty cons cell goes back to the early days of computing. People have been building amazing systems with this data structure since the 1950s.

We will build an @Immutable class DefaultNode which implements interface Node.

class: DefaultNode.java Java.png
methods: value
nextNode
package: stack.node.exercise
source folder: main/src/main/java

constructor and instance variables

The constructor

public DefaultNode(E value, Optional<Node<E>> nextNode)

is passed a value and a nextNode. Hang on to this data in instance variables. As instances of DefaultNode are to be immutable, the instance variables should be marked as final.

value

return the value.

nextNode

return the next node.

Stack

public interface Stack<E> {
	void push(E value);

	Optional<E> peek();

	Optional<E> pop();
}

NotThreadSafeStack

@NotThreadSafe

class: NotThreadSafeStack.java Java.png
methods: constructor
nodeConstructor
push
peek
pop
package: stack.notthreadsafe.exercise
source folder: student/src/main/java

constructor and instance variables

nodeConstructor

push

peek

pop

ConcurrentStack

@ThreadSafe

class: ConcurrentStack.java Java.png
methods: constructor
nodeConstructor
push
peek
pop
package: stack.concurrent.exercise
source folder: student/src/main/java

constructor and instance variables

nodeConstructor

push

peek

pop

AtomicStack

@ThreadSafe

class: AtomicStack.java Java.png
methods: constructor
nodeConstructor
push
peek
pop
package: stack.atomic.exercise
source folder: student/src/main/java

constructor and instance variables

nodeConstructor

push

peek

pop

Testing

class: StackTestSuite.java Junit.png
package: stack.exercise
source folder: testing/src/test/java

DefaultNode

class: _DefaultNodeTestSuite.java Junit.png
package: stack.node.exercise
source folder: testing/src/test/java

NotThreadSafeStack

class: _NotThreadSafeStackTestSuite.java Junit.png
package: stack.notthreadsafe.exercise
source folder: testing/src/test/java

ConcurrentStack

class: __ConcurrentStackTestSuite.java Junit.png
package: stack.concurrent.exercise
source folder: testing/src/test/java

sequential

class: _ConcurrentStackSequentialTestSuite.java Junit.png
package: stack.concurrent.exercise
source folder: testing/src/test/java

parallel

class: _ConcurrentStackParallelTestSuite.java Junit.png
package: stack.concurrent.exercise
source folder: testing/src/test/java

AtomicStack

class: __AtomicStackTestSuite.java Junit.png
package: stack.atomic.exercise
source folder: testing/src/test/java

sequential

class: _AtomicStackSequentialTestSuite.java Junit.png
package: stack.atomic.exercise
source folder: testing/src/test/java

parallel

class: _AtomicStackParallelTestSuite.java Junit.png
package: stack.atomic.exercise
source folder: testing/src/test/java