Your API is missing some of the advantages relative to hash tables though. Because it's a tree, operations like union and difference of two instances can be sublinear in the size of the instances. E.g. union can copy subtrees when the other instance has empty at the corresponding position.
You're also missing a batch construction call, create a new tree out of N key/value pairs. That's much faster than inserting one at a time because you can sort the array up front and then create the tree without any temporary nodes.
The function pointers in the interface are probably difficult for the compiler to devirtualise. Changing that in C means macros or code generators though, does some damage to ease of use.
Your API is missing some of the advantages relative to hash tables though. Because it's a tree, operations like union and difference of two instances can be sublinear in the size of the instances. E.g. union can copy subtrees when the other instance has empty at the corresponding position.
You're also missing a batch construction call, create a new tree out of N key/value pairs. That's much faster than inserting one at a time because you can sort the array up front and then create the tree without any temporary nodes.
The function pointers in the interface are probably difficult for the compiler to devirtualise. Changing that in C means macros or code generators though, does some damage to ease of use.
Thanks for sharing it