Cross Reference: /external/e2fsprogs/lib/support/dict.c

Lines Matching refs:dict
17  * $Id: dict.c,v 1.40.2.7 2000/11/13 01:36:44 kaz Exp $
39 #include "dict.h"
42 static const char rcsid[] = "$Id: dict.c,v 1.40.2.7 2000/11/13 01:36:44 kaz Exp $";
49  * program which uses dict to define, for instance, a macro called ``parent''.
144 static void free_nodes(dict_t *dict, dnode_t *node, dnode_t *nil)
148     free_nodes(dict, node->left, nil);
149     free_nodes(dict, node->right, nil);
150     dict->freenode(node, dict->context);
162 static int verify_bintree(dict_t *dict)
166     first = dict_first(dict);
168     if (dict->dupes) {
169 	while (first && (next = dict_next(dict, first))) {
170 	    if (dict->compare(first->key, next->key) > 0)
175 	while (first && (next = dict_next(dict, first))) {
176 	    if (dict->compare(first->key, next->key) >= 0)
286 void dict_set_allocator(dict_t *dict, dnode_alloc_t al,
289     dict_assert (dict_count(dict) == 0);
292     dict->allocnode = al ? al : dnode_alloc;
293     dict->freenode = fr ? fr : dnode_free;
294     dict->context = context;
303 void dict_destroy(dict_t *dict)
305     dict_assert (dict_isempty(dict));
306     free(dict);
315 void dict_free_nodes(dict_t *dict)
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;
328 void dict_free(dict_t *dict)
333     dict_free_nodes(dict);
341 dict_t *dict_init(dict_t *dict, dictcount_t maxcount, dict_comp_t comp)
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;
362 void dict_init_like(dict_t *dict, const dict_t *template)
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;
376     dict_assert (dict_similar(dict, template));
383 static void dict_clear(dict_t *dict)
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);
401 int dict_verify(dict_t *dict)
403     dnode_t *nil = dict_nil(dict), *root = dict_root(dict);
416     if (!verify_bintree(dict))
421     if (verify_node_count(nil, root) != dict_count(dict))
460 dnode_t *dict_lookup(dict_t *dict, const void *key)
462     dnode_t *root = dict_root(dict);
463     dnode_t *nil = dict_nil(dict);
470 	result = dict->compare(key, root->key);
476 	    if (!dict->dupes) {	/* no duplicates, return match		*/
482 		    while (root != nil && dict->compare(key, root->key))
499 dnode_t *dict_lower_bound(dict_t *dict, const void *key)
501     dnode_t *root = dict_root(dict);
502     dnode_t *nil = dict_nil(dict);
506 	int result = dict->compare(key, root->key);
514 	    if (!dict->dupes) {
531 dnode_t *dict_upper_bound(dict_t *dict, const void *key)
533     dnode_t *root = dict_root(dict);
534     dnode_t *nil = dict_nil(dict);
538 	int result = dict->compare(key, root->key);
546 	    if (!dict->dupes) {
567 void dict_insert(dict_t *dict, dnode_t *node, const void *key)
569     dnode_t *where = dict_root(dict), *nil = dict_nil(dict);
575     dict_assert (!dict_isfull(dict));
576     dict_assert (!dict_contains(dict, node));
583 	result = dict->compare(key, where->key);
585 	dict_assert (dict->dupes || result != 0);
603     dict->nodecount++;
653     dict_root(dict)->color = dnode_black;
655     dict_assert (dict_verify(dict));
665 dnode_t *dict_delete(dict_t *dict, dnode_t *delete)
667     dnode_t *nil = dict_nil(dict), *child, *delparent = delete->parent;
671     dict_assert (!dict_isempty(dict));
672     dict_assert (dict_contains(dict, delete));
687 	dnode_t *next = dict_next(dict, delete);
750     dict->nodecount--;
752     dict_assert (verify_bintree(dict));
759 	dict_root(dict)->color = dnode_red;
826 	dict_root(dict)->color = dnode_black;
829     dict_assert (dict_verify(dict));
840 int dict_alloc_insert(dict_t *dict, const void *key, void *data)
842     dnode_t *node = dict->allocnode(dict->context);
846 	dict_insert(dict, node, key);
853 void dict_delete_free(dict_t *dict, dnode_t *node)
855     dict_delete(dict, node);
856     dict->freenode(node, dict->context);
862  * (that is, dict_isempty(dict) returns 1) a null pointer is returned.
865 dnode_t *dict_first(dict_t *dict)
867     dnode_t *nil = dict_nil(dict), *root = dict_root(dict), *left;
878  * (that is, dict_isempty(dict) returns 1) a null pointer is returned.
881 dnode_t *dict_last(dict_t *dict)
883     dnode_t *nil = dict_nil(dict), *root = dict_root(dict), *right;
899 dnode_t *dict_next(dict_t *dict, dnode_t *curr)
901     dnode_t *nil = dict_nil(dict), *parent, *left;
925 dnode_t *dict_prev(dict_t *dict, dnode_t *curr)
927     dnode_t *nil = dict_nil(dict), *parent, *right;
946 void dict_allow_dupes(dict_t *dict)
948     dict->dupes = 1;
958 dictcount_t dict_count(dict_t *dict)
960     return dict->nodecount;
963 int dict_isempty(dict_t *dict)
965     return dict->nodecount == 0;
968 int dict_isfull(dict_t *dict)
970     return dict->nodecount == dict->maxcount;
973 int dict_contains(dict_t *dict, dnode_t *node)
975     return verify_dict_has_node(dict_nil(dict), dict_root(dict), node);
1040 void dict_process(dict_t *dict, void *context, dnode_process_t function)
1042     dnode_t *node = dict_first(dict), *next;
1047 	dict_assert (dict_contains(dict, node));
1048 	next = dict_next(dict, node);
1049 	function(dict, node, context);
1054 static void load_begin_internal(dict_load_t *load, dict_t *dict)
1056     load->dictptr = dict;
1061 void dict_load_begin(dict_load_t *load, dict_t *dict)
1063     dict_assert (dict_isempty(dict));
1064     load_begin_internal(load, dict);
1069     dict_t *dict = load->dictptr;
1073     dict_assert (dict->nodecount < dict->maxcount);
1076     if (dict->nodecount > 0) {
1077 	if (dict->dupes)
1078 	    dict_assert (dict->compare(nil->left->key, key) <= 0);
1080 	    dict_assert (dict->compare(nil->left->key, key) < 0);
1088     dict->nodecount++;
1093     dict_t *dict = load->dictptr;
1095     dnode_t *curr, *dictnil = dict_nil(dict), *loadnil = &load->nilnode, *next;
1097     dictcount_t fullcount = DICTCOUNT_T_MAX, nodecount = dict->nodecount;
1167     dict_root(dict) = complete;
1169     dict_assert (dict_verify(dict));