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