Lines Matching refs:root
93 /* don't need to check for root node here because root->parent is
94 the sentinel nil node, and root->parent->left points back to root */
182 * checks that every path has the same count of black nodes from root to leaf.
187 * black height of the subtree rooted at the node ``root'', or zero if the
191 static unsigned int verify_redblack(dnode_t *nil, dnode_t *root)
195 if (root != nil) {
196 height_left = verify_redblack(nil, root->left);
197 height_right = verify_redblack(nil, root->right);
202 if (root->color == dnode_red) {
203 if (root->left->color != dnode_black)
205 if (root->right->color != dnode_black)
209 if (root->color != dnode_black)
222 static dictcount_t verify_node_count(dnode_t *nil, dnode_t *root)
224 if (root == nil)
227 return 1 + verify_node_count(nil, root->left)
228 + verify_node_count(nil, root->right);
239 static int verify_dict_has_node(dnode_t *nil, dnode_t *root, dnode_t *node)
241 if (root != nil) {
242 return root == node
243 || verify_dict_has_node(nil, root->left, node)
244 || verify_dict_has_node(nil, root->right, node);
311 dnode_t *nil = dict_nil(dict), *root = dict_root(dict);
312 free_nodes(dict, root, nil);
397 dnode_t *nil = dict_nil(dict), *root = dict_root(dict);
399 /* check that the sentinel node and root node are black */
400 if (root->color != dnode_black)
406 /* nil->left is the root node; check that its parent pointer is nil */
413 if (!verify_redblack(nil, root))
415 if (verify_node_count(nil, root) != dict_count(dict))
456 dnode_t *root = dict_root(dict);
463 while (root != nil) {
464 result = dict->compare(key, root->key);
466 root = root->left;
468 root = root->right;
471 return root;
474 saved = root;
475 root = root->left;
476 while (root != nil && dict->compare(key, root->key))
477 root = root->right;
478 } while (root != nil);
495 dnode_t *root = dict_root(dict);
499 while (root != nil) {
500 int result = dict->compare(key, root->key);
503 root = root->right;
505 tentative = root;
506 root = root->left;
509 return root;
511 tentative = root;
512 root = root->left;
527 dnode_t *root = dict_root(dict);
531 while (root != nil) {
532 int result = dict->compare(key, root->key);
535 root = root->left;
537 tentative = root;
538 root = root->right;
541 return root;
543 tentative = root;
544 root = root->right;
861 dnode_t *nil = dict_nil(dict), *root = dict_root(dict), *left;
863 if (root != nil)
864 while ((left = root->left) != nil)
865 root = left;
867 return (root == nil) ? NULL : root;
877 dnode_t *nil = dict_nil(dict), *root = dict_root(dict), *right;
879 if (root != nil)
880 while ((right = root->right) != nil)
881 root = right;
883 return (root == nil) ? NULL : root;
