—

              
HideShow 297 lines of Pod
=head1 NAME
Judy::L - library for creating and accessing a dynamic array of words, using a word as an index.
=head1 SYNOPSIS
=head1 EXPORT
All functions are exportable by L<Sub::Exporter>.
=head1 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).
=head1 DATA TYPES
=over
=item *
$Rc - return code
=item *
(Word_t)$Index, $Nth - index into array
=item *
(Word_t*)$PValue - pointer to $Value
=item *
(Word_t)$Value - stored value
=item *
(Pvoid_t)$Judy - Judy::L array
=back
=head1 BASIC FUNCTIONS
=head2 $PValue = Set( $Judy, $Index, $Value )
Insert an C<$Index> and C<$Value> into the Judy::L array C<$Judy>. Sets the value to C<$Value>.
Return C<$PValue> pointing to C<$Value>. Your program can use this
pointer to read or modify C<$Value> until the next C<Set()>,
C<Delete()>, C<Free()> is executed on C<$Judy>y. 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: C<Set()> and
C<Delete()> reorganize the Judy::L array. Therefore, C<$PValue>
returned from previous Judy::L calls become invalid and must be
re-acquired.
Modifies C<$Judy> to point to allocated JudyL object.
=head2 $Rc = Delete( $Judy, $Index )
Delete the C<$Index>/C<$Value> pair from the Judy::L array.
Return C<$Rc> set to 1 if successful. Return $C<$Rc> set to 0 if Index
was not present. Croaks if a malloc() fail occurred.
=head2 ($PValue,$Value) = JLG($PValue, $PJLArray, $Index)
Get the pointer C<$PValue> and value C<$Value> associated with
C<$Index> in the C<$Judy> Judy array.
Return C<$PValue> pointing to C<$Value> and C<$Value>. Return nothing
if the C<$Index> was not present. Croak if a malloc() fail occured.
=head2 $Rc = Count( $Judy, $Index1, $Index2 )
Count the number of indexes present in the Judy::L array C<$Judy>
between C<$Index1> and C<$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 );
=head2 ( $PValue, $Value, $Index ) = Nth( $Judy, $Nth )
Locate the C<$Nth> index that is present in the Judy::L array C<$Judy>
(C<$Nth> = 1 returns the first index present).
Return pointer to value, value, and index. Return nothing if there
isn't an C<$Nth> element.
=head2 $Bytes = Free( $Judy )
Given a pointer to a Judy::L array, free the entire array (much faster
than using a C<Next()>, C<Delete()> loop).
Return number of bytes freed and C<$Judy> set to 0.
=head2 $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.
=head1 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, C<$Index> is returned set to the
found index, C<$PValue> is returned set to a pointer to C<$Index>'s
C<$Value> and C<$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 C<$Index> is returned set to a not present
("empty") index. If unsuccessful, nothing is returned.
=head2 $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.
=head2 $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.
=head2 $Index = Last( $Judy, C<$Index>)
Search (inclusive) for the last index present that is equal to or less
than the passed C<$Index>. (Start with C<$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.
=head2 $Index = Prev( $Judy, $Index )
Search (exclusive) for the previous index present that is less than
the passed C<$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.
=head2 $Index = FirstEmpty( $Judy, $Index )
Search (inclusive) for the first index absent that is equal to or
greater than the passed C<$Index>. (Start with C<$Index> = 0 to find
the first index absent in the array.)
=head2 $Index = NextEmpty( $Judy, $Index )
Search (exclusive) for the next index absent that is greater than the
passed C<$Index>.
=head2 $Index = LastEmpty( $Judy, $Index )
Search (inclusive) for the last index absent that is equal to or less
than the passed C<$Index>. (Start with C<$Index> = -1, that is, all
ones, to find the last index absent in the array.)
=head2 $Indx = PrevEmpty( $Judy, $Index )
Search (exclusive) for the previous index absent that is less than the
passed C<$Index>.
=head1 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.
=head1 ERRORS
See L<Judy>
=head1 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 );