]>
Commit | Line | Data |
---|---|---|
eb5d44eb | 1 | /* |
2 | * Dictionary Abstract Data Type | |
3 | * Copyright (C) 1997 Kaz Kylheku <kaz@ashi.footprints.net> | |
4 | * | |
5 | * Free Software License: | |
6 | * | |
7 | * All rights are reserved by the author, with the following exceptions: | |
8 | * Permission is granted to freely reproduce and distribute this software, | |
9 | * possibly in exchange for a fee, provided that this copyright notice appears | |
10 | * intact. Permission is also granted to adapt this software to produce | |
11 | * derivative works, as long as the modified versions carry this copyright | |
12 | * notice and additional notices stating that the work has been modified. | |
13 | * This source code may be translated into executable form and incorporated | |
14 | * into proprietary software; there is no requirement for such software to | |
15 | * contain a copyright notice related to this source. | |
16 | * | |
238497fc PJ |
17 | * $Id$ |
18 | * $Name$ | |
eb5d44eb | 19 | */ |
20 | ||
21 | #include <stdlib.h> | |
22 | #include <stddef.h> | |
238497fc | 23 | #include "zebra.h" |
cee3df1e | 24 | #include "zassert.h" |
eb5d44eb | 25 | #define DICT_IMPLEMENTATION |
26 | #include "dict.h" | |
27 | ||
28 | #ifdef KAZLIB_RCSID | |
ffe543af | 29 | static const char rcsid[] = "Id: dict.c,v 1.40.2.7 2000/11/13 01:36:44 kaz"; |
eb5d44eb | 30 | #endif |
31 | ||
32 | /* | |
33 | * These macros provide short convenient names for structure members, | |
34 | * which are embellished with dict_ prefixes so that they are | |
35 | * properly confined to the documented namespace. It's legal for a | |
36 | * program which uses dict to define, for instance, a macro called ``parent''. | |
37 | * Such a macro would interfere with the dnode_t struct definition. | |
38 | * In general, highly portable and reusable C modules which expose their | |
39 | * structures need to confine structure member names to well-defined spaces. | |
40 | * The resulting identifiers aren't necessarily convenient to use, nor | |
41 | * readable, in the implementation, however! | |
42 | */ | |
43 | ||
44 | #define left dict_left | |
45 | #define right dict_right | |
46 | #define parent dict_parent | |
47 | #define color dict_color | |
48 | #define key dict_key | |
49 | #define data dict_data | |
50 | ||
51 | #define nilnode dict_nilnode | |
52 | #define nodecount dict_nodecount | |
53 | #define maxcount dict_maxcount | |
54 | #define compare dict_compare | |
55 | #define allocnode dict_allocnode | |
56 | #define freenode dict_freenode | |
57 | #define context dict_context | |
58 | #define dupes dict_dupes | |
59 | ||
60 | #define dictptr dict_dictptr | |
61 | ||
62 | #define dict_root(D) ((D)->nilnode.left) | |
63 | #define dict_nil(D) (&(D)->nilnode) | |
64 | #define DICT_DEPTH_MAX 64 | |
65 | ||
ffe543af | 66 | static dnode_t *dnode_alloc(void *context); |
67 | static void dnode_free(dnode_t *node, void *context); | |
eb5d44eb | 68 | |
69 | /* | |
70 | * Perform a ``left rotation'' adjustment on the tree. The given node P and | |
71 | * its right child C are rearranged so that the P instead becomes the left | |
72 | * child of C. The left subtree of C is inherited as the new right subtree | |
73 | * for P. The ordering of the keys within the tree is thus preserved. | |
74 | */ | |
75 | ||
ffe543af | 76 | static void rotate_left(dnode_t *upper) |
eb5d44eb | 77 | { |
ffe543af | 78 | dnode_t *lower, *lowleft, *upparent; |
eb5d44eb | 79 | |
ffe543af | 80 | lower = upper->right; |
81 | upper->right = lowleft = lower->left; | |
82 | lowleft->parent = upper; | |
eb5d44eb | 83 | |
ffe543af | 84 | lower->parent = upparent = upper->parent; |
eb5d44eb | 85 | |
ffe543af | 86 | /* don't need to check for root node here because root->parent is |
87 | the sentinel nil node, and root->parent->left points back to root */ | |
eb5d44eb | 88 | |
ffe543af | 89 | if (upper == upparent->left) { |
90 | upparent->left = lower; | |
91 | } else { | |
92 | assert (upper == upparent->right); | |
93 | upparent->right = lower; | |
eb5d44eb | 94 | } |
95 | ||
ffe543af | 96 | lower->left = upper; |
97 | upper->parent = lower; | |
eb5d44eb | 98 | } |
99 | ||
100 | /* | |
101 | * This operation is the ``mirror'' image of rotate_left. It is | |
102 | * the same procedure, but with left and right interchanged. | |
103 | */ | |
104 | ||
ffe543af | 105 | static void rotate_right(dnode_t *upper) |
eb5d44eb | 106 | { |
ffe543af | 107 | dnode_t *lower, *lowright, *upparent; |
eb5d44eb | 108 | |
ffe543af | 109 | lower = upper->left; |
110 | upper->left = lowright = lower->right; | |
111 | lowright->parent = upper; | |
eb5d44eb | 112 | |
ffe543af | 113 | lower->parent = upparent = upper->parent; |
eb5d44eb | 114 | |
ffe543af | 115 | if (upper == upparent->right) { |
116 | upparent->right = lower; | |
117 | } else { | |
118 | assert (upper == upparent->left); | |
119 | upparent->left = lower; | |
eb5d44eb | 120 | } |
121 | ||
ffe543af | 122 | lower->right = upper; |
123 | upper->parent = lower; | |
eb5d44eb | 124 | } |
125 | ||
126 | /* | |
127 | * Do a postorder traversal of the tree rooted at the specified | |
128 | * node and free everything under it. Used by dict_free(). | |
129 | */ | |
130 | ||
ffe543af | 131 | static void free_nodes(dict_t *dict, dnode_t *node, dnode_t *nil) |
eb5d44eb | 132 | { |
ffe543af | 133 | if (node == nil) |
134 | return; | |
135 | free_nodes(dict, node->left, nil); | |
136 | free_nodes(dict, node->right, nil); | |
137 | dict->freenode(node, dict->context); | |
eb5d44eb | 138 | } |
139 | ||
140 | /* | |
141 | * This procedure performs a verification that the given subtree is a binary | |
142 | * search tree. It performs an inorder traversal of the tree using the | |
143 | * dict_next() successor function, verifying that the key of each node is | |
144 | * strictly lower than that of its successor, if duplicates are not allowed, | |
145 | * or lower or equal if duplicates are allowed. This function is used for | |
146 | * debugging purposes. | |
147 | */ | |
148 | ||
ffe543af | 149 | static int verify_bintree(dict_t *dict) |
eb5d44eb | 150 | { |
ffe543af | 151 | dnode_t *first, *next; |
eb5d44eb | 152 | |
ffe543af | 153 | first = dict_first(dict); |
eb5d44eb | 154 | |
ffe543af | 155 | if (dict->dupes) { |
156 | while (first && (next = dict_next(dict, first))) { | |
157 | if (dict->compare(first->key, next->key) > 0) | |
158 | return 0; | |
159 | first = next; | |
eb5d44eb | 160 | } |
ffe543af | 161 | } else { |
162 | while (first && (next = dict_next(dict, first))) { | |
163 | if (dict->compare(first->key, next->key) >= 0) | |
164 | return 0; | |
165 | first = next; | |
eb5d44eb | 166 | } |
167 | } | |
ffe543af | 168 | return 1; |
eb5d44eb | 169 | } |
170 | ||
171 | ||
172 | /* | |
173 | * This function recursively verifies that the given binary subtree satisfies | |
174 | * three of the red black properties. It checks that every red node has only | |
175 | * black children. It makes sure that each node is either red or black. And it | |
176 | * checks that every path has the same count of black nodes from root to leaf. | |
177 | * It returns the blackheight of the given subtree; this allows blackheights to | |
178 | * be computed recursively and compared for left and right siblings for | |
179 | * mismatches. It does not check for every nil node being black, because there | |
180 | * is only one sentinel nil node. The return value of this function is the | |
181 | * black height of the subtree rooted at the node ``root'', or zero if the | |
182 | * subtree is not red-black. | |
183 | */ | |
184 | ||
ffe543af | 185 | static unsigned int verify_redblack(dnode_t *nil, dnode_t *root) |
eb5d44eb | 186 | { |
ffe543af | 187 | unsigned height_left, height_right; |
eb5d44eb | 188 | |
ffe543af | 189 | if (root != nil) { |
190 | height_left = verify_redblack(nil, root->left); | |
191 | height_right = verify_redblack(nil, root->right); | |
192 | if (height_left == 0 || height_right == 0) | |
eb5d44eb | 193 | return 0; |
ffe543af | 194 | if (height_left != height_right) |
eb5d44eb | 195 | return 0; |
ffe543af | 196 | if (root->color == dnode_red) { |
197 | if (root->left->color != dnode_black) | |
198 | return 0; | |
199 | if (root->right->color != dnode_black) | |
200 | return 0; | |
201 | return height_left; | |
eb5d44eb | 202 | } |
ffe543af | 203 | if (root->color != dnode_black) |
204 | return 0; | |
205 | return height_left + 1; | |
206 | } | |
207 | return 1; | |
eb5d44eb | 208 | } |
209 | ||
210 | /* | |
211 | * Compute the actual count of nodes by traversing the tree and | |
212 | * return it. This could be compared against the stored count to | |
213 | * detect a mismatch. | |
214 | */ | |
215 | ||
ffe543af | 216 | static dictcount_t verify_node_count(dnode_t *nil, dnode_t *root) |
eb5d44eb | 217 | { |
ffe543af | 218 | if (root == nil) |
219 | return 0; | |
220 | else | |
221 | return 1 + verify_node_count(nil, root->left) | |
222 | + verify_node_count(nil, root->right); | |
eb5d44eb | 223 | } |
224 | ||
225 | /* | |
226 | * Verify that the tree contains the given node. This is done by | |
227 | * traversing all of the nodes and comparing their pointers to the | |
228 | * given pointer. Returns 1 if the node is found, otherwise | |
229 | * returns zero. It is intended for debugging purposes. | |
230 | */ | |
231 | ||
ffe543af | 232 | static int verify_dict_has_node(dnode_t *nil, dnode_t *root, dnode_t *node) |
eb5d44eb | 233 | { |
ffe543af | 234 | if (root != nil) { |
235 | return root == node | |
236 | || verify_dict_has_node(nil, root->left, node) | |
237 | || verify_dict_has_node(nil, root->right, node); | |
eb5d44eb | 238 | } |
ffe543af | 239 | return 0; |
eb5d44eb | 240 | } |
241 | ||
ffe543af | 242 | |
eb5d44eb | 243 | /* |
244 | * Dynamically allocate and initialize a dictionary object. | |
245 | */ | |
246 | ||
ffe543af | 247 | dict_t *dict_create(dictcount_t maxcount, dict_comp_t comp) |
eb5d44eb | 248 | { |
ffe543af | 249 | dict_t *new = malloc(sizeof *new); |
250 | ||
251 | if (new) { | |
252 | new->compare = comp; | |
253 | new->allocnode = dnode_alloc; | |
254 | new->freenode = dnode_free; | |
255 | new->context = NULL; | |
256 | new->nodecount = 0; | |
257 | new->maxcount = maxcount; | |
258 | new->nilnode.left = &new->nilnode; | |
259 | new->nilnode.right = &new->nilnode; | |
260 | new->nilnode.parent = &new->nilnode; | |
261 | new->nilnode.color = dnode_black; | |
262 | new->dupes = 0; | |
eb5d44eb | 263 | } |
ffe543af | 264 | return new; |
eb5d44eb | 265 | } |
266 | ||
267 | /* | |
268 | * Select a different set of node allocator routines. | |
269 | */ | |
270 | ||
ffe543af | 271 | void dict_set_allocator(dict_t *dict, dnode_alloc_t al, |
272 | dnode_free_t fr, void *context) | |
eb5d44eb | 273 | { |
ffe543af | 274 | assert (dict_count(dict) == 0); |
275 | assert ((al == NULL && fr == NULL) || (al != NULL && fr != NULL)); | |
eb5d44eb | 276 | |
ffe543af | 277 | dict->allocnode = al ? al : dnode_alloc; |
278 | dict->freenode = fr ? fr : dnode_free; | |
279 | dict->context = context; | |
eb5d44eb | 280 | } |
281 | ||
282 | /* | |
283 | * Free a dynamically allocated dictionary object. Removing the nodes | |
284 | * from the tree before deleting it is required. | |
285 | */ | |
286 | ||
ffe543af | 287 | void dict_destroy(dict_t *dict) |
eb5d44eb | 288 | { |
ffe543af | 289 | assert (dict_isempty(dict)); |
290 | free(dict); | |
eb5d44eb | 291 | } |
292 | ||
293 | /* | |
294 | * Free all the nodes in the dictionary by using the dictionary's | |
295 | * installed free routine. The dictionary is emptied. | |
296 | */ | |
297 | ||
ffe543af | 298 | void dict_free_nodes(dict_t *dict) |
eb5d44eb | 299 | { |
ffe543af | 300 | dnode_t *nil = dict_nil(dict), *root = dict_root(dict); |
301 | free_nodes(dict, root, nil); | |
302 | dict->nodecount = 0; | |
303 | dict->nilnode.left = &dict->nilnode; | |
304 | dict->nilnode.right = &dict->nilnode; | |
eb5d44eb | 305 | } |
306 | ||
307 | /* | |
308 | * Obsolescent function, equivalent to dict_free_nodes | |
309 | */ | |
310 | ||
ffe543af | 311 | void dict_free(dict_t *dict) |
eb5d44eb | 312 | { |
313 | #ifdef KAZLIB_OBSOLESCENT_DEBUG | |
ffe543af | 314 | assert ("call to obsolescent function dict_free()" && 0); |
eb5d44eb | 315 | #endif |
ffe543af | 316 | dict_free_nodes(dict); |
eb5d44eb | 317 | } |
318 | ||
319 | /* | |
320 | * Initialize a user-supplied dictionary object. | |
321 | */ | |
322 | ||
ffe543af | 323 | dict_t *dict_init(dict_t *dict, dictcount_t maxcount, dict_comp_t comp) |
eb5d44eb | 324 | { |
ffe543af | 325 | dict->compare = comp; |
326 | dict->allocnode = dnode_alloc; | |
327 | dict->freenode = dnode_free; | |
328 | dict->context = NULL; | |
329 | dict->nodecount = 0; | |
330 | dict->maxcount = maxcount; | |
331 | dict->nilnode.left = &dict->nilnode; | |
332 | dict->nilnode.right = &dict->nilnode; | |
333 | dict->nilnode.parent = &dict->nilnode; | |
334 | dict->nilnode.color = dnode_black; | |
335 | dict->dupes = 0; | |
336 | return dict; | |
eb5d44eb | 337 | } |
338 | ||
339 | /* | |
340 | * Initialize a dictionary in the likeness of another dictionary | |
341 | */ | |
342 | ||
ffe543af | 343 | void dict_init_like(dict_t *dict, const dict_t *template) |
eb5d44eb | 344 | { |
ffe543af | 345 | dict->compare = template->compare; |
346 | dict->allocnode = template->allocnode; | |
347 | dict->freenode = template->freenode; | |
348 | dict->context = template->context; | |
349 | dict->nodecount = 0; | |
350 | dict->maxcount = template->maxcount; | |
351 | dict->nilnode.left = &dict->nilnode; | |
352 | dict->nilnode.right = &dict->nilnode; | |
353 | dict->nilnode.parent = &dict->nilnode; | |
354 | dict->nilnode.color = dnode_black; | |
355 | dict->dupes = template->dupes; | |
356 | ||
357 | assert (dict_similar(dict, template)); | |
eb5d44eb | 358 | } |
359 | ||
360 | /* | |
361 | * Remove all nodes from the dictionary (without freeing them in any way). | |
362 | */ | |
363 | ||
ffe543af | 364 | static void dict_clear(dict_t *dict) |
eb5d44eb | 365 | { |
ffe543af | 366 | dict->nodecount = 0; |
367 | dict->nilnode.left = &dict->nilnode; | |
368 | dict->nilnode.right = &dict->nilnode; | |
369 | dict->nilnode.parent = &dict->nilnode; | |
370 | assert (dict->nilnode.color == dnode_black); | |
eb5d44eb | 371 | } |
372 | ||
ffe543af | 373 | |
eb5d44eb | 374 | /* |
375 | * Verify the integrity of the dictionary structure. This is provided for | |
376 | * debugging purposes, and should be placed in assert statements. Just because | |
377 | * this function succeeds doesn't mean that the tree is not corrupt. Certain | |
378 | * corruptions in the tree may simply cause undefined behavior. | |
ffe543af | 379 | */ |
eb5d44eb | 380 | |
ffe543af | 381 | int dict_verify(dict_t *dict) |
eb5d44eb | 382 | { |
ffe543af | 383 | dnode_t *nil = dict_nil(dict), *root = dict_root(dict); |
eb5d44eb | 384 | |
ffe543af | 385 | /* check that the sentinel node and root node are black */ |
386 | if (root->color != dnode_black) | |
387 | return 0; | |
388 | if (nil->color != dnode_black) | |
389 | return 0; | |
390 | if (nil->right != nil) | |
391 | return 0; | |
392 | /* nil->left is the root node; check that its parent pointer is nil */ | |
393 | if (nil->left->parent != nil) | |
394 | return 0; | |
395 | /* perform a weak test that the tree is a binary search tree */ | |
396 | if (!verify_bintree(dict)) | |
397 | return 0; | |
398 | /* verify that the tree is a red-black tree */ | |
399 | if (!verify_redblack(nil, root)) | |
400 | return 0; | |
401 | if (verify_node_count(nil, root) != dict_count(dict)) | |
402 | return 0; | |
403 | return 1; | |
eb5d44eb | 404 | } |
405 | ||
406 | /* | |
407 | * Determine whether two dictionaries are similar: have the same comparison and | |
408 | * allocator functions, and same status as to whether duplicates are allowed. | |
409 | */ | |
410 | ||
ffe543af | 411 | int dict_similar(const dict_t *left, const dict_t *right) |
eb5d44eb | 412 | { |
ffe543af | 413 | if (left->compare != right->compare) |
414 | return 0; | |
eb5d44eb | 415 | |
ffe543af | 416 | if (left->allocnode != right->allocnode) |
417 | return 0; | |
eb5d44eb | 418 | |
ffe543af | 419 | if (left->freenode != right->freenode) |
420 | return 0; | |
eb5d44eb | 421 | |
ffe543af | 422 | if (left->context != right->context) |
423 | return 0; | |
eb5d44eb | 424 | |
ffe543af | 425 | if (left->dupes != right->dupes) |
426 | return 0; | |
eb5d44eb | 427 | |
ffe543af | 428 | return 1; |
eb5d44eb | 429 | } |
430 | ||
431 | /* | |
432 | * Locate a node in the dictionary having the given key. | |
433 | * If the node is not found, a null a pointer is returned (rather than | |
434 | * a pointer that dictionary's nil sentinel node), otherwise a pointer to the | |
435 | * located node is returned. | |
436 | */ | |
437 | ||
ffe543af | 438 | dnode_t *dict_lookup(dict_t *dict, const void *key) |
eb5d44eb | 439 | { |
ffe543af | 440 | dnode_t *root = dict_root(dict); |
441 | dnode_t *nil = dict_nil(dict); | |
442 | dnode_t *saved; | |
443 | int result; | |
444 | ||
445 | /* simple binary search adapted for trees that contain duplicate keys */ | |
446 | ||
447 | while (root != nil) { | |
448 | result = dict->compare(key, root->key); | |
449 | if (result < 0) | |
450 | root = root->left; | |
451 | else if (result > 0) | |
452 | root = root->right; | |
453 | else { | |
454 | if (!dict->dupes) { /* no duplicates, return match */ | |
455 | return root; | |
456 | } else { /* could be dupes, find leftmost one */ | |
457 | do { | |
458 | saved = root; | |
459 | root = root->left; | |
460 | while (root != nil && dict->compare(key, root->key)) | |
461 | root = root->right; | |
462 | } while (root != nil); | |
463 | return saved; | |
eb5d44eb | 464 | } |
465 | } | |
466 | } | |
467 | ||
ffe543af | 468 | return NULL; |
eb5d44eb | 469 | } |
470 | ||
471 | /* | |
472 | * Look for the node corresponding to the lowest key that is equal to or | |
473 | * greater than the given key. If there is no such node, return null. | |
474 | */ | |
475 | ||
ffe543af | 476 | dnode_t *dict_lower_bound(dict_t *dict, const void *key) |
eb5d44eb | 477 | { |
ffe543af | 478 | dnode_t *root = dict_root(dict); |
479 | dnode_t *nil = dict_nil(dict); | |
480 | dnode_t *tentative = 0; | |
481 | ||
482 | while (root != nil) { | |
483 | int result = dict->compare(key, root->key); | |
484 | ||
485 | if (result > 0) { | |
486 | root = root->right; | |
487 | } else if (result < 0) { | |
488 | tentative = root; | |
489 | root = root->left; | |
490 | } else { | |
491 | if (!dict->dupes) { | |
492 | return root; | |
493 | } else { | |
494 | tentative = root; | |
495 | root = root->left; | |
eb5d44eb | 496 | } |
ffe543af | 497 | } |
eb5d44eb | 498 | } |
ffe543af | 499 | |
500 | return tentative; | |
eb5d44eb | 501 | } |
502 | ||
503 | /* | |
504 | * Look for the node corresponding to the greatest key that is equal to or | |
505 | * lower than the given key. If there is no such node, return null. | |
506 | */ | |
507 | ||
ffe543af | 508 | dnode_t *dict_upper_bound(dict_t *dict, const void *key) |
eb5d44eb | 509 | { |
ffe543af | 510 | dnode_t *root = dict_root(dict); |
511 | dnode_t *nil = dict_nil(dict); | |
512 | dnode_t *tentative = 0; | |
513 | ||
514 | while (root != nil) { | |
515 | int result = dict->compare(key, root->key); | |
516 | ||
517 | if (result < 0) { | |
518 | root = root->left; | |
519 | } else if (result > 0) { | |
520 | tentative = root; | |
521 | root = root->right; | |
522 | } else { | |
523 | if (!dict->dupes) { | |
524 | return root; | |
525 | } else { | |
526 | tentative = root; | |
527 | root = root->right; | |
eb5d44eb | 528 | } |
ffe543af | 529 | } |
eb5d44eb | 530 | } |
ffe543af | 531 | |
532 | return tentative; | |
eb5d44eb | 533 | } |
534 | ||
535 | /* | |
536 | * Insert a node into the dictionary. The node should have been | |
537 | * initialized with a data field. All other fields are ignored. | |
538 | * The behavior is undefined if the user attempts to insert into | |
539 | * a dictionary that is already full (for which the dict_isfull() | |
540 | * function returns true). | |
541 | */ | |
542 | ||
ffe543af | 543 | void dict_insert(dict_t *dict, dnode_t *node, const void *key) |
eb5d44eb | 544 | { |
ffe543af | 545 | dnode_t *where = dict_root(dict), *nil = dict_nil(dict); |
546 | dnode_t *parent = nil, *uncle, *grandpa; | |
547 | int result = -1; | |
548 | ||
549 | node->key = key; | |
550 | ||
551 | assert (!dict_isfull(dict)); | |
552 | assert (!dict_contains(dict, node)); | |
553 | assert (!dnode_is_in_a_dict(node)); | |
554 | ||
555 | /* basic binary tree insert */ | |
556 | ||
557 | while (where != nil) { | |
558 | parent = where; | |
559 | result = dict->compare(key, where->key); | |
560 | /* trap attempts at duplicate key insertion unless it's explicitly allowed */ | |
561 | assert (dict->dupes || result != 0); | |
562 | if (result < 0) | |
563 | where = where->left; | |
564 | else | |
565 | where = where->right; | |
eb5d44eb | 566 | } |
567 | ||
ffe543af | 568 | assert (where == nil); |
569 | ||
570 | if (result < 0) | |
571 | parent->left = node; | |
572 | else | |
573 | parent->right = node; | |
574 | ||
575 | node->parent = parent; | |
576 | node->left = nil; | |
577 | node->right = nil; | |
578 | ||
579 | dict->nodecount++; | |
580 | ||
581 | /* red black adjustments */ | |
582 | ||
583 | node->color = dnode_red; | |
584 | ||
585 | while (parent->color == dnode_red) { | |
586 | grandpa = parent->parent; | |
587 | if (parent == grandpa->left) { | |
588 | uncle = grandpa->right; | |
589 | if (uncle->color == dnode_red) { /* red parent, red uncle */ | |
590 | parent->color = dnode_black; | |
591 | uncle->color = dnode_black; | |
592 | grandpa->color = dnode_red; | |
593 | node = grandpa; | |
594 | parent = grandpa->parent; | |
595 | } else { /* red parent, black uncle */ | |
596 | if (node == parent->right) { | |
597 | rotate_left(parent); | |
598 | parent = node; | |
599 | assert (grandpa == parent->parent); | |
600 | /* rotation between parent and child preserves grandpa */ | |
eb5d44eb | 601 | } |
ffe543af | 602 | parent->color = dnode_black; |
603 | grandpa->color = dnode_red; | |
604 | rotate_right(grandpa); | |
605 | break; | |
eb5d44eb | 606 | } |
ffe543af | 607 | } else { /* symmetric cases: parent == parent->parent->right */ |
608 | uncle = grandpa->left; | |
609 | if (uncle->color == dnode_red) { | |
610 | parent->color = dnode_black; | |
611 | uncle->color = dnode_black; | |
612 | grandpa->color = dnode_red; | |
613 | node = grandpa; | |
614 | parent = grandpa->parent; | |
615 | } else { | |
616 | if (node == parent->left) { | |
617 | rotate_right(parent); | |
618 | parent = node; | |
619 | assert (grandpa == parent->parent); | |
eb5d44eb | 620 | } |
ffe543af | 621 | parent->color = dnode_black; |
622 | grandpa->color = dnode_red; | |
623 | rotate_left(grandpa); | |
624 | break; | |
eb5d44eb | 625 | } |
626 | } | |
627 | } | |
628 | ||
ffe543af | 629 | dict_root(dict)->color = dnode_black; |
eb5d44eb | 630 | |
ffe543af | 631 | assert (dict_verify(dict)); |
eb5d44eb | 632 | } |
633 | ||
634 | /* | |
635 | * Delete the given node from the dictionary. If the given node does not belong | |
636 | * to the given dictionary, undefined behavior results. A pointer to the | |
637 | * deleted node is returned. | |
638 | */ | |
639 | ||
ffe543af | 640 | dnode_t *dict_delete(dict_t *dict, dnode_t *delete) |
eb5d44eb | 641 | { |
ffe543af | 642 | dnode_t *nil = dict_nil(dict), *child, *delparent = delete->parent; |
643 | ||
644 | /* basic deletion */ | |
645 | ||
646 | assert (!dict_isempty(dict)); | |
647 | assert (dict_contains(dict, delete)); | |
648 | ||
649 | /* | |
650 | * If the node being deleted has two children, then we replace it with its | |
651 | * successor (i.e. the leftmost node in the right subtree.) By doing this, | |
652 | * we avoid the traditional algorithm under which the successor's key and | |
653 | * value *only* move to the deleted node and the successor is spliced out | |
654 | * from the tree. We cannot use this approach because the user may hold | |
655 | * pointers to the successor, or nodes may be inextricably tied to some | |
656 | * other structures by way of embedding, etc. So we must splice out the | |
657 | * node we are given, not some other node, and must not move contents from | |
658 | * one node to another behind the user's back. | |
659 | */ | |
660 | ||
661 | if (delete->left != nil && delete->right != nil) { | |
662 | dnode_t *next = dict_next(dict, delete); | |
663 | dnode_t *nextparent = next->parent; | |
664 | dnode_color_t nextcolor = next->color; | |
665 | ||
666 | assert (next != nil); | |
667 | assert (next->parent != nil); | |
668 | assert (next->left == nil); | |
669 | ||
670 | /* | |
671 | * First, splice out the successor from the tree completely, by | |
672 | * moving up its right child into its place. | |
673 | */ | |
674 | ||
675 | child = next->right; | |
676 | child->parent = nextparent; | |
677 | ||
678 | if (nextparent->left == next) { | |
679 | nextparent->left = child; | |
680 | } else { | |
681 | assert (nextparent->right == next); | |
682 | nextparent->right = child; | |
eb5d44eb | 683 | } |
684 | ||
ffe543af | 685 | /* |
686 | * Now that the successor has been extricated from the tree, install it | |
687 | * in place of the node that we want deleted. | |
688 | */ | |
689 | ||
690 | next->parent = delparent; | |
691 | next->left = delete->left; | |
692 | next->right = delete->right; | |
693 | next->left->parent = next; | |
694 | next->right->parent = next; | |
695 | next->color = delete->color; | |
696 | delete->color = nextcolor; | |
697 | ||
698 | if (delparent->left == delete) { | |
699 | delparent->left = next; | |
700 | } else { | |
701 | assert (delparent->right == delete); | |
702 | delparent->right = next; | |
eb5d44eb | 703 | } |
704 | ||
ffe543af | 705 | } else { |
706 | assert (delete != nil); | |
707 | assert (delete->left == nil || delete->right == nil); | |
eb5d44eb | 708 | |
ffe543af | 709 | child = (delete->left != nil) ? delete->left : delete->right; |
eb5d44eb | 710 | |
ffe543af | 711 | child->parent = delparent = delete->parent; |
eb5d44eb | 712 | |
ffe543af | 713 | if (delete == delparent->left) { |
714 | delparent->left = child; | |
715 | } else { | |
716 | assert (delete == delparent->right); | |
717 | delparent->right = child; | |
eb5d44eb | 718 | } |
719 | } | |
720 | ||
ffe543af | 721 | delete->parent = NULL; |
722 | delete->right = NULL; | |
723 | delete->left = NULL; | |
eb5d44eb | 724 | |
ffe543af | 725 | dict->nodecount--; |
eb5d44eb | 726 | |
ffe543af | 727 | assert (verify_bintree(dict)); |
eb5d44eb | 728 | |
ffe543af | 729 | /* red-black adjustments */ |
eb5d44eb | 730 | |
ffe543af | 731 | if (delete->color == dnode_black) { |
732 | dnode_t *parent, *sister; | |
eb5d44eb | 733 | |
ffe543af | 734 | dict_root(dict)->color = dnode_red; |
eb5d44eb | 735 | |
ffe543af | 736 | while (child->color == dnode_black) { |
737 | parent = child->parent; | |
738 | if (child == parent->left) { | |
739 | sister = parent->right; | |
740 | assert (sister != nil); | |
741 | if (sister->color == dnode_red) { | |
742 | sister->color = dnode_black; | |
743 | parent->color = dnode_red; | |
744 | rotate_left(parent); | |
745 | sister = parent->right; | |
746 | assert (sister != nil); | |
eb5d44eb | 747 | } |
ffe543af | 748 | if (sister->left->color == dnode_black |
749 | && sister->right->color == dnode_black) { | |
750 | sister->color = dnode_red; | |
751 | child = parent; | |
752 | } else { | |
753 | if (sister->right->color == dnode_black) { | |
754 | assert (sister->left->color == dnode_red); | |
755 | sister->left->color = dnode_black; | |
756 | sister->color = dnode_red; | |
757 | rotate_right(sister); | |
758 | sister = parent->right; | |
759 | assert (sister != nil); | |
eb5d44eb | 760 | } |
ffe543af | 761 | sister->color = parent->color; |
762 | sister->right->color = dnode_black; | |
763 | parent->color = dnode_black; | |
764 | rotate_left(parent); | |
765 | break; | |
eb5d44eb | 766 | } |
ffe543af | 767 | } else { /* symmetric case: child == child->parent->right */ |
768 | assert (child == parent->right); | |
769 | sister = parent->left; | |
770 | assert (sister != nil); | |
771 | if (sister->color == dnode_red) { | |
772 | sister->color = dnode_black; | |
773 | parent->color = dnode_red; | |
774 | rotate_right(parent); | |
775 | sister = parent->left; | |
776 | assert (sister != nil); | |
eb5d44eb | 777 | } |
ffe543af | 778 | if (sister->right->color == dnode_black |
779 | && sister->left->color == dnode_black) { | |
780 | sister->color = dnode_red; | |
781 | child = parent; | |
782 | } else { | |
783 | if (sister->left->color == dnode_black) { | |
784 | assert (sister->right->color == dnode_red); | |
785 | sister->right->color = dnode_black; | |
786 | sister->color = dnode_red; | |
787 | rotate_left(sister); | |
788 | sister = parent->left; | |
789 | assert (sister != nil); | |
eb5d44eb | 790 | } |
ffe543af | 791 | sister->color = parent->color; |
792 | sister->left->color = dnode_black; | |
793 | parent->color = dnode_black; | |
794 | rotate_right(parent); | |
795 | break; | |
eb5d44eb | 796 | } |
797 | } | |
798 | } | |
799 | ||
ffe543af | 800 | child->color = dnode_black; |
801 | dict_root(dict)->color = dnode_black; | |
eb5d44eb | 802 | } |
803 | ||
ffe543af | 804 | assert (dict_verify(dict)); |
eb5d44eb | 805 | |
ffe543af | 806 | return delete; |
eb5d44eb | 807 | } |
808 | ||
809 | /* | |
810 | * Allocate a node using the dictionary's allocator routine, give it | |
811 | * the data item. | |
812 | */ | |
813 | ||
ffe543af | 814 | int dict_alloc_insert(dict_t *dict, const void *key, void *data) |
eb5d44eb | 815 | { |
ffe543af | 816 | dnode_t *node = dict->allocnode(dict->context); |
eb5d44eb | 817 | |
ffe543af | 818 | if (node) { |
819 | dnode_init(node, data); | |
820 | dict_insert(dict, node, key); | |
821 | return 1; | |
eb5d44eb | 822 | } |
ffe543af | 823 | return 0; |
eb5d44eb | 824 | } |
825 | ||
ffe543af | 826 | void dict_delete_free(dict_t *dict, dnode_t *node) |
eb5d44eb | 827 | { |
ffe543af | 828 | dict_delete(dict, node); |
829 | dict->freenode(node, dict->context); | |
eb5d44eb | 830 | } |
831 | ||
832 | /* | |
833 | * Return the node with the lowest (leftmost) key. If the dictionary is empty | |
834 | * (that is, dict_isempty(dict) returns 1) a null pointer is returned. | |
835 | */ | |
836 | ||
ffe543af | 837 | dnode_t *dict_first(dict_t *dict) |
eb5d44eb | 838 | { |
ffe543af | 839 | dnode_t *nil = dict_nil(dict), *root = dict_root(dict), *left; |
eb5d44eb | 840 | |
ffe543af | 841 | if (root != nil) |
842 | while ((left = root->left) != nil) | |
843 | root = left; | |
eb5d44eb | 844 | |
ffe543af | 845 | return (root == nil) ? NULL : root; |
eb5d44eb | 846 | } |
847 | ||
848 | /* | |
849 | * Return the node with the highest (rightmost) key. If the dictionary is empty | |
850 | * (that is, dict_isempty(dict) returns 1) a null pointer is returned. | |
851 | */ | |
852 | ||
ffe543af | 853 | dnode_t *dict_last(dict_t *dict) |
eb5d44eb | 854 | { |
ffe543af | 855 | dnode_t *nil = dict_nil(dict), *root = dict_root(dict), *right; |
eb5d44eb | 856 | |
ffe543af | 857 | if (root != nil) |
858 | while ((right = root->right) != nil) | |
859 | root = right; | |
eb5d44eb | 860 | |
ffe543af | 861 | return (root == nil) ? NULL : root; |
eb5d44eb | 862 | } |
863 | ||
864 | /* | |
865 | * Return the given node's successor node---the node which has the | |
866 | * next key in the the left to right ordering. If the node has | |
867 | * no successor, a null pointer is returned rather than a pointer to | |
868 | * the nil node. | |
869 | */ | |
870 | ||
ffe543af | 871 | dnode_t *dict_next(dict_t *dict, dnode_t *curr) |
eb5d44eb | 872 | { |
ffe543af | 873 | dnode_t *nil = dict_nil(dict), *parent, *left; |
874 | ||
875 | if (curr->right != nil) { | |
876 | curr = curr->right; | |
877 | while ((left = curr->left) != nil) | |
878 | curr = left; | |
879 | return curr; | |
eb5d44eb | 880 | } |
881 | ||
ffe543af | 882 | parent = curr->parent; |
eb5d44eb | 883 | |
ffe543af | 884 | while (parent != nil && curr == parent->right) { |
885 | curr = parent; | |
886 | parent = curr->parent; | |
eb5d44eb | 887 | } |
888 | ||
ffe543af | 889 | return (parent == nil) ? NULL : parent; |
eb5d44eb | 890 | } |
891 | ||
892 | /* | |
893 | * Return the given node's predecessor, in the key order. | |
894 | * The nil sentinel node is returned if there is no predecessor. | |
895 | */ | |
896 | ||
ffe543af | 897 | dnode_t *dict_prev(dict_t *dict, dnode_t *curr) |
eb5d44eb | 898 | { |
ffe543af | 899 | dnode_t *nil = dict_nil(dict), *parent, *right; |
900 | ||
901 | if (curr->left != nil) { | |
902 | curr = curr->left; | |
903 | while ((right = curr->right) != nil) | |
904 | curr = right; | |
905 | return curr; | |
eb5d44eb | 906 | } |
907 | ||
ffe543af | 908 | parent = curr->parent; |
eb5d44eb | 909 | |
ffe543af | 910 | while (parent != nil && curr == parent->left) { |
911 | curr = parent; | |
912 | parent = curr->parent; | |
eb5d44eb | 913 | } |
914 | ||
ffe543af | 915 | return (parent == nil) ? NULL : parent; |
eb5d44eb | 916 | } |
917 | ||
ffe543af | 918 | void dict_allow_dupes(dict_t *dict) |
eb5d44eb | 919 | { |
ffe543af | 920 | dict->dupes = 1; |
eb5d44eb | 921 | } |
922 | ||
923 | #undef dict_count | |
924 | #undef dict_isempty | |
925 | #undef dict_isfull | |
926 | #undef dnode_get | |
927 | #undef dnode_put | |
928 | #undef dnode_getkey | |
929 | ||
ffe543af | 930 | dictcount_t dict_count(dict_t *dict) |
eb5d44eb | 931 | { |
ffe543af | 932 | return dict->nodecount; |
eb5d44eb | 933 | } |
934 | ||
ffe543af | 935 | int dict_isempty(dict_t *dict) |
eb5d44eb | 936 | { |
ffe543af | 937 | return dict->nodecount == 0; |
eb5d44eb | 938 | } |
939 | ||
ffe543af | 940 | int dict_isfull(dict_t *dict) |
eb5d44eb | 941 | { |
ffe543af | 942 | return dict->nodecount == dict->maxcount; |
eb5d44eb | 943 | } |
944 | ||
ffe543af | 945 | int dict_contains(dict_t *dict, dnode_t *node) |
eb5d44eb | 946 | { |
ffe543af | 947 | return verify_dict_has_node(dict_nil(dict), dict_root(dict), node); |
eb5d44eb | 948 | } |
949 | ||
ffe543af | 950 | static dnode_t *dnode_alloc(void *context) |
eb5d44eb | 951 | { |
ffe543af | 952 | return malloc(sizeof *dnode_alloc(NULL)); |
eb5d44eb | 953 | } |
954 | ||
ffe543af | 955 | static void dnode_free(dnode_t *node, void *context) |
eb5d44eb | 956 | { |
ffe543af | 957 | free(node); |
eb5d44eb | 958 | } |
959 | ||
ffe543af | 960 | dnode_t *dnode_create(void *data) |
eb5d44eb | 961 | { |
ffe543af | 962 | dnode_t *new = malloc(sizeof *new); |
963 | if (new) { | |
964 | new->data = data; | |
965 | new->parent = NULL; | |
966 | new->left = NULL; | |
967 | new->right = NULL; | |
eb5d44eb | 968 | } |
ffe543af | 969 | return new; |
eb5d44eb | 970 | } |
971 | ||
ffe543af | 972 | dnode_t *dnode_init(dnode_t *dnode, void *data) |
eb5d44eb | 973 | { |
ffe543af | 974 | dnode->data = data; |
975 | dnode->parent = NULL; | |
976 | dnode->left = NULL; | |
977 | dnode->right = NULL; | |
978 | return dnode; | |
eb5d44eb | 979 | } |
980 | ||
ffe543af | 981 | void dnode_destroy(dnode_t *dnode) |
eb5d44eb | 982 | { |
ffe543af | 983 | assert (!dnode_is_in_a_dict(dnode)); |
984 | free(dnode); | |
eb5d44eb | 985 | } |
986 | ||
ffe543af | 987 | void *dnode_get(dnode_t *dnode) |
eb5d44eb | 988 | { |
ffe543af | 989 | return dnode->data; |
eb5d44eb | 990 | } |
991 | ||
ffe543af | 992 | const void *dnode_getkey(dnode_t *dnode) |
eb5d44eb | 993 | { |
ffe543af | 994 | return dnode->key; |
eb5d44eb | 995 | } |
996 | ||
ffe543af | 997 | void dnode_put(dnode_t *dnode, void *data) |
eb5d44eb | 998 | { |
ffe543af | 999 | dnode->data = data; |
eb5d44eb | 1000 | } |
1001 | ||
ffe543af | 1002 | int dnode_is_in_a_dict(dnode_t *dnode) |
eb5d44eb | 1003 | { |
ffe543af | 1004 | return (dnode->parent && dnode->left && dnode->right); |
eb5d44eb | 1005 | } |
1006 | ||
ffe543af | 1007 | void dict_process(dict_t *dict, void *context, dnode_process_t function) |
eb5d44eb | 1008 | { |
ffe543af | 1009 | dnode_t *node = dict_first(dict), *next; |
1010 | ||
1011 | while (node != NULL) { | |
1012 | /* check for callback function deleting */ | |
1013 | /* the next node from under us */ | |
1014 | assert (dict_contains(dict, node)); | |
1015 | next = dict_next(dict, node); | |
1016 | function(dict, node, context); | |
1017 | node = next; | |
eb5d44eb | 1018 | } |
1019 | } | |
1020 | ||
ffe543af | 1021 | static void load_begin_internal(dict_load_t *load, dict_t *dict) |
eb5d44eb | 1022 | { |
ffe543af | 1023 | load->dictptr = dict; |
1024 | load->nilnode.left = &load->nilnode; | |
1025 | load->nilnode.right = &load->nilnode; | |
eb5d44eb | 1026 | } |
1027 | ||
ffe543af | 1028 | void dict_load_begin(dict_load_t *load, dict_t *dict) |
eb5d44eb | 1029 | { |
ffe543af | 1030 | assert (dict_isempty(dict)); |
1031 | load_begin_internal(load, dict); | |
eb5d44eb | 1032 | } |
1033 | ||
ffe543af | 1034 | void dict_load_next(dict_load_t *load, dnode_t *newnode, const void *key) |
eb5d44eb | 1035 | { |
ffe543af | 1036 | dict_t *dict = load->dictptr; |
1037 | dnode_t *nil = &load->nilnode; | |
1038 | ||
1039 | assert (!dnode_is_in_a_dict(newnode)); | |
1040 | assert (dict->nodecount < dict->maxcount); | |
1041 | ||
1042 | #ifndef NDEBUG | |
1043 | if (dict->nodecount > 0) { | |
1044 | if (dict->dupes) | |
1045 | assert (dict->compare(nil->left->key, key) <= 0); | |
1046 | else | |
1047 | assert (dict->compare(nil->left->key, key) < 0); | |
eb5d44eb | 1048 | } |
ffe543af | 1049 | #endif |
eb5d44eb | 1050 | |
ffe543af | 1051 | newnode->key = key; |
1052 | nil->right->left = newnode; | |
1053 | nil->right = newnode; | |
1054 | newnode->left = nil; | |
1055 | dict->nodecount++; | |
eb5d44eb | 1056 | } |
1057 | ||
ffe543af | 1058 | void dict_load_end(dict_load_t *load) |
eb5d44eb | 1059 | { |
ffe543af | 1060 | dict_t *dict = load->dictptr; |
1061 | dnode_t *tree[DICT_DEPTH_MAX] = { 0 }; | |
1062 | dnode_t *curr, *dictnil = dict_nil(dict), *loadnil = &load->nilnode, *next; | |
1063 | dnode_t *complete = 0; | |
1064 | dictcount_t fullcount = DICTCOUNT_T_MAX, nodecount = dict->nodecount; | |
1065 | dictcount_t botrowcount; | |
1066 | unsigned baselevel = 0, level = 0, i; | |
1067 | ||
1068 | assert (dnode_red == 0 && dnode_black == 1); | |
1069 | ||
1070 | while (fullcount >= nodecount && fullcount) | |
1071 | fullcount >>= 1; | |
1072 | ||
1073 | botrowcount = nodecount - fullcount; | |
1074 | ||
1075 | for (curr = loadnil->left; curr != loadnil; curr = next) { | |
1076 | next = curr->left; | |
1077 | ||
1078 | if (complete == NULL && botrowcount-- == 0) { | |
1079 | assert (baselevel == 0); | |
1080 | assert (level == 0); | |
1081 | baselevel = level = 1; | |
1082 | complete = tree[0]; | |
1083 | ||
1084 | if (complete != 0) { | |
1085 | tree[0] = 0; | |
1086 | complete->right = dictnil; | |
1087 | while (tree[level] != 0) { | |
1088 | tree[level]->right = complete; | |
1089 | complete->parent = tree[level]; | |
1090 | complete = tree[level]; | |
1091 | tree[level++] = 0; | |
eb5d44eb | 1092 | } |
1093 | } | |
1094 | } | |
1095 | ||
ffe543af | 1096 | if (complete == NULL) { |
1097 | curr->left = dictnil; | |
1098 | curr->right = dictnil; | |
1099 | curr->color = level % 2; | |
1100 | complete = curr; | |
1101 | ||
1102 | assert (level == baselevel); | |
1103 | while (tree[level] != 0) { | |
1104 | tree[level]->right = complete; | |
1105 | complete->parent = tree[level]; | |
1106 | complete = tree[level]; | |
1107 | tree[level++] = 0; | |
eb5d44eb | 1108 | } |
ffe543af | 1109 | } else { |
1110 | curr->left = complete; | |
1111 | curr->color = (level + 1) % 2; | |
1112 | complete->parent = curr; | |
1113 | tree[level] = curr; | |
1114 | complete = 0; | |
1115 | level = baselevel; | |
eb5d44eb | 1116 | } |
1117 | } | |
1118 | ||
ffe543af | 1119 | if (complete == NULL) |
1120 | complete = dictnil; | |
eb5d44eb | 1121 | |
ffe543af | 1122 | for (i = 0; i < DICT_DEPTH_MAX; i++) { |
1123 | if (tree[i] != 0) { | |
1124 | tree[i]->right = complete; | |
1125 | complete->parent = tree[i]; | |
1126 | complete = tree[i]; | |
eb5d44eb | 1127 | } |
1128 | } | |
1129 | ||
ffe543af | 1130 | dictnil->color = dnode_black; |
1131 | dictnil->right = dictnil; | |
1132 | complete->parent = dictnil; | |
1133 | complete->color = dnode_black; | |
1134 | dict_root(dict) = complete; | |
eb5d44eb | 1135 | |
ffe543af | 1136 | assert (dict_verify(dict)); |
eb5d44eb | 1137 | } |
1138 | ||
ffe543af | 1139 | void dict_merge(dict_t *dest, dict_t *source) |
eb5d44eb | 1140 | { |
ffe543af | 1141 | dict_load_t load; |
1142 | dnode_t *leftnode = dict_first(dest), *rightnode = dict_first(source); | |
eb5d44eb | 1143 | |
ffe543af | 1144 | assert (dict_similar(dest, source)); |
eb5d44eb | 1145 | |
ffe543af | 1146 | if (source == dest) |
1147 | return; | |
eb5d44eb | 1148 | |
ffe543af | 1149 | dest->nodecount = 0; |
1150 | load_begin_internal(&load, dest); | |
eb5d44eb | 1151 | |
ffe543af | 1152 | for (;;) { |
1153 | if (leftnode != NULL && rightnode != NULL) { | |
1154 | if (dest->compare(leftnode->key, rightnode->key) < 0) | |
1155 | goto copyleft; | |
1156 | else | |
1157 | goto copyright; | |
1158 | } else if (leftnode != NULL) { | |
eb5d44eb | 1159 | goto copyleft; |
ffe543af | 1160 | } else if (rightnode != NULL) { |
eb5d44eb | 1161 | goto copyright; |
ffe543af | 1162 | } else { |
1163 | assert (leftnode == NULL && rightnode == NULL); | |
1164 | break; | |
eb5d44eb | 1165 | } |
ffe543af | 1166 | |
1167 | copyleft: | |
f390d2c7 | 1168 | { |
ffe543af | 1169 | dnode_t *next = dict_next(dest, leftnode); |
1170 | #ifndef NDEBUG | |
1171 | leftnode->left = NULL; /* suppress assertion in dict_load_next */ | |
1172 | #endif | |
1173 | dict_load_next(&load, leftnode, leftnode->key); | |
1174 | leftnode = next; | |
1175 | continue; | |
f390d2c7 | 1176 | } |
ffe543af | 1177 | |
1178 | copyright: | |
eb5d44eb | 1179 | { |
ffe543af | 1180 | dnode_t *next = dict_next(source, rightnode); |
1181 | #ifndef NDEBUG | |
1182 | rightnode->left = NULL; | |
1183 | #endif | |
1184 | dict_load_next(&load, rightnode, rightnode->key); | |
1185 | rightnode = next; | |
1186 | continue; | |
eb5d44eb | 1187 | } |
1188 | } | |
1189 | ||
ffe543af | 1190 | dict_clear(source); |
1191 | dict_load_end(&load); | |
eb5d44eb | 1192 | } |
1193 | ||
1194 | #ifdef KAZLIB_TEST_MAIN | |
1195 | ||
1196 | #include <stdio.h> | |
1197 | #include <string.h> | |
1198 | #include <ctype.h> | |
1199 | #include <stdarg.h> | |
1200 | ||
1201 | typedef char input_t[256]; | |
1202 | ||
ffe543af | 1203 | static int tokenize(char *string, ...) |
eb5d44eb | 1204 | { |
ffe543af | 1205 | char **tokptr; |
1206 | va_list arglist; | |
1207 | int tokcount = 0; | |
1208 | ||
1209 | va_start(arglist, string); | |
1210 | tokptr = va_arg(arglist, char **); | |
1211 | while (tokptr) { | |
1212 | while (*string && isspace((unsigned char) *string)) | |
1213 | string++; | |
1214 | if (!*string) | |
1215 | break; | |
1216 | *tokptr = string; | |
1217 | while (*string && !isspace((unsigned char) *string)) | |
1218 | string++; | |
1219 | tokptr = va_arg(arglist, char **); | |
1220 | tokcount++; | |
1221 | if (!*string) | |
1222 | break; | |
1223 | *string++ = 0; | |
eb5d44eb | 1224 | } |
ffe543af | 1225 | va_end(arglist); |
eb5d44eb | 1226 | |
ffe543af | 1227 | return tokcount; |
eb5d44eb | 1228 | } |
1229 | ||
ffe543af | 1230 | static int comparef(const void *key1, const void *key2) |
eb5d44eb | 1231 | { |
ffe543af | 1232 | return strcmp(key1, key2); |
eb5d44eb | 1233 | } |
1234 | ||
ffe543af | 1235 | static char *dupstring(char *str) |
eb5d44eb | 1236 | { |
ffe543af | 1237 | int sz = strlen(str) + 1; |
1238 | char *new = malloc(sz); | |
1239 | if (new) | |
1240 | memcpy(new, str, sz); | |
1241 | return new; | |
eb5d44eb | 1242 | } |
1243 | ||
ffe543af | 1244 | static dnode_t *new_node(void *c) |
eb5d44eb | 1245 | { |
ffe543af | 1246 | static dnode_t few[5]; |
1247 | static int count; | |
eb5d44eb | 1248 | |
ffe543af | 1249 | if (count < 5) |
1250 | return few + count++; | |
eb5d44eb | 1251 | |
ffe543af | 1252 | return NULL; |
eb5d44eb | 1253 | } |
1254 | ||
ffe543af | 1255 | static void del_node(dnode_t *n, void *c) |
eb5d44eb | 1256 | { |
1257 | } | |
1258 | ||
1259 | static int prompt = 0; | |
1260 | ||
ffe543af | 1261 | static void construct(dict_t *d) |
eb5d44eb | 1262 | { |
ffe543af | 1263 | input_t in; |
1264 | int done = 0; | |
1265 | dict_load_t dl; | |
1266 | dnode_t *dn; | |
1267 | char *tok1, *tok2, *val; | |
1268 | const char *key; | |
1269 | char *help = | |
1270 | "p turn prompt on\n" | |
1271 | "q finish construction\n" | |
1272 | "a <key> <val> add new entry\n"; | |
1273 | ||
1274 | if (!dict_isempty(d)) | |
1275 | puts("warning: dictionary not empty!"); | |
1276 | ||
1277 | dict_load_begin(&dl, d); | |
1278 | ||
1279 | while (!done) { | |
1280 | if (prompt) | |
1281 | putchar('>'); | |
1282 | fflush(stdout); | |
1283 | ||
1284 | if (!fgets(in, sizeof(input_t), stdin)) | |
1285 | break; | |
1286 | ||
1287 | switch (in[0]) { | |
1288 | case '?': | |
1289 | puts(help); | |
1290 | break; | |
1291 | case 'p': | |
1292 | prompt = 1; | |
1293 | break; | |
1294 | case 'q': | |
1295 | done = 1; | |
1296 | break; | |
1297 | case 'a': | |
1298 | if (tokenize(in+1, &tok1, &tok2, (char **) 0) != 2) { | |
1299 | puts("what?"); | |
1300 | break; | |
1301 | } | |
1302 | key = dupstring(tok1); | |
1303 | val = dupstring(tok2); | |
1304 | dn = dnode_create(val); | |
1305 | ||
1306 | if (!key || !val || !dn) { | |
1307 | puts("out of memory"); | |
1308 | free((void *) key); | |
1309 | free(val); | |
1310 | if (dn) | |
1311 | dnode_destroy(dn); | |
1312 | } | |
eb5d44eb | 1313 | |
ffe543af | 1314 | dict_load_next(&dl, dn, key); |
1315 | break; | |
1316 | default: | |
1317 | putchar('?'); | |
1318 | putchar('\n'); | |
1319 | break; | |
eb5d44eb | 1320 | } |
1321 | } | |
1322 | ||
ffe543af | 1323 | dict_load_end(&dl); |
eb5d44eb | 1324 | } |
1325 | ||
ffe543af | 1326 | int main(void) |
eb5d44eb | 1327 | { |
ffe543af | 1328 | input_t in; |
1329 | dict_t darray[10]; | |
1330 | dict_t *d = &darray[0]; | |
1331 | dnode_t *dn; | |
1332 | int i; | |
1333 | char *tok1, *tok2, *val; | |
1334 | const char *key; | |
1335 | ||
1336 | char *help = | |
1337 | "a <key> <val> add value to dictionary\n" | |
1338 | "d <key> delete value from dictionary\n" | |
1339 | "l <key> lookup value in dictionary\n" | |
1340 | "( <key> lookup lower bound\n" | |
1341 | ") <key> lookup upper bound\n" | |
1342 | "# <num> switch to alternate dictionary (0-9)\n" | |
1343 | "j <num> <num> merge two dictionaries\n" | |
1344 | "f free the whole dictionary\n" | |
1345 | "k allow duplicate keys\n" | |
1346 | "c show number of entries\n" | |
1347 | "t dump whole dictionary in sort order\n" | |
1348 | "m make dictionary out of sorted items\n" | |
1349 | "p turn prompt on\n" | |
1350 | "s switch to non-functioning allocator\n" | |
1351 | "q quit"; | |
1352 | ||
1353 | for (i = 0; i < sizeof darray / sizeof *darray; i++) | |
1354 | dict_init(&darray[i], DICTCOUNT_T_MAX, comparef); | |
1355 | ||
1356 | for (;;) { | |
1357 | if (prompt) | |
1358 | putchar('>'); | |
1359 | fflush(stdout); | |
1360 | ||
1361 | if (!fgets(in, sizeof(input_t), stdin)) | |
1362 | break; | |
1363 | ||
1364 | switch(in[0]) { | |
1365 | case '?': | |
1366 | puts(help); | |
1367 | break; | |
1368 | case 'a': | |
1369 | if (tokenize(in+1, &tok1, &tok2, (char **) 0) != 2) { | |
1370 | puts("what?"); | |
1371 | break; | |
1372 | } | |
1373 | key = dupstring(tok1); | |
1374 | val = dupstring(tok2); | |
eb5d44eb | 1375 | |
ffe543af | 1376 | if (!key || !val) { |
1377 | puts("out of memory"); | |
1378 | free((void *) key); | |
1379 | free(val); | |
1380 | } | |
1381 | ||
1382 | if (!dict_alloc_insert(d, key, val)) { | |
1383 | puts("dict_alloc_insert failed"); | |
1384 | free((void *) key); | |
1385 | free(val); | |
1386 | break; | |
1387 | } | |
1388 | break; | |
1389 | case 'd': | |
1390 | if (tokenize(in+1, &tok1, (char **) 0) != 1) { | |
1391 | puts("what?"); | |
1392 | break; | |
1393 | } | |
1394 | dn = dict_lookup(d, tok1); | |
1395 | if (!dn) { | |
1396 | puts("dict_lookup failed"); | |
1397 | break; | |
1398 | } | |
1399 | val = dnode_get(dn); | |
1400 | key = dnode_getkey(dn); | |
1401 | dict_delete_free(d, dn); | |
1402 | ||
1403 | free(val); | |
1404 | free((void *) key); | |
1405 | break; | |
1406 | case 'f': | |
1407 | dict_free(d); | |
1408 | break; | |
eb5d44eb | 1409 | case 'l': |
1410 | case '(': | |
1411 | case ')': | |
ffe543af | 1412 | if (tokenize(in+1, &tok1, (char **) 0) != 1) { |
1413 | puts("what?"); | |
1414 | break; | |
eb5d44eb | 1415 | } |
ffe543af | 1416 | dn = 0; |
1417 | switch (in[0]) { | |
1418 | case 'l': | |
1419 | dn = dict_lookup(d, tok1); | |
1420 | break; | |
1421 | case '(': | |
1422 | dn = dict_lower_bound(d, tok1); | |
1423 | break; | |
1424 | case ')': | |
1425 | dn = dict_upper_bound(d, tok1); | |
1426 | break; | |
eb5d44eb | 1427 | } |
ffe543af | 1428 | if (!dn) { |
1429 | puts("lookup failed"); | |
1430 | break; | |
1431 | } | |
1432 | val = dnode_get(dn); | |
1433 | puts(val); | |
1434 | break; | |
1435 | case 'm': | |
1436 | construct(d); | |
1437 | break; | |
1438 | case 'k': | |
1439 | dict_allow_dupes(d); | |
1440 | break; | |
1441 | case 'c': | |
1442 | printf("%lu\n", (unsigned long) dict_count(d)); | |
1443 | break; | |
1444 | case 't': | |
1445 | for (dn = dict_first(d); dn; dn = dict_next(d, dn)) { | |
1446 | printf("%s\t%s\n", (char *) dnode_getkey(dn), | |
1447 | (char *) dnode_get(dn)); | |
1448 | } | |
1449 | break; | |
1450 | case 'q': | |
1451 | exit(0); | |
1452 | break; | |
1453 | case '\0': | |
1454 | break; | |
1455 | case 'p': | |
1456 | prompt = 1; | |
1457 | break; | |
1458 | case 's': | |
1459 | dict_set_allocator(d, new_node, del_node, NULL); | |
1460 | break; | |
1461 | case '#': | |
1462 | if (tokenize(in+1, &tok1, (char **) 0) != 1) { | |
1463 | puts("what?"); | |
1464 | break; | |
1465 | } else { | |
1466 | int dictnum = atoi(tok1); | |
1467 | if (dictnum < 0 || dictnum > 9) { | |
1468 | puts("invalid number"); | |
1469 | break; | |
1470 | } | |
1471 | d = &darray[dictnum]; | |
1472 | } | |
1473 | break; | |
1474 | case 'j': | |
1475 | if (tokenize(in+1, &tok1, &tok2, (char **) 0) != 2) { | |
1476 | puts("what?"); | |
1477 | break; | |
1478 | } else { | |
1479 | int dict1 = atoi(tok1), dict2 = atoi(tok2); | |
1480 | if (dict1 < 0 || dict1 > 9 || dict2 < 0 || dict2 > 9) { | |
1481 | puts("invalid number"); | |
1482 | break; | |
1483 | } | |
1484 | dict_merge(&darray[dict1], &darray[dict2]); | |
1485 | } | |
1486 | break; | |
1487 | default: | |
1488 | putchar('?'); | |
1489 | putchar('\n'); | |
1490 | break; | |
eb5d44eb | 1491 | } |
1492 | } | |
1493 | ||
ffe543af | 1494 | return 0; |
eb5d44eb | 1495 | } |
1496 | ||
1497 | #endif |