Lines Matching defs:node
80 rb_node_minimum(struct rb_node *node)
82 while (node->left)
83 node = node->left;
84 return node;
88 rb_node_maximum(struct rb_node *node)
90 while (node->right)
91 node = node->right;
92 return node;
106 * The node to be replaced is assumed to be a non-leaf.
156 struct rb_node *node, bool insert_left)
159 memset(node, 0, sizeof(*node));
163 T->root = node;
164 rb_node_set_black(node);
170 parent->left = node;
173 parent->right = node;
175 rb_node_set_parent(node, parent);
178 struct rb_node *z = node;
232 /* x_p is always the parent node of X. We have to track this
247 /* Find the minimum sub-node of z->right */
344 rb_node_next(struct rb_node *node)
346 if (node->right) {
348 * node) is the left-most child of our right child.
350 return rb_node_minimum(node->right);
352 /* If node doesn't have a right child, crawl back up the to the
355 struct rb_node *p = rb_node_parent(node);
356 while (p && node == p->right) {
357 node = p;
358 p = rb_node_parent(node);
360 assert(p == NULL || node == p->left);
366 rb_node_prev(struct rb_node *node)
368 if (node->left) {
370 * this node) is the right-most child of our left child.
372 return rb_node_maximum(node->left);
374 /* If node doesn't have a left child, crawl back up the to the
377 struct rb_node *p = rb_node_parent(node);
378 while (p && node == p->left) {
379 node = p;
380 p = rb_node_parent(node);
382 assert(p == NULL || node == p->right);