74 static dnode_t *dnode_alloc(void *context);
75 static void dnode_free(dnode_t *node, void *context);
83 static void rotate_left(dnode_t *upper)  in rotate_left()
85 	dnode_t *lower, *lowleft, *upparent;  in rotate_left()
111 static void rotate_right(dnode_t *upper)  in rotate_right()
113 	dnode_t *lower, *lowright, *upparent;  in rotate_right()
136 static void free_nodes(dict_t *dict, dnode_t *node, dnode_t *nil)  in free_nodes()
156 	dnode_t *first, *next;  in verify_bintree()
188 static unsigned int verify_redblack(dnode_t *nil, dnode_t *root)  in verify_redblack()
218 static dictcount_t verify_node_count(dnode_t *nil, dnode_t *root)  in verify_node_count()
234 static int verify_dict_has_node(dnode_t *nil, dnode_t *root, dnode_t *node)  in verify_dict_has_node()
301 	dnode_t *nil = dict_nil(dict), *root = dict_root(dict);  in dict_free_nodes()
383 	dnode_t *nil = dict_nil(dict), *root = dict_root(dict);  in dict_verify()
439 dnode_t *dict_lookup(dict_t *dict, const void *key)  in dict_lookup()
441 	dnode_t *root = dict_root(dict);  in dict_lookup()
442 	dnode_t *nil = dict_nil(dict);  in dict_lookup()
443 	dnode_t *saved;  in dict_lookup()
477 dnode_t *dict_lower_bound(dict_t *dict, const void *key)  in dict_lower_bound()
479 	dnode_t *root = dict_root(dict);  in dict_lower_bound()
480 	dnode_t *nil = dict_nil(dict);  in dict_lower_bound()
481 	dnode_t *tentative = 0;  in dict_lower_bound()
508 dnode_t *dict_upper_bound(dict_t *dict, const void *key)  in dict_upper_bound()
510 	dnode_t *root = dict_root(dict);  in dict_upper_bound()
511 	dnode_t *nil = dict_nil(dict);  in dict_upper_bound()
512 	dnode_t *tentative = 0;  in dict_upper_bound()
543 void dict_insert(dict_t *dict, dnode_t *node, const void *key)  in dict_insert()
545 	dnode_t *where = dict_root(dict), *nil = dict_nil(dict);  in dict_insert()
546 	dnode_t *parent = nil, *uncle, *grandpa;  in dict_insert()
640 dnode_t *dict_delete(dict_t *dict, dnode_t *delete)  in dict_delete()
642 	dnode_t *nil = dict_nil(dict), *child, *delparent = delete->parent;  in dict_delete()
662 		dnode_t *next = dict_next(dict, delete);  in dict_delete()
663 		dnode_t *nextparent = next->parent;  in dict_delete()
732 		dnode_t *parent, *sister;  in dict_delete()
816 	dnode_t *node = dict->allocnode(dict->context);  in dict_alloc_insert()
827 void dict_delete_free(dict_t *dict, dnode_t *node)  in dict_delete_free()
838 dnode_t *dict_first(dict_t *dict)  in dict_first()
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()
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()
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()
897 	dnode_t *nil = dict_nil(dict), *parent, *right;  in dict_prev()
943 int dict_contains(dict_t *dict, dnode_t *node)  in dict_contains()
948 static dnode_t *dnode_alloc(void *UNUSED(context))  in dnode_alloc()
953 static void dnode_free(dnode_t *node, void *UNUSED(context))  in dnode_free()
958 dnode_t *dnode_create(void *data)  in dnode_create()
960 	dnode_t *new = malloc(sizeof *new);  in dnode_create()
970 dnode_t *dnode_init(dnode_t *dnode, void *data)  in dnode_init()
979 void dnode_destroy(dnode_t *dnode)  in dnode_destroy()
985 void *dnode_get(dnode_t *dnode)  in dnode_get()
990 const void *dnode_getkey(dnode_t *dnode)  in dnode_getkey()
996 void dnode_put(dnode_t *dnode, void *data)  in dnode_put()
1003 int dnode_is_in_a_dict(dnode_t *dnode)  in dnode_is_in_a_dict()
1012 	dnode_t *node = dict_first(dict), *next;  in dict_process()
1037 void dict_load_next(dict_load_t *load, dnode_t *newnode, const void *key)  in dict_load_next()
1040 	dnode_t *nil = &load->nilnode;  in dict_load_next()
1064 	dnode_t *tree[DICT_DEPTH_MAX] = { 0 };  in dict_load_end()
1065 	dnode_t *curr, *dictnil = dict_nil(dict), *loadnil = &load->nilnode, *next;  in dict_load_end()
1066 	dnode_t *complete = 0;  in dict_load_end()
1145 	dnode_t *leftnode = dict_first(dest), *rightnode = dict_first(source);  in dict_merge()
1172 			dnode_t *next = dict_next(dest, leftnode);  in dict_merge()
1183 			dnode_t *next = dict_next(source, rightnode);  in dict_merge()
1248 static dnode_t *new_node(void *c)  in new_node()
1250 	static dnode_t few[5];  in new_node()
1259 static void del_node(dnode_t *n, void *c)  in del_node()
1270 	dnode_t *dn;  in construct()
1335 	dnode_t *dn;  in main()