Lines Matching refs:dict
17 * $Id: dict.c,v 1.40.2.7 2000/11/13 01:36:44 kaz Exp $
33 #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''.
138 static void free_nodes(dict_t *dict, dnode_t *node, dnode_t *nil)
142 free_nodes(dict, node->left, nil);
143 free_nodes(dict, node->right, nil);
144 dict->freenode(node, dict->context);
156 static int verify_bintree(dict_t *dict)
160 first = dict_first(dict);
162 if (dict->dupes) {
163 while (first && (next = dict_next(dict, first))) {
164 if (dict->compare(first->key, next->key) > 0)
169 while (first && (next = dict_next(dict, first))) {
170 if (dict->compare(first->key, next->key) >= 0)
280 void dict_set_allocator(dict_t *dict, dnode_alloc_t al,
283 assert (dict_count(dict) == 0);
286 dict->allocnode = al ? al : dnode_alloc;
287 dict->freenode = fr ? fr : dnode_free;
288 dict->context = context;
297 void dict_destroy(dict_t *dict)
299 assert (dict_isempty(dict));
300 free(dict);
309 void dict_free_nodes(dict_t *dict)
311 dnode_t *nil = dict_nil(dict), *root = dict_root(dict);
312 free_nodes(dict, root, nil);
313 dict->nodecount = 0;
314 dict->nilnode.left = &dict->nilnode;
315 dict->nilnode.right = &dict->nilnode;
322 void dict_free(dict_t *dict)
327 dict_free_nodes(dict);
335 dict_t *dict_init(dict_t *dict, dictcount_t maxcount, dict_comp_t comp)
337 dict->compare = comp;
338 dict->allocnode = dnode_alloc;
339 dict->freenode = dnode_free;
340 dict->context = NULL;
341 dict->nodecount = 0;
342 dict->maxcount = maxcount;
343 dict->nilnode.left = &dict->nilnode;
344 dict->nilnode.right = &dict->nilnode;
345 dict->nilnode.parent = &dict->nilnode;
346 dict->nilnode.color = dnode_black;
347 dict->dupes = 0;
348 return dict;
356 void dict_init_like(dict_t *dict, const dict_t *template)
358 dict->compare = template->compare;
359 dict->allocnode = template->allocnode;
360 dict->freenode = template->freenode;
361 dict->context = template->context;
362 dict->nodecount = 0;
363 dict->maxcount = template->maxcount;
364 dict->nilnode.left = &dict->nilnode;
365 dict->nilnode.right = &dict->nilnode;
366 dict->nilnode.parent = &dict->nilnode;
367 dict->nilnode.color = dnode_black;
368 dict->dupes = template->dupes;
370 assert (dict_similar(dict, template));
377 static void dict_clear(dict_t *dict)
379 dict->nodecount = 0;
380 dict->nilnode.left = &dict->nilnode;
381 dict->nilnode.right = &dict->nilnode;
382 dict->nilnode.parent = &dict->nilnode;
383 assert (dict->nilnode.color == dnode_black);
394 int dict_verify(dict_t *dict)
397 dnode_t *nil = dict_nil(dict), *root = dict_root(dict);
410 if (!verify_bintree(dict))
415 if (verify_node_count(nil, root) != dict_count(dict))
454 dnode_t *dict_lookup(dict_t *dict, const void *key)
456 dnode_t *root = dict_root(dict);
457 dnode_t *nil = dict_nil(dict);
464 result = dict->compare(key, root->key);
470 if (!dict->dupes) { /* no duplicates, return match */
476 while (root != nil && dict->compare(key, root->key))
493 dnode_t *dict_lower_bound(dict_t *dict, const void *key)
495 dnode_t *root = dict_root(dict);
496 dnode_t *nil = dict_nil(dict);
500 int result = dict->compare(key, root->key);
508 if (!dict->dupes) {
525 dnode_t *dict_upper_bound(dict_t *dict, const void *key)
527 dnode_t *root = dict_root(dict);
528 dnode_t *nil = dict_nil(dict);
532 int result = dict->compare(key, root->key);
540 if (!dict->dupes) {
561 void dict_insert(dict_t *dict, dnode_t *node, const void *key)
563 dnode_t *where = dict_root(dict), *nil = dict_nil(dict);
569 assert (!dict_isfull(dict));
570 assert (!dict_contains(dict, node));
577 result = dict->compare(key, where->key);
579 assert (dict->dupes || result != 0);
597 dict->nodecount++;
647 dict_root(dict)->color = dnode_black;
649 assert (dict_verify(dict));
659 dnode_t *dict_delete(dict_t *dict, dnode_t *delete)
661 dnode_t *nil = dict_nil(dict), *child, *delparent = delete->parent;
665 assert (!dict_isempty(dict));
666 assert (dict_contains(dict, delete));
681 dnode_t *next = dict_next(dict, delete);
744 dict->nodecount--;
746 assert (verify_bintree(dict));
753 dict_root(dict)->color = dnode_red;
820 dict_root(dict)->color = dnode_black;
823 assert (dict_verify(dict));
834 int dict_alloc_insert(dict_t *dict, const void *key, void *data)
836 dnode_t *node = dict->allocnode(dict->context);
840 dict_insert(dict, node, key);
847 void dict_delete_free(dict_t *dict, dnode_t *node)
849 dict_delete(dict, node);
850 dict->freenode(node, dict->context);
856 * (that is, dict_isempty(dict) returns 1) a null pointer is returned.
859 dnode_t *dict_first(dict_t *dict)
861 dnode_t *nil = dict_nil(dict), *root = dict_root(dict), *left;
872 * (that is, dict_isempty(dict) returns 1) a null pointer is returned.
875 dnode_t *dict_last(dict_t *dict)
877 dnode_t *nil = dict_nil(dict), *root = dict_root(dict), *right;
893 dnode_t *dict_next(dict_t *dict, dnode_t *curr)
895 dnode_t *nil = dict_nil(dict), *parent, *left;
919 dnode_t *dict_prev(dict_t *dict, dnode_t *curr)
921 dnode_t *nil = dict_nil(dict), *parent, *right;
940 void dict_allow_dupes(dict_t *dict)
942 dict->dupes = 1;
952 dictcount_t dict_count(dict_t *dict)
954 return dict->nodecount;
957 int dict_isempty(dict_t *dict)
959 return dict->nodecount == 0;
962 int dict_isfull(dict_t *dict)
964 return dict->nodecount == dict->maxcount;
967 int dict_contains(dict_t *dict, dnode_t *node)
969 return verify_dict_has_node(dict_nil(dict), dict_root(dict), node);
1030 void dict_process(dict_t *dict, void *context, dnode_process_t function)
1032 dnode_t *node = dict_first(dict), *next;
1037 assert (dict_contains(dict, node));
1038 next = dict_next(dict, node);
1039 function(dict, node, context);
1044 static void load_begin_internal(dict_load_t *load, dict_t *dict)
1046 load->dictptr = dict;
1051 void dict_load_begin(dict_load_t *load, dict_t *dict)
1053 assert (dict_isempty(dict));
1054 load_begin_internal(load, dict);
1059 dict_t *dict = load->dictptr;
1063 assert (dict->nodecount < dict->maxcount);
1066 if (dict->nodecount > 0) {
1067 if (dict->dupes)
1068 assert (dict->compare(nil->left->key, key) <= 0);
1070 assert (dict->compare(nil->left->key, key) < 0);
1078 dict->nodecount++;
1083 dict_t *dict = load->dictptr;
1085 dnode_t *curr, *dictnil = dict_nil(dict), *loadnil = &load->nilnode, *next;
1087 dictcount_t fullcount = DICTCOUNT_T_MAX, nodecount = dict->nodecount;
1157 dict_root(dict) = complete;
1159 assert (dict_verify(dict));
