1Judy1(3) Library Functions Manual Judy1(3)
2
6 Judy1 macros - C library for creating and accessing a dynamic array of
7 bits, using any value of 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 Pvoid_t PJ1Array = (Pvoid_t) NULL; // initialize Judy1 array
19 J1S( Rc_int, PJ1Array, Index); // Judy1Set()
21 J1U( Rc_int, PJ1Array, Index); // Judy1Unset()
22 J1T( Rc_int, PJ1Array, Index); // Judy1Test()
23 J1C( Rc_word, PJ1Array, Index1, Index2); // Judy1Count()
24 J1BC(Rc_int, PJ1Array, Nth, Index); // Judy1ByCount()
25 J1FA(Rc_word, PJ1Array); // Judy1FreeArray()
26 J1MU(Rc_word, PJ1Array); // Judy1MemUsed()
27 J1F( Rc_int, PJ1Array, Index); // Judy1First()
28 J1N( Rc_int, PJ1Array, Index); // Judy1Next()
29 J1L( Rc_int, PJ1Array, Index); // Judy1Last()
30 J1P( Rc_int, PJ1Array, Index); // Judy1Prev()
31 J1FE(Rc_int, PJ1Array, Index); // Judy1FirstEmpty()
32 J1NE(Rc_int, PJ1Array, Index); // Judy1NextEmpty()
33 J1LE(Rc_int, PJ1Array, Index); // Judy1LastEmpty()
34 J1PE(Rc_int, PJ1Array, Index); // Judy1PrevEmpty()
35
37 A Judy1 array is the equivalent of a bit array or bit map. A bit is
38 addressed by an Index (key). The array may be sparse, and the Index
39 may be any word-sized Value. If an index is present, it represents a
40 set bit (a bit set represents an index present). If an index is ab‐
41 sent, it represents an unset bit (a bit unset represents an absent in‐
42 dex).
43 A Judy1 array is allocated with a NULL pointer
45 Pvoid_t PJ1Array = (Pvoid_t) NULL;
47 Memory to support the array is allocated as bits are set, and released
48 as bits are unset. If the Judy1 pointer (PJ1Array) is NULL, all bits
49 are unset (and the Judy1 array requires no memory).
50 As with an ordinary array, a Judy1 array contains no duplicate indexes.
52 Using the macros described here, rather than the Judy1 function calls,
54 the default error handling sends a message to the standard error and
55 terminates the program with exit(1). For other error handling methods,
56 see the ERRORS section.
57 Because the macro forms are sometimes faster and have a simpler error
59 handling interface than the equivalent functions, they are the pre‐
60 ferred way of calling the Judy1 functions.
61 J1S(Rc_int, PJ1Array, Index); // Judy1Set()
63 Set Index's bit in the Judy1 array PJ1Array.
64 Return Rc_int set to 1 if Index's bit was previously un‐
66 set (successful), otherwise 0 if the bit was already set
67 (unsuccessful).
68 J1U(Rc_int, PJ1Array, Index); // Judy1Unset()
70 Unset Index's bit in the Judy1 array PJ1Array; that is,
71 remove Index from the Judy1 array.
72 Return Rc_int set to 1 if Index's bit was previously set
74 (successful), otherwise 0 if the bit was already unset
75 (unsuccessful).
76 J1T(Rc_int, PJ1Array, Index); // Judy1Test()
78 Test if Index's bit is set in the Judy1 array PJ1Array.
79 Return Rc_int set to 1 if Index's bit is set (Index is
81 present), 0 if it is unset (Index is absent).
82 J1C(Rc_word, PJ1Array, Index1, Index2); // Judy1Count()
84 Count the number of indexes present in the Judy1 array
85 PJ1Array between Index1 and Index2 (inclusive).
86 Return Rc_word set to the count. A return Value of 0
88 can be valid as a count, or it can indicate a special
89 case for fully populated array (32-bit machines only).
90 See Judy1Count() for ways to resolve this.
91 To count all indexes present (population) in a Judy1 bit
93 array, use:
94 J1C(Rc_word, PJ1Array, 0, -1);
96 Note: The -1 promotes to the maximum index, that is, all
97 ones.
98 J1BC(Rc_int, PJ1Array, Nth, Index); // Judy1ByCount()
100 Locate the Nth index that is present in the Judy1 array
101 PJ1Array (Nth = 1 returns the first index present). To
102 refer to the last index in a fully populated array (all
103 indexes present, which is rare), use Nth = 0.
104 Return Rc_int set to 1 and Index set to the Nth index if
106 found, otherwise return Rc_int set to 0 (the Value of
107 Index contains no useful information).
108 J1FA(Rc_word, PJ1Array); // Judy1FreeArray()
110 Free the entire Judy1 array PJ1Array (much faster than
111 using a J1N(), J1U() loop).
112 Return Rc_word set to the number of bytes freed, and
114 PJ1Array set to NULL.
115 J1MU(Rc_word, PJ1Array); // Judy1MemUsed()
117 Return Rc_word set to the number of bytes of memory cur‐
118 rently in use by Judy1 array PJ1Array. This is a very
119 fast routine, and may be used after a J1S() or J1U()
120 call with little performance impact.
121 Judy1 Search Functions
123 The Judy1 search functions allow you to search for set
124 or unset bits in the array. You may search inclusively
125 or exclusively, in either forward or reverse directions.
126 All of the search functions use a similar calling se‐
127 quence. Rc_int is returned set to 1 for a successful
128 search and the found Index is returned. Rc_int is re‐
129 turned set to 0 for an unsuccessful search, and Index
130 contains no useful information. The return code Rc_int
131 must be checked prior to using the returned Index, since
132 a search failure is possible.
133 J1F(Rc_int, PJ1Array, Index); // Judy1First()
135 Search (inclusive) for the first index present that is
136 equal to or greater than the passed Index. (Start with
137 Index = 0 to find the first index in the array.) J1F()
138 is typically used to begin a sorted-order scan of the
139 indexes present in a Judy1 array.
140 J1N(Rc_int, PJ1Array, Index); // Judy1Next()
142 Search (exclusive) for the next index present that is
143 greater than the passed Index. J1N() is typically used
144 to continue a sorted-order scan of the indexes present
145 in a Judy1 array, or to locate a "neighbor" of a given
146 index.
147 J1L(Rc_int, PJ1Array, Index); // Judy1Last()
149 Search (inclusive) for the last index present that is
150 equal to or less than the passed Index. (Start with In‐
151 dex = -1, that is, all ones, to find the last index in
152 the array.) J1L() is typically used to begin a reverse-
153 sorted-order scan of the indexes present in a Judy1 ar‐
154 ray.
155 J1P(Rc_int, PJ1Array, Index); // Judy1Prev()
157 Search (exclusive) for the previous index present that
158 is less than the passed Index. J1P() is typically used
159 to continue a reverse-sorted-order scan of the indexes
160 present in a Judy1 array, or to locate a "neighbor" of a
161 given index.
162 J1FE(Rc_int, PJ1Array, Index); // Judy1FirstEmpty()
164 Search (inclusive) for the first absent index that is
165 equal to or greater than the passed Index. (Start with
166 Index = 0 to find the first index absent in the array.)
167 J1NE(Rc_int, PJ1Array, Index); // Judy1NextEmpty()
169 Search (exclusive) for the next absent index that is
170 greater than the passed Index.
171 J1LE(Rc_int, PJ1Array, Index); // Judy1LastEmpty()
173 Search (inclusive) for the last absent index that is
174 equal to or less than the passed Index. (Start with In‐
175 dex = -1 to find the last index absent in the array.)
176 J1PE(Rc_int, PJ1Array, Index); // Judy1PrevEmpty()
178 Search (exclusive) for the previous absent index that is
179 less than the passed Index.
180
183 In the following example, errors in the J1S() or J1U() calls go to a
184 user-defined procedure, process_malloc_failure. This is not needed
185 when you use the default JUDYERROR() macro, since the default causes
186 your program to exit on all failures, including malloc() failure.
187 #include <stdio.h>
189 #include <Judy.h>
190 int main() // Example program of Judy1 macro APIs
192 {
193 Word_t Index; // index (or key)
194 Word_t Rcount; // count of indexes (or bits set)
195 Word_t Rc_word; // full word return value
196 int Rc_int; // boolean values returned (0 or 1)
197 Pvoid_t PJ1Array = (Pvoid_t) NULL; // initialize Judy1 array
199 Index = 123456;
201 J1S(Rc_int, J1Array, Index); // set bit at 123456
202 if (Rc_int == JERR) goto process_malloc_failure;
203 if (Rc_int == 1) printf("OK - bit successfully set at %lu\n", Index);
204 if (Rc_int == 0) printf("BUG - bit already set at %lu\n", Index);
205 Index = 654321;
207 J1T(Rc_int, J1Array, Index); // test if bit set at 654321
208 if (Rc_int == 1) printf("BUG - set bit at %lu\n", Index);
209 if (Rc_int == 0) printf("OK - bit not set at %lu\n", Index);
210 J1C(Rcount, J1Array, 0, -1); // count all bits set in array
212 printf("%lu bits set in Judy1 array\n", Rcount);
213 Index = 0;
215 J1F(Rc_int, J1Array, Index); // find first bit set in array
216 if (Rc_int == 1) printf("OK - first bit set is at %lu\n", Index);
217 if (Rc_int == 0) printf("BUG - no bits set in array\n");
218 J1MU(Rc_word, J1Array); // how much memory was used?
220 printf("%lu Indexes used %lu bytes of memory\n", Rcount, Rc_word);
221 Index = 123456;
223 J1U(Rc_int, J1Array, Index); // unset bit at 123456
224 if (Rc_int == JERR) goto process_malloc_failure;
225 if (Rc_int == 1) printf("OK - bit successfully unset at %lu\n", Index);
226 if (Rc_int == 0) printf("BUG - bit was not set at %lu\n", Index);
227 return(0);
229 }
230
232 Judy was invented by Doug Baskins and implemented by Hewlett-Packard.
233
235 Judy(3), JudyL(3), JudySL(3), JudyHS(3),
236 malloc(),
237 the Judy website, http://judy.sourceforge.net, for more information and
238 Application Notes.
239 Judy1(3)