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