144 static void free_nodes(dict_t *dict, dnode_t *node, dnode_t *nil)  in free_nodes()  argument
146     if (node == nil)  in free_nodes()
148     free_nodes(dict, node->left, nil);  in free_nodes()
149     free_nodes(dict, node->right, nil);  in free_nodes()
197 static unsigned int verify_redblack(dnode_t *nil, dnode_t *root)  in verify_redblack()  argument
201     if (root != nil) {  in verify_redblack()
202 	height_left = verify_redblack(nil, root->left);  in verify_redblack()
203 	height_right = verify_redblack(nil, root->right);  in verify_redblack()
228 static dictcount_t verify_node_count(dnode_t *nil, dnode_t *root)  in verify_node_count()  argument
230     if (root == nil)  in verify_node_count()
233 	return 1 + verify_node_count(nil, root->left)  in verify_node_count()
234 	    + verify_node_count(nil, root->right);  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()  argument
247     if (root != nil) {  in verify_dict_has_node()
249 		|| verify_dict_has_node(nil, root->left, node)  in verify_dict_has_node()
250 		|| verify_dict_has_node(nil, root->right, node);  in verify_dict_has_node()
326     dnode_t *nil = dict_nil(dict), *root = dict_root(dict);  in dict_free_nodes()  local
327     free_nodes(dict, root, nil);  in dict_free_nodes()
412     dnode_t *nil = dict_nil(dict), *root = dict_root(dict);  in dict_verify()  local
417     if (nil->color != dnode_black)  in dict_verify()
419     if (nil->right != nil)  in dict_verify()
422     if (nil->left->parent != nil)  in dict_verify()
428     if (!verify_redblack(nil, root))  in dict_verify()
430     if (verify_node_count(nil, root) != dict_count(dict))  in dict_verify()
472     dnode_t *nil = dict_nil(dict);  in dict_lookup()  local
478     while (root != nil) {  in dict_lookup()
491 		    while (root != nil  in dict_lookup()
494 		} while (root != nil);  in dict_lookup()
512     dnode_t *nil = dict_nil(dict);  in dict_lower_bound()  local
515     while (root != nil) {  in dict_lower_bound()
544     dnode_t *nil = dict_nil(dict);  in dict_upper_bound()  local
547     while (root != nil) {  in dict_upper_bound()
579     dnode_t *where = dict_root(dict), *nil = dict_nil(dict);  in dict_insert()  local
580     dnode_t *parent = nil, *uncle, *grandpa;  in dict_insert()
591     while (where != nil) {  in dict_insert()
602     dict_assert (where == nil);  in dict_insert()
610     node->left = nil;  in dict_insert()
611     node->right = nil;  in dict_insert()
677     dnode_t *nil = dict_nil(dict), *child, *delparent = delete->parent;  in dict_delete()  local
696     if (delete->left != nil && delete->right != nil) {  in dict_delete()
701 	dict_assert (next != nil);  in dict_delete()
702 	dict_assert (next->parent != nil);  in dict_delete()
703 	dict_assert (next->left == nil);  in dict_delete()
741 	dict_assert (delete != nil);  in dict_delete()
742 	dict_assert (delete->left == nil || delete->right == nil);  in dict_delete()
744 	child = (delete->left != nil) ? delete->left : delete->right;  in dict_delete()
775 		dict_assert (sister != nil);  in dict_delete()
781 		    dict_assert (sister != nil);  in dict_delete()
794 			dict_assert (sister != nil);  in dict_delete()
805 		dict_assert (sister != nil);  in dict_delete()
811 		    dict_assert (sister != nil);  in dict_delete()
824 			dict_assert (sister != nil);  in dict_delete()
877     dnode_t *nil = dict_nil(dict), *root = dict_root(dict), *left;  in dict_first()  local
879     if (root != nil)  in dict_first()
880 	while ((left = root->left) != nil)  in dict_first()
883     return (root == nil) ? NULL : root;  in dict_first()
893     dnode_t *nil = dict_nil(dict), *root = dict_root(dict), *right;  in dict_last()  local
895     if (root != nil)  in dict_last()
896 	while ((right = root->right) != nil)  in dict_last()
899     return (root == nil) ? NULL : root;  in dict_last()
911     dnode_t *nil = dict_nil(dict), *parent, *left;  in dict_next()  local
913     if (curr->right != nil) {  in dict_next()
915 	while ((left = curr->left) != nil)  in dict_next()
922     while (parent != nil && curr == parent->right) {  in dict_next()
927     return (parent == nil) ? NULL : parent;  in dict_next()
937     dnode_t *nil = dict_nil(dict), *parent, *right;  in dict_prev()  local
939     if (curr->left != nil) {  in dict_prev()
941 	while ((right = curr->right) != nil)  in dict_prev()
948     while (parent != nil && curr == parent->left) {  in dict_prev()
953     return (parent == nil) ? NULL : parent;  in dict_prev()
1080     dnode_t *nil = &load->nilnode;  in dict_load_next()  local
1088 	    dict_assert (dict->compare(nil->left->key, key) <= 0);  in dict_load_next()
1090 	    dict_assert (dict->compare(nil->left->key, key) < 0);  in dict_load_next()
1095     nil->right->left = newnode;  in dict_load_next()
1096     nil->right = newnode;  in dict_load_next()
1097     newnode->left = nil;  in dict_load_next()