Man Linux: Main Page and Category List

NAME

       JudyL  macros - C library for creating and accessing a dynamic array of
       words, using 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;
       PWord_t  PValue;                          // pointer to return value
       Pvoid_t PJLArray = (Pvoid_t) NULL;        // initialize JudyL array

       JLI( PValue,  PJLArray, Index);          // JudyLIns()
       JLD( Rc_int,  PJLArray, Index);          // JudyLDel()
       JLG( PValue,  PJLArray, Index);          // JudyLGet()
       JLC( Rc_word, PJLArray, Index1, Index2); // JudyLCount()
       JLBC(PValue,  PJLArray, Nth, Index);     // JudyLByCount()
       JLFA(Rc_word, PJLArray);                 // JudyLFreeArray()
       JLMU(Rc_word, PJLArray);                 // JudyLMemUsed()
       JLF( PValue,  PJLArray, Index);          // JudyLFirst()
       JLN( PValue,  PJLArray, Index);          // JudyLNext()
       JLL( PValue,  PJLArray, Index);          // JudyLLast()
       JLP( PValue,  PJLArray, Index);          // JudyLPrev()
       JLFE(Rc_int,  PJLArray, Index);          // JudyLFirstEmpty()
       JLNE(Rc_int,  PJLArray, Index);          // JudyLNextEmpty()
       JLLE(Rc_int,  PJLArray, Index);          // JudyLLastEmpty()
       JLPE(Rc_int,  PJLArray, Index);          // JudyLPrevEmpty()

DESCRIPTION

       A JudyL 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 JudyL 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 JudyL
       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 NULL pointer

       Pvoid_t PJLArray = (Pvoid_t) NULL;

       Using  the macros described here, rather than the JudyL 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.   JLI(  PValue,   PJLArray,  Index);
       // JudyLIns()

       Because  the  macro forms are sometimes faster and have a simpler error
       handling interface than the equivalent JudyL functions,  they  are  the
       preferred way of calling the JudyL functions.

        JLI(PValue, PJLArray, Index) // JudyLIns()
                      Insert an Index and Value into the JudyL array PJLArray.
                      If the Index is  successfully  inserted,  the  Value  is
                      initialized  to 0. If the Index was already present, the
                      Value is not modified.

                      Return PValue pointing to Value.  Your program  can  use
                      this  pointer  to  read  or  modify Value until the next
                      JLI() (insert), JLD() (delete) or JLFA() (freearray)  is
                      executed on PJLArray. Examples:

                      *PValue = 1234;
                      Value = *PValue;

                      Return  PValue  set to PJERR if a malloc() fail occured.
                      Note:  JLI()  and  JLD()  reorganize  the  JudyL  array.
                      Therefore,  PValue  returned  from  previous JudyL calls
                      become invalid and must be re-acquired.

        JLD(Rc_int, PJLArray, Index) // JudyLDel()
                      Delete the Index/Value pair from the JudyL array.

                      Return Rc_int set to 1 if successful.  Return Rc_int set
                      to  0  if  Index  was not present.  Return Rc_int set to
                      JERR if a malloc() fail occured.

        JLG(PValue, PJLArray, Index) // JudyLGet()
                      Get the pointer PValue  associated  with  Index  in  the
                      PJLArray Judy array.

                      Return  PValue  pointing to Value.  Return PValue set to
                      NULL if the Index was not present.  Return PValue set to
                      PJERR if a malloc() fail occured.

        JLC(Rc_word, PJLArray, Index1, Index2) // JudyLCount()
                      Count  the  number of indexes present in the JudyL array
                      PJLArray between Index1 and Index2 (inclusive).

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

                      To count all indexes present in a JudyL array, use:

                      JLC(Rc_word, PJLArray, 0, -1);

        JLBC(PValue, PJLArray, Nth, Index) // JudyLByCount()
                      Locate  the Nth index that is present in the JudyL array
                      PJLArray (Nth = 1 returns the first index present).

                      Return PValue pointing to its Value and Index set to the
                      Nth  index if found, otherwise return PValue set to NULL
                      (the value of Index is undefined).

        JLFA(Rc_word, PJLArray) // JudyLFreeArray()
                      Given a pointer to a JudyL array, free the entire  array
                      (much faster than using a JLN(), JLD() loop).

                      Return  Rc_word  set  to  the  number of bytes freed and
                      PJLArray set to NULL.

        JLMU(Rc_word, PJLArray) // JudyLMemUsed()
                      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.

        JudyL Search Functions
                      JLF(),  JLN(),  JLL(),  JLP()  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,
                      and  PValue  is  returned  set  to  a pointer to Index’s
                      Value.  If unsuccessful, PValue is returned set to NULL,
                      and  Index  contains no useful information.  PValue must
                      be tested for non-NULL prior to  using  Index,  since  a
                      search failure is possible.

                      JLFE(),  JLNE(),  JLLE(), JLPE() 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, Index  is
                      returned  set  to  a  not  present  ("empty") index, and
                      Rc_int is returned set to 1.  If unsuccessful, Rc_int is
                      returned  set  to  0,  and  and Index contains no useful
                      information.  Rc_int must  be  checked  prior  to  using
                      Index, since a search failure is possible.

        JLF(PValue, PJLArray, Index) // JudyLFirst()
                      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.)  JLF()
                      is typically used to begin a sorted-order  scan  of  the
                      indexes present in a JudyL array.

        JLN(PValue, PJLArray, Index) // JudyLNext()
                      Search  (exclusive)  for  the next index present that is
                      greater than the passed Index.  JLN() 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.

        JLL(PValue, PJLArray, Index) // JudyLLast()
                      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.)  JLL() is typically used to begin a reverse-
                      sorted-order  scan  of  the  indexes  present in a JudyL
                      array.

        JLP(PValue, PJLArray, Index) // JudyLPrev()
                      Search (exclusive) for the previous index  present  that
                      is  less than the passed Index.  JLP() 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.

        JLFE(Rc_int, PJLArray, Index) // JudyLFirstEmpty()
                      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.)

        JLNE(Rc_int, PJLArray, Index) // JudyLNextEmpty()
                      Search  (exclusive)  for  the  next index absent that is
                      greater than the passed Index.

        JLLE(Rc_int, PJLArray, Index) // JudyLLastEmpty()
                      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.)

        JLPE(Rc_int, PJLArray, Index) // JudyLPrevEmpty()
                      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 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  JLAP_INVALID  flag  is  used  in  the   least
       significant  bit(s)  of  the  pointer.   After the flag JLAP_INVALID is
       removed, it is used as a pointer to the users data.  The Judy.h  header
       file defines JLAP_INVALID.  See code fragment below.

       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 versions of valgrind).

       The  following example code segment can be used to determine whether or
       not a pointer points to another JudyL:

       PValue = (PWord_t)PMultiDimArray;

       for (Dim = 0; ;Dim++)
       {
          if (PValue == (PWord_t)NULL) goto IndexNotFound;

          /* Advance to next dimension in array */
          JLG(PValue, (Pvoid_t)*PValue, Index[Dim]);

          /* Check if pointer to user buffer: */
          if (*PValue & JLAP_INVALID)) break;
       }
       UPointer = (UPointer_t) (*PValue & ~JLAP_INVALID);  // mask and cast.
       printf("User object pointer is 0x%lx\n", (Word_t) UPointer);
              ...

       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_3.htm#ERRORS

EXAMPLE

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

       #include <stdio.h>
       #include <Judy.h>

       Word_t   Index;                     // array index
       Word_t   Value;                     // array element value
       Word_t * PValue;                    // pointer to array element value
       int      Rc_int;                    // return code

       Pvoid_t  PJLArray = (Pvoid_t) NULL; // initialize JudyL array

       while (scanf("%lu %lu", &Index, &Value))
       {
           JLI(PValue, PJLArray, Index);
           If (PValue == PJERR) goto process_malloc_failure;
           *PValue = Value;                 // store new value
       }
       // Next, visit all the stored indexes in sorted order, first ascending,
       // then descending, and delete each index during the descending pass.

       Index = 0;
       JLF(PValue, PJLArray, Index);
       while (PValue != NULL)
       {
           printf("%lu %lu\n", Index, *PValue));
           JLN(PValue, PJLArray, Index);
       }

       Index = -1;
       JLL(PValue, PJLArray, Index);
       while (PValue != NULL)
       {
           printf("%lu %lu\n", Index, *PValue));

           JLD(Rc_int, PJLArray, Index);
           if (Rc_int == JERR) goto process_malloc_failure;

           JLP(PValue, PJLArray, Index);
       }

AUTHOR

       Judy was invented by Doug Baskins and implemented by Hewlett-Packard.

SEE ALSO

       Judy(3), Judy1(3), JudySL(3), JudyHS(3),
       malloc(),
       http://judy.sourceforge.net,   for  more  information  and  Application
       Notes.

                                                                      JudyL(3)