Lines Matching refs:nil
93 the sentinel nil node, and root->parent->left points back to root */
135 static void free_nodes(dict_t *dict, dnode_t *node, dnode_t *nil)
137 if (node == nil)
139 free_nodes(dict, node->left, nil);
140 free_nodes(dict, node->right, nil);
182 * mismatches. It does not check for every nil node being black, because there
183 * is only one sentinel nil node. The return value of this function is 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);
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) {
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);
387 if (nil->color != dnode_black)
389 if (nil->right != nil)
391 /* nil->left is the root node; check that its parent pointer is nil */
392 if (nil->left->parent != nil)
398 if (!verify_redblack(nil, root))
400 if (verify_node_count(nil, root) != dict_count(dict))
435 * a pointer that dictionary's nil sentinel node), otherwise a pointer to the
441 dnode_t *nil = dict_nil(dict);
447 while (root != nil) {
460 while (root != nil && dict->compare(key, root->key))
462 } while (root != nil);
479 dnode_t *nil = dict_nil(dict);
482 while (root != nil) {
510 dnode_t *nil = dict_nil(dict);
513 while (root != nil) {
544 dnode_t *where = dict_root(dict), *nil = dict_nil(dict);
545 dnode_t *parent = nil, *uncle, *grandpa;
556 while (where != nil) {
567 dict_assert(where == nil);
575 node->left = nil;
576 node->right = nil;
641 dnode_t *nil = dict_nil(dict), *child, *delparent = delete->parent;
660 if (delete->left != nil && delete->right != nil) {
665 dict_assert(next != nil);
666 dict_assert(next->parent != nil);
667 dict_assert(next->left == nil);
705 dict_assert(delete != nil);
706 dict_assert(delete->left == nil || delete->right == nil);
708 child = (delete->left != nil) ? delete->left : delete->right;
739 dict_assert(sister != nil);
745 dict_assert(sister != nil);
758 dict_assert(sister != nil);
769 dict_assert(sister != nil);
775 dict_assert(sister != nil);
788 dict_assert(sister != nil);
839 dnode_t *nil = dict_nil(dict), *root = dict_root(dict), *left;
841 if (root != nil)
842 while ((left = root->left) != nil)
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)
860 return (root == nil) ? NULL : root;
867 * the nil node.
871 dnode_t *nil = dict_nil(dict), *parent, *left;
873 if (curr->right != nil) {
875 while ((left = curr->left) != nil)
882 while (parent != nil && curr == parent->right) {
887 return (parent == nil) ? NULL : parent;
892 * The nil sentinel node is returned if there is no predecessor.
896 dnode_t *nil = dict_nil(dict), *parent, *right;
898 if (curr->left != nil) {
900 while ((right = curr->right) != nil)
907 while (parent != nil && curr == parent->left) {
912 return (parent == nil) ? NULL : parent;
1039 dnode_t *nil = &load->nilnode;
1047 dict_assert(dict->compare(nil->left->key, key) <= 0);
1049 dict_assert(dict->compare(nil->left->key, key) < 0);
1054 nil->right->left = newnode;
1055 nil->right = newnode;
1056 newnode->left = nil;