Awesome

Judy Array Templates

The Judy Array is a sparse dynamic array. It is a particular kind of trie that is highly efficient in space and time, and does not require tuning.

This uses Karl Malbrain's implementation of the Judy Array. Additional information can be found with Doug Baskins' original implementation on sourceforge, or on Wikipedia.

judyLArray - a C++ template wrapper for an int-int Judy Array. JudyKey and JudyValue must be integer types and the same size as a pointer (i.e. 32- or 64-bit)
judySArray - Same as judyLArray, but with string-int mapping. The above restrictions on JudyValue apply here as well.
judyL2Array, judyS2Array - single-key, multi-value versions of the above
TODO - single-key, n-value versions of the above (?)

Doug Baskins' code is licenced under the LGPL. While more permissive than the GPL, it's still not always acceptable. His code is very fast but weighs in at ~20k lines.
Karl Malbrain's code is ~1250 lines, in a single file containing the judy array and the test code; use requires creating a header.
Both of the above are written in C, so they don't fit neatly into object-oriented C++.
Unlike Doug's code, this is ~1250 lines. Unlike Karl's, this is split into several files.

CMakeLists.txt - CMake build logic. If you don't have CMake, it should be quite easy to write a file for the build system of your choice.
src/
judy.c, judy.h - implementation of the Judy Array
judyLArray.h - the judyLArray template
judySArray.h - the judySArray template
judyL2Array.h, judyS2Array.h - single-key, multi-value versions of the above
test/
hexSort.c - Sorts a file where each line contains 32 hex chars. Compiles to hexsort, which is the same executable as compiling Karl's code with -DHEXSORT -DSTANDALONE
pennySort.c - Sorts strings; compiles to pennysort. Same as compiling Karl's code with -DSTANDALONE.
sort.c, sort.h - Karl's sorting functions. Only used by hexsort and pennysort.
judyLtest.cc - an incomplete test of the judyLArray template.
judyL2test.cc - an incomplete test of the judyL2Array template.
judyStest.cc - an incomplete test of the judySArray template.
judyS2test.cc - an incomplete test of the judyS2Array template.

Karl Malbrain's judy array code is public domain; what I've added is public domain as well.

mpictor -a-t- gmail