1Judy(3) Library Functions Manual Judy(3)
2
6 Judy arrays - C library functions for creating and accessing dynamic
7 arrays
8
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
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 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 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 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 JudySL functions: Index is a null-terminated string and Value is a
34 Word_t.
35 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 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 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 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 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
75 may be found at http://judy.sourceforge.net/downloads/10minutes.htm
76
78 may be found at http://judy.sourceforge.net/application/shop_interm.pdf
79
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 For versions including more platforms and/or new features see:
86 http://judy.sourceforge.net/downloads/
87
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
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
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 There are two [4m(2) categories of Judy error returns, (or for any dynamic
115 ADT):
116 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 There are roughly three [4m(3) methods of handling errors when using the
124 macros:
125
127 The default is to print error messages to stderr, for example:
128 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
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 #define JUDYERROR_NOTEST 1
151 (in your program code), or
152 cc -DJUDYERROR_NOTEST sourcefile -lJudy
154 (on your command line).
155 // This is an example of how to program using method two (2).
157 JLI(PValue, PLArray, Index);
159 if (PValue == PJERR) goto out_of_memory_handling;
160 JLD(RC_int, PLArray, Index);
162 if (RC_int == JERR) goto out_of_memory_handling;
163 J1S(RC_int, P1Array, Index);
165 if (RC_int == JERR) goto out_of_memory_handling;
166 J1U(RC_int, P1Array, Index);
168 if (RC_int == JERR) goto out_of_memory_handling;
169 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 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
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 // 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 #ifndef JUDYERROR_NOTEST
192 #include <stdio.h> // needed for fprintf()
193 // This is the macro that the Judy macro APIs use for return codes of -1:
195 #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
212 Judy1(3), JudyL(3), JudySL(3), JudyHS(3)
213 Judy(3)