Lines Matching refs:node
31 /** A red-black tree node
33 * This struct represents a node in the red-black tree. This struct should
38 /** Parent and color of this node
47 /** Left child of this node, null for a leaf */
50 /** Right child of this node, null for a leaf */
54 /** Return the parent node of the given node or NULL if it is the root */
64 * to the root node with no other metadata.
80 /** Retrieve the data structure containing a node
84 * \param node A pointer to a rb_node
88 #define rb_node_data(type, node, field) \
89 ((type *)(((char *)(node)) - offsetof(type, field)))
91 /** Insert a node into a tree at a particular location
94 * caller to ensure that the parent node is correct. Use rb_tree_insert
97 * \param T The red-black tree into which to insert the new node
99 * \param parent The node in the tree that will be the parent of the
100 * newly inserted node
102 * \param node The node to insert
104 * \param insert_left If true, the new node will be the left child of
108 struct rb_node *node, bool insert_left);
110 /** Insert a node into a tree
112 * \param T The red-black tree into which to insert the new node
114 * \param node The node to insert
119 rb_tree_insert(struct rb_tree *T, struct rb_node *node,
130 left = cmp(node, x) < 0;
137 rb_tree_insert_at(T, y, node, left);
140 /** Remove a node from a tree
142 * \param T The red-black tree from which to remove the node
144 * \param node The node to remove
148 /** Search the tree for a node
150 * If a node with a matching key exists, the first matching node found will
151 * be returned. If no matching node exists, NULL is returned.
180 /** Sloppily search the tree for a node
182 * This function searches the tree for a given node. If a node with a
183 * matching key exists, that first matching node found will be returned.
184 * If no node with an exactly matching key exists, the node returned will
185 * be either the right-most node comparing less than \p key or the
186 * right-most node comparing greater than \p key. If the tree is empty,
218 /** Get the first (left-most) node in the tree or NULL */
221 /** Get the last (right-most) node in the tree or NULL */
224 /** Get the next node (to the right) in the tree or NULL */
225 struct rb_node *rb_node_next(struct rb_node *node);
228 struct rb_node *rb_node_prev(struct rb_node *node);
230 /** Get the next node if available or the same node again.
234 * \param node The variable name for current node in the iteration;
239 #define rb_tree_node_next_if_available(type, node, field) \
240 (&node->field != NULL) ? rb_node_data(type, rb_node_next(&node->field), field) : node
242 /** Get the previous node if available or the same node again.
246 * \param node The variable name for current node in the iteration;
251 #define rb_tree_node_prev_if_available(type, node, field) \
252 (&node->field != NULL) ? rb_node_data(type, rb_node_prev(&node->field), field) : node
258 * \param node The variable name for current node in the iteration;
265 #define rb_tree_foreach(type, node, T, field) \
266 for (type *node = rb_node_data(type, rb_tree_first(T), field); \
267 &node->field != NULL; \
268 node = rb_node_data(type, rb_node_next(&node->field), field))
270 /** Iterate over the nodes in the tree, allowing the current node to be freed
274 * \param node The variable name for current node in the iteration;
281 #define rb_tree_foreach_safe(type, node, T, field) \
282 for (type *node = rb_node_data(type, rb_tree_first(T), field), \
283 *__next = rb_tree_node_next_if_available(type, node, field); \
284 &node->field != NULL; \
285 node = __next, __next = rb_tree_node_next_if_available(type, node, field))
291 * \param node The variable name for current node in the iteration;
298 #define rb_tree_foreach_rev(type, node, T, field) \
299 for (type *node = rb_node_data(type, rb_tree_last(T), field); \
300 &node->field != NULL; \
301 node = rb_node_data(type, rb_node_prev(&node->field), field))
303 /** Iterate over the nodes in the tree in reverse, allowing the current node to be freed
307 * \param node The variable name for current node in the iteration;
314 #define rb_tree_foreach_rev_safe(type, node, T, field) \
315 for (type *node = rb_node_data(type, rb_tree_last(T), field), \
316 *__prev = rb_tree_node_prev_if_available(type, node, field); \
317 &node->field != NULL; \
318 node = __prev, __prev = rb_tree_node_prev_if_available(type, node, field))