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