Lines Matching refs:dict
144 static void free_nodes(dict_t *dict, dnode_t *node, dnode_t *nil) in free_nodes() argument
148 free_nodes(dict, node->left, nil); in free_nodes()
149 free_nodes(dict, node->right, nil); in free_nodes()
150 dict->freenode(node, dict->context); in free_nodes()
162 static int verify_bintree(dict_t *dict) in verify_bintree() argument
166 first = dict_first(dict); in verify_bintree()
168 if (dict->dupes) { in verify_bintree()
169 while (first && (next = dict_next(dict, first))) { in verify_bintree()
170 if (dict->compare(first->key, next->key) > 0) in verify_bintree()
175 while (first && (next = dict_next(dict, first))) { in verify_bintree()
176 if (dict->compare(first->key, next->key) >= 0) in verify_bintree()
286 void dict_set_allocator(dict_t *dict, dnode_alloc_t al, in dict_set_allocator() argument
289 dict_assert (dict_count(dict) == 0); in dict_set_allocator()
292 dict->allocnode = al ? al : dnode_alloc; in dict_set_allocator()
293 dict->freenode = fr ? fr : dnode_free; in dict_set_allocator()
294 dict->context = context; in dict_set_allocator()
303 void dict_destroy(dict_t *dict) in dict_destroy() argument
305 dict_assert (dict_isempty(dict)); in dict_destroy()
306 free(dict); in dict_destroy()
315 void dict_free_nodes(dict_t *dict) in dict_free_nodes() argument
317 dnode_t *nil = dict_nil(dict), *root = dict_root(dict); in dict_free_nodes()
318 free_nodes(dict, root, nil); in dict_free_nodes()
319 dict->nodecount = 0; in dict_free_nodes()
320 dict->nilnode.left = &dict->nilnode; in dict_free_nodes()
321 dict->nilnode.right = &dict->nilnode; in dict_free_nodes()
328 void dict_free(dict_t *dict) in dict_free() argument
333 dict_free_nodes(dict); in dict_free()
341 dict_t *dict_init(dict_t *dict, dictcount_t maxcount, dict_comp_t comp) in dict_init() argument
343 dict->compare = comp; in dict_init()
344 dict->allocnode = dnode_alloc; in dict_init()
345 dict->freenode = dnode_free; in dict_init()
346 dict->context = NULL; in dict_init()
347 dict->nodecount = 0; in dict_init()
348 dict->maxcount = maxcount; in dict_init()
349 dict->nilnode.left = &dict->nilnode; in dict_init()
350 dict->nilnode.right = &dict->nilnode; in dict_init()
351 dict->nilnode.parent = &dict->nilnode; in dict_init()
352 dict->nilnode.color = dnode_black; in dict_init()
353 dict->dupes = 0; in dict_init()
354 return dict; in dict_init()
362 void dict_init_like(dict_t *dict, const dict_t *template) in dict_init_like() argument
364 dict->compare = template->compare; in dict_init_like()
365 dict->allocnode = template->allocnode; in dict_init_like()
366 dict->freenode = template->freenode; in dict_init_like()
367 dict->context = template->context; in dict_init_like()
368 dict->nodecount = 0; in dict_init_like()
369 dict->maxcount = template->maxcount; in dict_init_like()
370 dict->nilnode.left = &dict->nilnode; in dict_init_like()
371 dict->nilnode.right = &dict->nilnode; in dict_init_like()
372 dict->nilnode.parent = &dict->nilnode; in dict_init_like()
373 dict->nilnode.color = dnode_black; in dict_init_like()
374 dict->dupes = template->dupes; in dict_init_like()
376 dict_assert (dict_similar(dict, template)); in dict_init_like()
383 static void dict_clear(dict_t *dict) in dict_clear() argument
385 dict->nodecount = 0; in dict_clear()
386 dict->nilnode.left = &dict->nilnode; in dict_clear()
387 dict->nilnode.right = &dict->nilnode; in dict_clear()
388 dict->nilnode.parent = &dict->nilnode; in dict_clear()
389 dict_assert (dict->nilnode.color == dnode_black); in dict_clear()
401 int dict_verify(dict_t *dict) in dict_verify() argument
403 dnode_t *nil = dict_nil(dict), *root = dict_root(dict); in dict_verify()
416 if (!verify_bintree(dict)) in dict_verify()
421 if (verify_node_count(nil, root) != dict_count(dict)) in dict_verify()
460 dnode_t *dict_lookup(dict_t *dict, const void *key) in dict_lookup() argument
462 dnode_t *root = dict_root(dict); in dict_lookup()
463 dnode_t *nil = dict_nil(dict); in dict_lookup()
470 result = dict->compare(key, root->key); in dict_lookup()
476 if (!dict->dupes) { /* no duplicates, return match */ in dict_lookup()
482 while (root != nil && dict->compare(key, root->key)) in dict_lookup()
499 dnode_t *dict_lower_bound(dict_t *dict, const void *key) in dict_lower_bound() argument
501 dnode_t *root = dict_root(dict); in dict_lower_bound()
502 dnode_t *nil = dict_nil(dict); in dict_lower_bound()
506 int result = dict->compare(key, root->key); in dict_lower_bound()
514 if (!dict->dupes) { in dict_lower_bound()
531 dnode_t *dict_upper_bound(dict_t *dict, const void *key) in dict_upper_bound() argument
533 dnode_t *root = dict_root(dict); in dict_upper_bound()
534 dnode_t *nil = dict_nil(dict); in dict_upper_bound()
538 int result = dict->compare(key, root->key); in dict_upper_bound()
546 if (!dict->dupes) { in dict_upper_bound()
567 void dict_insert(dict_t *dict, dnode_t *node, const void *key) in dict_insert() argument
569 dnode_t *where = dict_root(dict), *nil = dict_nil(dict); in dict_insert()
575 dict_assert (!dict_isfull(dict)); in dict_insert()
576 dict_assert (!dict_contains(dict, node)); in dict_insert()
583 result = dict->compare(key, where->key); in dict_insert()
585 dict_assert (dict->dupes || result != 0); in dict_insert()
603 dict->nodecount++; in dict_insert()
653 dict_root(dict)->color = dnode_black; in dict_insert()
655 dict_assert (dict_verify(dict)); in dict_insert()
665 dnode_t *dict_delete(dict_t *dict, dnode_t *delete) in dict_delete() argument
667 dnode_t *nil = dict_nil(dict), *child, *delparent = delete->parent; in dict_delete()
671 dict_assert (!dict_isempty(dict)); in dict_delete()
672 dict_assert (dict_contains(dict, delete)); in dict_delete()
687 dnode_t *next = dict_next(dict, delete); in dict_delete()
750 dict->nodecount--; in dict_delete()
752 dict_assert (verify_bintree(dict)); in dict_delete()
759 dict_root(dict)->color = dnode_red; in dict_delete()
826 dict_root(dict)->color = dnode_black; in dict_delete()
829 dict_assert (dict_verify(dict)); in dict_delete()
840 int dict_alloc_insert(dict_t *dict, const void *key, void *data) in dict_alloc_insert() argument
842 dnode_t *node = dict->allocnode(dict->context); in dict_alloc_insert()
846 dict_insert(dict, node, key); in dict_alloc_insert()
853 void dict_delete_free(dict_t *dict, dnode_t *node) in dict_delete_free() argument
855 dict_delete(dict, node); in dict_delete_free()
856 dict->freenode(node, dict->context); in dict_delete_free()
865 dnode_t *dict_first(dict_t *dict) in dict_first() argument
867 dnode_t *nil = dict_nil(dict), *root = dict_root(dict), *left; in dict_first()
881 dnode_t *dict_last(dict_t *dict) in dict_last() argument
883 dnode_t *nil = dict_nil(dict), *root = dict_root(dict), *right; in dict_last()
899 dnode_t *dict_next(dict_t *dict, dnode_t *curr) in dict_next() argument
901 dnode_t *nil = dict_nil(dict), *parent, *left; in dict_next()
925 dnode_t *dict_prev(dict_t *dict, dnode_t *curr) in dict_prev() argument
927 dnode_t *nil = dict_nil(dict), *parent, *right; in dict_prev()
946 void dict_allow_dupes(dict_t *dict) in dict_allow_dupes() argument
948 dict->dupes = 1; in dict_allow_dupes()
958 dictcount_t dict_count(dict_t *dict) in dict_count() argument
960 return dict->nodecount; in dict_count()
963 int dict_isempty(dict_t *dict) in dict_isempty() argument
965 return dict->nodecount == 0; in dict_isempty()
968 int dict_isfull(dict_t *dict) in dict_isfull() argument
970 return dict->nodecount == dict->maxcount; in dict_isfull()
973 int dict_contains(dict_t *dict, dnode_t *node) in dict_contains() argument
975 return verify_dict_has_node(dict_nil(dict), dict_root(dict), node); in dict_contains()
1040 void dict_process(dict_t *dict, void *context, dnode_process_t function) in dict_process() argument
1042 dnode_t *node = dict_first(dict), *next; in dict_process()
1047 dict_assert (dict_contains(dict, node)); in dict_process()
1048 next = dict_next(dict, node); in dict_process()
1049 function(dict, node, context); in dict_process()
1054 static void load_begin_internal(dict_load_t *load, dict_t *dict) in load_begin_internal() argument
1056 load->dictptr = dict; in load_begin_internal()
1061 void dict_load_begin(dict_load_t *load, dict_t *dict) in dict_load_begin() argument
1063 dict_assert (dict_isempty(dict)); in dict_load_begin()
1064 load_begin_internal(load, dict); in dict_load_begin()
1069 dict_t *dict = load->dictptr; in dict_load_next() local
1073 dict_assert (dict->nodecount < dict->maxcount); in dict_load_next()
1076 if (dict->nodecount > 0) { in dict_load_next()
1077 if (dict->dupes) in dict_load_next()
1078 dict_assert (dict->compare(nil->left->key, key) <= 0); in dict_load_next()
1080 dict_assert (dict->compare(nil->left->key, key) < 0); in dict_load_next()
1088 dict->nodecount++; in dict_load_next()
1093 dict_t *dict = load->dictptr; in dict_load_end() local
1095 dnode_t *curr, *dictnil = dict_nil(dict), *loadnil = &load->nilnode, *next; in dict_load_end()
1097 dictcount_t fullcount = DICTCOUNT_T_MAX, nodecount = dict->nodecount; in dict_load_end()
1167 dict_root(dict) = complete; in dict_load_end()
1169 dict_assert (dict_verify(dict)); in dict_load_end()