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

NAME

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

SYNOPSIS

10       cc [flags] sourcefiles -lJudy
11
12       #include <Judy.h>
13
14       int     Rc_int;                          // return code - integer
15       Word_t  Rc_word;                         // return code - unsigned word
16       Word_t  Index, Index1, Index2, Nth;
17
18       Pvoid_t PJ1Array = (Pvoid_t) NULL;       // initialize Judy1 array
19
20       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

DESCRIPTION

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
44       A Judy1 array is allocated with a NULL pointer
45
46       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
51       As with an ordinary array, a Judy1 array contains no duplicate indexes.
52
53       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
58       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
62        J1S(Rc_int, PJ1Array, Index); // Judy1Set()
63                      Set Index's bit in the Judy1 array PJ1Array.
64
65                      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
69        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
73                      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
77        J1T(Rc_int, PJ1Array, Index); // Judy1Test()
78                      Test if Index's bit is set in the Judy1 array PJ1Array.
79
80                      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
83        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
87                      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
92                      To count all indexes present (population) in a Judy1 bit
93                      array, use:
94
95                      J1C(Rc_word, PJ1Array, 0, -1);
96                      Note: The -1 promotes to the maximum index, that is, all
97                      ones.
98
99        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
105                      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
109        J1FA(Rc_word, PJ1Array); // Judy1FreeArray()
110                      Free  the  entire Judy1 array PJ1Array (much faster than
111                      using a J1N(), J1U() loop).
112
113                      Return Rc_word set to the number  of  bytes  freed,  and
114                      PJ1Array set to NULL.
115
116        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
122        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
134        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
141        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
148        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
156        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
163        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
168        J1NE(Rc_int, PJ1Array, Index); // Judy1NextEmpty()
169                      Search (exclusive) for the next  absent  index  that  is
170                      greater than the passed Index.
171
172        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
177        J1PE(Rc_int, PJ1Array, Index); // Judy1PrevEmpty()
178                      Search (exclusive) for the previous absent index that is
179                      less than the passed Index.
180

ERRORS: See: Judy_3.htm#ERRORS

EXAMPLE

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
188       #include <stdio.h>
189       #include <Judy.h>
190
191       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
198          Pvoid_t PJ1Array = (Pvoid_t) NULL; // initialize Judy1 array
199
200          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
206          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
211          J1C(Rcount, J1Array, 0, -1);  // count all bits set in array
212          printf("%lu bits set in Judy1 array\n", Rcount);
213
214          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
219          J1MU(Rc_word, J1Array);       // how much memory was used?
220          printf("%lu Indexes used %lu bytes of memory\n", Rcount, Rc_word);
221
222          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
228          return(0);
229       }
230

AUTHOR

232       Judy was invented by Doug Baskins and implemented by Hewlett-Packard.
233

SEE ALSO

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
240
241
242                                                                      Judy1(3)
Impressum