Skip to content

An implementation of the Judy array, wrapped in a c++ template. Uses Karl Malbrain's implementation, http://code.google.com/p/judyarray/ . Public domain.

Notifications You must be signed in to change notification settings

mpictor/judy-template

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

85 Commits
 
 
 
 
 
 
 
 
 
 

Repository files navigation

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.

The templates

  • 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 (?)

Comparison between this and the versions Karl and Doug wrote

  • 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.

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.

Compiling

  • requires C and C++ compilers, CMake.
  • from the command line:
  • mkdir build; cd build
  • cmake .. -DENABLE_TESTING=TRUE
  • make

License

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

Contact

mpictor -a-t- gmail

About

An implementation of the Judy array, wrapped in a c++ template. Uses Karl Malbrain's implementation, http://code.google.com/p/judyarray/ . Public domain.

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published