NAME
Judy::L - library for creating and accessing a dynamic array of words, using a word as an index.
SYNOPSIS
EXPORT
All functions are exportable by Sub::Exporter.
DESCRIPTION
A Judy::L 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 Judy::L 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 Judy::L 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 0 or undef value.
my $Judy = 0;The default error handling sends a message to the standard error and terminates the program with exit(1).
DATA TYPES
$Rc - return code
(Word_t)$Index, $Nth - index into array
(Word_t*)$PValue - pointer to $Value
(Word_t)$Value - stored value
(Pvoid_t)$Judy - Judy::L array
BASIC FUNCTIONS
$PValue = Set( $Judy, $Index, $Value )
Insert an $Index and $Value into the Judy::L array $Judy. Sets the value to $Value.
Return $PValue pointing to $Value. Your program can use this pointer to read or modify $Value until the next Set(), Delete(), Free() is executed on $Judyy. Examples:
use Judy::L qw( Set );
use Judy::Mem qw( PokeI PeekI );
$pvalue = Set( $judy, 2, 43 );
PokeI( $pvalue, 44 );
44 == PeekI( $pvalue );Croak if a malloc() fail occured. Note: Set() and Delete() reorganize the Judy::L array. Therefore, $PValue returned from previous Judy::L calls become invalid and must be re-acquired.
Modifies $Judy to point to allocated JudyL object.
$Rc = Delete( $Judy, $Index )
Delete the $Index/$Value pair from the Judy::L array.
Return $Rc set to 1 if successful. Return $$Rc set to 0 if Index was not present. Croaks if a malloc() fail occurred.
($PValue,$Value) = JLG($PValue, $PJLArray, $Index)
Get the pointer $PValue and value $Value associated with $Index in the $Judy Judy array.
Return $PValue pointing to $Value and $Value. Return nothing if the $Index was not present. Croak if a malloc() fail occured.
$Rc = Count( $Judy, $Index1, $Index2 )
Count the number of indexes present in the Judy::L array $Judy between $Index1 and $Index2 (inclusive).
Return the count. A return value of 0 can be valid as a count.
To count all indexes present in a Judy::L array, use:
Count( $judy, 0, -1 );( $PValue, $Value, $Index ) = Nth( $Judy, $Nth )
Locate the $Nth index that is present in the Judy::L array $Judy ($Nth = 1 returns the first index present).
Return pointer to value, value, and index. Return nothing if there isn't an $Nth element.
$Bytes = Free( $Judy )
Given a pointer to a Judy::L array, free the entire array (much faster than using a Next(), Delete() loop).
Return number of bytes freed and $Judy set to 0.
$Bytes = MemUsed( $Judy )
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.
Search Functions
First(), Next(), Last(), Prev() 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, $PValue is returned set to a pointer to $Index's $Value and $Value is returned. If unsuccessful, nothing is returned
FirstEmpty(), NextEmpty(), LastEmpty(), PrevEmpty() 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, an $Index is returned set to a not present ("empty") index. If unsuccessful, nothing is returned.
$Index = First( $Judy, $Index )
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.) First() is typically used to begin a sorted-order scan of the indexes present in a JudyL array.
$Index = Next( $Judy, $Index )
Search (exclusive) for the next index present that is greater than the passed Index. Next() 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.
$Index = Last( $Judy, $Index)
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.) Last() is typically used to begin a reverse-sorted-order scan of the indexes present in a JudyL array.
$Index = Prev( $Judy, $Index )
Search (exclusive) for the previous index present that is less than the passed $Index. Prev() 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.
$Index = FirstEmpty( $Judy, $Index )
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.)
$Index = NextEmpty( $Judy, $Index )
Search (exclusive) for the next index absent that is greater than the passed $Index.
$Index = LastEmpty( $Judy, $Index )
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.)
$Indx = PrevEmpty( $Judy, $Index )
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 JudyL 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 Judy::JLAP_INVALID flag is used in the least significant bit(s) of the pointer. After the flag Judy::JLAP_INVALID is removed, it is used as a pointer to the users data.
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 v algrind).
The following example code segment can be used to determine whether or not a pointer points to another JudyL:
use Judy 'JLAP_INVALID';
sub Dive {
my ( $judy, @walk ) = @_;
my ( $pvalue, $value );
for my $index ( @walk ) {
return if ! $judy;
# Advance to next dimension.
( $pvalue, $value ) = Get( $judy, $index );
# Check if pointer to user buffer
if ( $value & JLAP_INVALID ) {
last;
}
else {
$judy = $value;
}
}
# Remove our flag.
$value &= ~ JLAP_INVALID;
# Return the value.
printf "User object pointer is 0x%x\n", $value;
return $value;
}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
EXAMPLE
Read a series of index/value pairs from the standard input, store in a JudyL array, and then print out in sorted order.
use Judy::Mem qw( PeekI );
use Judy::L qw( Get Set First Next Last Prev Delete );
# Load judy.
my $judy;
while (<>) {
my ( $index, $value ) = split ' ';
Set( $judy, $index, $value );
}
# Print in ascending order.
my ( $index ) = First( $judy, 0 );
while ( defined $index ) {
print("%d %d\n", $index, PeekI( $index ) );
( $index ) = Next( $judy, $index );
}
# Now in descending order, deleting on the way.
( $index ) = Last( $judy, 0 );
while ( defined $index ) {
print("%d %d\n", $index, PeekI( $index ) );
Delete( $judy, $index );
( $index ) = Prev( $judy, $index );
}
# Ought to be a no-op since Judy is already empty.
Free( $judy );1 POD Error
The following errors were encountered while parsing the POD:
- Around line 142:
Unterminated C<...> sequence