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