xref: /third_party/f2fs-tools/fsck/dict.c

17  * $Id: dict.c,v 1.40.2.7 2000/11/13 01:36:44 kaz Exp $
32 #include "dict.h"
36 static const char rcsid[] = "$Id: dict.c,v 1.40.2.7 2000/11/13 01:36:44 kaz Exp $";
43  * program which uses dict to define, for instance, a macro called ``parent''.
135 static void free_nodes(dict_t *dict, dnode_t *node, dnode_t *nil)
139 	free_nodes(dict, node->left, nil);
140 	free_nodes(dict, node->right, nil);
141 	dict->freenode(node, dict->context);
153 static int verify_bintree(dict_t *dict)
157 	first = dict_first(dict);
159 	if (dict->dupes) {
160 		while (first && (next = dict_next(dict, first))) {
161 			if (dict->compare(first->key, next->key) > 0)
166 		while (first && (next = dict_next(dict, first))) {
167 			if (dict->compare(first->key, next->key) >= 0)
271 void dict_set_allocator(dict_t *dict, dnode_alloc_t al,
274 	dict_assert(dict_count(dict) == 0);
277 	dict->allocnode = al ? al : dnode_alloc;
278 	dict->freenode = fr ? fr : dnode_free;
279 	dict->context = context;
287 void dict_destroy(dict_t *dict)
289 	dict_assert(dict_isempty(dict));
290 	free(dict);
298 void dict_free_nodes(dict_t *dict)
300 	dnode_t *nil = dict_nil(dict), *root = dict_root(dict);
301 	free_nodes(dict, root, nil);
302 	dict->nodecount = 0;
303 	dict->nilnode.left = &dict->nilnode;
304 	dict->nilnode.right = &dict->nilnode;
311 void dict_free(dict_t *dict)
316 	dict_free_nodes(dict);
323 dict_t *dict_init(dict_t *dict, dictcount_t maxcount, dict_comp_t comp)
325 	dict->compare = comp;
326 	dict->allocnode = dnode_alloc;
327 	dict->freenode = dnode_free;
328 	dict->context = NULL;
329 	dict->nodecount = 0;
330 	dict->maxcount = maxcount;
331 	dict->nilnode.left = &dict->nilnode;
332 	dict->nilnode.right = &dict->nilnode;
333 	dict->nilnode.parent = &dict->nilnode;
334 	dict->nilnode.color = dnode_black;
335 	dict->dupes = 0;
336 	return dict;
343 void dict_init_like(dict_t *dict, const dict_t *template)
345 	dict->compare = template->compare;
346 	dict->allocnode = template->allocnode;
347 	dict->freenode = template->freenode;
348 	dict->context = template->context;
349 	dict->nodecount = 0;
350 	dict->maxcount = template->maxcount;
351 	dict->nilnode.left = &dict->nilnode;
352 	dict->nilnode.right = &dict->nilnode;
353 	dict->nilnode.parent = &dict->nilnode;
354 	dict->nilnode.color = dnode_black;
355 	dict->dupes = template->dupes;
357 	dict_assert(dict_similar(dict, template));
363 static void dict_clear(dict_t *dict)
365 	dict->nodecount = 0;
366 	dict->nilnode.left = &dict->nilnode;
367 	dict->nilnode.right = &dict->nilnode;
368 	dict->nilnode.parent = &dict->nilnode;
369 	dict_assert(dict->nilnode.color == dnode_black);
380 int dict_verify(dict_t *dict)
382 	dnode_t *nil = dict_nil(dict), *root = dict_root(dict);
395 	if (!verify_bintree(dict))
400 	if (verify_node_count(nil, root) != dict_count(dict))
438 dnode_t *dict_lookup(dict_t *dict, const void *key)
440 	dnode_t *root = dict_root(dict);
441 	dnode_t *nil = dict_nil(dict);
448 		result = dict->compare(key, root->key);
454 			if (!dict->dupes) {	/* no duplicates, return match		*/
460 					while (root != nil && dict->compare(key, root->key))
476 dnode_t *dict_lower_bound(dict_t *dict, const void *key)
478 	dnode_t *root = dict_root(dict);
479 	dnode_t *nil = dict_nil(dict);
483 		int result = dict->compare(key, root->key);
491 			if (!dict->dupes) {
507 dnode_t *dict_upper_bound(dict_t *dict, const void *key)
509 	dnode_t *root = dict_root(dict);
510 	dnode_t *nil = dict_nil(dict);
514 		int result = dict->compare(key, root->key);
522 			if (!dict->dupes) {
542 void dict_insert(dict_t *dict, dnode_t *node, const void *key)
544 	dnode_t *where = dict_root(dict), *nil = dict_nil(dict);
550 	dict_assert(!dict_isfull(dict));
551 	dict_assert(!dict_contains(dict, node));
558 		result = dict->compare(key, where->key);
560 		dict_assert(dict->dupes || result != 0);
578 	dict->nodecount++;
628 	dict_root(dict)->color = dnode_black;
630 	dict_assert(dict_verify(dict));
639 dnode_t *dict_delete(dict_t *dict, dnode_t *delete)
641 	dnode_t *nil = dict_nil(dict), *child, *delparent = delete->parent;
645 	dict_assert(!dict_isempty(dict));
646 	dict_assert(dict_contains(dict, delete));
661 		dnode_t *next = dict_next(dict, delete);
724 	dict->nodecount--;
726 	dict_assert(verify_bintree(dict));
733 		dict_root(dict)->color = dnode_red;
800 		dict_root(dict)->color = dnode_black;
803 	dict_assert(dict_verify(dict));
813 int dict_alloc_insert(dict_t *dict, const void *key, void *data)
815 	dnode_t *node = dict->allocnode(dict->context);
819 		dict_insert(dict, node, key);
826 void dict_delete_free(dict_t *dict, dnode_t *node)
828 	dict_delete(dict, node);
829 	dict->freenode(node, dict->context);
835  * (that is, dict_isempty(dict) returns 1) a null pointer is returned.
837 dnode_t *dict_first(dict_t *dict)
839 	dnode_t *nil = dict_nil(dict), *root = dict_root(dict), *left;
850  * (that is, dict_isempty(dict) returns 1) a null pointer is returned.
852 dnode_t *dict_last(dict_t *dict)
854 	dnode_t *nil = dict_nil(dict), *root = dict_root(dict), *right;
869 dnode_t *dict_next(dict_t *dict, dnode_t *curr)
871 	dnode_t *nil = dict_nil(dict), *parent, *left;
894 dnode_t *dict_prev(dict_t *dict, dnode_t *curr)
896 	dnode_t *nil = dict_nil(dict), *parent, *right;
915 void dict_allow_dupes(dict_t *dict)
917 	dict->dupes = 1;
927 dictcount_t dict_count(dict_t *dict)
929 	return dict->nodecount;
932 int dict_isempty(dict_t *dict)
934 	return dict->nodecount == 0;
937 int dict_isfull(dict_t *dict)
939 	return dict->nodecount == dict->maxcount;
942 int dict_contains(dict_t *dict, dnode_t *node)
944 	return verify_dict_has_node(dict_nil(dict), dict_root(dict), node);
1009 void dict_process(dict_t *dict, void *context, dnode_process_t function)
1011 	dnode_t *node = dict_first(dict), *next;
1016 		dict_assert(dict_contains(dict, node));
1017 		next = dict_next(dict, node);
1018 		function(dict, node, context);
1023 static void load_begin_internal(dict_load_t *load, dict_t *dict)
1025 	load->dictptr = dict;
1030 void dict_load_begin(dict_load_t *load, dict_t *dict)
1032 	dict_assert(dict_isempty(dict));
1033 	load_begin_internal(load, dict);
1038 	dict_t *dict = load->dictptr;
1042 	dict_assert(dict->nodecount < dict->maxcount);
1045 	if (dict->nodecount > 0) {
1046 		if (dict->dupes)
1047 			dict_assert(dict->compare(nil->left->key, key) <= 0);
1049 			dict_assert(dict->compare(nil->left->key, key) < 0);
1057 	dict->nodecount++;
1062 	dict_t *dict = load->dictptr;
1064 	dnode_t *curr, *dictnil = dict_nil(dict), *loadnil = &load->nilnode, *next;
1066 	dictcount_t fullcount = DICTCOUNT_T_MAX, nodecount = dict->nodecount;
1136 	dict_root(dict) = complete;
1138 	dict_assert(dict_verify(dict));

Indexes created Thu Nov 07 10:32:03 CST 2024