Stacked up (Easy Version)

This is the easy version of LockFreeStack. The only differences between this and the hard version are the memory reclamation strategy required and the type constraints on stored elements. Solving one problem does not guarantee solving the other.

Implement the class LockFreeStack, which is an unbounded lock-free multi-producer multi-consumer stack.

Constructor

LockFreeStack()

• Constructs an empty stack.

Methods

push(value)

• Pushes value onto the top of the stack.
• This operation always succeeds (the stack is unbounded).
• Multiple threads may call push concurrently.

pop(out)

• Attempts to pop the top element and store it in out.
• Returns true if the pop succeeds.
• Returns false if the stack is empty at the operation's linearization point (no spurious failures).
• Multiple threads may call pop concurrently.

Notes

• The implementation must be lock-free (no std::mutex, no condition variables, etc.). Using a lock may result in a compilation error.
• Multiple producers and multiple consumers may call push/pop concurrently.
• You do not need to write any input/output parsing.
• Your submission will be tested with a multithreaded grader and heavy stress tests.
• ABA prevention is required. A naive CAS loop on raw pointers is vulnerable to ABA. Your implementation must use a strategy to prevent it. Common approaches include:
  • Tagged pointers (pack a monotonic counter alongside the pointer in a single atomic word).
  • Hazard pointers (defer reclamation of nodes that may still be referenced by other threads).
  • Epoch-based reclamation.
  • For this easy version, tagged pointers with deferred delete are sufficient. You do not need to implement full safe memory reclamation — but you must prevent ABA on the head pointer.
• Runtime environment: The judge runs on a resource-constrained container. Heavyweight reclamation strategies (hazard pointers, epoch-based reclamation) may cause timeouts or flaky results due to limited core count. Tagged pointers are the intended approach for this version. The hard version requires safe memory reclamation and runs on a less constrained environment.
• Type constraints (easy version):
  • You may assume the stored type T is int. Note that the class is still templated.
• We run strong stress tests to catch common concurrency bugs (duplicate pops, lost pushes, ABA-triggered corruption), but this does not prove the absence of all data races.
• You may assume the stack will not be destroyed during concurrent push or pop operations.
• The grader uses a node-reuse allocator to actively trigger ABA in vulnerable implementations. A solution that "works in practice" but is theoretically vulnerable to ABA will fail.