NAME

       Judy - C library functions for creating and accessing dynamic arrays

SYNOPSIS

       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

DESCRIPTION

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

A 10 MINUTE TECHNICAL DESCRIPTION

       may be found at http://judy.sourceforge.net/downloads/10minutes.htm

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

       may be found at http://judy.sourceforge.net/application/shop_interm.pdf

DOWNLOADS

       Judy source downloads are available at http://sourceforge.net/projects/judy
       Binarys may be built and installed in a minute or two after downloading

       For versions including more platforms and/or new features see: http://judy.sourceforge.net/downloads/

AUTHOR

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

FILES

       Locations of interest include:
       http://sourceforge.net/projects/judy -- 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 "http://judy.sourceforge.net/application/ (Some may be out of date).

ERRORS

       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 memory).

       #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 program.

SEE ALSO

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

                                                                                                         Judy(3)