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;

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()

A Judy1 array is allocated with a NULL pointer

Pvoid_t PJ1Array = (Pvoid_t) NULL;

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). 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 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 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.

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.

Default Error Handling Method

The default is to print error messages to stderr, for example:

File 'YourCfile.c', line 1234: Judy1Set(), JU_ERRNO_* == 2, ID == 321

This indicates that an error occurred in a J1S() 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).

User-Specified JUDYERROR() Macro Method

The JUDYERROR() macro provides flexibility for handling error returns as needed to suit your program while still accessing Judy1 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 Judy1 macro API to continue when out of memory.

#ifndef JUDYERROR_NOTEST
#include <stdio.h>

// 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\n",                               \
            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.

Disable Macro Error Handling

When your program is "bug free", the only errors occurring should be malloc(3) errors. You can turn off error handling included in the Judy1 macros by using

#define JUDYERROR_NOTEST 1

(in your program code), or

cc -DJUDYERROR_NOTEST sourcefile -lJudy

(on your command line).

#include <stdio.h>

#include <Judy.h>

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);
}