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