3
<!-- @(#) $Revision: 4.43 $ $Source: /cvsroot/judy/doc/ext/JudyHS_3.htm,v $ --->
4
<TITLE>JudyHS(3)</TITLE>
7
<TABLE border=0 width="100%"><TR>
8
<TD width="40%" align="left">JudyHS(3)</TD>
9
<TD width="10%" align="center"> </TD>
10
<TD width="40%" align="right">JudyHS(3)</TD>
16
JudyHS macros - C library for creating and accessing a dynamic array,
17
using an array-of-bytes of <B>Length</B> as an <B>Index</B> and a word
21
<DT><B>SYNOPSIS</B></DT>
24
cc [flags] <I>sourcefiles</I> -lJudy
26
#include <Judy.h>
28
Word_t * PValue; // JudyHS array element
29
int Rc_int; // return flag
30
Word_t Rc_word; // full word return value
31
Pvoid_t PJHSArray = (Pvoid_t) NULL; // initialize JudyHS array
32
uint8_t * Index; // array-of-bytes pointer
33
Word_t Length; // number of bytes in Index
35
<A href="#JHSI" >JHSI</A>( PValue, PJHSArray, Index, Length); // <A href="JudyHS_funcs_3.htm#JudyHSIns">JudyHSIns()</A>
36
<A href="#JHSD" >JHSD</A>( Rc_int, PJHSArray, Index, Length); // <A href="JudyHS_funcs_3.htm#JudyHSDel">JudyHSDel()</A>
37
<A href="#JHSG" >JHSG</A>( PValue, PJHSArray, Index, Length); // <A href="JudyHS_funcs_3.htm#JudyHSGet">JudyHSGet()</A>
38
<A href="#JHSFA">JHSFA</A>(Rc_word, PJHSArray); // <A href="JudyHS_funcs_3.htm#JudyHSFreeArray">JudyHSFreeArray()</A>
41
<DT><B>DESCRIPTION</B></DT>
43
A JudyHS array is the equivalent of an array of word-sized
44
value/pointers. An <B>Index</B> is a pointer to an array-of-bytes of
45
specified length: <B>Length</B>. Rather than using a null terminated
46
string, this difference from <A href="JudySL_3.htm">JudySL(3)</A>
47
allows strings to contain all bits (specifically the null character).
48
This new addition (May 2004) to Judy arrays is a hybird using the best
49
capabilities of hashing and Judy methods. <B>JudyHS</B> does not have a
50
poor performance case where knowledge of the hash algorithm can be used
51
to degrade the performance.
53
Since JudyHS is based on a hash method, <B>Indexes</B> are not stored in
54
any particular order. Therefore the JudyHSFirst(), JudyHSNext(),
55
JudyHSPrev() and JudyHSLast() neighbor search functions are not
56
practical. The <B>Length</B> of each array-of-bytes can be from 0 to
57
the limits of <I>malloc()</I> (about 2GB).
59
The hallmark of <B>JudyHS</B> is speed with scalability, but memory
60
efficiency is excellent. The speed is very competitive with the best
61
hashing methods. The memory efficiency is similar to a linked list of
62
the same <B>Indexes</B> and <B>Values</B>. <B>JudyHS</B> is designed to
63
scale from 0 to billions of <B>Indexes</B>.
65
A JudyHS array is allocated with a <B>NULL</B> pointer
67
Pvoid_t PJHSArray = (Pvoid_t) NULL;
70
Because the macro forms of the API have a simpler error handling
71
interface than the equivalent
72
<A href="JudyHS_funcs_3.htm">functions</A>,
73
they are the preferred way to use JudyHS.
76
<A name="JHSI"><B>JHSI(PValue, PJHSArray, Index, Length)</B></A> // <A href="JudyHS_funcs_3.htm#JudyHSIns">JudyHSIns()</A></DT>
78
Given a pointer to a JudyHS array (<B>PJHSArray</B>), insert an
79
<B>Index</B> string of length: <B>Length</B> and a <B>Value</B> into the
80
JudyHS array: <B>PJHSArray</B>. If the <B>Index</B> is successfully
81
inserted, the <B>Value</B> is initialized to 0. If the <B>Index</B> was
82
already present, the <B>Value</B> is not modified.
84
Return <B>PValue</B> pointing to <B>Value</B>. Your program should use
85
this pointer to read or modify the <B>Value</B>, for example:
92
<B>JHSI()</B> and <B>JHSD</B> can reorganize the JudyHS array.
93
Therefore, pointers returned from previous <B>JudyHS</B> calls become
94
invalid and must be re-acquired (using <B>JHSG()</B>).
96
<DT><A name="JHSD"><B>JHSD(Rc_int, PJHSArray, Index, Length)</B></A> // <A href="JudyHS_funcs_3.htm#JudyHSDel">JudyHSDel()</A></DT>
98
Given a pointer to a JudyHS array (<B>PJHSArray</B>), delete the
99
specified <B>Index</B> along with the <B>Value</B> from the JudyHS
102
Return <B>Rc_int</B> set to 1 if successfully removed from the array.
103
Return <B>Rc_int</B> set to 0 if <B>Index</B> was not present.
105
<DT><A name="JHSG"><B>JHSG(PValue, PJHSArray, Index, Length)</B></A> // <A href="JudyHS_funcs_3.htm#JudyHSGet">JudyHSGet()</A></DT>
107
Given a pointer to a JudyHS array (<B>PJHSArray</B>),
108
find <B>Value</B> associated with <B>Index</B>.
110
Return <B>PValue</B> pointing to <B>Index</B>'s <B>Value</B>.
111
Return <B>PValue</B> set to <B>NULL</B> if the <B>Index</B> was not present.
113
<DT><A name="JHSFA"><B>JHSFA(Rc_word, PJHSArray)</B></A> // <A href="JudyHS_funcs_3.htm#JudyHSFreeArray">JudyHSFreeArray()</A></DT>
115
Given a pointer to a JudyHS array (<B>PJHSArray</B>), free the entire array.
117
Return <B>Rc_word</B> set to the number of bytes freed and <B>PJHSArray</B> set to NULL.
120
<DT><A name="ERRORS"><B>ERRORS:</B> See: </A><A href="Judy_3.htm#ERRORS">Judy_3.htm#ERRORS</A></DT>
123
<DT><B>EXAMPLES</B></DT>
125
Show how to program with the JudyHS macros. This program will print
126
duplicate lines and their line number from <I>stdin</I>.
128
#include <unistd.h>
129
#include <stdio.h>
130
#include <string.h>
131
#include <Judy.h>
134
// cc -O PrintDupLines.c -lJudy -o PrintDupLines
136
#define MAXLINE 1000000 /* max fgets length of line */
137
uint8_t Index[MAXLINE]; // string to check
139
int // Usage: PrintDupLines < file
142
Pvoid_t PJArray = (PWord_t)NULL; // Judy array.
143
PWord_t PValue; // Judy array element pointer.
144
Word_t Bytes; // size of JudyHS array.
145
Word_t LineNumb = 0; // current line number
146
Word_t Dups = 0; // number of duplicate lines
148
while (fgets(Index, MAXLINE, stdin) != (char *)NULL)
150
LineNumb++; // line number
152
// store string into array
153
JHSI(PValue, PJArray, Index, strlen(Index));
154
if (PValue == PJERR) // See ERRORS section
156
fprintf(stderr, "Out of memory -- exit\n");
159
if (*PValue == 0) // check if duplicate
162
printf("Duplicate lines %lu:%lu:%s", *PValue, LineNumb, Index);
166
*PValue = LineNumb; // store Line number
169
printf("%lu Duplicates, free JudyHS array of %lu Lines\n",
170
Dups, LineNumb - Dups);
171
JHSFA(Bytes, PJArray); // free JudyHS array
172
printf("JudyHSFreeArray() free'ed %lu bytes of memory\n", Bytes);
178
<DT><B>AUTHOR</B></DT>
180
JudyHS was invented and implemented by Doug Baskins after retiring from Hewlett-Packard.
183
<DT><B>SEE ALSO</B></DT>
185
<A href="Judy_3.htm">Judy(3)</A>,
186
<A href="Judy1_3.htm">Judy1(3)</A>,
187
<A href="JudyL_3.htm">JudyL(3)</A>,
188
<A href="JudySL_3.htm">JudySL(3)</A>,
193
<A href="http://judy.sourceforge.net">
194
http://judy.sourceforge.net</A>,
195
for further information and Application Notes.
added
removed
doc/ext/JudyHS_3.htm
