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()
317     dnode_t *nil = dict_nil(dict), *root = dict_root(dict);  in dict_free_nodes()  local
318     free_nodes(dict, root, nil);  in dict_free_nodes()
403     dnode_t *nil = dict_nil(dict), *root = dict_root(dict);  in dict_verify()  local
408     if (nil->color != dnode_black)  in dict_verify()
410     if (nil->right != nil)  in dict_verify()
413     if (nil->left->parent != nil)  in dict_verify()
419     if (!verify_redblack(nil, root))  in dict_verify()
421     if (verify_node_count(nil, root) != dict_count(dict))  in dict_verify()
463     dnode_t *nil = dict_nil(dict);  in dict_lookup()  local
469     while (root != nil) {  in dict_lookup()
482 		    while (root != nil && dict->compare(key, root->key))  in dict_lookup()
484 		} while (root != nil);  in dict_lookup()
502     dnode_t *nil = dict_nil(dict);  in dict_lower_bound()  local
505     while (root != nil) {  in dict_lower_bound()
534     dnode_t *nil = dict_nil(dict);  in dict_upper_bound()  local
537     while (root != nil) {  in dict_upper_bound()
569     dnode_t *where = dict_root(dict), *nil = dict_nil(dict);  in dict_insert()  local
570     dnode_t *parent = nil, *uncle, *grandpa;  in dict_insert()
581     while (where != nil) {  in dict_insert()
592     dict_assert (where == nil);  in dict_insert()
600     node->left = nil;  in dict_insert()
601     node->right = nil;  in dict_insert()
667     dnode_t *nil = dict_nil(dict), *child, *delparent = delete->parent;  in dict_delete()  local
686     if (delete->left != nil && delete->right != nil) {  in dict_delete()
691 	dict_assert (next != nil);  in dict_delete()
692 	dict_assert (next->parent != nil);  in dict_delete()
693 	dict_assert (next->left == nil);  in dict_delete()
731 	dict_assert (delete != nil);  in dict_delete()
732 	dict_assert (delete->left == nil || delete->right == nil);  in dict_delete()
734 	child = (delete->left != nil) ? delete->left : delete->right;  in dict_delete()
765 		dict_assert (sister != nil);  in dict_delete()
771 		    dict_assert (sister != nil);  in dict_delete()
784 			dict_assert (sister != nil);  in dict_delete()
795 		dict_assert (sister != nil);  in dict_delete()
801 		    dict_assert (sister != nil);  in dict_delete()
814 			dict_assert (sister != nil);  in dict_delete()
867     dnode_t *nil = dict_nil(dict), *root = dict_root(dict), *left;  in dict_first()  local
869     if (root != nil)  in dict_first()
870 	while ((left = root->left) != nil)  in dict_first()
873     return (root == nil) ? NULL : root;  in dict_first()
883     dnode_t *nil = dict_nil(dict), *root = dict_root(dict), *right;  in dict_last()  local
885     if (root != nil)  in dict_last()
886 	while ((right = root->right) != nil)  in dict_last()
889     return (root == nil) ? NULL : root;  in dict_last()
901     dnode_t *nil = dict_nil(dict), *parent, *left;  in dict_next()  local
903     if (curr->right != nil) {  in dict_next()
905 	while ((left = curr->left) != nil)  in dict_next()
912     while (parent != nil && curr == parent->right) {  in dict_next()
917     return (parent == nil) ? NULL : parent;  in dict_next()
927     dnode_t *nil = dict_nil(dict), *parent, *right;  in dict_prev()  local
929     if (curr->left != nil) {  in dict_prev()
931 	while ((right = curr->right) != nil)  in dict_prev()
938     while (parent != nil && curr == parent->left) {  in dict_prev()
943     return (parent == nil) ? NULL : parent;  in dict_prev()
1070     dnode_t *nil = &load->nilnode;  in dict_load_next()  local
1078 	    dict_assert (dict->compare(nil->left->key, key) <= 0);  in dict_load_next()
1080 	    dict_assert (dict->compare(nil->left->key, key) < 0);  in dict_load_next()
1085     nil->right->left = newnode;  in dict_load_next()
1086     nil->right = newnode;  in dict_load_next()
1087     newnode->left = nil;  in dict_load_next()