Lines Matching defs:node
96 /// In the example below, we first allocate a node, acquire a spinlock, then insert the node into
104 /// // Pre-allocate node. This may fail (as it allocates memory).
105 /// let node = RBTreeNode::new(10, 100, flags::GFP_KERNEL)?;
107 /// // Insert node while holding the lock. It is guaranteed to succeed with no allocation
110 /// guard.insert(node);
115 /// In the example below, we reuse an existing node allocation from an element we removed.
137 /// // Remove a node, getting back ownership of it.
151 /// // Insert a new node into the tree, reusing the previous allocation. This is guaranteed to
170 /// valid, and pointing to a field of our internal representation of a node.
206 // - `bindings::rb_first` produces a valid pointer to a node given `root` is valid.
221 // - `bindings::rb_first` produces a valid pointer to a node given `root` is valid.
248 // SAFETY: `self.root` is always a valid root node.
252 // - `current` is a valid node in the [`RBTree`] pointed to by `self`.
263 // SAFETY: `self.root` is always a valid root node.
267 // - `current` is a valid node in the [`RBTree`] pointed to by `self`.
278 // SAFETY: `self.root` is always a valid root node.
282 // - `current` is a valid node in the [`RBTree`] pointed to by `self`.
293 // SAFETY: `self.root` is always a valid root node.
297 // - `current` is a valid node in the [`RBTree`] pointed to by `self`.
312 /// It overwrites a node if one already exists with the same key and returns it (containing the
313 /// key/value pair). Returns [`None`] if a node with the same key didn't already exist.
315 /// Returns an error if it cannot allocate memory for the new node.
325 /// Inserts a new node into the tree.
327 /// It overwrites a node if one already exists with the same key and returns it (containing the
328 /// key/value pair). Returns [`None`] if a node with the same key didn't already exist.
331 pub fn insert(&mut self, node: RBTreeNode<K, V>) -> Option<RBTreeNode<K, V>> {
332 match self.raw_entry(&node.node.key) {
333 RawEntry::Occupied(entry) => Some(entry.replace(node)),
335 entry.insert(node);
345 // - `node`: A pointer to an uninitialized node being inserted.
346 // - `parent`: A pointer to an existing node in the tree. One of its child pointers must be
347 // null, and `node` will become a child of `parent` by replacing that child pointer
348 // with a pointer to `node`.
350 // specifies which child of `parent` should hold `node` after this call. The
355 // We will traverse the tree looking for a node that has a null pointer as its child,
356 // representing an empty subtree where we can insert our new node. We need to make sure
358 // we store `parent` and `child_field_of_parent`, and the new `node` will go somewhere
360 // we find an empty subtree, we can insert the new node using `rb_link_node`.
368 let node = unsafe { container_of!(curr, Node<K, V>, links) };
370 // SAFETY: `node` is a non-null node so it is valid by the type invariants.
371 match key.cmp(unsafe { &(*node).key }) {
372 // SAFETY: `curr` is a non-null node so it is valid by the type invariants.
374 // SAFETY: `curr` is a non-null node so it is valid by the type invariants.
402 /// Used for accessing the given node, if it exists.
412 let mut node = self.root.rb_node;
413 while !node.is_null() {
416 let this = unsafe { container_of!(node, Node<K, V>, links) };
418 // SAFETY: `this` is a non-null node so it is valid by the type invariants.
421 // SAFETY: `node` is a non-null node so it is valid by the type invariants.
422 let node_ref = unsafe { &*node };
424 node = match key.cmp(&this_ref.key) {
435 self.find_mut(key).map(|node| node.into_mut())
438 /// Removes the node with the given key from the tree.
440 /// It returns the node that was removed if one exists, or [`None`] otherwise.
445 /// Removes the node with the given key from the tree.
465 // - `current` is a valid node in the [`RBTree`] pointed to by `self`.
486 // - `current` is a valid node in the [`RBTree`] pointed to by `self`.
495 let mut node = self.root.rb_node;
498 while !node.is_null() {
501 let this = unsafe { container_of!(node, Node<K, V>, links) };
502 // SAFETY: `this` is a non-null node so it is valid by the type invariants.
505 // SAFETY: `node` is a non-null node so it is valid by the type invariants.
506 let node_ref = unsafe { &*node };
510 // SAFETY: `this` is a non-null node so it is valid by the type invariants.
515 node = node_ref.rb_right;
524 // SAFETY: `this` is a non-null node so it is valid by the type invariants.
527 node = node_ref.rb_left;
551 // Find out what the next node is before disposing of the current one.
639 /// [`RBTree::cursor_lower_bound`] can be used to start at an arbitrary node in the tree.
698 /// It also allows node removal. The following examples demonstrate the behavior of removing the current node.
717 /// // If a node exists after the current element, it is returned.
726 /// // Since there is no next node, the previous node is returned.
737 /// Nodes adjacent to the current node can also be removed.
782 /// - `current` points to a node that is in the same [`RBTree`] as `tree`.
828 /// The current node
831 // - `self.current` is a valid node by the type invariants.
838 /// - `node` must be a valid pointer to a node in an [`RBTree`].
839 /// - The caller has immutable access to `node` for the duration of `'b`.
840 unsafe fn to_key_value<'b>(node: NonNull<bindings::rb_node>) -> (&'b K, &'b V) {
843 let this = unsafe { container_of!(node.as_ptr(), Node<K, V>, links) };
844 // SAFETY: The passed `node` is the current node or a non-null neighbor,
847 // SAFETY: The passed `node` is the current node or a non-null neighbor,
853 /// Access the previous node without moving the cursor.
858 /// Access the next node without moving the cursor.
866 // - `neighbor` is a valid tree node.
897 /// The current node.
900 // - `self.current` is a valid node by the type invariants.
905 /// The current node, with a mutable value
908 // - `self.current` is a valid node by the type invariants.
913 /// Remove the current node from the tree.
915 /// Returns a tuple where the first element is a cursor to the next node, if it exists,
916 /// else the previous node, else [`None`] (if the tree becomes empty). The second element
917 /// is the removed node.
925 let node = unsafe { KBox::from_raw(this) };
926 let node = RBTreeNode { node };
932 // - `current` is a valid node in the [`RBTree`] pointed to by `self.tree`.
938 (cursor, node)
941 /// Remove the previous node, returning it if it exists.
946 /// Remove the next node, returning it if it exists.
961 let node = unsafe { KBox::from_raw(this) };
962 return Some(RBTreeNode { node });
967 /// Move the cursor to the previous node, returning [`None`] if it doesn't exist.
972 /// Move the cursor to the next node, returning [`None`] if it doesn't exist.
979 // - `neighbor` is a valid node in the [`RBTree`] pointed to by `self.tree`.
986 /// Access the previous node without moving the cursor.
991 /// Access the next node without moving the cursor.
999 // - `neighbor` is a valid tree node.
1005 /// Access the previous node mutably without moving the cursor.
1010 /// Access the next node mutably without moving the cursor.
1018 // - `neighbor` is a valid tree node.
1038 /// - `node` must be a valid pointer to a node in an [`RBTree`].
1039 /// - The caller has immutable access to `node` for the duration of `'b`.
1040 unsafe fn to_key_value<'b>(node: NonNull<bindings::rb_node>) -> (&'b K, &'b V) {
1041 // SAFETY: the caller guarantees that `node` is a valid pointer in an `RBTree`.
1042 let (k, v) = unsafe { Self::to_key_value_raw(node) };
1043 // SAFETY: the caller guarantees immutable access to `node`.
1049 /// - `node` must be a valid pointer to a node in an [`RBTree`].
1050 /// - The caller has mutable access to `node` for the duration of `'b`.
1051 unsafe fn to_key_value_mut<'b>(node: NonNull<bindings::rb_node>) -> (&'b K, &'b mut V) {
1052 // SAFETY: the caller guarantees that `node` is a valid pointer in an `RBTree`.
1053 let (k, v) = unsafe { Self::to_key_value_raw(node) };
1054 // SAFETY: the caller guarantees mutable access to `node`.
1060 /// - `node` must be a valid pointer to a node in an [`RBTree`].
1062 unsafe fn to_key_value_raw<'b>(node: NonNull<bindings::rb_node>) -> (&'b K, *mut V) {
1065 let this = unsafe { container_of!(node.as_ptr(), Node<K, V>, links) };
1066 // SAFETY: The passed `node` is the current node or a non-null neighbor,
1069 // SAFETY: The passed `node` is the current node or a non-null neighbor,
1078 /// the node immediately before, in sort order
1080 /// the node immediately after, in sort order
1158 /// - `self.next` points to a node stored inside of a valid `RBTree`.
1172 // SAFETY: By the type invariant of `IterRaw`, `self.next` is a valid node in an `RBTree`,
1176 // SAFETY: `self.next` is a valid tree node by the type invariants.
1179 // SAFETY: By the same reasoning above, it is safe to dereference the node.
1184 /// A memory reservation for a red-black tree node.
1187 /// It contains the memory needed to hold a node that can be inserted into a red-black tree. One
1190 node: KBox<MaybeUninit<Node<K, V>>>,
1194 /// Allocates memory for a node to be eventually initialised and inserted into the tree via a
1198 node: KBox::new_uninit(flags)?,
1211 /// Initialises a node reservation.
1215 let node = KBox::write(
1216 self.node,
1223 RBTreeNode { node }
1227 /// A red-black tree node.
1229 /// The node is fully initialised (with key and value) and can be inserted into a tree without any
1232 node: KBox<Node<K, V>>,
1236 /// Allocates and initialises a node that can be inserted into the tree via
1242 /// Get the key and value from inside the node.
1244 let node = KBox::into_inner(self.node);
1246 (node.key, node.value)
1261 /// It then becomes a reservation that can be re-initialised into a different node (i.e., with
1265 /// may be freed (but only for the key/value; memory for the node itself is kept for reuse).
1268 node: KBox::drop_contents(self.node),
1279 /// This [`RBTree`] does not have a node with this key.
1281 /// This [`RBTree`] already has a node with this key.
1300 /// - `parent` may be null if the new node becomes the root.
1305 /// The node that will become the parent of the new node if we insert one.
1314 /// Inserts the given node into the [`RBTree`] at this entry.
1316 /// The `node` must have a key such that inserting it here does not break the ordering of this
1318 fn insert(self, node: RBTreeNode<K, V>) -> &'a mut V {
1319 let node = KBox::into_raw(node.node);
1321 // SAFETY: `node` is valid at least until we call `KBox::from_raw`, which only happens when
1322 // the node is removed or replaced.
1323 let node_links = unsafe { addr_of_mut!((*node).links) };
1325 // INVARIANT: We are linking in a new node, which is valid. It remains valid because we
1330 // SAFETY: All pointers are valid. `node` has just been inserted into the tree.
1333 // SAFETY: The node is valid until we remove it from the tree.
1334 unsafe { &mut (*node).value }
1339 /// Inserts the given node into the [`RBTree`] at this entry.
1348 /// - `node_links` is a valid, non-null pointer to a tree node in `self.rbtree`
1351 /// The node that this entry corresponds to.
1359 // - `self.node_links` is a valid pointer to a node in the tree.
1367 // - `self.node_links` is a valid pointer to a node in the tree.
1377 // - `self.node_links` is a valid pointer to a node in the tree.
1384 // SAFETY: The node is a node in the tree, so it is valid.
1387 // INVARIANT: The node is being returned and the caller may free it, however, it was
1390 // SAFETY: The node was a node in the tree, but we removed it, so we can convert it
1392 node: unsafe { KBox::from_raw(container_of!(self.node_links, Node<K, V>, links)) },
1399 let node = KBox::into_inner(rb_node.node);
1401 node.value
1404 /// Swap the current node for the provided node.
1407 fn replace(self, node: RBTreeNode<K, V>) -> RBTreeNode<K, V> {
1408 let node = KBox::into_raw(node.node);
1410 // SAFETY: `node` is valid at least until we call `KBox::from_raw`, which only happens when
1411 // the node is removed or replaced.
1412 let new_node_links = unsafe { addr_of_mut!((*node).links) };
1421 // - `self.node_ptr` produces a valid pointer to a node in the tree.
1422 // - Now that we removed this entry from the tree, we can convert the node to a box.
1425 RBTreeNode { node: old_node }