I wrote something fun during my week off: a concurrent map & set. https://gitlab.com/boats/skiplist/tree/master …
-
-
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).
-
4/4) To build level `i`, do this: new.tower[i].store(succs[i]); preds[i].tower[i].compare_and_set(succs[i], new); If the CAS at level `i` fails, simply repeat the search to refresh lists `preds[]` and `succs[]` and try building this level again.
- 1 more reply
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.