PATRICIA

Wednesday, 4 June 2008.

---

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.

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. So… I wrote one myself! And 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.)

• Current Release: 0.1 (download C source)

The library was designed with speed-efficiency in mind; to that end, all methods are iterative. However, there is still a lot of room for improvement:

• The “delete” method needs to be implemented in such a fashion that it reclaims unused memory. (The current version is a hack, since delete is an uncommon use case in the program I was writing.)

• I use strdup all over the place, since it’s awesome. However, querying string length all the time is suboptimal; we can do better by passing string lengths as parameters to the methods (specifically, the “create” method).

• The code needs to be audited for memory leaks. (I havn’t done this since I don’t have a “delete” method yet!)

• I'm sure there are other clever optimizations that can be performed without risking code clarity or length.

If you feel the need to hack on it, please, let me know what revisions you've made: I would love to include them!