Fridge Library

When we started our E&CE354 project, a small operating system, I realised that we were going to be writing a fair number of queues. Since some of them needed to be priority, I wrote a generic priority queue using a binary heap and a whole mess of pointers. It did its job, but it had a small bug that James spent much time debugging and came to a deep loathing of my dreaded queue. People sitting in the lab actually thought James was going to physically injure me. In E&CE457, I suggested to Dan that we would benefit from my queue. Remembering James's horror stories, but recognising the need for it, he shakily agreed. I was convinced all the bugs had been worked out...however, Dan claimed that it was malfunctioning and tore into it, leading to unfortunate brain damage watching the re-heaping. Turns out the items going into the queue were improperly marked and that was the reason they were becoming disordered. The queue then made it into the E&CE454 project; I did ask for James and Dan's permission. I also needed a string-indexable database, so I decided to code a radix tree (a.k.a., trie). Now, I pronounce trie like tree since it is a contraction of retrieval, but Dan insists it should be pronounced like try to avoid confusion with other trees. Unlike the queue, the pronunciation has been a greater source of tension than the code. That may also be because I wrote a collection of unit tests so that James could sleep easy. For the record, I got vengeance for the queue.

At the end of all this, James suggested I push this into a library. So, I proudly present the BSD-licensed Fridge Library. You'll have to pull a copy from git.

FridgeLib Repository

It uses flexible array members in the trie, so you'll probably need to put your C compiler into C99 mode.