Judy(3X)Judy(3X)NAMEJudy functions - C libraries for creating and accessing dynamic arrays
SYNOPSIS
Judy1 - maps an Index (word) to a bit
JudyL - maps an Index (word) to a word
JudySL - maps an Index (string) to a word
DESCRIPTION
The Judy family of functions supports fully dynamic arrays. These
arrays may be indexed by a 32- or 64-bit word (depending on the proces‐
sor) or a string. A dynamic array that is sparsely populated can be
thought of as a mapping function. There are 3 different Judy mappings
currently supported:
Judy1 maps an Index (word) to a bit.
JudyL maps an Index (word) to a word.
JudySL maps an Index (string) to a word.
For Judy1 functions and JudyL functions, Index should be declared as a
Word_t type. Word_t is defined in the Judy.h header file as a 32- or
64-bit unsigned native integer, and has the same number of bits as a
pointer.
For JudySL functions, each index is a null-terminated string.
Judy arrays are both speed- and memory-efficient, with no tuning or
configuration required, across a wide range of index set types (sequen‐
tial, periodic, clustered, random). Judy's speed and memory usage are
typically better than other data storage models such as skiplists,
binary trees, b-trees, or even hashing, and improves with very large
data sets.
A Judy array is created merely by defining a null pointer and then
storing (inserting) the first element into the array under that
pointer. The memory used by a Judy array is proportional to the popu‐
lation (number of elements).
Judy has two Application Program Interfaces (APIs): a C macro inter‐
face, and a function call interface. Because the macro forms are
faster and have a simpler error handling interface than the equivalent
functions, they are the preferred way of calling the Judy functions.
Since an initial (empty) Judy array is represented by a null pointer,
it is possible to construct an array of Judy arrays. In other words, a
Judy array's values (except Judy1) can be pointers to other Judy
arrays.
AUTHORJudy was invented and implemented by Hewlett-Packard. (Note: Judy is
named for the inventor's sister.)
FILES
Locations of interest include:
Documents, including HTML versions of the manual entries.
Demonstration program source files.
SEE ALSOJudy1(3X), JudyL(3X), JudySL(3X),
the Judy website, http://www.hp.com/go/judy/, for more information and
Application Notes.
Judy(3X)