Freestyle linked lists tricks
6 points by signal-11
6 points by signal-11
If you’re writing C, instead of writing out linked list stuff in tedious longhand, it’s better to grab a copy of the BSD queue(3) macros (source) and/or their tree(3) siblings. Sadly there isn’t afaik a similar lightweight hash table of the kind this author might like.
Sadly there isn’t afaik a similar lightweight hash table of the kind this author might like.
Depending on someone's taste and requirements, the stb_ds (source) hash table idea might fit the bill. It has similar affordances to stb's stretchy buffers but for hash tables. It's essentially a stretchy buffer for the insertion-ordered key-value array where the pointer to the hash table for the key-to-index mapping is stored in the header before the array along with the length and capacity. So a cross-breeding of index maps with stretchy buffers. As a data structure it's nothing new; as with stretchy buffers it's about finding a design that works with C macros without having to stamp out strongly typed instantiations of the data structure for each key-value type.
it's about finding a design that works with C macros without having to stamp out strongly typed instantiations of the data structure for each key-value type.
You can also use sizeof with a duck typing approach to internal fields, e.g., https://gist.github.com/pkhuong/12b00066c238abdd261b6730c12efe98#file-array-h
I feel like that scales better when you need a little more complexity than just a vector.
A couple of notes related to the intrusive hash trie, because the author doesn’t deal with hash collisions or deletions from the tree.
If you’re using integer keys then you can avoid collisions by ensuring the hash function is a permutation; for string keys, turn the trie into a patricia / crit-bit tree.
It’s possible to implement deletion from an intrusive binary trie. I don’t know if anyone has actually implemented it, and sadly that old write-up is not very clear. (I didn’t pursue the idea because I was more interested in making a smaller+faster wide fan-out trie.)
The way that the hash trie is implemented handles collisions just fine, since the bit shift operations will eventually result in it repeatedly picking slot 0 and the structure gracefully degrading into a linear search over a linked list. So it'll be correct with degraded performance even if your hash function is \_ -> 0, but that's true for most hash maps.