Judy(3X) Judy(3X)
NAME
Judy 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 population (number of elements).
Judy has two Application Program Interfaces (APIs): a C macro interface, 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.
AUTHOR
Judy 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 ALSO
Judy1(3X), JudyL(3X), JudySL(3X),
the Judy website, http://www.hp.com/go/judy/, for more information and Application Notes.
Judy(3X)
Check Out this Related Man Page
JudySL_funcs(3X) JudySL_funcs(3X)
NAME
JudySL functions - C library for creating and accessing a dynamic array, using a null-terminated string as an index (associative array)
SYNOPSIS
PPvoid_t JudySLIns( PPvoid_t PPJSLArray, const char * Index, PJError_t PJError);
int JudySLDel( PPvoid_t PPJSLArray, const char * Index, PJError_t PJError);
PPvoid_t JudySLGet( Pcvoid_t PJSLArray, const char * Index, PJError_t PJError);
Word_t JudySLFreeArray(PPvoid_t PPJSLArray, PJError_t PJError);
PPvoid_t JudySLFirst( Pcvoid_t PJSLArray, char * Index, PJError_t PJError);
PPvoid_t JudySLNext( Pcvoid_t PJSLArray, char * Index, PJError_t PJError);
PPvoid_t JudySLLast( Pcvoid_t PJSLArray, char * Index, PJError_t PJError);
PPvoid_t JudySLPrev( Pcvoid_t PJSLArray, char * Index, PJError_t PJError);
DESCRIPTION
A macro equivalent exists for each function call. 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 JudySL functions. See JudySL(3X) for more information. The function call
definitions are included here for completeness.
One of the difficulties in using the JudySL function calls lies in determining whether to pass a pointer or the address of a pointer.
Since the functions that modify the JudySL array must also modify the pointer to the JudySL array, you must pass the address of the pointer
rather than the pointer itself. This often leads to hard-to-debug programmatic errors. In practice, the macros allow the compiler to
catch programming errors when pointers instead of addresses of pointers are passed.
The JudySL function calls have an additional parameter beyond those specified in the macro calls. This parameter is either a pointer to an
error structure, or NULL (in which case the detailed error information is not returned).
In the following descriptions, the functions are described in terms of how the macros use them (only in the case of #define JUDYER-
ROR_NOTEST 1). This is the suggested use of the macros after your program has been fully debugged. When the JUDYERROR_NOTEST macro is not
specified, an error structure is declared to store error information returned from the JudySL functions when an error occurs.
Notice the placement of the & in the different functions.
#define JSLI(PValue, PJSLArray, Index)
PValue = JudyLIns(&PJSLArray, Index, PJE0)
#define JSLD(Rc_int, PJSLArray, Index)
Rc_int = JudySLDel(&PJSLArray, Index, PJE0)
#define JSLG(PValue, PJSLArray, Index)
PValue = JudySLIns(PJSLArray, Index, PJE0)
#define JSLFA(Rc_word, PJSLArray)
Rc_word = JudySLFreeArray(&PJSLArray, PJE0)
#define JSLF(PValue, PJSLArray, Index)
PValue = JudySLFirst(PJSLArray, Index, PJE0)
#define JSLN(PValue, PJSLArray, Index)
PValue = JudySLNext(PJSLArray, Index, PJE0)
#define JSLL(PValue, PJSLArray, Index)
PValue = JudySLLast(PJSLArray, Index, PJE0)
#define JSLP(PValue, PJSLArray, Index)
PValue = JudySLPrev(PJSLArray, Index, PJE0)
Definitions for all the Judy functions, the types Pvoid_t, Pcvoid_t, PPvoid_t, Word_t , JError_t, and PJError_t, the constants NULL,
JU_ERRNO_*, JERR, PPJERR, and PJE0 are provided in the Judy.h header file (/usr/include/Judy.h). Note: Callers should define JudySL
arrays as type Pvoid_t, which can be passed by value to functions that take Pcvoid_t (constant Pvoid_t), and also by address to functions
that take PPvoid_t.
The return type from most JudySL functions is PPvoid_t so that the values stored in the array can be pointers to other objects, which is a
typical usage, or cast to a Word_t * when a pointer to a value is required instead of a pointer to a pointer.
AUTHOR
Judy was invented and implemented by Hewlett-Packard.
SEE ALSO
Judy(3X), Judy1(3X), Judy1_funcs(3X), JudyL(3X), JudyL_funcs(3X), JudySL(3X),
malloc(3),
the Judy website, http://www.hp.com/go/judy/, for more information and Application Notes.
JudySL_funcs(3X)