Lines Matching refs:root
92 /* don't need to check for root node here because root->parent is
93 the sentinel nil node, and root->parent->left points back to root */
179 * checks that every path has the same count of black nodes from root to leaf.
184 * black height of the subtree rooted at the node ``root'', or zero if the
187 static unsigned int verify_redblack(dnode_t *nil, dnode_t *root)
191 if (root != nil) {
192 height_left = verify_redblack(nil, root->left);
193 height_right = verify_redblack(nil, root->right);
198 if (root->color == dnode_red) {
199 if (root->left->color != dnode_black)
201 if (root->right->color != dnode_black)
205 if (root->color != dnode_black)
217 static dictcount_t verify_node_count(dnode_t *nil, dnode_t *root)
219 if (root == nil)
222 return 1 + verify_node_count(nil, root->left)
223 + verify_node_count(nil, root->right);
233 static int verify_dict_has_node(dnode_t *nil, dnode_t *root, dnode_t *node)
235 if (root != nil) {
236 return root == node
237 || verify_dict_has_node(nil, root->left, node)
238 || verify_dict_has_node(nil, root->right, node);
300 dnode_t *nil = dict_nil(dict), *root = dict_root(dict);
301 free_nodes(dict, root, nil);
382 dnode_t *nil = dict_nil(dict), *root = dict_root(dict);
384 /* check that the sentinel node and root node are black */
385 if (root->color != dnode_black)
391 /* nil->left is the root node; check that its parent pointer is nil */
398 if (!verify_redblack(nil, root))
400 if (verify_node_count(nil, root) != dict_count(dict))
440 dnode_t *root = dict_root(dict);
447 while (root != nil) {
448 result = dict->compare(key, root->key);
450 root = root->left;
452 root = root->right;
455 return root;
458 saved = root;
459 root = root->left;
460 while (root != nil && dict->compare(key, root->key))
461 root = root->right;
462 } while (root != nil);
478 dnode_t *root = dict_root(dict);
482 while (root != nil) {
483 int result = dict->compare(key, root->key);
486 root = root->right;
488 tentative = root;
489 root = root->left;
492 return root;
494 tentative = root;
495 root = root->left;
509 dnode_t *root = dict_root(dict);
513 while (root != nil) {
514 int result = dict->compare(key, root->key);
517 root = root->left;
519 tentative = root;
520 root = root->right;
523 return root;
525 tentative = root;
526 root = root->right;
839 dnode_t *nil = dict_nil(dict), *root = dict_root(dict), *left;
841 if (root != nil)
842 while ((left = root->left) != nil)
843 root = left;
845 return (root == nil) ? NULL : root;
854 dnode_t *nil = dict_nil(dict), *root = dict_root(dict), *right;
856 if (root != nil)
857 while ((right = root->right) != nil)
858 root = right;
860 return (root == nil) ? NULL : root;