Lines Matching refs:dict
136 static void free_nodes(dict_t *dict, dnode_t *node, dnode_t *nil) in free_nodes() argument
140 free_nodes(dict, node->left, nil); in free_nodes()
141 free_nodes(dict, node->right, nil); in free_nodes()
142 dict->freenode(node, dict->context); in free_nodes()
154 static int verify_bintree(dict_t *dict) in verify_bintree() argument
158 first = dict_first(dict); in verify_bintree()
160 if (dict->dupes) { in verify_bintree()
161 while (first && (next = dict_next(dict, first))) { in verify_bintree()
162 if (dict->compare(first->key, next->key) > 0) in verify_bintree()
167 while (first && (next = dict_next(dict, first))) { in verify_bintree()
168 if (dict->compare(first->key, next->key) >= 0) in verify_bintree()
272 void dict_set_allocator(dict_t *dict, dnode_alloc_t al, in dict_set_allocator() argument
275 dict_assert(dict_count(dict) == 0); in dict_set_allocator()
278 dict->allocnode = al ? al : dnode_alloc; in dict_set_allocator()
279 dict->freenode = fr ? fr : dnode_free; in dict_set_allocator()
280 dict->context = context; in dict_set_allocator()
288 void dict_destroy(dict_t *dict) in dict_destroy() argument
290 dict_assert(dict_isempty(dict)); in dict_destroy()
291 free(dict); in dict_destroy()
299 void dict_free_nodes(dict_t *dict) in dict_free_nodes() argument
301 dnode_t *nil = dict_nil(dict), *root = dict_root(dict); in dict_free_nodes()
302 free_nodes(dict, root, nil); in dict_free_nodes()
303 dict->nodecount = 0; in dict_free_nodes()
304 dict->nilnode.left = &dict->nilnode; in dict_free_nodes()
305 dict->nilnode.right = &dict->nilnode; in dict_free_nodes()
312 void dict_free(dict_t *dict) in dict_free() argument
317 dict_free_nodes(dict); in dict_free()
324 dict_t *dict_init(dict_t *dict, dictcount_t maxcount, dict_comp_t comp) in dict_init() argument
326 dict->compare = comp; in dict_init()
327 dict->allocnode = dnode_alloc; in dict_init()
328 dict->freenode = dnode_free; in dict_init()
329 dict->context = NULL; in dict_init()
330 dict->nodecount = 0; in dict_init()
331 dict->maxcount = maxcount; in dict_init()
332 dict->nilnode.left = &dict->nilnode; in dict_init()
333 dict->nilnode.right = &dict->nilnode; in dict_init()
334 dict->nilnode.parent = &dict->nilnode; in dict_init()
335 dict->nilnode.color = dnode_black; in dict_init()
336 dict->dupes = 0; in dict_init()
337 return dict; in dict_init()
344 void dict_init_like(dict_t *dict, const dict_t *template) in dict_init_like() argument
346 dict->compare = template->compare; in dict_init_like()
347 dict->allocnode = template->allocnode; in dict_init_like()
348 dict->freenode = template->freenode; in dict_init_like()
349 dict->context = template->context; in dict_init_like()
350 dict->nodecount = 0; in dict_init_like()
351 dict->maxcount = template->maxcount; in dict_init_like()
352 dict->nilnode.left = &dict->nilnode; in dict_init_like()
353 dict->nilnode.right = &dict->nilnode; in dict_init_like()
354 dict->nilnode.parent = &dict->nilnode; in dict_init_like()
355 dict->nilnode.color = dnode_black; in dict_init_like()
356 dict->dupes = template->dupes; in dict_init_like()
358 dict_assert(dict_similar(dict, template)); in dict_init_like()
364 static void dict_clear(dict_t *dict) in dict_clear() argument
366 dict->nodecount = 0; in dict_clear()
367 dict->nilnode.left = &dict->nilnode; in dict_clear()
368 dict->nilnode.right = &dict->nilnode; in dict_clear()
369 dict->nilnode.parent = &dict->nilnode; in dict_clear()
370 dict_assert(dict->nilnode.color == dnode_black); in dict_clear()
381 int dict_verify(dict_t *dict) in dict_verify() argument
383 dnode_t *nil = dict_nil(dict), *root = dict_root(dict); in dict_verify()
396 if (!verify_bintree(dict)) in dict_verify()
401 if (verify_node_count(nil, root) != dict_count(dict)) in dict_verify()
439 dnode_t *dict_lookup(dict_t *dict, const void *key) in dict_lookup() argument
441 dnode_t *root = dict_root(dict); in dict_lookup()
442 dnode_t *nil = dict_nil(dict); in dict_lookup()
449 result = dict->compare(key, root->key); in dict_lookup()
455 if (!dict->dupes) { /* no duplicates, return match */ in dict_lookup()
461 while (root != nil && dict->compare(key, root->key)) in dict_lookup()
477 dnode_t *dict_lower_bound(dict_t *dict, const void *key) in dict_lower_bound() argument
479 dnode_t *root = dict_root(dict); in dict_lower_bound()
480 dnode_t *nil = dict_nil(dict); in dict_lower_bound()
484 int result = dict->compare(key, root->key); in dict_lower_bound()
492 if (!dict->dupes) { in dict_lower_bound()
508 dnode_t *dict_upper_bound(dict_t *dict, const void *key) in dict_upper_bound() argument
510 dnode_t *root = dict_root(dict); in dict_upper_bound()
511 dnode_t *nil = dict_nil(dict); in dict_upper_bound()
515 int result = dict->compare(key, root->key); in dict_upper_bound()
523 if (!dict->dupes) { in dict_upper_bound()
543 void dict_insert(dict_t *dict, dnode_t *node, const void *key) in dict_insert() argument
545 dnode_t *where = dict_root(dict), *nil = dict_nil(dict); in dict_insert()
551 dict_assert(!dict_isfull(dict)); in dict_insert()
552 dict_assert(!dict_contains(dict, node)); in dict_insert()
559 result = dict->compare(key, where->key); in dict_insert()
561 dict_assert(dict->dupes || result != 0); in dict_insert()
579 dict->nodecount++; in dict_insert()
629 dict_root(dict)->color = dnode_black; in dict_insert()
631 dict_assert(dict_verify(dict)); in dict_insert()
640 dnode_t *dict_delete(dict_t *dict, dnode_t *delete) in dict_delete() argument
642 dnode_t *nil = dict_nil(dict), *child, *delparent = delete->parent; in dict_delete()
646 dict_assert(!dict_isempty(dict)); in dict_delete()
647 dict_assert(dict_contains(dict, delete)); in dict_delete()
662 dnode_t *next = dict_next(dict, delete); in dict_delete()
725 dict->nodecount--; in dict_delete()
727 dict_assert(verify_bintree(dict)); in dict_delete()
734 dict_root(dict)->color = dnode_red; in dict_delete()
801 dict_root(dict)->color = dnode_black; in dict_delete()
804 dict_assert(dict_verify(dict)); in dict_delete()
814 int dict_alloc_insert(dict_t *dict, const void *key, void *data) in dict_alloc_insert() argument
816 dnode_t *node = dict->allocnode(dict->context); in dict_alloc_insert()
820 dict_insert(dict, node, key); in dict_alloc_insert()
827 void dict_delete_free(dict_t *dict, dnode_t *node) in dict_delete_free() argument
829 dict_delete(dict, node); in dict_delete_free()
830 dict->freenode(node, dict->context); in dict_delete_free()
838 dnode_t *dict_first(dict_t *dict) in dict_first() argument
840 dnode_t *nil = dict_nil(dict), *root = dict_root(dict), *left; in dict_first()
853 dnode_t *dict_last(dict_t *dict) in dict_last() argument
855 dnode_t *nil = dict_nil(dict), *root = dict_root(dict), *right; in dict_last()
870 dnode_t *dict_next(dict_t *dict, dnode_t *curr) in dict_next() argument
872 dnode_t *nil = dict_nil(dict), *parent, *left; in dict_next()
895 dnode_t *dict_prev(dict_t *dict, dnode_t *curr) in dict_prev() argument
897 dnode_t *nil = dict_nil(dict), *parent, *right; in dict_prev()
916 void dict_allow_dupes(dict_t *dict) in dict_allow_dupes() argument
918 dict->dupes = 1; in dict_allow_dupes()
928 dictcount_t dict_count(dict_t *dict) in dict_count() argument
930 return dict->nodecount; in dict_count()
933 int dict_isempty(dict_t *dict) in dict_isempty() argument
935 return dict->nodecount == 0; in dict_isempty()
938 int dict_isfull(dict_t *dict) in dict_isfull() argument
940 return dict->nodecount == dict->maxcount; in dict_isfull()
943 int dict_contains(dict_t *dict, dnode_t *node) in dict_contains() argument
945 return verify_dict_has_node(dict_nil(dict), dict_root(dict), node); in dict_contains()
1010 void dict_process(dict_t *dict, void *context, dnode_process_t function) in dict_process() argument
1012 dnode_t *node = dict_first(dict), *next; in dict_process()
1017 dict_assert(dict_contains(dict, node)); in dict_process()
1018 next = dict_next(dict, node); in dict_process()
1019 function(dict, node, context); in dict_process()
1024 static void load_begin_internal(dict_load_t *load, dict_t *dict) in load_begin_internal() argument
1026 load->dictptr = dict; in load_begin_internal()
1031 void dict_load_begin(dict_load_t *load, dict_t *dict) in dict_load_begin() argument
1033 dict_assert(dict_isempty(dict)); in dict_load_begin()
1034 load_begin_internal(load, dict); in dict_load_begin()
1039 dict_t *dict = load->dictptr; in dict_load_next() local
1043 dict_assert(dict->nodecount < dict->maxcount); in dict_load_next()
1046 if (dict->nodecount > 0) { in dict_load_next()
1047 if (dict->dupes) in dict_load_next()
1048 dict_assert(dict->compare(nil->left->key, key) <= 0); in dict_load_next()
1050 dict_assert(dict->compare(nil->left->key, key) < 0); in dict_load_next()
1058 dict->nodecount++; in dict_load_next()
1063 dict_t *dict = load->dictptr; in dict_load_end() local
1065 dnode_t *curr, *dictnil = dict_nil(dict), *loadnil = &load->nilnode, *next; in dict_load_end()
1067 dictcount_t fullcount = DICTCOUNT_T_MAX, nodecount = dict->nodecount; in dict_load_end()
1137 dict_root(dict) = complete; in dict_load_end()
1139 dict_assert(dict_verify(dict)); in dict_load_end()