3
<!-- @(#) $Revision: 4.55 $ $Source: /cvsroot/judy/doc/ext/JudyL_3.htm,v $ --->
4
<TITLE>JudyL(3)</TITLE>
7
<TABLE border=0 width="100%"><TR>
8
<TD width="40%" align="left">JudyL(3)</TD>
9
<TD width="10%" align="center"> </TD>
10
<TD width="40%" align="right">JudyL(3)</TD>
18
C library for creating and accessing a dynamic array of words, using
22
<DT><B>SYNOPSIS</B></DT>
25
cc [flags] <I>sourcefiles</I> -lJudy
27
#include <Judy.h>
29
int Rc_int; // return code - integer
30
Word_t Rc_word; // return code - unsigned word
31
Word_t Index, Index1, Index2, Nth;
32
PWord_t PValue; // pointer to return value
33
Pvoid_t PJLArray = (Pvoid_t) NULL; // initialize JudyL array
35
<A href="#JLI" >JLI</A>( PValue, PJLArray, Index); // <A href="JudyL_funcs_3.htm#JudyLIns">JudyLIns()</A>
36
<A href="#JLD" >JLD</A>( Rc_int, PJLArray, Index); // <A href="JudyL_funcs_3.htm#JudyLDel">JudyLDel()</A>
37
<A href="#JLG" >JLG</A>( PValue, PJLArray, Index); // <A href="JudyL_funcs_3.htm#JudyLGet">JudyLGet()</A>
38
<A href="#JLC" >JLC</A>( Rc_word, PJLArray, Index1, Index2); // <A href="JudyL_funcs_3.htm#JudyLCount">JudyLCount()</A>
39
<A href="#JLBC" >JLBC</A>(PValue, PJLArray, Nth, Index); // <A href="JudyL_funcs_3.htm#JudyLByCount">JudyLByCount()</A>
40
<A href="#JLFA" >JLFA</A>(Rc_word, PJLArray); // <A href="JudyL_funcs_3.htm#JudyLFreeArray">JudyLFreeArray()</A>
41
<A href="#JLMU" >JLMU</A>(Rc_word, PJLArray); // <A href="JudyL_funcs_3.htm#JudyLMemUsed">JudyLMemUsed()</A>
42
<A href="#JLF" >JLF</A>( PValue, PJLArray, Index); // <A href="JudyL_funcs_3.htm#JudyLFirst">JudyLFirst()</A>
43
<A href="#JLN" >JLN</A>( PValue, PJLArray, Index); // <A href="JudyL_funcs_3.htm#JudyLNext">JudyLNext()</A>
44
<A href="#JLL" >JLL</A>( PValue, PJLArray, Index); // <A href="JudyL_funcs_3.htm#JudyLLast">JudyLLast()</A>
45
<A href="#JLP" >JLP</A>( PValue, PJLArray, Index); // <A href="JudyL_funcs_3.htm#JudyLPrev">JudyLPrev()</A>
46
<A href="#JLFE">JLFE</A>(Rc_int, PJLArray, Index); // <A href="JudyL_funcs_3.htm#JudyLFirstEmpty">JudyLFirstEmpty()</A>
47
<A href="#JLNE" >JLNE</A>(Rc_int, PJLArray, Index); // <A href="JudyL_funcs_3.htm#JudyLNextEmpty">JudyLNextEmpty()</A>
48
<A href="#JLLE" >JLLE</A>(Rc_int, PJLArray, Index); // <A href="JudyL_funcs_3.htm#JudyLLastEmpty">JudyLLastEmpty()</A>
49
<A href="#JLPE" >JLPE</A>(Rc_int, PJLArray, Index); // <A href="JudyL_funcs_3.htm#JudyLPrevEmpty">JudyLPrevEmpty()</A>
57
A JudyL array is the equivalent of an array of word-sized values.
58
A <B>Value</B> is addressed by an <B>Index</B> (key).
59
The array may be sparse, and the <B>Index</B> may be any word-sized number.
60
Memory to support the array is allocated as index/value pairs are inserted,
61
and released as index/value pairs are deleted. A JudyL array can also be
62
thought of as a mapper, that is "map" a word to another word/pointer.
64
As with an ordinary array, there are no duplicate indexes in a JudyL array.
66
The value may be used as a scalar, or a pointer to a structure or block of data
67
(or even another Judy array).
69
A JudyL array is allocated with a <B>NULL</B> pointer
71
Pvoid_t PJLArray = (Pvoid_t) NULL;
74
Using the macros described here, rather than the
75
<A href="JudyL_funcs_3.htm">JudyL function calls</A>,
76
the default error handling sends a
77
message to the standard error and terminates the program with <I>exit(1);</I>.
78
For other error handling methods, see the
79
<A href="#ERRORS">ERRORS</A> section.
80
<A href="#JLI" >JLI</A>( PValue, PJLArray, Index); // <A href="JudyL_funcs_3.htm#JudyLIns">JudyLIns()</A>
82
Because the macro forms are sometimes faster and have a simpler error
83
handling interface than the equivalent
84
<A href="JudyL_funcs_3.htm">JudyL functions</A>,
85
they are the preferred way of calling the JudyL functions.
88
<DT><A name="JLI"><B>JLI(PValue, PJLArray, Index)</B></A> // <A href="JudyL_funcs_3.htm#JudyLIns">JudyLIns()</A></DT>
90
Insert an <B>Index</B> and <B>Value</B> into the JudyL array <B>PJLArray</B>.
91
If the <B>Index</B> is successfully inserted,
92
the <B>Value</B> is initialized to 0. If the <B>Index</B> was already present,
93
the <B>Value</B> is not modified.
95
Return <B>PValue</B> pointing to <B>Value</B>.
96
Your program can use this pointer to read or modify <B>Value</B> until the next
97
<B>JLI()</B> (insert), <B>JLD()</B> (delete) or <B>JLFA()</B> (freearray)
98
is executed on <B>PJLArray</B>. Examples:
104
Return <B>PValue</B> set to <B>PJERR</B> if a <I>malloc()</I> fail occured.
106
<B>JLI()</B> and <B>JLD()</B> reorganize the JudyL array.
107
Therefore, <B>PValue</B> returned from previous <B>JudyL</B> calls become
108
invalid and must be re-acquired.
110
<DT><A name="JLD"><B>JLD(Rc_int, PJLArray, Index)</B></A> // <A href="JudyL_funcs_3.htm#JudyLDel">JudyLDel()</A></DT>
112
Delete the <B>Index</B>/<B>Value</B> pair from the JudyL array.
114
Return <B>Rc_int</B> set to 1 if successful.
115
Return <B>Rc_int</B> set to 0 if <B>Index</B> was not present.
116
Return <B>Rc_int</B> set to <B>JERR</B> if a <I>malloc()</I> fail occured.
118
<DT><A name="JLG"><B>JLG(PValue, PJLArray, Index)</B></A> // <A href="JudyL_funcs_3.htm#JudyLGet">JudyLGet()</A></DT>
120
Get the pointer <B>PValue</B> associated with <B>Index</B> in the <B>PJLArray</B> Judy array.
122
Return <B>PValue</B> pointing to <B>Value</B>.
123
Return <B>PValue</B> set to <B>NULL</B> if the <B>Index</B> was not present.
124
Return <B>PValue</B> set to <B>PJERR</B> if a <I>malloc()</I> fail occured.
126
<DT><A name="JLC"><B>JLC(Rc_word, PJLArray, Index1, Index2)</B></A> // <A href="JudyL_funcs_3.htm#JudyLCount">JudyLCount()</A></DT>
128
Count the number of indexes present in the JudyL array <B>PJLArray</B> between
129
<B>Index1</B> and <B>Index2</B> (inclusive).
131
Return <B>Rc_word</B> set to the count.
132
A return value of 0 can be valid as a count.
134
To count all indexes present in a JudyL array, use:
136
JLC(Rc_word, PJLArray, 0, -1);
139
<DT><A name="JLBC"><B>JLBC(PValue, PJLArray, Nth, Index)</B></A> // <A href="JudyL_funcs_3.htm#JudyLByCount">JudyLByCount()</A></DT>
141
Locate the <B>Nth</B> index that is present in the JudyL array
142
<B>PJLArray</B> (<B>Nth</B> = 1 returns the first index present).
144
Return <B>PValue</B> pointing to its <B>Value</B> and <B>Index</B>
145
set to the <B>Nth</B> index if found, otherwise return
146
<B>PValue</B> set to <B>NULL</B> (the value of <B>Index</B>
149
<DT><A name="JLFA"><B>JLFA(Rc_word, PJLArray)</B></A> // <A href="JudyL_funcs_3.htm#JudyLFreeArray">JudyLFreeArray()</A></DT>
151
Given a pointer to a JudyL array, free the entire array (much faster
153
<B>JLN()</B>, <B>JLD()</B> loop).
155
Return <B>Rc_word</B> set to the number of bytes freed and <B>PJLArray</B>
158
<DT><A name="JLMU"><B>JLMU(Rc_word, PJLArray)</B></A> // <A href="JudyL_funcs_3.htm#JudyLMemUsed">JudyLMemUsed()</A></DT>
160
Return <B>Rc_word</B> set to the number of bytes of memory <I>malloc()</I>'ed
162
This is a very fast routine, and may be used before and after
163
a <B>JLI()</B> or <B>JLD()</B> call with little performance impact.
165
<DT><B>JudyL Search Functions</B></DT>
167
<B>JLF()</B>, <B>JLN()</B>, <B>JLL()</B>, <B>JLP()</B>
168
allow you to search for indexes
170
You may search inclusively or exclusively,
171
in either forward or reverse directions.
173
<B>Index</B> is returned set to the found index, and
174
<B>PValue</B> is returned set to a pointer to <B>Index</B>'s <B>Value</B>.
176
<B>PValue</B> is returned set to <B>NULL</B>,
177
and <B>Index</B> contains no useful information.
178
<B>PValue</B> must be tested for non-<B>NULL</B> prior
179
to using <B>Index</B>,
180
since a search failure is possible.
182
<B>JLFE()</B>, <B>JLNE()</B>, <B>JLLE()</B>, <B>JLPE()</B> allow you to search for
183
indexes that are not present ("empty") in the array.
184
You may search inclusively or exclusively,
185
in either forward or reverse directions.
186
If successful, <B>Index</B> is returned set to a not present ("empty") index, and
187
<B>Rc_int</B> is returned set to 1.
188
If unsuccessful, <B>Rc_int</B> is returned set to 0, and and <B>Index</B> contains no useful information.
189
<B>Rc_int</B> must be checked prior to using <B>Index</B>, since a search failure is possible.
191
<DT><A name="JLF"><B>JLF(PValue, PJLArray, Index)</B></A> // <A href="JudyL_funcs_3.htm#JudyLFirst">JudyLFirst()</A></DT>
193
Search (inclusive) for the first index present that is equal to or greater than the
195
(Start with <B>Index</B> = 0 to find the first index in the array.)
196
<B>JLF()</B> is typically used to <I>begin</I> a sorted-order scan of
197
the indexes present in a JudyL array.
199
<DT><A name="JLN"><B>JLN(PValue, PJLArray, Index)</B></A> // <A href="JudyL_funcs_3.htm#JudyLNext">JudyLNext()</A></DT>
201
Search (exclusive) for the next index present that is greater than the passed
203
<B>JLN()</B> is typically used to <I>continue</I> a sorted-order scan of
204
the indexes present in a JudyL array, or to locate a "neighbor" of a given index.
206
<DT><A name="JLL"><B>JLL(PValue, PJLArray, Index)</B></A> // <A href="JudyL_funcs_3.htm#JudyLLast">JudyLLast()</A></DT>
208
Search (inclusive) for the last index present that is equal to or less than the passed <B>Index</B>.
209
(Start with <B>Index</B> = -1, that is, all ones, to find the last index in the array.)
210
<B>JLL()</B> is typically used to <I>begin</I> a reverse-sorted-order
211
scan of the indexes present in a JudyL array.
213
<DT><A name="JLP"><B>JLP(PValue, PJLArray, Index)</B></A> // <A href="JudyL_funcs_3.htm#JudyLPrev">JudyLPrev()</A></DT>
215
Search (exclusive) for the previous index present that is less than the
217
<B>JLP()</B> is typically used to <I>continue</I> a reverse-sorted-order
218
scan of the indexes present in a JudyL array, or to locate a "neighbor" of
221
<DT><A name="JLFE"><B>JLFE(Rc_int, PJLArray, Index)</B></A> // <A href="JudyL_funcs_3.htm#JudyLFirstEmpty">JudyLFirstEmpty()</A></DT>
223
Search (inclusive) for the first index absent that is equal to or greater than the passed
225
(Start with <B>Index</B> = 0 to find the first index absent in the array.)
227
<DT><A name="JLNE"><B>JLNE(Rc_int, PJLArray, Index)</B></A> // <A href="JudyL_funcs_3.htm#JudyLNextEmpty">JudyLNextEmpty()</A></DT>
229
Search (exclusive) for the next index absent that is greater than the passed <B>Index</B>.
231
<DT><A name="JLLE"><B>JLLE(Rc_int, PJLArray, Index)</B></A> // <A href="JudyL_funcs_3.htm#JudyLLastEmpty">JudyLLastEmpty()</A></DT>
233
Search (inclusive) for the last index absent that is equal to or less than the passed <B>Index</B>.
234
(Start with <B>Index</B> = -1, that is, all ones, to find the last index absent
237
<DT><A name="JLPE"><B>JLPE(Rc_int, PJLArray, Index)</B></A> // <A href="JudyL_funcs_3.htm#JudyLPrevEmpty">JudyLPrevEmpty()</A></DT>
239
Search (exclusive) for the previous index absent that is less than the passed
244
<DT><B>Multi-dimensional JudyL Arrays</B></DT>
246
Storing a pointer to another JudyL array in a JudyL array's <B>Value</B>
247
is a simple way to support dynamic multi-dimensional arrays.
248
These arrays (or trees) built using JudyL arrays are very fast and
249
memory efficient. (In fact, that is how JudySL and JudyHS are implemented).
250
An arbitrary number of dimensions can be realized this way.
251
To terminate the number of dimensions (or tree), the <B>Value</B> pointer is
252
marked to <B>NOT</B> point to another Judy array. A <B>JLAP_INVALID</B> flag is
253
used in the least significant bit(s) of the pointer.
254
After the flag <B>JLAP_INVALID</B> is removed, it is used as a pointer to the users data.
255
The <B>Judy.h</B> header file defines <B>JLAP_INVALID</B>.
256
See code fragment below.
258
Note: The current version of <B>Judy.h</B> changed this flag from 0x4 to 0x1
259
to allow for a <I>malloc()</I> that does not deliver memory on an 8 byte
260
aligned boundry (such as old versions of valgrind).
262
The following example code segment can be used to determine whether or
263
not a pointer points to another JudyL:
266
PValue = (PWord_t)PMultiDimArray;
268
for (Dim = 0; ;Dim++)
270
if (PValue == (PWord_t)NULL) goto IndexNotFound;
272
/* Advance to next dimension in array */
273
JLG(PValue, (Pvoid_t)*PValue, Index[Dim]);
275
/* Check if pointer to user buffer: */
276
if (*PValue & JLAP_INVALID)) break;
278
UPointer = (UPointer_t) (*PValue & ~JLAP_INVALID); // mask and cast.
279
printf("User object pointer is 0x%lx\n", (Word_t) UPointer);
283
Note: This works because <I>malloc()</I> guarantees to return a pointer
284
with the least bit(s) == 0x0.
285
You must remove <B>JLAP_INVALID</B> before using the pointer.
289
<DT><A name="JLERR"><B>ERRORS:</B> See: </A><A href="Judy_3.htm#ERRORS">Judy_3.htm#ERRORS</A></DT>
293
<DT><B>EXAMPLE</B></DT>
295
Read a series of index/value pairs from the standard input, store
296
in a JudyL array, and then print out in sorted order.
299
#include <stdio.h>
300
#include <Judy.h>
302
Word_t Index; // array index
303
Word_t Value; // array element value
304
Word_t * PValue; // pointer to array element value
305
int Rc_int; // return code
307
Pvoid_t PJLArray = (Pvoid_t) NULL; // initialize JudyL array
309
while (scanf("%lu %lu", &Index, &Value))
311
JLI(PValue, PJLArray, Index);
312
If (PValue == PJERR) goto process_malloc_failure;
313
*PValue = Value; // store new value
315
// Next, visit all the stored indexes in sorted order, first ascending,
316
// then descending, and delete each index during the descending pass.
319
JLF(PValue, PJLArray, Index);
320
while (PValue != NULL)
322
printf("%lu %lu\n", Index, *PValue));
323
JLN(PValue, PJLArray, Index);
327
JLL(PValue, PJLArray, Index);
328
while (PValue != NULL)
330
printf("%lu %lu\n", Index, *PValue));
332
JLD(Rc_int, PJLArray, Index);
333
if (Rc_int == JERR) goto process_malloc_failure;
335
JLP(PValue, PJLArray, Index);
340
<DT><B>AUTHOR</B></DT>
342
Judy was invented by Doug Baskins and implemented by Hewlett-Packard.
345
<DT><B>SEE ALSO</B></DT>
347
<A href="Judy_3.htm">Judy(3)</A>,
348
<A href="Judy1_3.htm">Judy1(3)</A>,
349
<A href="JudySL_3.htm">JudySL(3)</A>,
350
<A href="JudyHS_3.htm">JudyHS(3)</A>,
354
<A href="http://judy.sourceforge.net">
355
http://judy.sourceforge.net</A>,
356
for more information and Application Notes.
added
removed
doc/ext/JudyL_3.htm
