Chapter 3 Using Judy

The Judy library functions support small or large, dynamic arrays with 32- or 64-bit indexes depending on the processor type. Each type of Judy array has a different kind of index and/or value. You can think of a Judy array as:

value-type JudyArray [4294967296]; 
// or 232 on a 32-bit processor 

value-type JudyArray [18446744073709551616]; 
// or 264 on a 64-bit processor 

Judy arrays are quick to access and space efficient. A Judy array is created by storing (inserting) the first element and grows dynamically as elements are inserted.

The table below summarizes the Judy array types with functions provided. The Judy header file (Judy.h) provides definitions for these functions; the constants NULL, TRUE, and FALSE; and the macro equivalents for calling Judy functions.

Sorting

As part of normal processing, Judy sorts indexes numerically using its own, internal sorting criteria. Therefore, you cannot modify the sorting order to include user-defined sorting criteria (such as requesting a sort using multi-byte characters).

While Judy is not primarily intended as a sorting algorithm, in many cases it's faster to store values in a Judy array and read them back in sorted order than to sort them using standard sorting algorithms. JudySL strings are treated as series of N-byte numbers (N = 4 on a 32-bit system or 8 on a 64-bit system).

Keep in mind that Judy arrays do not support synonyms, that is multiple values associated with the same index. The caller must build synonyms outside of Judy; for instance, by having the Judy value (from JudyL or JudySL) point to a linked list of nodes, each with a different value for the same index.

Each index can only be stored once. If you store value xyz and then store the value xyz again, Judy uses the same value area.

JudySL sorts two strings that start with the same prefix like sort(1) in UNIX (but without multi-byte support):

If one string is a substring of another, the shorter one is first:

JudySL sorts are case sensitive and JudySL literally stores strings as chunks of bytes or numbers. Sorting is numeric per the ASCII value of the character, so the letter "A" is sorted using a different numeric sequence than the letter "a".

For more information about sorting strings, see the “JudySL sorting example ”.

Counting

You can use Judy counting functions to rapidly determine the number of valid indexes between any pair of indexes. Judy counts the population of any given expanse: the number of valid (stored) indexes in the expanse. Because each node in a Judy array maintains a count of the values under the node, Judy counts the number of keys between any two arbitrarily defined keys in nearly constant time.

Counting functions are available through Judy1Count() and JudyLCount(), which return counts of valid indexes between the specified indexes (including the indexes themselves if valid). In addition, you can use the JudyLByCount function to locate the Nth index (where
N = count) in an array and return a pointer to its value area.

Because counting happens in nearly constant time, Judy counting functions can support many novel problem solutions, such as repeated stack depth measurements. For more information about counting, refer to the Judy1(3X) and JudyL(3X) man pages.