138 static void free_nodes(dict_t *dict, dnode_t *node, dnode_t *nil)  in free_nodes()  argument
140     if (node == nil)  in free_nodes()
142     free_nodes(dict, node->left, nil);  in free_nodes()
143     free_nodes(dict, node->right, nil);  in free_nodes()
191 static unsigned int verify_redblack(dnode_t *nil, dnode_t *root)  in verify_redblack()  argument
195     if (root != nil) {  in verify_redblack()
196 	height_left = verify_redblack(nil, root->left);  in verify_redblack()
197 	height_right = verify_redblack(nil, root->right);  in verify_redblack()
222 static dictcount_t verify_node_count(dnode_t *nil, dnode_t *root)  in verify_node_count()  argument
224     if (root == nil)  in verify_node_count()
227 	return 1 + verify_node_count(nil, root->left)  in verify_node_count()
228 	    + verify_node_count(nil, root->right);  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()  argument
241     if (root != nil) {  in verify_dict_has_node()
243 		|| verify_dict_has_node(nil, root->left, node)  in verify_dict_has_node()
244 		|| verify_dict_has_node(nil, root->right, node);  in verify_dict_has_node()
311     dnode_t *nil = dict_nil(dict), *root = dict_root(dict);  in dict_free_nodes()  local
312     free_nodes(dict, root, nil);  in dict_free_nodes()
397     dnode_t *nil = dict_nil(dict), *root = dict_root(dict);  in dict_verify()  local
402     if (nil->color != dnode_black)  in dict_verify()
404     if (nil->right != nil)  in dict_verify()
407     if (nil->left->parent != nil)  in dict_verify()
413     if (!verify_redblack(nil, root))  in dict_verify()
415     if (verify_node_count(nil, root) != dict_count(dict))  in dict_verify()
457     dnode_t *nil = dict_nil(dict);  in dict_lookup()  local
463     while (root != nil) {  in dict_lookup()
476 		    while (root != nil && dict->compare(key, root->key))  in dict_lookup()
478 		} while (root != nil);  in dict_lookup()
496     dnode_t *nil = dict_nil(dict);  in dict_lower_bound()  local
499     while (root != nil) {  in dict_lower_bound()
528     dnode_t *nil = dict_nil(dict);  in dict_upper_bound()  local
531     while (root != nil) {  in dict_upper_bound()
563     dnode_t *where = dict_root(dict), *nil = dict_nil(dict);  in dict_insert()  local
564     dnode_t *parent = nil, *uncle, *grandpa;  in dict_insert()
575     while (where != nil) {  in dict_insert()
586     assert (where == nil);  in dict_insert()
594     node->left = nil;  in dict_insert()
595     node->right = nil;  in dict_insert()
661     dnode_t *nil = dict_nil(dict), *child, *delparent = delete->parent;  in dict_delete()  local
680     if (delete->left != nil && delete->right != nil) {  in dict_delete()
685 	assert (next != nil);  in dict_delete()
686 	assert (next->parent != nil);  in dict_delete()
687 	assert (next->left == nil);  in dict_delete()
725 	assert (delete != nil);  in dict_delete()
726 	assert (delete->left == nil || delete->right == nil);  in dict_delete()
728 	child = (delete->left != nil) ? delete->left : delete->right;  in dict_delete()
759 		assert (sister != nil);  in dict_delete()
765 		    assert (sister != nil);  in dict_delete()
778 			assert (sister != nil);  in dict_delete()
789 		assert (sister != nil);  in dict_delete()
795 		    assert (sister != nil);  in dict_delete()
808 			assert (sister != nil);  in dict_delete()
861     dnode_t *nil = dict_nil(dict), *root = dict_root(dict), *left;  in dict_first()  local
863     if (root != nil)  in dict_first()
864 	while ((left = root->left) != nil)  in dict_first()
867     return (root == nil) ? NULL : root;  in dict_first()
877     dnode_t *nil = dict_nil(dict), *root = dict_root(dict), *right;  in dict_last()  local
879     if (root != nil)  in dict_last()
880 	while ((right = root->right) != nil)  in dict_last()
883     return (root == nil) ? NULL : root;  in dict_last()
895     dnode_t *nil = dict_nil(dict), *parent, *left;  in dict_next()  local
897     if (curr->right != nil) {  in dict_next()
899 	while ((left = curr->left) != nil)  in dict_next()
906     while (parent != nil && curr == parent->right) {  in dict_next()
911     return (parent == nil) ? NULL : parent;  in dict_next()
921     dnode_t *nil = dict_nil(dict), *parent, *right;  in dict_prev()  local
923     if (curr->left != nil) {  in dict_prev()
925 	while ((right = curr->right) != nil)  in dict_prev()
932     while (parent != nil && curr == parent->left) {  in dict_prev()
937     return (parent == nil) ? NULL : parent;  in dict_prev()
1060     dnode_t *nil = &load->nilnode;  in dict_load_next()  local
1068 	    assert (dict->compare(nil->left->key, key) <= 0);  in dict_load_next()
1070 	    assert (dict->compare(nil->left->key, key) < 0);  in dict_load_next()
1075     nil->right->left = newnode;  in dict_load_next()
1076     nil->right = newnode;  in dict_load_next()
1077     newnode->left = nil;  in dict_load_next()