Man Linux: Main Page and Category List

NAME

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

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)