JLN(3) - f14

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

NAME

6       JudyL  macros - C library for creating and accessing a dynamic array of
7       words, using 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       PWord_t  PValue;                          // pointer to return value
18       Pvoid_t PJLArray = (Pvoid_t) NULL;        // initialize JudyL array
19
20       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

DESCRIPTION

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
40       allocated   as   index/value   pairs  are  inserted,  and  released  as
41       index/value pairs are deleted.  A JudyL array can also be thought of as
42       a mapper, that is "map" a word to another word/pointer.
43
44       As  with  an  ordinary array, there are no duplicate indexes in a JudyL
45       array.
46
47       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
50       A JudyL array is allocated with a NULL pointer
51
52       Pvoid_t PJLArray = (Pvoid_t) NULL;
53
54       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
60       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
64        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
70                      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
75                      *PValue = 1234;
76                      Value = *PValue;
77
78                      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
81                      become invalid and must be re-acquired.
82
83        JLD(Rc_int, PJLArray, Index) // JudyLDel()
84                      Delete the Index/Value pair from the JudyL array.
85
86                      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
90        JLG(PValue, PJLArray, Index) // JudyLGet()
91                      Get the pointer PValue  associated  with  Index  in  the
92                      PJLArray Judy array.
93
94                      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
98        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
102                      Return Rc_word set to the count.  A return  value  of  0
103                      can be valid as a count.
104
105                      To count all indexes present in a JudyL array, use:
106
107                      JLC(Rc_word, PJLArray, 0, -1);
108
109        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
113                      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
117        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
121                      Return  Rc_word  set  to  the  number of bytes freed and
122                      PJLArray set to NULL.
123
124        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
130        JudyL Search Functions
131                      JLF(),  JLN(),  JLL(),  JLP()  allow  you  to search for
132                      indexes in the array.  You  may  search  inclusively  or
133                      exclusively,  in  either  forward or reverse directions.
134                      If 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
141                      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
148                      information.  Rc_int must  be  checked  prior  to  using
149                      Index, since a search failure is possible.
150
151        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
158        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
165        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
168                      Index = -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
171                      array.
172
173        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
180        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
185        JLNE(Rc_int, PJLArray, Index) // JudyLNextEmpty()
186                      Search (exclusive) for the next  index  absent  that  is
187                      greater than the passed Index.
188
189        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
192                      Index  =  -1,  that is, all ones, to find the last index
193                      absent in the array.)
194
195        JLPE(Rc_int, PJLArray, Index) // JudyLPrevEmpty()
196                      Search (exclusive) for the previous index absent that is
197                      less than the passed Index.
198

Multi-dimensional JudyL Arrays

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
211       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
215       The following example code segment can be used to determine whether  or
216       not a pointer points to another JudyL:
217
218       PValue = (PWord_t)PMultiDimArray;
219
220       for (Dim = 0; ;Dim++)
221       {
222          if (PValue == (PWord_t)NULL) goto IndexNotFound;
223
224          /* Advance to next dimension in array */
225          JLG(PValue, (Pvoid_t)*PValue, Index[Dim]);
226
227          /* 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
234       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

ERRORS: See: Judy_3.htm#ERRORS

EXAMPLE

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
243       #include <stdio.h>
244       #include <Judy.h>
245
246       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
251       Pvoid_t  PJLArray = (Pvoid_t) NULL; // initialize JudyL array
252
253       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
262       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
270       Index = -1;
271       JLL(PValue, PJLArray, Index);
272       while (PValue != NULL)
273       {
274           printf("%lu %lu\n", Index, *PValue));
275
276           JLD(Rc_int, PJLArray, Index);
277           if (Rc_int == JERR) goto process_malloc_failure;
278
279           JLP(PValue, PJLArray, Index);
280       }
281

AUTHOR

283       Judy was invented by Doug Baskins and implemented by Hewlett-Packard.
284