A lock-free concurrent set.

Tested with loom and miri.

lib.rs:

A lock-free concurrent set. The operations on this set are O(n) where n is the number of distinct values that have ever been inserted into the set.

The intended use-case is to provide a way to ensure exclusivity over critical sections of code on a per-value basis, where the number of distinct values is small but dynamic.

This data structure uses atomic singly-linked lists in two forms to enable its operations. One list has a node for every distinct value that has ever been inserted. The other type of list exists within each of those nodes, and manages a queue of threads waiting in the wait_to_insert method for another thread to call remove.

An atomic singly-linked list is relatively straightforward to insert to: Allocate a new node, and then in loop, update the 'next' pointer of the node to the most recent value of the 'head' pointer, and then attempt a compare-exchange, replacing the old 'head' with the pointer to the new node.

Things get more complicated as soon as you additionally consider removing items from the list. Anything that dereferences a node pointer now runs the risk of attempting to dereference a value which has been removed between the load that returned the pointer and the dereference of the pointer. Note that removal itself requires a dereference of the head pointer, to determine the value of head.next. This data structure avoids this issue in slightly different ways for the two different types of list.

The main list of nodes for each value avoids the issue by never removing nodes except in Drop. The exclusive access guarentee of Drop ensures that no other thread could attempt to access the list while it is being freed.

The list of waiting threads instead avoids the issue by specifying, for each list of waiting threads, which in the context of this set, means for each unique value, that at most one thread at a time may dereference a pointer. It exposes this contract as the safety requirement of the unsafe remove method. This requirement is easy to fulfil for applications where a value is only removed from the set by a logical "owner" which knows that it previously inserted a value.

Example

The following code inserts some values into the set, then removes one of them, and then spawns a second thread that waits to insert into the set.

After this code has been run, we can expect the data structure to look like this: