NAME
Judy::1 macros - Library for creating and accessing a dynamic array of bits, using any value of a word as an index.
DATA TYPES
int Rc_int; // return code - integer
Word_t Rc_word; // return code - unsigned word
Word_t Index, Index1, Index2, Nth;DESCRIPTION
A Judy::1 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 Judy::1 array is allocated with a NULL pointer
my $judy;Memory to support the array is allocated as bits are set, and released as bits are unset. If the Judy::1 pointer ($Judy) is 0 or undef, all bits are unset (and the Judy::1 array requires no memory).
As with an ordinary array, a Judy::1 array contains no duplicate indexes.
The default error handling sends a message to the standard error and terminates the program with exit(1).
BASIC FUNCTIONS
bool = Set( $Judy, $Index )
Set $Index's bit in the Judy::1 array $Judy.
Return true if the bit was previously unset, false otherwise.
bool = Unset( $Judy, $Index )
Unset $Index's bit in the Judy::1 array $Judy; that is, remove $Index from the Judy::1 array.
Return true if the bit was previously set, false otherwise.
bool = J1T(Rc_int, $Judy, $Index); // Judy::1Test()
Test if $Index's bit is set in the Judy::1 array $Judy.
Return true if the bit is set, false otherwise.
count = Count( $Judy, $Key1, $Key2 )
Count the number of indexes present in the Judy::1 array $Judy between $Index1 and $Index2 (inclusive).
Return the count of indexes set. 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).
To count all indexes present (population) in a Judy::1 bit array, use:
$count = Count( $judy, 0, -1 );Note: The -1 promotes to the maximum index, that is, all ones.
$Index = Nth( $judy, $Nth )
Locate the c<$Nth> index that is present in the Judy::1 array $Judy ($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.
Returns nothing if there is not an nth index.
bytes = Free( $judy )
Free the entire Judy::1 array $Judy (much faster than using a Next(), Unset() loop).
Returns the number of bytes freed.
bytes = MemUsed( $judy )
Returns the number of bytes of memory currently in use by Judy::1 array $Judy. This is a very fast routine, and may be used after a Set() or Unset() call with little performance impact.
Search Functions
The Judy::1 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. $Index is returned for a sucessful search, nothing is returned under failure.
J1F(Rc_int, $Judy, $Index); // Judy::1First()
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 Judy::1 array.
J1N(Rc_int, $Judy, $Index); // Judy::1Next()
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 Judy::1 array, or to locate a "neighbor" of a given index.
J1L(Rc_int, $Judy, $Index); // Judy::1Last()
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 Judy::1 array.
J1P(Rc_int, $Judy, $Index); // Judy::1Prev()
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 Judy::1 array, or to locate a "neighbor" of a given index.
J1FE(Rc_int, $Judy, $Index); // Judy::1FirstEmpty()
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, $Judy, $Index); // Judy::1NextEmpty()
Search (exclusive) for the next absent index that is greater than the passed $Index.
J1LE(Rc_int, $Judy, $Index); // Judy::1LastEmpty()
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, $Judy, $Index); // Judy::1PrevEmpty()
Search (exclusive) for the previous absent index that is less than the passed $Index.
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.
use Judy::1 qw( Set Test Unset Count MemUsed );
my $judy;
print Set( $judy, 123456 )
? "OK - bit successfully set at 123456\n"
: "BUG - bit already set at 123456\n";
print Test( $judy, 654321 )
? "BUG - set bit at 654321\n"
: "OK - bit not set at 654321\n";
my ( $count ) = Count( $judy, 0, -1 );
print "$count bits set in Judy::1 array\n";
my ( $index ) = First( $judy, 0 );
if ( defind $index ) {
print "OK - first bit set is at $index\n";
}
else {
print "BUG - no bits set in array\n";
}
print "$count Indexes used %d bytes of memory\n", MemUsed( $judy );
print Unset( $judy, 123456 )
? "OK - bit successfully unset at 123456\n"
: "BUG - bit was not unset at 123456\n";AUTHOR
Judy was invented by Doug Baskins and implemented by Hewlett-Packard.
Judy::1 the perl wrapper was written by Joshua ben Jore.
1 POD Error
The following errors were encountered while parsing the POD:
- Around line 5:
Unknown directive: =head