I wrote something fun during my week off: a concurrent map & set. https://gitlab.com/boats/skiplist/tree/master …
Actually, I think you're right about writes requiring a mutex. That's a bummer. :( But, it's fairly easy to implement truly lock-free inserts. It goes like this:
-
-
1/4) Do a search to identify the 'hole' into which the new node will fall. The search operation returns two arrays `preds[]` and `succs[]`. These will be the predecessors and successors of the new node.
-
2/4) Perform a CAS operation at the lowest level to install the new node into the skiplist: new.tower[0].store(succs[0]); preds[0].tower[0].compare_and_set(succs[0], new);
- 4 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.