1JudyL(3) Library Functions Manual JudyL(3)
2
6 JudyL macros - C library for creating and accessing a dynamic array of
7 words, using a word as an index.
8
10 cc [flags] sourcefiles -lJudy
11 #include <Judy.h>
13 int Rc_int; // return code - integer
15 Word_t Rc_word; // return code - unsigned word
16 Word_t Index, Index1, Index2, Nth;
17 PWord_t PValue; // pointer to return value
18 Pvoid_t PJLArray = (Pvoid_t) NULL; // initialize JudyL array
19 JLI( PValue, PJLArray, Index); // JudyLIns()
21 JLD( Rc_int, PJLArray, Index); // JudyLDel()
22 JLG( PValue, PJLArray, Index); // JudyLGet()
23 JLC( Rc_word, PJLArray, Index1, Index2); // JudyLCount()
24 JLBC(PValue, PJLArray, Nth, Index); // JudyLByCount()
25 JLFA(Rc_word, PJLArray); // JudyLFreeArray()
26 JLMU(Rc_word, PJLArray); // JudyLMemUsed()
27 JLF( PValue, PJLArray, Index); // JudyLFirst()
28 JLN( PValue, PJLArray, Index); // JudyLNext()
29 JLL( PValue, PJLArray, Index); // JudyLLast()
30 JLP( PValue, PJLArray, Index); // JudyLPrev()
31 JLFE(Rc_int, PJLArray, Index); // JudyLFirstEmpty()
32 JLNE(Rc_int, PJLArray, Index); // JudyLNextEmpty()
33 JLLE(Rc_int, PJLArray, Index); // JudyLLastEmpty()
34 JLPE(Rc_int, PJLArray, Index); // JudyLPrevEmpty()
35
37 A JudyL array is the equivalent of an array of word-sized values. A
38 Value is addressed by an Index (key). The array may be sparse, and the
39 Index may be any word-sized number. Memory to support the array is al‐
40 located as index/value pairs are inserted, and released as index/value
41 pairs are deleted. A JudyL array can also be thought of as a mapper,
42 that is "map" a word to another word/pointer.
43 As with an ordinary array, there are no duplicate indexes in a JudyL
45 array.
46 The value may be used as a scalar, or a pointer to a structure or block
48 of data (or even another Judy array).
49 A JudyL array is allocated with a NULL pointer
51 Pvoid_t PJLArray = (Pvoid_t) NULL;
53 Using the macros described here, rather than the JudyL function calls,
55 the default error handling sends a message to the standard error and
56 terminates the program with exit(1);. For other error handling meth‐
57 ods, see the ERRORS section. JLI( PValue, PJLArray, Index);
58 // JudyLIns()
59 Because the macro forms are sometimes faster and have a simpler error
61 handling interface than the equivalent JudyL functions, they are the
62 preferred way of calling the JudyL functions.
63 JLI(PValue, PJLArray, Index) // JudyLIns()
65 Insert an Index and Value into the JudyL array PJLArray.
66 If the Index is successfully inserted, the Value is ini‐
67 tialized to 0. If the Index was already present, the
68 Value is not modified.
69 Return PValue pointing to Value. Your program can use
71 this pointer to read or modify Value until the next
72 JLI() (insert), JLD() (delete) or JLFA() (freearray) is
73 executed on PJLArray. Examples:
74 *PValue = 1234;
76 Value = *PValue;
77 Return PValue set to PJERR if a malloc() fail occured.
79 Note: JLI() and JLD() reorganize the JudyL array.
80 Therefore, PValue returned from previous JudyL calls be‐
81 come invalid and must be re-acquired.
82 JLD(Rc_int, PJLArray, Index) // JudyLDel()
84 Delete the Index/Value pair from the JudyL array.
85 Return Rc_int set to 1 if successful. Return Rc_int set
87 to 0 if Index was not present. Return Rc_int set to
88 JERR if a malloc() fail occured.
89 JLG(PValue, PJLArray, Index) // JudyLGet()
91 Get the pointer PValue associated with Index in the
92 PJLArray Judy array.
93 Return PValue pointing to Value. Return PValue set to
95 NULL if the Index was not present. Return PValue set to
96 PJERR if a malloc() fail occured.
97 JLC(Rc_word, PJLArray, Index1, Index2) // JudyLCount()
99 Count the number of indexes present in the JudyL array
100 PJLArray between Index1 and Index2 (inclusive).
101 Return Rc_word set to the count. A return value of 0
103 can be valid as a count.
104 To count all indexes present in a JudyL array, use:
106 JLC(Rc_word, PJLArray, 0, -1);
108 JLBC(PValue, PJLArray, Nth, Index) // JudyLByCount()
110 Locate the Nth index that is present in the JudyL array
111 PJLArray (Nth = 1 returns the first index present).
112 Return PValue pointing to its Value and Index set to the
114 Nth index if found, otherwise return PValue set to NULL
115 (the value of Index is undefined).
116 JLFA(Rc_word, PJLArray) // JudyLFreeArray()
118 Given a pointer to a JudyL array, free the entire array
119 (much faster than using a JLN(), JLD() loop).
120 Return Rc_word set to the number of bytes freed and
122 PJLArray set to NULL.
123 JLMU(Rc_word, PJLArray) // JudyLMemUsed()
125 Return Rc_word set to the number of bytes of memory mal‐
126 loc()'ed by PJLArray. This is a very fast routine, and
127 may be used before and after a JLI() or JLD() call with
128 little performance impact.
129 JudyL Search Functions
131 JLF(), JLN(), JLL(), JLP() allow you to search for in‐
132 dexes in the array. You may search inclusively or ex‐
133 clusively, in either forward or reverse directions. If
134 successful, Index is returned set to the found index,
135 and PValue is returned set to a pointer to Index's
136 Value. If unsuccessful, PValue is returned set to NULL,
137 and Index contains no useful information. PValue must
138 be tested for non-NULL prior to using Index, since a
139 search failure is possible.
140 JLFE(), JLNE(), JLLE(), JLPE() allow you to search for
142 indexes that are not present ("empty") in the array.
143 You may search inclusively or exclusively, in either
144 forward or reverse directions. If successful, Index is
145 returned set to a not present ("empty") index, and
146 Rc_int is returned set to 1. If unsuccessful, Rc_int is
147 returned set to 0, and and Index contains no useful in‐
148 formation. Rc_int must be checked prior to using Index,
149 since a search failure is possible.
150 JLF(PValue, PJLArray, Index) // JudyLFirst()
152 Search (inclusive) for the first index present that is
153 equal to or greater than the passed Index. (Start with
154 Index = 0 to find the first index in the array.) JLF()
155 is typically used to begin a sorted-order scan of the
156 indexes present in a JudyL array.
157 JLN(PValue, PJLArray, Index) // JudyLNext()
159 Search (exclusive) for the next index present that is
160 greater than the passed Index. JLN() is typically used
161 to continue a sorted-order scan of the indexes present
162 in a JudyL array, or to locate a "neighbor" of a given
163 index.
164 JLL(PValue, PJLArray, Index) // JudyLLast()
166 Search (inclusive) for the last index present that is
167 equal to or less than the passed Index. (Start with In‐
168 dex = -1, that is, all ones, to find the last index in
169 the array.) JLL() is typically used to begin a reverse-
170 sorted-order scan of the indexes present in a JudyL ar‐
171 ray.
172 JLP(PValue, PJLArray, Index) // JudyLPrev()
174 Search (exclusive) for the previous index present that
175 is less than the passed Index. JLP() is typically used
176 to continue a reverse-sorted-order scan of the indexes
177 present in a JudyL array, or to locate a "neighbor" of a
178 given index.
179 JLFE(Rc_int, PJLArray, Index) // JudyLFirstEmpty()
181 Search (inclusive) for the first index absent that is
182 equal to or greater than the passed Index. (Start with
183 Index = 0 to find the first index absent in the array.)
184 JLNE(Rc_int, PJLArray, Index) // JudyLNextEmpty()
186 Search (exclusive) for the next index absent that is
187 greater than the passed Index.
188 JLLE(Rc_int, PJLArray, Index) // JudyLLastEmpty()
190 Search (inclusive) for the last index absent that is
191 equal to or less than the passed Index. (Start with In‐
192 dex = -1, that is, all ones, to find the last index ab‐
193 sent in the array.)
194 JLPE(Rc_int, PJLArray, Index) // JudyLPrevEmpty()
196 Search (exclusive) for the previous index absent that is
197 less than the passed Index.
198
200 Storing a pointer to another JudyL array in a JudyL array's Value is a
201 simple way to support dynamic multi-dimensional arrays. These arrays
202 (or trees) built using JudyL arrays are very fast and memory efficient.
203 (In fact, that is how JudySL and JudyHS are implemented). An arbitrary
204 number of dimensions can be realized this way. To terminate the number
205 of dimensions (or tree), the Value pointer is marked to NOT point to
206 another Judy array. A JLAP_INVALID flag is used in the least signifi‐
207 cant bit(s) of the pointer. After the flag JLAP_INVALID is removed, it
208 is used as a pointer to the users data. The Judy.h header file defines
209 JLAP_INVALID. See code fragment below.
210 Note: The current version of Judy.h changed this flag from 0x4 to 0x1
212 to allow for a malloc() that does not deliver memory on an 8 byte
213 aligned boundry (such as old versions of valgrind).
214 The following example code segment can be used to determine whether or
216 not a pointer points to another JudyL:
217 PValue = (PWord_t)PMultiDimArray;
219 for (Dim = 0; ;Dim++)
221 {
222 if (PValue == (PWord_t)NULL) goto IndexNotFound;
223 /* Advance to next dimension in array */
225 JLG(PValue, (Pvoid_t)*PValue, Index[Dim]);
226 /* Check if pointer to user buffer: */
228 if (*PValue & JLAP_INVALID)) break;
229 }
230 UPointer = (UPointer_t) (*PValue & ~JLAP_INVALID); // mask and cast.
231 printf("User object pointer is 0x%lx\n", (Word_t) UPointer);
232 ...
233 Note: This works because malloc() guarantees to return a pointer with
235 the least bit(s) == 0x0. You must remove JLAP_INVALID before using the
236 pointer.
237
240 Read a series of index/value pairs from the standard input, store in a
241 JudyL array, and then print out in sorted order.
242 #include <stdio.h>
244 #include <Judy.h>
245 Word_t Index; // array index
247 Word_t Value; // array element value
248 Word_t * PValue; // pointer to array element value
249 int Rc_int; // return code
250 Pvoid_t PJLArray = (Pvoid_t) NULL; // initialize JudyL array
252 while (scanf("%lu %lu", &Index, &Value))
254 {
255 JLI(PValue, PJLArray, Index);
256 If (PValue == PJERR) goto process_malloc_failure;
257 *PValue = Value; // store new value
258 }
259 // Next, visit all the stored indexes in sorted order, first ascending,
260 // then descending, and delete each index during the descending pass.
261 Index = 0;
263 JLF(PValue, PJLArray, Index);
264 while (PValue != NULL)
265 {
266 printf("%lu %lu\n", Index, *PValue));
267 JLN(PValue, PJLArray, Index);
268 }
269 Index = -1;
271 JLL(PValue, PJLArray, Index);
272 while (PValue != NULL)
273 {
274 printf("%lu %lu\n", Index, *PValue));
275 JLD(Rc_int, PJLArray, Index);
277 if (Rc_int == JERR) goto process_malloc_failure;
278 JLP(PValue, PJLArray, Index);
280 }
281
283 Judy was invented by Doug Baskins and implemented by Hewlett-Packard.
284
286 Judy(3), Judy1(3), JudySL(3), JudyHS(3),
287 malloc(),
288 http://judy.sourceforge.net, for more information and Application
289 Notes.
290 JudyL(3)