LockFreeLinkedList

Lock Free Linked List Based On Harris'OrderedListBasedSet And Michael's Hazard Pointer.

Feature

• Thread-safe and Lock-free.
• ABA safe.
• Set implemented through singly ordered linked list[1].
• Use Hazard pointer to manage memory[2].
• Support Multi-producer & Multi-consumer.

Benchmark

Magnitude	Insert	Delete	Insert & Delete
1K	1.2ms	0ms	3.6ms
10K	147.1ms	18.9ms	293.5ms
100K	15064.4ms	1647ms	27176ms

The above data was tested on my 2013 macbook-pro with Intel Core i7 4 cores 2.3 GHz.

The data of first and second column was obtained by starting 8 threads to insert concurrently and delete concurrently, the data of third column was obtained by starting 4 threads to insert and 4 threads to delete concurrently, each looped 10 times to calculate the average time consumption. See also test.

Build

make && ./test

API

bool Insert(const T& data);
bool Insert(T&& data);
bool Emplace(Args&&... args);
bool Delete(const T& data);
bool Find(const T& data);
size_t size() const;

Reference

[1]A Pragmatic Implementation of Non-BlockingLinked-Lists. Timothy L.Harris
[2]Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects. Maged M. Michael