If you’ve never run across them before, PATRICIA trees are a ridiculously space-and-time efficient data structure for implementing a dictionary: they take less space than a dense array (achieved by clever key storage) and are as fast as a hash table. The only reason I can see that they’re not more commonly used is because they lack versatility: they require their keys to be strings. (They’re not particularly cache-efficient, either, though that complaint can also be levelled at hash tables, which are in wide use.)
I was playing with them as the storage engine for a distributed hash-table type system; unfortunately, I could not find a C library that did what I wanted. As you might have guessed, I wrote one myself. I’m hereby releasing it into the public domain for anyone to play with. (Please do so at your own risk: I will not be responsible for the code taking control of your computer and causing it to eat babies.)
The library was designed with speed-efficiency in mind; to that end, all methods are iterative. There is quite a lot of room for improvement if you’re interested in tuning for speed, though this should be a very good starting point.
Please see the source code for further documentation, and if you have any questions or corrections, feel free to send them my way!
Current Version: 0.1
Download C header and C source.
