Treiber Stack

Implementation here

Overview

• A Treiber lock-free stack with support for blocking pops.
• Usable with any number of producers and consumers.
• The stack is implemented as a singly linked list with a pointer to the top.
• Uses tagged pointers to avoid the ABA problem.

Related sources:

• Treiber stack: https://habr.com/ru/post/216013/
• Algorithm: https://people.csail.mit.edu/shanir/publications/Lock_Free.pdf

Other implementations:

• Libcdc:
  • Source code: https://github.com/khizmax/libcds/blob/master/cds/intrusive/treiber_stack.h
  • Doc: http://libcds.sourceforge.net/doc/cds-api/classcds_1_1container_1_1_treiber_stack.html
  • Intro guide: https://habr.com/ru/post/196834/
• Boost:
  • Source code: https://www.boost.org/doc/libs/1_54_0/boost/lockfree/stack.hpp