|0.1.2||Jun 28, 2023|
|0.1.1||Jun 28, 2023|
|0.1.0||Jun 28, 2023|
#650 in Data structures
12,341 downloads per month
Used in qcell
A lock-free concurrent set.
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
for another thread to call
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
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.
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: