136 static void free_nodes(dict_t *dict, dnode_t *node, dnode_t *nil)  in free_nodes()  argument
138 	if (node == nil)  in free_nodes()
140 	free_nodes(dict, node->left, nil);  in free_nodes()
141 	free_nodes(dict, node->right, nil);  in free_nodes()
188 static unsigned int verify_redblack(dnode_t *nil, dnode_t *root)  in verify_redblack()  argument
192 	if (root != nil) {  in verify_redblack()
193 		height_left = verify_redblack(nil, root->left);  in verify_redblack()
194 		height_right = verify_redblack(nil, root->right);  in verify_redblack()
218 static dictcount_t verify_node_count(dnode_t *nil, dnode_t *root)  in verify_node_count()  argument
220 	if (root == nil)  in verify_node_count()
223 		return 1 + verify_node_count(nil, root->left)  in verify_node_count()
224 			+ verify_node_count(nil, root->right);  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()  argument
236 	if (root != nil) {  in verify_dict_has_node()
238 			|| verify_dict_has_node(nil, root->left, node)  in verify_dict_has_node()
239 			|| verify_dict_has_node(nil, root->right, node);  in verify_dict_has_node()
301 	dnode_t *nil = dict_nil(dict), *root = dict_root(dict);  in dict_free_nodes()  local
302 	free_nodes(dict, root, nil);  in dict_free_nodes()
383 	dnode_t *nil = dict_nil(dict), *root = dict_root(dict);  in dict_verify()  local
388 	if (nil->color != dnode_black)  in dict_verify()
390 	if (nil->right != nil)  in dict_verify()
393 	if (nil->left->parent != nil)  in dict_verify()
399 	if (!verify_redblack(nil, root))  in dict_verify()
401 	if (verify_node_count(nil, root) != dict_count(dict))  in dict_verify()
442 	dnode_t *nil = dict_nil(dict);  in dict_lookup()  local
448 	while (root != nil) {  in dict_lookup()
461 					while (root != nil && dict->compare(key, root->key))  in dict_lookup()
463 				} while (root != nil);  in dict_lookup()
480 	dnode_t *nil = dict_nil(dict);  in dict_lower_bound()  local
483 	while (root != nil) {  in dict_lower_bound()
511 	dnode_t *nil = dict_nil(dict);  in dict_upper_bound()  local
514 	while (root != nil) {  in dict_upper_bound()
545 	dnode_t *where = dict_root(dict), *nil = dict_nil(dict);  in dict_insert()  local
546 	dnode_t *parent = nil, *uncle, *grandpa;  in dict_insert()
557 	while (where != nil) {  in dict_insert()
568 	dict_assert(where == nil);  in dict_insert()
576 	node->left = nil;  in dict_insert()
577 	node->right = nil;  in dict_insert()
642 	dnode_t *nil = dict_nil(dict), *child, *delparent = delete->parent;  in dict_delete()  local
661 	if (delete->left != nil && delete->right != nil) {  in dict_delete()
666 		dict_assert(next != nil);  in dict_delete()
667 		dict_assert(next->parent != nil);  in dict_delete()
668 		dict_assert(next->left == nil);  in dict_delete()
706 		dict_assert(delete != nil);  in dict_delete()
707 		dict_assert(delete->left == nil || delete->right == nil);  in dict_delete()
709 		child = (delete->left != nil) ? delete->left : delete->right;  in dict_delete()
740 				dict_assert(sister != nil);  in dict_delete()
746 					dict_assert(sister != nil);  in dict_delete()
759 						dict_assert(sister != nil);  in dict_delete()
770 				dict_assert(sister != nil);  in dict_delete()
776 					dict_assert(sister != nil);  in dict_delete()
789 						dict_assert(sister != nil);  in dict_delete()
840 	dnode_t *nil = dict_nil(dict), *root = dict_root(dict), *left;  in dict_first()  local
842 	if (root != nil)  in dict_first()
843 		while ((left = root->left) != nil)  in dict_first()
846 	return (root == nil) ? NULL : root;  in dict_first()
855 	dnode_t *nil = dict_nil(dict), *root = dict_root(dict), *right;  in dict_last()  local
857 	if (root != nil)  in dict_last()
858 		while ((right = root->right) != nil)  in dict_last()
861 	return (root == nil) ? NULL : root;  in dict_last()
872 	dnode_t *nil = dict_nil(dict), *parent, *left;  in dict_next()  local
874 	if (curr->right != nil) {  in dict_next()
876 		while ((left = curr->left) != nil)  in dict_next()
883 	while (parent != nil && curr == parent->right) {  in dict_next()
888 	return (parent == nil) ? NULL : parent;  in dict_next()
897 	dnode_t *nil = dict_nil(dict), *parent, *right;  in dict_prev()  local
899 	if (curr->left != nil) {  in dict_prev()
901 		while ((right = curr->right) != nil)  in dict_prev()
908 	while (parent != nil && curr == parent->left) {  in dict_prev()
913 	return (parent == nil) ? NULL : parent;  in dict_prev()
1040 	dnode_t *nil = &load->nilnode;  in dict_load_next()  local
1048 			dict_assert(dict->compare(nil->left->key, key) <= 0);  in dict_load_next()
1050 			dict_assert(dict->compare(nil->left->key, key) < 0);  in dict_load_next()
1055 	nil->right->left = newnode;  in dict_load_next()
1056 	nil->right = newnode;  in dict_load_next()
1057 	newnode->left = nil;  in dict_load_next()