Provided by: libjudy-dev_1.0.5-5.1build1_amd64 bug

NAME

       Judy1 - 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 -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)