I wrote something fun during my week off: a concurrent map & set. https://gitlab.com/boats/skiplist/tree/master …
-
-
3/4) If the CAS failed, go back to step 1. Otherwise, the new node is now a part of the skiplist. All that remains is to build the rest of the tower, i.e. initialize pointers `new.tower[1 .. new.height]`.
-
Note that once a node is installed into the lowest level (level 0), it's inserted. Building the rest of the tower is completely optional - it's just an optimization to make skiplist operations O(log n) rather than O(n).
- 2 more replies
New conversation -
Loading seems to be taking a while.
Twitter may be over capacity or experiencing a momentary hiccup. Try again or visit Twitter Status for more information.