Provided by: libjudy-dev_1.0.5-1ubuntu1_amd64 bug


       Judy arrays - C library functions for creating and accessing dynamic arrays


       Judy1  - maps an Index (word) to a bit
       JudyL  - maps an Index (word) to a Value (word/pointer)
       JudySL - maps an Index (null terminated string) to a Value
       JudyHS - maps an Index (array-of-bytes) of Length to a Value


       The  Judy  family of functions supports fully dynamic arrays.  These arrays may be indexed
       by a 32- or 64-bit word (depending on processor word size), a null terminated string or an
       array-of-bytes  plus  length.  A dynamic array (sparsely populated) can also be thought of
       as a mapping function or associative memory.

       A Word_t is a typedef unsigned  long  int   in  Judy.h  and  must  be  the  same  size  as
       sizeof(void *) I.E. a pointer.

       Judy1  functions: Index is a Word_t and Value is just a bit or simply a flag that Index is
       present or missing from the array.  This can be thought of as a huge bitmap.

       JudyL functions: Index is a Word_t and Value is a Word_t.  This makes JudyL a  pure  word-
       to-word/pointer mapper.  JudySL and JudyHL are based on this property of JudyL.

       JudySL functions: Index is a null-terminated string and Value is a Word_t.

       JudyHS  functions:   Index  is  an  array-of-bytes of length:  Length.  Value is a Word_t.
       This new addition (May 2004) to Judy is a hybird using the best features  of  hashing  and
       Judy  methods.  The author believes JudyHS is a good replacement for a hashing method when
       resizing the hash table is done during population growth.  A correctly tuned  hash  method
       with  a  static  hash  table size and population is unbeatable for speed.  However, JudyHS
       will perform better than a hashing method with smaller and  larger  populations  than  the
       optimum  hash  table  size.   JudyHS  does  not  have  a degenerate performance case where
       knowledge of the hash algorithm can be exploited.  (I.E.  JudyHS does  not  use  a  linked
       list  to  handle  hash collisions, it uses a tree of JudyL arrays and a virtual hash table
       size of 4 billion).

       Judy arrays are  both  speed-  and  memory-efficient,  with  no  tuning  or  configuration
       required,  across  a  wide  range  of  index  set  types (sequential, periodic, clustered,
       random).  Judy's speed and memory usage are  typically  better  than  other  data  storage
       models  such  as  skiplists,  linked lists, binary, ternary, b-trees, or even hashing, and
       improves with very large data sets.

       A Judy array is created merely by defining a null pointer and then storing (inserting) the
       first  element  into  the  array  under  that pointer.  The memory used by a Judy array is
       nearly proportional to the population (number of elements).

       Judy has two Application Program Interfaces (APIs):  a C macro interface, and  a  function
       call  interface.   Because  the  macro forms are sometimes faster and have a simpler error
       handling interface than the equivalent functions, they are the preferred way of using  the
       Judy functions.

       Since  an  initial  (empty) Judy array is represented by a null pointer, it is possible to
       construct an array of Judy arrays.  In other words, a Judy array's Values  (except  Judy1)
       can  be  pointers  to  other Judy arrays.  This makes it very simple to construct an array
       with an arbitrary number of dimensions or Index sizes.  (JudySL and JudyHS are implemented
       using JudyL this way).


       may be found at

A 3 HOUR TECHNICAL DESCRIPTION (out of date and a bit corny)

       may be found at


       Judy source downloads are available at
       Binarys may be built and installed in a minute or two after downloading

       For     versions     including     more     platforms    and/or    new    features    see:


       Judy was invented by Doug Baskins (dougbaskins .AT, and implemented by Hewlett-
       Packard.   (Note:  Judy is named for the inventor's sister, after discarding many proposed


       Locations of interest include: -- project downloads
       file:/usr/share/doc/Judy/ -- for HTML version of man pages.
       /usr/share/doc/Judy/demo/ -- demonstration program source files.
       The author attempted to write interesting application notes  using  advanced  features  of
       Judy.   They may be found at " (Some may be out of


       A lot of thought (and time)  went  into  making  error  handling  in  Judy  simple,  while
       maintaining  flexibility  and capability.  Error handling is a very boring subject even to
       write about.  So read this short section  and  use  the  recommended  second  method.   It
       generates  the  fastest  code,  uses  the least amount of memory and requires you to write
       extra code only for insert/deletes functions.  Also it is compatible with  the  other  two
       methods.   This  method  is  for  production  code  that may want to handle malloc() fails
       differently than the Judy default.  If the Judy default method of handling malloc()  fails
       are OK, then use the first method.

       There are two (2) categories of Judy error returns, (or for any dynamic ADT):

       1) User programming errors (bugs) such as memory corruption or invalid pointers.
       2)  Out-of-memory  (malloc() failure) with Insert (Set) or Delete (Unset) when modifying a
       Judy array.  Not all calls to insert and delete call malloc(), so they  may  succeed  even
       when a call to malloc() would fail.

       There are roughly three (3) methods of handling errors when using the macros:

1) Default Error Handling Method

       The default is to print error messages to stderr, for example:

       File 'YourCfile.c', line 1234: JudyLIns(), JU_ERRNO_* == 2, ID == 321
       This  indicates  that an error occurred in the JudyLIns() function at line 321.  Line 1234
       is the line in 'YourCfile.c' where the JLI() call failed.  JU_ERRNO_* ==  2  is  equal  to
       JU_ERRNO_NOMEM  (as  defined in the Judy.h file).  The ID number indicates the source line
       number in the function where the error originated.  Your program then terminates  with  an
       exit(1);.   By  default, both categories of Judy error returns are printed this way.  (The
       'ID == 321' is for die hards that want more detail or for debugging Judy itself.)

2) Disable Macro Error Handling

       When your program is "bug free", the only errors returned  should  be  malloc()  failures.
       Therefore  all  error  returns  can  be treated as a malloc() failure.  By using the below
       #define, all error testing and printing is turned off.  Additional code needs to be  added
       to  the code that can have malloc() failures.  Judy was designed to leave the same data in
       the array before the call if a malloc() fail occurs.  (During testing of  Judy,  we  found
       very  few  malloc()/OS's  that  were bug free after a malloc() failure.  Sometimes it took
       weeks to discover because most systems go into a  paging  frenzy  before  running  out  of

       #define JUDYERROR_NOTEST 1
       (in your program code), or

       cc -DJUDYERROR_NOTEST sourcefile -lJudy
       (on your command line).

       // This is an example of how to program using method two (2).

       JLI(PValue, PLArray, Index);
       if (PValue == PJERR) goto out_of_memory_handling;

       JLD(RC_int, PLArray, Index);
       if (RC_int == JERR) goto out_of_memory_handling;

       J1S(RC_int, P1Array, Index);
       if (RC_int == JERR) goto out_of_memory_handling;

       J1U(RC_int, P1Array, Index);
       if (RC_int == JERR) goto out_of_memory_handling;

       Note:  Without 'JUDYERROR_NOTEST' defined, the 'goto out_of_memory_handling' will never be
       executed and will be optimized out by the compiler.  The default method will  be  used  --
       Macro will print error information if an error occurs as explained above.

       With  'JUDYERROR_NOTEST'  defined, the 'goto out_of_memory_handling' will be executed when
       an error occurs -- which should only happen when malloc() fails.

3) User-Specified JUDYERROR() Macro Method

       The JUDYERROR() macro (in Judy.h) provides  flexibility  for  handling  error  returns  as
       needed  to  suit  your program while still using the Judy array macros instead of function
       calls.  You can use a different JUDYERROR() macro  to  suit  your  needs.   The  following
       example  is  a  possible alternative to the default. It is used to distinguish between the
       two  types  of  errors  (described  above),  and  explicitly  test   for   the   remaining
       JU_ERRNO_NOMEM errors possible in your program.

       // This is an example of Judy macro API to continue when out of memory
       // and print and exit(1) when any other error occurs.

       #ifndef JUDYERROR_NOTEST
       #include <stdio.h>  // needed for fprintf()

       // This is the macro that the Judy macro APIs use for return codes of -1:

       #define JUDYERROR(CallerFile, CallerLine, JudyFunc, JudyErrno, JudyErrID) \
       {                                                                         \
           if ((JudyErrno) != JU_ERRNO_NOMEM) /* ! a malloc() failure */         \
           {                                                                     \
               (void) fprintf(stderr, "File '%s', line %d: %s(), "               \
                   "JU_ERRNO_* == %d, ID == %d\n",                               \
                   CallerFile, CallerLine,                                       \
                   JudyFunc, JudyErrno, JudyErrID);                              \
               exit(1);                                                          \
           }                                                                     \
       #endif // JUDYERROR_NOTEST not defined
       This  error handling macro must be included before the #include <Judy.h> statement in your


       Judy1(3), JudyL(3), JudySL(3), JudyHS(3)