Post #2226735
2026-05-07 15:36 UTC
I just wrote a generic C macros implementation of integer-keyed radix trees.
It actually had not occurred to me before to read the bits one at a time and so avoid the need for Phil Bagwell’s trick with population counts. But this time I did that, and maybe if you are using fixnums this is a better approach in general. Maybe my Scheme implementation of hashmaps should be redone this way.
OTOH maybe it isn’t worth the effort.
Replies (1)
-
@chemoelectric@masto.ai 2026-05-07 15:43
I went least significant bit first and optimized for reducing the node count. This leads to a tree walk that gives the leaf nodes in a scrambled order. If you want them in-order I think that would work if you want most significant bit first. If you go MSB first and do not optimize for node count it seems to be called a ‘bit-trie’, among other names. The name ‘integer-keyed trie’ shows up, but I would consider that ambiguous. After all, what I just implemented is one, as well.