• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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