chiark / gitweb /
debugging for thing that crashed
[innduct.git] / lib / tst.c
1 /*  $Id: tst.c 6083 2002-12-27 07:24:36Z rra $
2 **
3 **  Ternary search trie implementation.
4 **
5 **  A ternary search trie stores key/value pairs where the key is a
6 **  nul-terminated string and the value is an arbitrary pointer.  It uses a
7 **  data structure designed for fast lookups, where each level of the trie
8 **  represents a character in the string being searched for.
9 **
10 **  This implementation is based on the implementation by Peter A. Friend
11 **  (version 1.3), but has been assimilated into INN and modified to use INN
12 **  formatting conventions.  If new versions are released, examine the
13 **  differences between that version and version 1.3 (which was checked into
14 **  INN as individual files in case it's no longer available) and then apply
15 **  the changes to this file.
16 **
17 **  Copyright (c) 2002, Peter A. Friend
18 **  All rights reserved.
19 **
20 **  Redistribution and use in source and binary forms, with or without
21 **  modification, are permitted provided that the following conditions are
22 **  met:
23 **
24 **  Redistributions of source code must retain the above copyright notice,
25 **  this list of conditions and the following disclaimer.
26 **
27 **  Redistributions in binary form must reproduce the above copyright notice,
28 **  this list of conditions and the following disclaimer in the documentation
29 **  and/or other materials provided with the distribution.
30 **
31 **  Neither the name of Peter A. Friend nor the names of his contributors may
32 **  be used to endorse or promote products derived from this software without
33 **  specific prior written permission.
34 **
35 **  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
36 **  IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
37 **  THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
38 **  PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
39 **  CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
40 **  EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
41 **  PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
42 **  PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
43 **  LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
44 **  NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
45 **  SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
46 */
47
48 #include "config.h"
49 #include "clibrary.h"
50
51 #include "inn/tst.h"
52 #include "libinn.h"
53
54
55 /* A single node in the ternary search trie.  Stores a character, which is
56    part of the string formed by walking the tree from its root down to the
57    node, and left, right, and middle pointers to child nodes.  If value is
58    non-zero (not a nul), middle is the pointer to follow if the desired
59    string's character matches value.  left is used if it's less than value and
60    right is used if it's greater than value.  If value is zero, this is a
61    terminal node, and middle holds a pointer to the data associated with the
62    string that ends at this point. */
63 struct node {
64     unsigned char value;
65     struct node *left;
66     struct node *middle;
67     struct node *right;
68 };
69
70 /* The search trie structure.  node_line_width is the number of nodes that are
71    allocated at a time, and node_lines holds a linked list of groups of nodes.
72    The free_list is a linked list (through the middle pointers) of available
73    nodes to use, and head holds pointers to the first nodes for each possible
74    first letter of the string. */
75 struct tst {
76     int node_line_width;
77     struct node_lines *node_lines;
78     struct node *free_list;
79     struct node *head[256];
80 };
81
82 /* A simple linked list structure used to hold all the groups of nodes. */
83 struct node_lines {
84     struct node *node_line;
85     struct node_lines *next;
86 };
87
88
89 /*
90 **  Given a node and a character, decide whether a new node for that character
91 **  should be placed as the left child of that node.  (If false, it should be
92 **  placed as the right child.)
93 */
94 #define LEFTP(n, c) (((n)->value == 0) ? ((c) < 64) : ((c) < (n)->value))
95
96
97 /*
98 **  Allocate new nodes for the free list, called when the free list is empty.
99 */
100 static void
101 tst_grow_node_free_list(struct tst *tst)
102 {
103     struct node *current_node;
104     struct node_lines *new_line;
105     int i;
106
107     new_line = xmalloc(sizeof(struct node_lines));
108     new_line->node_line = xcalloc(tst->node_line_width, sizeof(struct node));
109     new_line->next = tst->node_lines;
110     tst->node_lines = new_line;
111
112     current_node = tst->node_lines->node_line;
113     tst->free_list = current_node;
114     for (i = 1; i < tst->node_line_width; i++) {
115         current_node->middle = &(tst->node_lines->node_line[i]);
116         current_node = current_node->middle;
117     }
118     current_node->middle = NULL;
119 }
120
121
122 /*
123 **  Grab a node from the free list and initialize it with the given value.
124 */
125 static struct node *
126 tst_get_free_node(struct tst *tst, unsigned char value)
127 {
128     struct node *free_node;
129
130     if (tst->free_list == NULL)
131         tst_grow_node_free_list(tst);
132     free_node = tst->free_list;
133     tst->free_list = tst->free_list->middle;
134     free_node->middle = NULL;
135     free_node->value = value;
136     return free_node;
137 }
138
139
140 /*
141 **  tst_init allocates memory for members of struct tst, and allocates the
142 **  first node_line_width nodes.  The value for width must be chosen very
143 **  carefully.  One node is required for every character in the tree.  If you
144 **  choose a value that is too small, your application will spend too much
145 **  time calling malloc and your node space will be too spread out.  Too large
146 **  a value is just a waste of space.
147 */
148 struct tst *
149 tst_init(int width)
150 {
151     struct tst *tst;
152
153     tst = xcalloc(1, sizeof(struct tst));
154     tst->node_lines = NULL;
155     tst->node_line_width = width;
156     tst_grow_node_free_list(tst);
157     return tst;
158 }
159
160
161 /*
162 **  tst_insert inserts the string key into the tree.  Behavior when a
163 **  duplicate key is inserted is controlled by option.  If key is already in
164 **  the tree then TST_DUPLICATE_KEY is returned, and the data pointer for the
165 **  existing key is placed in exist_ptr.  If option is set to TST_REPLACE then
166 **  the existing data pointer for the existing key is replaced by data.  The
167 **  old data pointer will still be placed in exist_ptr.
168 **
169 **  If a duplicate key is encountered and option is not set to TST_REPLACE
170 **  then TST_DUPLICATE_KEY is returned.  If key is zero-length, then
171 **  TST_NULL_KEY is returned.  A successful insert or replace returns TST_OK.
172 **
173 **  The data argument may not be NULL; if it is, TST_NULL_DATA is returned.
174 **  If you just want a simple existence tree, use the tst pointer as the data
175 **  pointer.
176 */
177 int
178 tst_insert(struct tst *tst, const unsigned char *key, void *data, int option,
179            void **exist_ptr)
180 {
181     struct node *current_node = NULL;
182     struct node **root_node = NULL;
183     int key_index;
184
185     if (data == NULL)
186         return TST_NULL_DATA;
187
188     if (key == NULL || *key == '\0')
189         return TST_NULL_KEY;
190
191     key_index = 1;
192     if (tst->head[*key] == NULL)
193         root_node = &tst->head[*key];
194     else
195         current_node = tst->head[*key];
196
197     while (root_node == NULL) {
198         if (key[key_index] == current_node->value) {
199             if (key[key_index] == '\0') {
200                 if (exist_ptr != NULL)
201                     *exist_ptr = current_node->middle;
202                 if (option == TST_REPLACE) {
203                     current_node->middle = data;
204                     return TST_OK;
205                 } else
206                     return TST_DUPLICATE_KEY;
207             }
208             if (current_node->middle == NULL)
209                 root_node = &current_node->middle;
210             else {
211                 current_node = current_node->middle;
212                 key_index++;
213             }
214         } else if (LEFTP(current_node, key[key_index])) {
215             if (current_node->left == NULL)
216                 root_node = &current_node->left;
217             else
218                 current_node = current_node->left;
219         } else {
220             if (current_node->right == NULL)
221                 root_node = &current_node->right;
222             else
223                 current_node = current_node->right;
224         }
225
226     }
227
228     *root_node = tst_get_free_node(tst, key[key_index]);
229     current_node = *root_node;
230
231     while (key[key_index] != '\0') {
232         key_index++;
233         current_node->middle = tst_get_free_node(tst, key[key_index]);
234         current_node = current_node->middle;
235     }
236
237     current_node->middle = data;
238     return TST_OK;
239 }
240
241
242 /*
243 **  tst_search finds the string key in the tree if it exists and returns the
244 **  data pointer associated with that key or NULL if it's not found.
245 */
246 void *
247 tst_search(struct tst *tst, const unsigned char *key)
248 {
249     struct node *current_node;
250     int key_index;
251
252     if (key == NULL || *key == '\0')
253         return NULL;
254
255     if (tst->head[*key] == NULL)
256         return NULL;
257
258     current_node = tst->head[*key];
259     key_index = 1;
260     while (current_node != NULL) {
261         if (key[key_index] == current_node->value) {
262             if (current_node->value == '\0')
263                 return current_node->middle;
264             else {
265                 current_node = current_node->middle;
266                 key_index++;
267                 continue;
268             }
269         } else if (LEFTP(current_node, key[key_index]))
270             current_node = current_node->left;
271         else
272             current_node = current_node->right;
273     }
274     return NULL;
275 }
276
277
278 /*
279 **  tst_delete deletes the string key from the tree if it exists and returns
280 **  the data pointer assocaited with that key, or NULL if it wasn't found.
281 */
282 void *
283 tst_delete(struct tst *tst, const unsigned char *key)
284 {
285     struct node *current_node;
286     struct node *current_node_parent;
287     struct node *last_branch;
288     struct node *last_branch_parent;
289     struct node *next_node;
290     struct node *last_branch_replacement;
291     struct node *last_branch_dangling_child;
292     int key_index;
293
294     if (key == NULL || *key == '\0')
295         return NULL;
296
297     if (tst->head[*key] == NULL)
298         return NULL;
299
300     last_branch = NULL;
301     last_branch_parent = NULL;
302     current_node = tst->head[*key];
303     current_node_parent = NULL;
304     key_index = 1;
305     while (current_node != NULL) {
306         if (key[key_index] == current_node->value) {
307             if (current_node->left != NULL || current_node->right != NULL) {
308                 last_branch = current_node;
309                 last_branch_parent = current_node_parent;
310             }
311             if (key[key_index] == '\0')
312                 break;
313             else {
314                 current_node_parent = current_node;
315                 current_node = current_node->middle;
316                 key_index++;
317             }
318         } else if (LEFTP(current_node, key[key_index])) {
319             last_branch_parent = current_node;
320             current_node_parent = current_node;
321             current_node = current_node->left;
322             last_branch = current_node;
323         } else {
324             last_branch_parent = current_node;
325             current_node_parent = current_node;
326             current_node = current_node->right;
327             last_branch = current_node;
328         }
329     }
330     if (current_node == NULL)
331         return NULL;
332
333     if (last_branch == NULL) {
334         next_node = tst->head[*key];
335         tst->head[*key] = NULL;
336     } else if (last_branch->left == NULL && last_branch->right == NULL) {
337         if (last_branch_parent->left == last_branch)
338             last_branch_parent->left = NULL;
339         else
340             last_branch_parent->right = NULL;
341         next_node = last_branch;
342     } else {
343         if (last_branch->left != NULL && last_branch->right != NULL) {
344             last_branch_replacement = last_branch->right;
345             last_branch_dangling_child = last_branch->left;
346         } else if (last_branch->right != NULL) {
347             last_branch_replacement = last_branch->right;
348             last_branch_dangling_child = NULL;
349         } else {
350             last_branch_replacement = last_branch->left;
351             last_branch_dangling_child = NULL;
352         }
353
354         if (last_branch_parent == NULL)
355             tst->head[*key] = last_branch_replacement;
356         else {
357             if (last_branch_parent->left == last_branch)
358                 last_branch_parent->left = last_branch_replacement;
359             else if (last_branch_parent->right == last_branch)
360                 last_branch_parent->right = last_branch_replacement;
361             else
362                 last_branch_parent->middle = last_branch_replacement;
363         }
364
365         if (last_branch_dangling_child != NULL) {
366             current_node = last_branch_replacement;
367             while (current_node->left != NULL)
368                 current_node = current_node->left;
369             current_node->left = last_branch_dangling_child;
370         }
371
372         next_node = last_branch;
373     }
374
375     do {
376         current_node = next_node;
377         next_node = current_node->middle;
378
379         current_node->left = NULL;
380         current_node->right = NULL;
381         current_node->middle = tst->free_list;
382         tst->free_list = current_node;
383     } while (current_node->value != 0);
384
385     return next_node;
386 }
387
388
389 /*
390 **  tst_cleanup frees all memory allocated to nodes, internal structures,
391 **  as well as tst itself.
392 */
393 void
394 tst_cleanup(struct tst *tst)
395 {
396     struct node_lines *current_line;
397     struct node_lines *next_line;
398
399     next_line = tst->node_lines;
400     do {
401         current_line = next_line;
402         next_line = current_line->next;
403         free(current_line->node_line);
404         free(current_line);
405     } while (next_line != NULL);
406
407     free(tst);
408 }