1JudySL(3) Library Functions Manual JudySL(3)
2
6 JudySL macros - C library for creating and accessing a dynamic array,
7 using a null-terminated string as an Index (associative array)
8
10 cc [flags] sourcefiles -lJudy
11 #include <Judy.h>
13 #define MAXLINELEN 1000000 // define maximum string length
15 Word_t * PValue; // JudySL array element
17 uint8_t Index[MAXLINELEN]; // string
18 int Rc_int; // return value
19 Word_t Rc_word; // full word return value
20 Pvoid_t PJSLArray = (Pvoid_t) NULL; // initialize JudySL array
22 JSLI( PValue, PJSLArray, Index); // JudySLIns()
24 JSLD( Rc_int, PJSLArray, Index); // JudySLDel()
25 JSLG( PValue, PJSLArray, Index); // JudySLGet()
26 JSLFA(Rc_word, PJSLArray); // JudySLFreeArray()
27 JSLF( PValue, PJSLArray, Index); // JudySLFirst()
28 JSLN( PValue, PJSLArray, Index); // JudySLNext()
29 JSLL( PValue, PJSLArray, Index); // JudySLLast()
30 JSLP( PValue, PJSLArray, Index); // JudySLPrev()
31
33 A JudySL array is the equivalent of a sorted set of strings, each asso‐
34 ciated with a Value (word). A Value is addressed by an Index (key),
35 which is a null-terminated character string of any length. Memory to
36 support the array is allocated as index/value pairs are inserted, and
37 released as index/value pairs are deleted. This is a form of associa‐
38 tive array, where array elements are also sorted lexicographically
39 (case-sensitive) by indexes. This could be thought of as
40 void * JudySLArray["Toto, I don't think we're in Kansas any more"];
42 A JudySL array is allocated with a NULL pointer
44 Pvoid_t PJSLArray = (Pvoid_t) NULL;
46 As with an ordinary array, there are no duplicate indexes (strings) in
47 a JudySL array.
48 Using the macros described here, rather than the JudySL function calls,
50 the default error handling sends a message to the standard error and
51 terminates the program with exit(1).
52
54 Insert an Index string and Value in the JudySL array PJSLArray. If the
55 Index is successfully inserted, the Value is initialized to 0. If the
56 Index was already present, the Value is not modified.
57 Return PValue pointing to Index's Value. Your program must use this
59 pointer to modify the Value, for example:
60 *PValue = 1234;
62 Note: JSLI() and JSLD reorganize the JudySL array. Therefore, pointers
64 returned from previous JudySL calls become invalid and must be reac‐
65 quired.
66
68 Delete the specified Index/Value pair (array element) from the JudySL
69 array.
70 Return Rc_int set to 1 if successful. array and it was previously
72 inserted. Return Rc_int set to 0 if Index was not present.
73
75 Get the pointer to Index's Value.
76 Return PValue pointing to Index's Value. Return PValue set to NULL if
78 the Index was not present.
79
81 Given a pointer to a JudySL array (PJSLArray), free the entire array
82 (much faster than using a JSLN(), JSLD() loop.)
83 Return Rc_word set to the number of bytes freed and PJSLArray set to
85 NULL.
86
88 The JudySL search functions allow you to search for indexes in the
89 array. You may search inclusively or exclusively, in either forward or
90 reverse directions.
91 If successful, Index is returned set to the found index, and PValue is
93 returned set to a pointer to Index's Value. If unsuccessful, PValue is
94 returned set to NULL, and Index contains no useful information. PValue
95 must be tested for non-NULL prior to using Index, since a search fail‐
96 ure is possible.
97 Note: To accomodate all possible returns, the Index buffer must be at
99 least as large as the largest string stored in the array.
100
102 Search (inclusive) for the first index present that is equal to or
103 greater than the passed Index string. (Start with a null string to
104 find the first index in the array.) JSLF() is typically used to begin
105 a sorted-order scan of the valid indexes in a JudySL array.
106 uint8_t Index[MAXLINELEN];
108 strcpy (Index, "");
109 JSLF(PValue, PJSLArray, Index);
110
112 Search (exclusive) for the next index present that is greater than the
113 passed Index string. JSLN() is typically used to continue a sorted-
114 order scan of the valid indexes in a JudySL array, or to locate a
115 "neighbor" of a given index.
116
118 Search (inclusive) for the last index present that is equal to or less
119 than the passed Index string. (Start with a maximum-valued string to
120 look up the last index in the array, such as a max-length string of
121 0xff bytes.) JSLL() is typically used to begin a reverse-sorted-order
122 scan of the valid indexes in a JudySL array.
123
125 Search (exclusive) for the previous index present that is less than the
126 passed Index string. JSLP() is typically used to continue a reverse-
127 sorted-order scan of the valid indexes in a JudySL array, or to locate
128 a "neighbor" of a given index.
129
132 #include <stdio.h>
133 #include <Judy.h>
134 #define MAXLINE 1000000 // max string (line) length
136 uint8_t Index[MAXLINE]; // string to insert
138 int // Usage: JudySort < file_to_sort
140 main()
141 {
142 Pvoid_t PJArray = (PWord_t)NULL; // Judy array.
143 PWord_t PValue; // Judy array element.
144 Word_t Bytes; // size of JudySL array.
145 while (fgets(Index, MAXLINE, stdin) != (char *)NULL)
147 {
148 JSLI(PValue, PJArray, Index); // store string into array
149 if (PValue == PJERR) // if out of memory?
150 { // so do something
151 printf("Malloc failed -- get more ram\n");
152 exit(1);
153 }
154 ++(*PValue); // count instances of string
155 }
156 Index[0] = '\0'; // start with smallest string.
157 JSLF(PValue, PJArray, Index); // get first string
158 while (PValue != NULL)
159 {
160 while ((*PValue)--) // print duplicates
161 printf("%s", Index);
162 JSLN(PValue, PJArray, Index); // get next string
163 }
164 JSLFA(Bytes, PJArray); // free array
165 fprintf(stderr, "The JudySL array used %lu bytes of memory\n", Bytes);
167 return (0);
168 }
169
171 Judy was invented by Doug Baskins and implemented by Hewlett-Packard.
172
174 Judy(3), Judy1(3), JudyL(3), JudyHS(3),
175 malloc(),
176 the Judy website, http://judy.sourceforge.net, for further information
177 and Application Notes.
178 JudySL(3)