79 static dnode_t *dnode_alloc(void *context);
80 static void dnode_free(dnode_t *node, void *context);
89 static void rotate_left(dnode_t *upper)  in rotate_left()
91     dnode_t *lower, *lowleft, *upparent;  in rotate_left()
118 static void rotate_right(dnode_t *upper)  in rotate_right()
120     dnode_t *lower, *lowright, *upparent;  in rotate_right()
144 static void free_nodes(dict_t *dict, dnode_t *node, dnode_t *nil)  in free_nodes()
164     dnode_t *first, *next;  in verify_bintree()
197 static unsigned int verify_redblack(dnode_t *nil, dnode_t *root)  in verify_redblack()
228 static dictcount_t verify_node_count(dnode_t *nil, dnode_t *root)  in verify_node_count()
245 static int verify_dict_has_node(dnode_t *nil, dnode_t *root, dnode_t *node)  in verify_dict_has_node()
317     dnode_t *nil = dict_nil(dict), *root = dict_root(dict);  in dict_free_nodes()
403     dnode_t *nil = dict_nil(dict), *root = dict_root(dict);  in dict_verify()
460 dnode_t *dict_lookup(dict_t *dict, const void *key)  in dict_lookup()
462     dnode_t *root = dict_root(dict);  in dict_lookup()
463     dnode_t *nil = dict_nil(dict);  in dict_lookup()
464     dnode_t *saved;  in dict_lookup()
499 dnode_t *dict_lower_bound(dict_t *dict, const void *key)  in dict_lower_bound()
501     dnode_t *root = dict_root(dict);  in dict_lower_bound()
502     dnode_t *nil = dict_nil(dict);  in dict_lower_bound()
503     dnode_t *tentative = 0;  in dict_lower_bound()
531 dnode_t *dict_upper_bound(dict_t *dict, const void *key)  in dict_upper_bound()
533     dnode_t *root = dict_root(dict);  in dict_upper_bound()
534     dnode_t *nil = dict_nil(dict);  in dict_upper_bound()
535     dnode_t *tentative = 0;  in dict_upper_bound()
567 void dict_insert(dict_t *dict, dnode_t *node, const void *key)  in dict_insert()
569     dnode_t *where = dict_root(dict), *nil = dict_nil(dict);  in dict_insert()
570     dnode_t *parent = nil, *uncle, *grandpa;  in dict_insert()
665 dnode_t *dict_delete(dict_t *dict, dnode_t *delete)  in dict_delete()
667     dnode_t *nil = dict_nil(dict), *child, *delparent = delete->parent;  in dict_delete()
687 	dnode_t *next = dict_next(dict, delete);  in dict_delete()
688 	dnode_t *nextparent = next->parent;  in dict_delete()
757 	dnode_t *parent, *sister;  in dict_delete()
842     dnode_t *node = dict->allocnode(dict->context);  in dict_alloc_insert()
853 void dict_delete_free(dict_t *dict, dnode_t *node)  in dict_delete_free()
865 dnode_t *dict_first(dict_t *dict)  in dict_first()
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()
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()
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()
927     dnode_t *nil = dict_nil(dict), *parent, *right;  in dict_prev()
973 int dict_contains(dict_t *dict, dnode_t *node)  in dict_contains()
978 static dnode_t *dnode_alloc(void *context EXT2FS_ATTR((unused)))  in dnode_alloc()
983 static void dnode_free(dnode_t *node, void *context EXT2FS_ATTR((unused)))  in dnode_free()
988 dnode_t *dnode_create(void *data)  in dnode_create()
990     dnode_t *new = malloc(sizeof *new);  in dnode_create()
1000 dnode_t *dnode_init(dnode_t *dnode, void *data)  in dnode_init()
1009 void dnode_destroy(dnode_t *dnode)  in dnode_destroy()
1015 void *dnode_get(dnode_t *dnode)  in dnode_get()
1020 const void *dnode_getkey(dnode_t *dnode)  in dnode_getkey()
1026 void dnode_put(dnode_t *dnode, void *data)  in dnode_put()
1033 int dnode_is_in_a_dict(dnode_t *dnode)  in dnode_is_in_a_dict()
1042     dnode_t *node = dict_first(dict), *next;  in dict_process()
1067 void dict_load_next(dict_load_t *load, dnode_t *newnode, const void *key)  in dict_load_next()
1070     dnode_t *nil = &load->nilnode;  in dict_load_next()
1094     dnode_t *tree[DICT_DEPTH_MAX] = { 0 };  in dict_load_end()
1095     dnode_t *curr, *dictnil = dict_nil(dict), *loadnil = &load->nilnode, *next;  in dict_load_end()
1096     dnode_t *complete = 0;  in dict_load_end()
1175     dnode_t *leftnode = dict_first(dest), *rightnode = dict_first(source);  in dict_merge()
1202 	    dnode_t *next = dict_next(dest, leftnode);  in dict_merge()
1213 	    dnode_t *next = dict_next(source, rightnode);  in dict_merge()
1278 static dnode_t *new_node(void *c)  in new_node()
1280     static dnode_t few[5];  in new_node()
1289 static void del_node(dnode_t *n, void *c)  in del_node()
1300     dnode_t *dn;  in construct()
1365     dnode_t *dn;  in main()