73 static dnode_t *dnode_alloc(void *context);
74 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()
112 static void rotate_right(dnode_t *upper)  in rotate_right()
114     dnode_t *lower, *lowright, *upparent;  in rotate_right()
138 static void free_nodes(dict_t *dict, dnode_t *node, dnode_t *nil)  in free_nodes()
158     dnode_t *first, *next;  in verify_bintree()
191 static unsigned int verify_redblack(dnode_t *nil, dnode_t *root)  in verify_redblack()
222 static dictcount_t verify_node_count(dnode_t *nil, dnode_t *root)  in verify_node_count()
239 static int verify_dict_has_node(dnode_t *nil, dnode_t *root, dnode_t *node)  in verify_dict_has_node()
311     dnode_t *nil = dict_nil(dict), *root = dict_root(dict);  in dict_free_nodes()
397     dnode_t *nil = dict_nil(dict), *root = dict_root(dict);  in dict_verify()
454 dnode_t *dict_lookup(dict_t *dict, const void *key)  in dict_lookup()
456     dnode_t *root = dict_root(dict);  in dict_lookup()
457     dnode_t *nil = dict_nil(dict);  in dict_lookup()
458     dnode_t *saved;  in dict_lookup()
493 dnode_t *dict_lower_bound(dict_t *dict, const void *key)  in dict_lower_bound()
495     dnode_t *root = dict_root(dict);  in dict_lower_bound()
496     dnode_t *nil = dict_nil(dict);  in dict_lower_bound()
497     dnode_t *tentative = 0;  in dict_lower_bound()
525 dnode_t *dict_upper_bound(dict_t *dict, const void *key)  in dict_upper_bound()
527     dnode_t *root = dict_root(dict);  in dict_upper_bound()
528     dnode_t *nil = dict_nil(dict);  in dict_upper_bound()
529     dnode_t *tentative = 0;  in dict_upper_bound()
561 void dict_insert(dict_t *dict, dnode_t *node, const void *key)  in dict_insert()
563     dnode_t *where = dict_root(dict), *nil = dict_nil(dict);  in dict_insert()
564     dnode_t *parent = nil, *uncle, *grandpa;  in dict_insert()
659 dnode_t *dict_delete(dict_t *dict, dnode_t *delete)  in dict_delete()
661     dnode_t *nil = dict_nil(dict), *child, *delparent = delete->parent;  in dict_delete()
681 	dnode_t *next = dict_next(dict, delete);  in dict_delete()
682 	dnode_t *nextparent = next->parent;  in dict_delete()
751 	dnode_t *parent, *sister;  in dict_delete()
836     dnode_t *node = dict->allocnode(dict->context);  in dict_alloc_insert()
847 void dict_delete_free(dict_t *dict, dnode_t *node)  in dict_delete_free()
859 dnode_t *dict_first(dict_t *dict)  in dict_first()
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()
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()
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()
921     dnode_t *nil = dict_nil(dict), *parent, *right;  in dict_prev()
967 int dict_contains(dict_t *dict, dnode_t *node)  in dict_contains()
972 static dnode_t *dnode_alloc(void *context EXT2FS_ATTR((unused)))  in dnode_alloc()
977 static void dnode_free(dnode_t *node, void *context EXT2FS_ATTR((unused)))  in dnode_free()
982 dnode_t *dnode_create(void *data)  in dnode_create()
984     dnode_t *new = malloc(sizeof *new);  in dnode_create()
994 dnode_t *dnode_init(dnode_t *dnode, void *data)  in dnode_init()
1003 void dnode_destroy(dnode_t *dnode)  in dnode_destroy()
1009 void *dnode_get(dnode_t *dnode)  in dnode_get()
1014 const void *dnode_getkey(dnode_t *dnode)  in dnode_getkey()
1020 void dnode_put(dnode_t *dnode, void *data)  in dnode_put()
1025 int dnode_is_in_a_dict(dnode_t *dnode)  in dnode_is_in_a_dict()
1032     dnode_t *node = dict_first(dict), *next;  in dict_process()
1057 void dict_load_next(dict_load_t *load, dnode_t *newnode, const void *key)  in dict_load_next()
1060     dnode_t *nil = &load->nilnode;  in dict_load_next()
1084     dnode_t *tree[DICT_DEPTH_MAX] = { 0 };  in dict_load_end()
1085     dnode_t *curr, *dictnil = dict_nil(dict), *loadnil = &load->nilnode, *next;  in dict_load_end()
1086     dnode_t *complete = 0;  in dict_load_end()
1165     dnode_t *leftnode = dict_first(dest), *rightnode = dict_first(source);  in dict_merge()
1192 	    dnode_t *next = dict_next(dest, leftnode);  in dict_merge()
1203 	    dnode_t *next = dict_next(source, rightnode);  in dict_merge()
1268 static dnode_t *new_node(void *c)  in new_node()
1270     static dnode_t few[5];  in new_node()
1279 static void del_node(dnode_t *n, void *c)  in del_node()
1290     dnode_t *dn;  in construct()
1355     dnode_t *dn;  in main()