JudyL(3X) JudyL(3X)
NAME
JudyL macros - C library for creating and accessing a dynamic array of words, using any value of a word as an index
SYNOPSIS
cc [flags] sourcefiles -lJudy
#include <Judy.h>
int Rc_int; // return code - integer
Word_t Rc_word; // return code - unsigned word
Word_t Index, Index1, Index2, Nth;
Word_t * PValue; // pointer to return value
Pvoid_t PJLArray = (Pvoid_t) NULL; // initialize JudyL array
JLI( PValue, PJLArray, Index); // JudyLIns()
JLD( Rc_int, PJLArray, Index); // JudyLDel()
JLG( PValue, PJLArray, Index); // JudyLGet()
JLC( Rc_word, PJLArray, Index1, Index2); // JudyLCount()
JLBC(PValue, PJLArray, Nth, Index); // JudyLByCount()
JLFA(Rc_word, PJLArray); // JudyLFreeArray()
JLMU(Rc_word, PJLArray); // JudyLMemUsed()
JLF( PValue, PJLArray, Index); // JudyLFirst()
JLN( PValue, PJLArray, Index); // JudyLNext()
JLL( PValue, PJLArray, Index); // JudyLLast()
JLP( PValue, PJLArray, Index); // JudyLPrev()
JLFE(Rc_int, PJLArray, Index); // JudyLFirstEmpty()
JLNE(Rc_int, PJLArray, Index); // JudyLNextEmpty()
JLLE(Rc_int, PJLArray, Index); // JudyLLastEmpty()
JLPE(Rc_int, PJLArray, Index); // JudyLPrevEmpty()
DESCRIPTION
A JudyL array is the equivalent of an array of word-sized values. A value is addressed by an Index (key). The array may be sparse, and
the Index may be any word-sized number. Memory to support the array is allocated as index/value pairs are inserted, and released as
index/value pairs are deleted.
As with an ordinary array, there are no duplicate indexes in a JudyL array.
The value may be used as a scalar, or a pointer to a structure or block of data (or even another Judy array).
A JudyL array is allocated with a NULL pointer
Pvoid_t PJLArray = (Pvoid_t) NULL;
Using the macros described here, rather than the JudyL function calls, the default error handling sends a message to the standard error and
terminates the program with exit(1). For other error handling methods, see the ERRORS section.
Because the macro forms are faster and have a simpler error handling interface than the equivalent JudyL functions, they are the preferred
way of calling the JudyL functions.
Insert an Index and value in the JudyL array PJLArray.
If the Index is successfully inserted, the value is initialized to 0. If the Index was already present, the value is not
modified.
Return PValue pointing to Index's value. Your program must use this pointer to modify the value, for example:
*PValue = 1234;
Note: JLI() and JLD() reorganize the JudyL array. Therefore, pointers returned from previous JudyL calls become invalid and
must be reacquired.
Delete the Index/value pair from the JudyL array.
Return Rc_int set to 1 if successful. Return Rc_int set to 0 if Index was not present.
Get the pointer to Index's value.
Return PValue pointing to Index's value. Return PValue set to NULL if the Index was not present.
Count the number of indexes present in the JudyL array PJLArray between
Index1 and Index2 (inclusive).
Return Rc_word set to the count. A return value of 0 can be valid as a count.
To count all indexes present in a JudyL array, use:
JLC(Rc_word, PJLArray, 0, -1);
Locate the Nth index that is present in the JudyL array
PJLArray (Nth = 1 returns the first index present).
Return PValue pointing to its value and Index set to the Nth index if found, otherwise return PValue set to NULL (the value
of Index contains no useful information).
Given a pointer to a JudyL array, free the entire array (much faster
than using a JLN(), JLD() loop).
Return Rc_word set to the number of bytes freed and PJLArray set to NULL.
Return Rc_word set to the number of bytes of memory currently in use
by PJLArray. This is a very fast routine, and may be used after a JLI() or JLD() call with little performance impact.
JLF(), JLN(), JLL(), JLP()
allow you to search for indexes in the array. You may search inclusively or exclusively, in either forward or reverse
directions. If successful, Index is returned set to the found index, and PValue is returned set to a pointer to Index's
value. If unsuccessful, PValue is returned set to NULL, and Index contains no useful information. PValue must be tested
for non-NULL prior to using Index, since a search failure is possible.
JLFE(), JLNE(), JLLE(), JLPE() allow you to search for indexes that are not present ("empty") in the array. You may search
inclusively or exclusively, in either forward or reverse directions. If successful, Index is returned set to a not present
("empty") index, and Rc_int is returned set to 1. If unsuccessful, Rc_int is returned set to 0, and and Index contains no
useful information. Rc_int must be checked prior to using Index, since a search failure is possible.
Search (inclusive) for the first index present that is equal to or greater than the
passed Index. (Start with Index = 0 to find the first index in the array.) JLF() is typically used to begin a sorted-order
scan of the indexes present in a JudyL array.
Search (exclusive) for the next index present that is greater than the passed
Index. JLN() is typically used to continue a sorted-order scan of the indexes present in a JudyL array, or to locate a
"neighbor" of a given index.
Search (inclusive) for the last index present that is equal
to or less than the passed Index. (Start with Index = -1, that is, all ones, to find the last index in the array.) JLL()
is typically used to begin a reverse-sorted-order scan of the indexes present in a JudyL array.
Search (exclusive) for the previous index present that is less than the
passed Index. JLP() is typically used to continue a reverse-sorted-order scan of the indexes present in a JudyL array, or
to locate a "neighbor" of a given index.
Search (inclusive) for the first index absent that is equal to or greater than the passed
Index. (Start with Index = 0 to find the first index absent in the array.)
Search (exclusive) for the next index absent that is greater than the passed Index.
Search (inclusive) for the last index absent that is equal to or less than
the passed Index. (Start with Index = -1, that is, all ones, to find the last index absent in the array.)
Search (exclusive) for the previous index absent that is less than the passed
Index.
Storing in a JudyL (or JudySL) array a value that is actually a pointer
to another JudyL (or JudySL) array supports dynamic multi-dimensional arrays, or similarly, arrays where one or more of the
keys/indexes is longer than one word and treated as a series of words. Multi-dimensional arrays (trees) built using JudyL
(or JudySL) arrays (as the branch nodes) are usually very fast and efficient. When the dimensionality (and/or length of
each key/index) of the array is fixed, the implementation is straightforward and can be thought of as:
Array[dim1, dim2, dim3, dim4];
However, for applications where the tree is dynamic, such as when a JudyL (or JudySL) value (subsidiary pointer) points to a
user-defined node (that is, it "escapes" from the hierarchy of JudyL/JudySL arrays) because the number of dimensions (and/or
the length of one or more keys/indexes) is dynamic, the pointer must be recognizable as pointing to such a node rather than
another Judy array. A value of 4 in the least significant 3 bits of a JudyL (or JudySL) array pointer indicates that the
pointer is not in fact to a subsidiary Judy array, but rather it points (with the least three bits masked off) to a user-
defined location. The Judy.h header file defines two values: JLAP_MASK to mask the last 3 bits of the pointer, and
JLAP_INVALID that has the value 0x4 for checking the value of the pointer (JLAP_INVALID == 0x4).
The following example code segment can be used to determine whether or not a pointer points to another JudyL or JudySL
array:
// Obtain a pointer to a value:
JLG (PValue, PJLArray, Index1);
// Check if it is a JudyL/JudySL array pointer:
if ((*PValue & JLAP_MASK) == JLAP_INVALID) // not a Judy array pointer.
{
UPointer = (UPointer_t) (*PValue & ~JLAP_MASK); // mask and cast.
printf("User object pointer is 0x%lx
", (Word_t) UPointer);
...
}
else // a JudyL array pointer, traverse through it:
{
Pvoid_t PJLArray1 = (Pvoid_t) *PValue;
JLG(PValue1, PJLArray1, Index2);
...
}
Note: This works because malloc() guarantees to return a pointer with the least 3 bits == 0x0. You must add JLAP_INVALID
to the pointer, and remove it before using the pointer, to note that it is not a pointer to a JudyL array.
ERRORS
There are two categories of Judy error returns:
1) User programming errors (bugs) such as memory corruption or invalid pointers.
2) Out-of-memory (malloc() failure) when modifying a JudyL array with JLI() or JLD().
There are three methods of handling errors when using the macros:
1) Default error handling.
2) User-specified JUDYERROR() macro.
3) Disable macro error handling.
The default is to print error messages to stderr, for example:
File 'YourCfile.c', line 1234: JudyLIns(), JU_ERRNO_* == 2, ID == 321
This indicates that an error occurred in a JLI() call at line 1234 in 'YourCfile.c'. JU_ERRNO_* == 2 is JU_ERRNO_NOMEM (as
defined in the Judy.h file). The ID number indicates the Judy source line number where the error was detected.
Your program then terminates with an exit(1).
The JUDYERROR() macro provides flexibility for handling error returns
as needed to suit your program while still accessing JudyL arrays using macros instead of function calls. You can modify
JUDYERROR() to distinguish between the two types of errors (described above), and explicitly test for the remaining
JU_ERRNO_NOMEM errors possible in your program.
// This is an example of JudyL macro API to continue when out of memory.
#ifndef JUDYERROR_NOTEST
#include <stdio.h> // needed for fprintf()
// This is the macro that the Judy macro APIs use for return codes of -1:
#define JUDYERROR(CallerFile, CallerLine, JudyFunc, JudyErrno, JudyErrID)
{
if ((JudyErrno) != JU_ERRNO_NOMEM) /* ! a malloc() failure */
{
(void) fprintf(stderr, "File '%s', line %d: %s(), "
"JU_ERRNO_* == %d, ID == %d
",
CallerFile, CallerLine,
JudyFunc, JudyErrno, JudyErrID);
exit(1);
}
}
#endif // JUDYERROR_NOTEST not defined
This error handling macro must be included before the #include <Judy.h> statement in your program.
When your program is "bug free",
the only errors occurring should be malloc(3) errors. You can turn off error handling included in the JudyL macros by using
#define JUDYERROR_NOTEST 1
(in your program code), or
cc -DJUDYERROR_NOTEST sourcefile -lJudy
(on your command line).
EXAMPLE
Read a series of index/value pairs from the standard input, store each in a JudyL array, and then print out in sorted order.
#include <stdio.h>
#include <Judy.h>
Word_t Index; // array index
Word_t Value; // array element value
Word_t * PValue; // pointer to array element value
int Rc_int; // return code
Pvoid_t PJLArray = (Pvoid_t) NULL; // initialize JudyL array
while (scanf("%lu %lu", &Index, &Value))
{
JLI(PValue, PJLArray, Index);
If (PValue == PJERR) goto process_malloc_failure;
*PValue = Value; // store new value
}
// Next, visit all the stored indexes in sorted order, first ascending,
// then descending, and delete each index during the second pass.
Index = 0;
JLF(PValue, PJLArray, Index);
while (PValue != NULL)
{
printf("%lu %lu
", Index, *PValue));
JLN(PValue, PJLArray, Index);
}
Index = -1;
JLL(PValue, PJLArray, Index);
while (PValue != NULL)
{
printf("%lu %lu
", Index, *PValue));
JLD(Rc_int, PJLArray, Index);
if (Rc_int == JERR) goto process_malloc_failure;
JLP(PValue, PJLArray, Index);
}
AUTHOR
Judy was invented and implemented by Hewlett-Packard.
SEE ALSO
Judy(3X), Judy1(3X), Judy1_funcs(3X), JudyL_funcs(3X), JudySL(3X), JudySL_funcs(3X),
malloc(3),
the Judy website, http://www.hp.com/go/judy/, for more information and Application Notes.
JudyL(3X)