1Judy(3)                    Library Functions Manual                    Judy(3)
2
3
4

NAME

6       Judy  arrays  -  C library functions for creating and accessing dynamic
7       arrays
8

SYNOPSIS

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

DESCRIPTION

16       The Judy family of functions supports fully dynamic arrays.  These  ar‐
17       rays  may  be  indexed  by a 32- or 64-bit word (depending on processor
18       word size), a null terminated string or an array-of-bytes plus  length.
19       A  dynamic  array (sparsely populated) can also be thought of as a map‐
20       ping function or associative memory.
21
22       A Word_t is a typedef unsigned long int  in Judy.h and must be the same
23       size as sizeof(void *) I.E. a pointer.
24
25       Judy1  functions: Index is a Word_t and Value is just a bit or simply a
26       flag that Index is present or missing from  the  array.   This  can  be
27       thought of as a huge bitmap.
28
29       JudyL  functions:  Index is a Word_t and Value is a Word_t.  This makes
30       JudyL a pure word-to-word/pointer mapper.  JudySL and JudyHL are  based
31       on this property of JudyL.
32
33       JudySL  functions:  Index  is  a  null-terminated string and Value is a
34       Word_t.
35
36       JudyHS functions:  Index  is  an  array-of-bytes  of  length:   Length.
37       Value  is  a  Word_t.  This new addition (May 2004) to Judy is a hybird
38       using the best features of hashing and Judy methods.   The  author  be‐
39       lieves  JudyHS is a good replacement for a hashing method when resizing
40       the hash table is done during population  growth.   A  correctly  tuned
41       hash  method with a static hash table size and population is unbeatable
42       for speed.  However, JudyHS will perform better than a  hashing  method
43       with  smaller  and larger populations than the optimum hash table size.
44       JudyHS does not have a degenerate performance case where  knowledge  of
45       the  hash  algorithm  can  be  exploited.  (I.E.  JudyHS does not use a
46       linked list to handle hash collisions, it uses a tree of  JudyL  arrays
47       and a virtual hash table size of 4 billion).
48
49       Judy  arrays  are  both  speed- and memory-efficient, with no tuning or
50       configuration required, across a wide range of index set types (sequen‐
51       tial,  periodic, clustered, random).  Judy's speed and memory usage are
52       typically better than other data  storage  models  such  as  skiplists,
53       linked  lists,  binary, ternary, b-trees, or even hashing, and improves
54       with very large data sets.
55
56       A Judy array is created merely by defining  a  null  pointer  and  then
57       storing  (inserting)  the  first  element  into  the  array  under that
58       pointer.  The memory used by a Judy array is nearly proportional to the
59       population (number of elements).
60
61       Judy  has  two Application Program Interfaces (APIs):  a C macro inter‐
62       face, and a function call interface.  Because the macro forms are some‐
63       times  faster  and  have  a  simpler  error handling interface than the
64       equivalent functions, they are the preferred  way  of  using  the  Judy
65       functions.
66
67       Since  an  initial (empty) Judy array is represented by a null pointer,
68       it is possible to construct an array of Judy arrays.  In other words, a
69       Judy  array's  Values  (except Judy1) can be pointers to other Judy ar‐
70       rays.  This makes it very simple to construct an array  with  an  arbi‐
71       trary  number of dimensions or Index sizes.  (JudySL and JudyHS are im‐
72       plemented using JudyL this way).
73

A 10 MINUTE TECHNICAL DESCRIPTION

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

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

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

DOWNLOADS

81       Judy    source    downloads    are    available    at    http://source
82       forge.net/projects/judy
83       Binarys may be built and installed in a minute or two after downloading
84
85       For   versions  including  more  platforms  and/or  new  features  see:
86       http://judy.sourceforge.net/downloads/
87

AUTHOR

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

FILES

94       Locations of interest include:
95       http://sourceforge.net/projects/judy -- project downloads
96       file:/usr/share/doc/Judy/ -- for HTML version of man pages.
97       /usr/share/doc/Judy/demo/ -- demonstration program source files.
98       The author attempted to write interesting application notes  using  ad‐
99       vanced  features  of  Judy.   They may be found at "http://judy.source
100       forge.net/application/ (Some may be out of date).
101

ERRORS

103       A lot of thought (and time) went into making  error  handling  in  Judy
104       simple,  while  maintaining flexibility and capability.  Error handling
105       is a very boring subject even to write about.  So read this short  sec‐
106       tion  and  use the recommended second method.  It generates the fastest
107       code, uses the least amount of memory and requires you to  write  extra
108       code only for insert/deletes functions.  Also it is compatible with the
109       other two methods.  This method is for production code that may want to
110       handle  malloc()  fails differently than the Judy default.  If the Judy
111       default method of handling malloc() fails are OK, then  use  the  first
112       method.
113
114       There are two (2) categories of Judy error returns, (or for any dynamic
115       ADT):
116
117       1) User programming errors (bugs) such as memory corruption or  invalid
118       pointers.
119       2) Out-of-memory (malloc() failure) with Insert (Set) or Delete (Unset)
120       when modifying a Judy array.  Not all calls to insert and  delete  call
121       malloc(), so they may succeed even when a call to malloc() would fail.
122
123       There  are  roughly three (3) methods of handling errors when using the
124       macros:
125

1) Default Error Handling Method

127       The default is to print error messages to stderr, for example:
128
129       File 'YourCfile.c', line 1234: JudyLIns(), JU_ERRNO_* == 2, ID == 321
130       This indicates that an error occurred in  the  JudyLIns()  function  at
131       line  321.  Line 1234 is the line in 'YourCfile.c' where the JLI() call
132       failed.  JU_ERRNO_* == 2 is equal to JU_ERRNO_NOMEM (as defined in  the
133       Judy.h  file).   The  ID number indicates the source line number in the
134       function where the error originated.  Your program then terminates with
135       an  exit(1);.   By  default,  both categories of Judy error returns are
136       printed this way.  (The 'ID == 321' is for die hards that want more de‐
137       tail or for debugging Judy itself.)
138

2) Disable Macro Error Handling

140       When  your  program  is  "bug free", the only errors returned should be
141       malloc() failures.  Therefore all error returns can  be  treated  as  a
142       malloc()  failure.   By  using the below #define, all error testing and
143       printing is turned off.  Additional code needs to be added to the  code
144       that  can  have malloc() failures.  Judy was designed to leave the same
145       data in the array before the call if a malloc() fail  occurs.   (During
146       testing of Judy, we found very few malloc()/OS's that were bug free af‐
147       ter a malloc() failure.  Sometimes it took weeks  to  discover  because
148       most systems go into a paging frenzy before running out of memory).
149
150       #define JUDYERROR_NOTEST 1
151       (in your program code), or
152
153       cc -DJUDYERROR_NOTEST sourcefile -lJudy
154       (on your command line).
155
156       // This is an example of how to program using method two (2).
157
158       JLI(PValue, PLArray, Index);
159       if (PValue == PJERR) goto out_of_memory_handling;
160
161       JLD(RC_int, PLArray, Index);
162       if (RC_int == JERR) goto out_of_memory_handling;
163
164       J1S(RC_int, P1Array, Index);
165       if (RC_int == JERR) goto out_of_memory_handling;
166
167       J1U(RC_int, P1Array, Index);
168       if (RC_int == JERR) goto out_of_memory_handling;
169
170       Note:  Without 'JUDYERROR_NOTEST' defined, the 'goto out_of_memory_han‐
171       dling' will never be executed and will be optimized  out  by  the  com‐
172       piler.   The  default method will be used -- Macro will print error in‐
173       formation if an error occurs as explained above.
174
175       With 'JUDYERROR_NOTEST' defined, the 'goto out_of_memory_handling' will
176       be  executed when an error occurs -- which should only happen when mal‐
177       loc() fails.
178

3) User-Specified JUDYERROR() Macro Method

180       The JUDYERROR() macro (in Judy.h) provides flexibility for handling er‐
181       ror  returns  as needed to suit your program while still using the Judy
182       array macros instead of function calls.  You can use a different  JUDY‐
183       ERROR()  macro to suit your needs.  The following example is a possible
184       alternative to the default. It is used to distinguish between  the  two
185       types  of errors (described above), and explicitly test for the remain‐
186       ing JU_ERRNO_NOMEM errors possible in your program.
187
188       // This is an example of Judy macro API to continue when out of memory
189       // and print and exit(1) when any other error occurs.
190
191       #ifndef JUDYERROR_NOTEST
192       #include <stdio.h>  // needed for fprintf()
193
194       // This is the macro that the Judy macro APIs use for return codes of -1:
195
196       #define JUDYERROR(CallerFile, CallerLine, JudyFunc, JudyErrno, JudyErrID) \
197       {                                                                         \
198           if ((JudyErrno) != JU_ERRNO_NOMEM) /* ! a malloc() failure */         \
199           {                                                                     \
200               (void) fprintf(stderr, "File '%s', line %d: %s(), "               \
201                   "JU_ERRNO_* == %d, ID == %d\n",                               \
202                   CallerFile, CallerLine,                                       \
203                   JudyFunc, JudyErrno, JudyErrID);                              \
204               exit(1);                                                          \
205           }                                                                     \
206       }
207       #endif // JUDYERROR_NOTEST not defined
208       This error handling macro must be included before the #include <Judy.h>
209       statement in your program.
210

SEE ALSO

212       Judy1(3), JudyL(3), JudySL(3), JudyHS(3)
213
214
215
216                                                                       Judy(3)
Impressum