The Perl Toolchain Summit needs more sponsors. If your company depends on Perl, please support this very important event.

NAME

Judy::L - Efficient integer to integer map

SYNOPSIS

Read a series of key/value pairs from the standard input, store in a JudyL array, and then print out in sorted order.

  use Judy::L qw( Set First Next Last Prev Delete Free );

  # Load judy.
  my $judy;
  Set( $judy, 123, 345 );
  Set( $judy, 324, 456 );
  Set( $judy, 234, 567 );

  # Print in ascending order.
  print "ascending\n";
  my ( undef, $value , $key ) = First( $judy, 0 );
  while ( defined $key ) {
      print "$key=$value\n";
      ( undef, $value, $key ) = Next( $judy, $key );
  }

  # Now in descending order, deleting on the way.
  print "descending\n";
  ( undef, $value, $key ) = Last( $judy, -1 );
  while ( defined $key ) {
      print "$key=$value\n";
      Delete( $judy, $key );
      ( undef, $value, $key ) = Prev( $judy, $key );
  }

  # Ought to be a no-op since Judy is already empty.
  Free( $judy );

EXPORT

All functions are exportable by Sub::Exporter.

DESCRIPTION

Judy::L is the equivalent of a sparse array of integers. Memory to support the array is allocated as key/value pairs are inserted, and released as key/value pairs are deleted.

The value may be used as a scalar, or a pointer to a structure or block of data (or even another Judy array). JudySL and JudyHS are implemented on top of JudyL where the values are pointers. See http://perlmonks.org/?node_id=733140 for an example.

Nothing special is required to allocate a Judy::L array. Just start using it.

    my $judy;
    if ( Get( $judy, 10 ) ) {
        ....
    }

As with an ordinary array, there are no duplicate keys in a Judy::L array.

DATA TYPES

$Judy - Judy::L array

$Key - integer

$Value - integer

$PValue - pointer to integer

$Nth - integer

BASIC FUNCTIONS

$PValue = Set( $Judy, $Key, $Value )

Insert/set an $Key and $Value into the Judy::L array $Judy.

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 $Judy. Examples:

    use Judy::L   qw( Set         );
    use Judy::Mem qw( Poke Peek );

    $pvalue = Set( $judy, 2, 43 );

    Poke( $pvalue, 44 );
    44 == Peek( $pvalue );

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 Judy::L object.

bool = Delete( $Judy, $Key )

Delete the $Key/$Value pair from the Judy::L array. Return true if the key was removed.

($PValue, $Value) = Get( $Judy, $Key )

Get the pointer $PValue and value $Value associated with $Key in the $Judy Judy array.

Return $PValue pointing to $Value and $Value. Return nothing if the $Key was not present.

Search Functions

First(), Next(), Last(), Prev() allow you to search for keys in the array. You may search inclusively or exclusively, in either forward or reverse directions. If successful, $Key is returned set to the found key, $PValue is returned set to a pointer to $Key's $Value and $Value is returned. If unsuccessful, nothing is returned.

FirstEmpty(), NextEmpty(), LastEmpty(), PrevEmpty() allow you to search for keys that are not present ("empty") in the array. You may search inclusively or exclusively, in either forward or reverse directions. If successful, an $Key is returned set to a not present ("empty") key. If unsuccessful, nothing is returned.

( $PValue, $Value, $Key ) = First( $Judy, $Key )

Search (inclusive) for the first key present that is equal to or greater than the passed $Key. (Start with $Key = 0 to find the first key in the array.) First() is typically used to begin a sorted-order scan of the keys present in a JudyL array.

Returns nothing if the search finds nothing.

( $PValue, $Value, $Key ) = Next( $Judy, $Key )

Search (exclusive) for the next key present that is greater than the passed Key. Next() is typically used to continue a sorted-order scan of the keys present in a JudyL array, or to locate a "neighbor" of a given key.

  # Prints the contents of $judy
  my ( undef, $value, $key ) = First( $judy, 0 );
  while ( defined $key ) {
      print "$key=$value\n";

      ( undef, $value, $key ) = Next( $judy, $key );
  }

Returns nothing if the search finds nothing.

( $PValue, $Value, $Key ) = Last( $Judy, $Key)

Search (inclusive) for the last key present that is equal to or less than the passed $Key. (Start with $Key = -1, that is, all ones, to find the last key in the array.) Last() is typically used to begin a reverse-sorted-order scan of the keys present in a JudyL array.

Returns nothing if the search finds nothing.

( $PValue, $Value, $Key ) = Prev( $Judy, $Key )

Search (exclusive) for the previous key present that is less than the passed $Key. Prev() is typically used to continue a reverse-sorted-order scan of the keys present in a JudyL array, or to locate a "neighbor" of a given key.

Returns nothing if the search finds nothing.

$Key = FirstEmpty( $Judy, $Key )

Search (inclusive) for the first key absent that is equal to or greater than the passed $Key. (Start with $Key = 0 to find the first key absent in the array.)

Returns nothing if the search finds nothing.

$Key = NextEmpty( $Judy, $Key )

Search (exclusive) for the next key absent that is greater than the passed $Key.

Returns nothing if the search finds nothing.

$Key = LastEmpty( $Judy, $Key )

Search (inclusive) for the last key absent that is equal to or less than the passed $Key. (Start with $Key = -1, that is, all ones, to find the last key absent in the array.)

Returns nothing if the search finds nothing.

$Indx = PrevEmpty( $Judy, $Key )

Search (exclusive) for the previous key absent that is less than the passed $Key.

Returns nothing if the search finds nothing.

$Rc = Count( $Judy, $Key1, $Key2 )

Count the number of keys present in $Judy between $Key1 and $Key2 (inclusive).

Return the count. A return value of 0 can be valid as a count.

To count all keys present in a Judy::L array, use:

  my $count = Count( $judy, 0, -1 );

( $PValue, $Value, $Key ) = Nth( $Judy, $Nth )

Locate the $Nth key that is present in $Judy ($Nth = 1 returns the first key present).

Return pointer to value, value, and key. Return nothing if there isn't an $Nth element.

UTILITY FUNCTIONS

bytes = Free( $Judy )

Frees an entire Judy::L array. This is much faster than a Next/Delete loop. Return number of bytes freed. $Judy is set to 0.

bytes = MemUsed( $Judy )

Return the number of bytes of memory malloc()'ed by $Judy. This is a very fast routine, and may be used before and after a Set() or Delete() call with little performance impact.

MULTIDIMENSIONAL Judy::L

See Judy.

ERRORS & WARNINGS

See Judy.

AUTHOR

See Judy.