289
The find operation is wait-free. That is, every find operation is bound only by
the number of steps the algorithm takes. And a thread is guaranteed to complete
the operation regardless of the activity of other threads. The implementation of
pmem::obj::concurrent_map uses atomic load-with-acquire memory semantics when
reading pointers to the next node.
Insert Operation
The insert operation, shown in Figure 14-4, employs fine-grained locking schema for
thread-safety and consists of the following basic steps to insert a new node with key=7
into the list:
1. Allocate the new node with randomly generated height.
2. Find a position to insert the new node. We must find the
predecessor and successor nodes on each level.
3. Acquire locks for each predecessor node and check that the
successor nodes have not been changed. If successor nodes have
changed, the algorithm returns to step 2.
4. Insert the new node to all layers starting from the bottom one.
Since the find operation is lock-free, we must update pointers on
each level atomically using store- with- release memory semantics.
Figure 14-3. Finding key=9 in the skip list data structure
Chapter 14 ConCurrenCy and persistent MeMory