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