Lines Matching full:nil
94 the sentinel nil node, and root->parent->left points back to root */
138 static void free_nodes(dict_t *dict, dnode_t *node, dnode_t *nil)
140 if (node == nil)
142 free_nodes(dict, node->left, nil);
143 free_nodes(dict, node->right, nil);
185 * mismatches. It does not check for every nil node being black, because there
186 * is only one sentinel nil node. The return value of this function is 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);
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) {
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);
402 if (nil->color != dnode_black)
404 if (nil->right != nil)
406 /* nil->left is the root node; check that its parent pointer is nil */
407 if (nil->left->parent != nil)
413 if (!verify_redblack(nil, root))
415 if (verify_node_count(nil, root) != dict_count(dict))
450 * a pointer that dictionary's nil sentinel node), otherwise a pointer to the
457 dnode_t *nil = dict_nil(dict);
463 while (root != nil) {
476 while (root != nil && dict->compare(key, root->key))
478 } while (root != nil);
496 dnode_t *nil = dict_nil(dict);
499 while (root != nil) {
528 dnode_t *nil = dict_nil(dict);
531 while (root != nil) {
563 dnode_t *where = dict_root(dict), *nil = dict_nil(dict);
564 dnode_t *parent = nil, *uncle, *grandpa;
575 while (where != nil) {
586 assert (where == nil);
594 node->left = nil;
595 node->right = nil;
661 dnode_t *nil = dict_nil(dict), *child, *delparent = delete->parent;
680 if (delete->left != nil && delete->right != nil) {
685 assert (next != nil);
686 assert (next->parent != nil);
687 assert (next->left == nil);
725 assert (delete != nil);
726 assert (delete->left == nil || delete->right == nil);
728 child = (delete->left != nil) ? delete->left : delete->right;
759 assert (sister != nil);
765 assert (sister != nil);
778 assert (sister != nil);
789 assert (sister != nil);
795 assert (sister != nil);
808 assert (sister != nil);
861 dnode_t *nil = dict_nil(dict), *root = dict_root(dict), *left;
863 if (root != nil)
864 while ((left = root->left) != nil)
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)
883 return (root == nil) ? NULL : root;
890 * the nil node.
895 dnode_t *nil = dict_nil(dict), *parent, *left;
897 if (curr->right != nil) {
899 while ((left = curr->left) != nil)
906 while (parent != nil && curr == parent->right) {
911 return (parent == nil) ? NULL : parent;
916 * The nil sentinel node is returned if there is no predecessor.
921 dnode_t *nil = dict_nil(dict), *parent, *right;
923 if (curr->left != nil) {
925 while ((right = curr->right) != nil)
932 while (parent != nil && curr == parent->left) {
937 return (parent == nil) ? NULL : parent;
1060 dnode_t *nil = &load->nilnode;
1068 assert (dict->compare(nil->left->key, key) <= 0);
1070 assert (dict->compare(nil->left->key, key) < 0);
1075 nil->right->left = newnode;
1076 nil->right = newnode;
1077 newnode->left = nil;
