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