Man Linux: Main Page and Category List

NAME

       Judy1  macros - C library for creating and accessing a dynamic array of
       bits, using any value of 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;

       Pvoid_t PJ1Array = (Pvoid_t) NULL;       // initialize Judy1 array

       J1S( Rc_int,  PJ1Array, Index);          // Judy1Set()
       J1U( Rc_int,  PJ1Array, Index);          // Judy1Unset()
       J1T( Rc_int,  PJ1Array, Index);          // Judy1Test()
       J1C( Rc_word, PJ1Array, Index1, Index2); // Judy1Count()
       J1BC(Rc_int,  PJ1Array, Nth, Index);     // Judy1ByCount()
       J1FA(Rc_word, PJ1Array);                 // Judy1FreeArray()
       J1MU(Rc_word, PJ1Array);                 // Judy1MemUsed()
       J1F( Rc_int,  PJ1Array, Index);          // Judy1First()
       J1N( Rc_int,  PJ1Array, Index);          // Judy1Next()
       J1L( Rc_int,  PJ1Array, Index);          // Judy1Last()
       J1P( Rc_int,  PJ1Array, Index);          // Judy1Prev()
       J1FE(Rc_int,  PJ1Array, Index);          // Judy1FirstEmpty()
       J1NE(Rc_int,  PJ1Array, Index);          // Judy1NextEmpty()
       J1LE(Rc_int,  PJ1Array, Index);          // Judy1LastEmpty()
       J1PE(Rc_int,  PJ1Array, Index);          // Judy1PrevEmpty()

DESCRIPTION

       A Judy1 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 Judy1 array is allocated with a NULL pointer

       Pvoid_t PJ1Array = (Pvoid_t) NULL;
       Memory  to support the array is allocated as bits are set, and released
       as bits are unset.  If the Judy1 pointer (PJ1Array) is NULL,  all  bits
       are unset (and the Judy1 array requires no memory).

       As with an ordinary array, a Judy1 array contains no duplicate indexes.

       Using the macros described here, rather than the Judy1 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.

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

        J1S(Rc_int, PJ1Array, Index); // Judy1Set()
                      Set Index’s bit in the Judy1 array PJ1Array.

                      Return  Rc_int  set  to  1 if Index’s bit was previously
                      unset (successful), otherwise 0 if the bit  was  already
                      set (unsuccessful).

        J1U(Rc_int, PJ1Array, Index); // Judy1Unset()
                      Unset  Index’s bit in the Judy1 array PJ1Array; that is,
                      remove Index from the Judy1 array.

                      Return Rc_int set to 1 if Index’s bit was previously set
                      (successful),  otherwise  0 if the bit was already unset
                      (unsuccessful).

        J1T(Rc_int, PJ1Array, Index); // Judy1Test()
                      Test if Index’s bit is set in the Judy1 array  PJ1Array.

                      Return  Rc_int  set to 1 if Index’s bit is set (Index is
                      present), 0 if it is unset (Index is absent).

        J1C(Rc_word, PJ1Array, Index1, Index2); // Judy1Count()
                      Count the number of indexes present in the  Judy1  array
                      PJ1Array between Index1 and Index2 (inclusive).

                      Return  Rc_word  set  to the count.  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).
                      See Judy1Count() for ways to resolve this.

                      To count all indexes present (population) in a Judy1 bit
                      array, use:

                      J1C(Rc_word, PJ1Array, 0, -1);
                      Note: The -1 promotes to the maximum index, that is, all
                      ones.

        J1BC(Rc_int, PJ1Array, Nth, Index); // Judy1ByCount()
                      Locate the Nth index that is present in the Judy1  array
                      PJ1Array  (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.

                      Return Rc_int set to 1 and Index set to the Nth index if
                      found, otherwise return Rc_int set to 0  (the  Value  of
                      Index contains no useful information).

        J1FA(Rc_word, PJ1Array); // Judy1FreeArray()
                      Free  the  entire Judy1 array PJ1Array (much faster than
                      using a J1N(), J1U() loop).

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

        J1MU(Rc_word, PJ1Array); // Judy1MemUsed()
                      Return  Rc_word  set  to  the  number of bytes of memory
                      currently in use by Judy1 array PJ1Array. This is a very
                      fast  routine,  and  may  be used after a J1S() or J1U()
                      call with little performance impact.

        Judy1 Search Functions
                      The Judy1 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.  Rc_int is returned set to 1 for a  successful
                      search  and  the  found  Index  is  returned.  Rc_int is
                      returned set to 0 for an unsuccessful search, and  Index
                      contains  no useful information.  The return code Rc_int
                      must be checked prior to using the returned Index, since
                      a search failure is possible.

        J1F(Rc_int, PJ1Array, Index); // Judy1First()
                      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 Judy1 array.

        J1N(Rc_int, PJ1Array, Index); // Judy1Next()
                      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 Judy1 array, or to locate a "neighbor" of  a  given
                      index.

        J1L(Rc_int, PJ1Array, Index); // Judy1Last()
                      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 Judy1
                      array.

        J1P(Rc_int, PJ1Array, Index); // Judy1Prev()
                      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 Judy1 array, or to locate a "neighbor" of a
                      given index.

        J1FE(Rc_int, PJ1Array, Index); // Judy1FirstEmpty()
                      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, PJ1Array, Index); // Judy1NextEmpty()
                      Search  (exclusive)  for  the  next absent index that is
                      greater than the passed Index.

        J1LE(Rc_int, PJ1Array, Index); // Judy1LastEmpty()
                      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, PJ1Array, Index); // Judy1PrevEmpty()
                      Search (exclusive) for the previous absent index that is
                      less than the passed Index.

ERRORS: See: Judy_3.htm#ERRORS

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.

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

       int main()                       // Example program of Judy1 macro APIs
       {
          Word_t Index;                 // index (or key)
          Word_t Rcount;                // count of indexes (or bits set)
          Word_t Rc_word;               // full word return value
          int    Rc_int;                // boolean values returned (0 or 1)

          Pvoid_t PJ1Array = (Pvoid_t) NULL; // initialize Judy1 array

          Index = 123456;
          J1S(Rc_int, J1Array, Index);  // set bit at 123456
          if (Rc_int == JERR) goto process_malloc_failure;
          if (Rc_int == 1) printf("OK - bit successfully set at %lu\n", Index);
          if (Rc_int == 0) printf("BUG - bit already set at %lu\n", Index);

          Index = 654321;
          J1T(Rc_int, J1Array, Index);  // test if bit set at 654321
          if (Rc_int == 1) printf("BUG - set bit at %lu\n", Index);
          if (Rc_int == 0) printf("OK - bit not set at %lu\n", Index);

          J1C(Rcount, J1Array, 0, -1);  // count all bits set in array
          printf("%lu bits set in Judy1 array\n", Rcount);

          Index = 0;
          J1F(Rc_int, J1Array, Index);  // find first bit set in array
          if (Rc_int == 1) printf("OK - first bit set is at %lu\n", Index);
          if (Rc_int == 0) printf("BUG - no bits set in array\n");

          J1MU(Rc_word, J1Array);       // how much memory was used?
          printf("%lu Indexes used %lu bytes of memory\n", Rcount, Rc_word);

          Index = 123456;
          J1U(Rc_int, J1Array, Index);  // unset bit at 123456
          if (Rc_int == JERR) goto process_malloc_failure;
          if (Rc_int == 1) printf("OK - bit successfully unset at %lu\n", Index);
          if (Rc_int == 0) printf("BUG - bit was not set at %lu\n", Index);

          return(0);
       }

AUTHOR

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

SEE ALSO

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

                                                                      Judy1(3)