Lines Matching defs:node
25 static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)
27 struct rb_node *right = node->rb_right;
28 struct rb_node *parent = rb_parent(node);
30 if ((node->rb_right = right->rb_left))
31 rb_set_parent(right->rb_left, node);
32 right->rb_left = node;
38 if (node == parent->rb_left)
45 rb_set_parent(node, right);
48 static void __rb_rotate_right(struct rb_node *node, struct rb_root *root)
50 struct rb_node *left = node->rb_left;
51 struct rb_node *parent = rb_parent(node);
53 if ((node->rb_left = left->rb_right))
54 rb_set_parent(left->rb_right, node);
55 left->rb_right = node;
61 if (node == parent->rb_right)
68 rb_set_parent(node, left);
71 void rb_insert_color(struct rb_node *node, struct rb_root *root)
75 while ((parent = rb_parent(node)) && rb_is_red(parent))
88 node = gparent;
93 if (parent->rb_right == node)
98 parent = node;
99 node = tmp;
113 node = gparent;
118 if (parent->rb_left == node)
123 parent = node;
124 node = tmp;
136 static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
141 while ((!node || rb_is_black(node)) && node != root->rb_node)
143 if (parent->rb_left == node)
157 node = parent;
158 parent = rb_parent(node);
176 node = root->rb_node;
194 node = parent;
195 parent = rb_parent(node);
213 node = root->rb_node;
218 if (node)
219 rb_set_black(node);
222 void rb_erase(struct rb_node *node, struct rb_root *root)
227 if (!node->rb_left)
228 child = node->rb_right;
229 else if (!node->rb_right)
230 child = node->rb_left;
233 struct rb_node *old = node, *left;
235 node = node->rb_right;
236 while ((left = node->rb_left) != NULL)
237 node = left;
238 child = node->rb_right;
239 parent = rb_parent(node);
240 color = rb_color(node);
246 parent = node;
250 node->rb_parent_color = old->rb_parent_color;
251 node->rb_right = old->rb_right;
252 node->rb_left = old->rb_left;
257 rb_parent(old)->rb_left = node;
259 rb_parent(old)->rb_right = node;
261 root->rb_node = node;
263 rb_set_parent(old->rb_left, node);
265 rb_set_parent(old->rb_right, node);
269 parent = rb_parent(node);
270 color = rb_color(node);
276 if (parent->rb_left == node)
290 * This function returns the first node (in sort order) of the tree.
316 struct rb_node *rb_next(struct rb_node *node)
320 if (rb_parent(node) == node)
325 if (node->rb_right) {
326 node = node->rb_right;
327 while (node->rb_left)
328 node=node->rb_left;
329 return node;
333 smaller than us, so any 'next' node must be in the general
337 parent is our 'next' node. */
338 while ((parent = rb_parent(node)) && node == parent->rb_right)
339 node = parent;
344 struct rb_node *rb_prev(struct rb_node *node)
348 if (rb_parent(node) == node)
353 if (node->rb_left) {
354 node = node->rb_left;
355 while (node->rb_right)
356 node=node->rb_right;
357 return node;
362 while ((parent = rb_parent(node)) && node == parent->rb_left)
363 node = parent;