--- name: "JLP" section: "3" platform: "linux" package: "libjudy-dev" version: "1.0.5-5.1" release: "Debian 13 (Trixie)" platforms: ["linux"] url: "https://new.carta.tech/JLP" --- # JLP(3) C library for creating and accessing a dynamic array of words, using a word as an index. ## NAME JudyL - C library for creating and accessing a dynamic array of words, using a word as an index. ## SYNOPSIS ``` cc [flags] sourcefiles -lJudy ``` **#include \** **int Rc\_int; // return code - integer** **Word\_t Rc\_word; // return code - unsigned word** **Word\_t Index, Index1, Index2, Nth;** **PWord\_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. A JudyL array can also be** **thought of as a mapper, that is "map" a word to another word/pointer.** **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)](/exit/1.md);***.** **For other error handling methods, see the** *ERRORS* **section.** *JLI***( PValue, PJLArray, Index); // JudyLIns()** **Because the macro forms are sometimes faster and have a simpler error** **handling interface than the equivalent** **JudyL functions,** **they are the preferred way of calling the JudyL functions.** - **JLI(PValue, PJLArray, Index) // JudyLIns()** **Insert an Index and Value into 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 Value.** **Your program can use this pointer to read or modify Value until the next** **JLI() (insert), JLD() (delete) or JLFA() (freearray)** **is executed on PJLArray. Examples:** - ``` *PValue = 1234; Value = *PValue; ``` - **Return PValue set to PJERR if a** *malloc()* **fail occured.** **Note:** **JLI() and JLD() reorganize the JudyL array.** **Therefore, PValue returned from previous JudyL calls become** **invalid and must be re-acquired.** - - **JLD(Rc\_int, PJLArray, Index) // JudyLDel()** **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.** **Return Rc\_int set to JERR if a** *malloc()* **fail occured.** - - **JLG(PValue, PJLArray, Index) // JudyLGet()** **Get the pointer PValue associated with Index in the PJLArray Judy array.** - **Return PValue pointing to Value.** **Return PValue set to NULL if the Index was not present.** **Return PValue set to PJERR if a** *malloc()* **fail occured.** - - **JLC(Rc\_word, PJLArray, Index1, Index2) // JudyLCount()** **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); ``` - - **JLBC(PValue, PJLArray, Nth, Index) // JudyLByCount()** **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** **is undefined).** - - **JLFA(Rc\_word, PJLArray) // JudyLFreeArray()** **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.** - - **JLMU(Rc\_word, PJLArray) // JudyLMemUsed()** **Return Rc\_word set to the number of bytes of memory** *malloc()***'ed** **by PJLArray.** **This is a very fast routine, and may be used before and after** **a JLI() or JLD() call with little performance impact.** - - **JudyL Search Functions** **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.** - - **JLF(PValue, PJLArray, Index) // JudyLFirst()** **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.** - - **JLN(PValue, PJLArray, Index) // JudyLNext()** **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.** - - **JLL(PValue, PJLArray, Index) // JudyLLast()** **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.** - - **JLP(PValue, PJLArray, Index) // JudyLPrev()** **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.** - - **JLFE(Rc\_int, PJLArray, Index) // JudyLFirstEmpty()** **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.)** - - **JLNE(Rc\_int, PJLArray, Index) // JudyLNextEmpty()** **Search (exclusive) for the next index absent that is greater than the passed Index.** - - **JLLE(Rc\_int, PJLArray, Index) // JudyLLastEmpty()** **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.)** - - **JLPE(Rc\_int, PJLArray, Index) // JudyLPrevEmpty()** **Search (exclusive) for the previous index absent that is less than the passed** **Index.** ## Multi-dimensional JudyL Arrays **Storing a pointer to another JudyL array in a JudyL array's Value** **is a simple way to support dynamic multi-dimensional arrays.** **These arrays (or trees) built using JudyL arrays are very fast and** **memory efficient. (In fact, that is how JudySL and JudyHS are implemented).** **An arbitrary number of dimensions can be realized this way.** **To terminate the number of dimensions (or tree), the Value pointer is** **marked to NOT point to another Judy array. A JLAP\_INVALID flag is** **used in the least significant bit(s) of the pointer.** **After the flag JLAP\_INVALID is removed, it is used as a pointer to the users data.** **The Judy.h header file defines JLAP\_INVALID.** **See code fragment below.** **Note: The current version of Judy.h changed this flag from 0x4 to 0x1** **to allow for a** *malloc()* **that does not deliver memory on an 8 byte** **aligned boundry (such as old versions of valgrind).** **The following example code segment can be used to determine whether or** **not a pointer points to another JudyL:** ``` PValue = (PWord_t)PMultiDimArray; ``` **for (Dim = 0; ;Dim++)** **{**\ **if (PValue == (PWord\_t)NULL) goto IndexNotFound;** **/\* Advance to next dimension in array \*/**\ **JLG(PValue, (Pvoid\_t)\*PValue, Index\[Dim\]);** **/\* Check if pointer to user buffer: \*/**\ **if (\*PValue & JLAP\_INVALID)) break;** **}** **UPointer = (UPointer\_t) (\*PValue & ~JLAP\_INVALID); // mask and cast.** **printf("User object pointer is 0x%lx\\n", (Word\_t) UPointer);**\ **&.&.&.** **Note: This works because** *malloc()* **guarantees to return a pointer** **with the least bit(s) == 0x0.** **You must remove JLAP\_INVALID before using the pointer.** ## ERRORS: See: *Judy\_3.htm#ERRORS* ## EXAMPLE **Read a series of index/value pairs from the standard input, store** **in a JudyL array, and then print out in sorted order.** ``` #include #include ``` **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 descending pass.** **Index = 0;** **JLF(PValue, PJLArray, Index);** **while (PValue != NULL)** **{**\ **printf("%lu %lu\\n", Index, \*PValue));**\ **JLN(PValue, PJLArray, Index);** **}** **Index = -1;** **JLL(PValue, PJLArray, Index);** **while (PValue != NULL)** **{**\ **printf("%lu %lu\\n", Index, \*PValue));** **JLD(Rc\_int, PJLArray, Index);**\ **if (Rc\_int == JERR) goto process\_malloc\_failure;** **JLP(PValue, PJLArray, Index);** **}** ## AUTHOR **Judy was invented by Doug Baskins and implemented -Packard.** ## SEE ALSO *Judy***(3),** *Judy1***(3),** *JudySL***(3),** *JudyHS***(3),**\ *malloc()***,**\ *http://judy.sourceforge.net***,** **for more information and Application Notes.**