xjp8hg
4.496K
· January 2013 ·
F93e90d4db9dc0eb3b5681c6fccfa0e2

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

tl;dr

http://www.nedprod.com/programs/portable/nedtries/
https://github.com/ned14/nedtries/blob/master/test.c

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.
Sign in or sign up to add your response.
Featured Programming Job

Senior Frontend Engineer
·
San Francisco
·
Full Time
Search all programming jobs