--- name: "Judy1" section: "3" platform: "linux" package: "judy" version: "1.0.5-10" release: "Arch Linux 2026-11-01" platforms: ["linux"] url: "https://new.carta.tech/Judy1" --- # Judy1(3) C library for creating and accessing a dynamic array of bits, using any value of a word as an index. ## NAME Judy1 macros - C library for creating and accessing a dynamic array of bits, using any value of 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;** **Pvoid\_t PJ1Array = (Pvoid\_t) NULL; // initialize Judy1 array** **J1S( Rc\_int, PJ1Array, Index); // Judy1Set()** **J1U( Rc\_int, PJ1Array, Index); // Judy1Unset()** **J1T( Rc\_int, PJ1Array, Index); // Judy1Test()** **J1C( Rc\_word, PJ1Array, Index1, Index2); // Judy1Count()** **J1BC(Rc\_int, PJ1Array, Nth, Index); // Judy1ByCount()** **J1FA(Rc\_word, PJ1Array); // Judy1FreeArray()** **J1MU(Rc\_word, PJ1Array); // Judy1MemUsed()** **J1F( Rc\_int, PJ1Array, Index); // Judy1First()** **J1N( Rc\_int, PJ1Array, Index); // Judy1Next()** **J1L( Rc\_int, PJ1Array, Index); // Judy1Last()** **J1P( Rc\_int, PJ1Array, Index); // Judy1Prev()** **J1FE(Rc\_int, PJ1Array, Index); // Judy1FirstEmpty()** **J1NE(Rc\_int, PJ1Array, Index); // Judy1NextEmpty()** **J1LE(Rc\_int, PJ1Array, Index); // Judy1LastEmpty()** **J1PE(Rc\_int, PJ1Array, Index); // Judy1PrevEmpty()** ## DESCRIPTION **A Judy1 array is the equivalent of a bit array or bit map.** **A bit is addressed by an Index (key).** **The array may be sparse, and the Index may be any word-sized Value.** **If an index is present, it represents a set bit** **(a bit set represents an index present).** **If an index is absent, it represents an unset bit** **(a bit unset represents an absent index).** **A Judy1 array is allocated with a NULL pointer** ``` Pvoid_t PJ1Array = (Pvoid_t) NULL; ``` **Memory to support the array is allocated as bits are set,** **and released as bits are unset.** **If the Judy1 pointer (PJ1Array) is NULL, all bits are unset (and** **the Judy1 array requires no memory).** **As with an ordinary array, a Judy1 array contains no duplicate indexes.** **Using the macros described here, rather than the** **Judy1 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.** **Because the macro forms are sometimes faster and have a simpler error** **handling interface than the equivalent** *functions***,** **they are the preferred way of calling the Judy1 functions.** - **J1S(Rc\_int, PJ1Array, Index); // Judy1Set()** **Set Index's bit in the Judy1 array PJ1Array.** - **Return Rc\_int set to 1 if Index's bit was previously unset** **(successful), otherwise 0** **if the bit was already set (unsuccessful).** - - **J1U(Rc\_int, PJ1Array, Index); // Judy1Unset()** **Unset Index's bit in the Judy1 array PJ1Array;** **that is, remove Index from the Judy1 array.** - **Return Rc\_int set to 1 if Index's bit was** **previously set (successful), otherwise 0** **if the bit was already unset (unsuccessful).** - - **J1T(Rc\_int, PJ1Array, Index); // Judy1Test()** **Test if Index's bit is set in the** **Judy1 array PJ1Array.** - **Return Rc\_int set to 1 if Index's bit is set** **(Index is present),** **0 if it is unset (Index is absent).** - - **J1C(Rc\_word, PJ1Array, Index1, Index2); // Judy1Count()** **Count the number of indexes present in the Judy1 array** **PJ1Array between** **Index1 and Index2 (inclusive).** - **Return Rc\_word set to the count.** **A return Value of 0 can be valid as a count,** **or it can indicate a special case for fully** **populated array (32-bit machines only). See** **Judy1Count()** **for ways to resolve this.** - **To count all indexes present (population) in a Judy1 bit array, use:** - ``` J1C(Rc_word, PJ1Array, 0, -1); ``` **Note: The -1 promotes to the maximum index, that is, all ones.** - - **J1BC(Rc\_int, PJ1Array, Nth, Index); // Judy1ByCount()** **Locate the Nth index that is present in the Judy1 array** **PJ1Array (Nth = 1 returns the first index present).** **To refer to the last index in a fully populated array (all indexes** **present, which is rare), use Nth = 0.** - **Return Rc\_int set to 1 and Index set to the** **Nth index if found, otherwise return Rc\_int** **set to 0 (the Value of Index contains no** **useful information).** - - **J1FA(Rc\_word, PJ1Array); // Judy1FreeArray()** **Free the entire Judy1 array PJ1Array (much faster than using a** **J1N(), J1U() loop).** - **Return Rc\_word set to the number of bytes freed,** **and PJ1Array set to NULL.** - - **J1MU(Rc\_word, PJ1Array); // Judy1MemUsed()** **Return Rc\_word set to the number of bytes of memory currently in use by** **Judy1 array PJ1Array. This is a very fast routine, and may be used after** **a J1S() or J1U() call with little performance impact.** - - **Judy1 Search Functions** **The Judy1 search functions allow you to search for set or unset bits in the array.** **You may search inclusively or exclusively,** **in either forward or reverse directions.** **All of the search functions use a similar calling sequence.** **Rc\_int is returned set to 1 for a successful search and the found Index is returned.** **Rc\_int is returned set to 0 for an unsuccessful search,** **and Index contains no useful information.** **The return code Rc\_int must be checked prior to using the returned Index,** **since a search failure is possible.** - - **J1F(Rc\_int, PJ1Array, Index); // Judy1First()** **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.) J1F() is typically used to** *begin* **a** **sorted-order scan of the indexes present in a Judy1 array.** - - **J1N(Rc\_int, PJ1Array, Index); // Judy1Next()** **Search (exclusive) for the next index present that is** **greater than the passed Index.** **J1N() is typically used to** *continue* **a** **sorted-order scan of the indexes present** **in a Judy1 array, or to locate a "neighbor" of a given index.** - - **J1L(Rc\_int, PJ1Array, Index); // Judy1Last()** **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.) J1L() is typically used to** *begin* **a reverse-sorted-order scan** **of the indexes present in a Judy1 array.** - - **J1P(Rc\_int, PJ1Array, Index); // Judy1Prev()** **Search (exclusive) for the previous index present that is** **less than the passed Index. J1P() is typically** **used to** *continue* **a reverse-sorted-order scan of the indexes** **present in a Judy1 array, or to locate a "neighbor" of a given index.** - - **J1FE(Rc\_int, PJ1Array, Index); // Judy1FirstEmpty()** **Search (inclusive) for the first absent index that is equal to** **or greater than the passed Index. (Start with** **Index = 0 to find the first index absent in the array.)** - - **J1NE(Rc\_int, PJ1Array, Index); // Judy1NextEmpty()** **Search (exclusive) for the next absent index that is** **greater than the passed Index.** - - **J1LE(Rc\_int, PJ1Array, Index); // Judy1LastEmpty()** **Search (inclusive) for the last absent index that is** **equal to or less than the passed Index.** **(Start with Index = -1 to find the last index** **absent in the array.)** - - **J1PE(Rc\_int, PJ1Array, Index); // Judy1PrevEmpty()** **Search (exclusive) for the previous absent index that is** **less than the passed Index.** ## ERRORS: See: *Judy\_3.htm#ERRORS* ## EXAMPLE **In the following example, errors in the J1S() or J1U() calls** **go to a user-defined procedure, process\_malloc\_failure. This is not needed** **when you use the default JUDYERROR() macro, since the default causes** **your program to exit on all failures,** **including** *malloc()* **failure.** ``` #include #include ``` **int main() // Example program of Judy1 macro APIs** **{**\ **Word\_t Index; // index (or key)**\ **Word\_t Rcount; // count of indexes (or bits set)**\ **Word\_t Rc\_word; // full word return value**\ **int Rc\_int; // boolean values returned (0 or 1)** **Pvoid\_t PJ1Array = (Pvoid\_t) NULL; // initialize Judy1 array** **Index = 123456;**\ **J1S(Rc\_int, J1Array, Index); // set bit at 123456**\ **if (Rc\_int == JERR) goto process\_malloc\_failure;**\ **if (Rc\_int == 1) printf("OK - bit successfully set at %lu\\n", Index);**\ **if (Rc\_int == 0) printf("BUG - bit already set at %lu\\n", Index);** **Index = 654321;**\ **J1T(Rc\_int, J1Array, Index); // test if bit set at 654321**\ **if (Rc\_int == 1) printf("BUG - set bit at %lu\\n", Index);**\ **if (Rc\_int == 0) printf("OK - bit not set at %lu\\n", Index);** **J1C(Rcount, J1Array, 0, -1); // count all bits set in array**\ **printf("%lu bits set in Judy1 array\\n", Rcount);** **Index = 0;**\ **J1F(Rc\_int, J1Array, Index); // find first bit set in array**\ **if (Rc\_int == 1) printf("OK - first bit set is at %lu\\n", Index);**\ **if (Rc\_int == 0) printf("BUG - no bits set in array\\n");** **J1MU(Rc\_word, J1Array); // how much memory was used?**\ **printf("%lu Indexes used %lu bytes of memory\\n", Rcount, Rc\_word);** **Index = 123456;**\ **J1U(Rc\_int, J1Array, Index); // unset bit at 123456**\ **if (Rc\_int == JERR) goto process\_malloc\_failure;**\ **if (Rc\_int == 1) printf("OK - bit successfully unset at %lu\\n", Index);**\ **if (Rc\_int == 0) printf("BUG - bit was not set at %lu\\n", Index);** **return(0);** **}** ## AUTHOR **Judy was invented by Doug Baskins and implemented by Hewlett-Packard.** ## SEE ALSO *Judy***(3),** *JudyL***(3),** *JudySL***(3),** *JudyHS***(3),**\ *malloc()***,**\ **the Judy website,** *http://judy.sourceforge.net***,** **for more information and Application Notes.**