Last Updated: December 30, 2020
· creaktive

Associative/sparse arrays in pure C? Give it a trie!


While we usually take associative array/dictionary/hash data structure as granted in modern programming languages, there is no such thing builtin in a good old C. It might be tempting to use SQLite or even Berkeley DB to fullfil that urge in many project, but the extra dependency handling is a PITA.
Plus, there are many tasks that do not require ACID neither persistent storage.
Even a red-black tree could be an overkill sometimes. Then, there is a bitwise trie. One particular implementation, nedtries, caught my attention:

  1. It is distributed as a single header file (nedtrie.h);
  2. It is really fast;
  3. It is really tiny;
  4. It requires no dynamic memory allocation;
  5. It is both C/C++ compatible.