News for hackers. Stuff that matters.
Re:What Cannot Be Skipped About the Skiplist: A Survey of Sk... by jpfr on Sunday March 10, 2024 @03:58AM (#39657494)
Zip trees are great!

For a project I made a version that uses the memory location of the entries to construct the (random) rank on the fly.

So it’s a binary tree structure that requires the same memory as a linked list (two pointers) only!

https://github.com/open62541/open62541/blob/master/deps/zipt...

Re:What Cannot Be Skipped About the Skiplist: A Survey of Sk... by jstanley on Sunday March 10, 2024 @04:44AM (#39657656)
I don't know anything about zip trees, but I'd think in a common scenario the memory addresses are reasonably consecutive. Would that be a problem? If not, why not just assign consecutive ranks in the first place?
Re:What Cannot Be Skipped About the Skiplist: A Survey of Sk... by jpfr on Sunday March 10, 2024 @02:55PM (#39661562)
The address is scrambled (similar to a random-number generator) to produce the rank. So consecutive locations do not hurt performance.
Re:What Cannot Be Skipped About the Skiplist: A Survey of Sk... by hinkley on Sunday March 10, 2024 @06:41PM (#39663113)