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