3 ms·
bcache uses this technique, for building up lookup tables for searching btree nodes. One thing I didn't see mentioned in this treatment is that's possible to d
by koverstreet 11y ago
bcache uses this technique, for building up lookup tables for searching btree nodes.
One thing I didn't see mentioned in this treatment is that's possible to directly compute, given the size of the tree and a position in the tree (i.e. index into the array), the position of that node in an inorder traversal - and it's fast. That can be quite useful (bcache uses it for pointer compression).
http://evilpiepirate.org/git/linux-bcache.git/tree/drivers/md/bcache/bset.c#n278 http://evilpiepirate.org/git/linux-bcache.git/tree/drivers/m...
- joaquintides 11y agoThanks for the link. The inorder_next you refer to is equivalent to my increment (even the structure of the code is the same) with the difference that inorder_next relies on 1-based indices and uses intrinsic ffz. Definitely worth a try.