Initial intrusive list implementation
Change-Id: I08974c2fd6eb8a2bfe5221251faa3820f38361b6
Reviewed-on: https://pigweed-review.googlesource.com/c/pigweed/maize/+/258633
Lint: Lint 🤖 <android-build-ayeaye@system.gserviceaccount.com>
Reviewed-by: Travis Geiselbrecht <travisg@google.com>
Commit-Queue: Erik Gilling <konkers@google.com>
diff --git a/lib/list/BUILD.bazel b/lib/list/BUILD.bazel
new file mode 100644
index 0000000..4748110
--- /dev/null
+++ b/lib/list/BUILD.bazel
@@ -0,0 +1,32 @@
+# Copyright 2025 The Pigweed Authors
+#
+# Licensed under the Apache License, Version 2.0 (the "License"); you may not
+# use this file except in compliance with the License. You may obtain a copy of
+# the License at
+#
+# https://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+# WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+# License for the specific language governing permissions and limitations under
+# the License.
+
+load("@rules_rust//rust:defs.bzl", "rust_library", "rust_test")
+
+package(default_visibility = ["//visibility:public"])
+
+rust_library(
+ name = "list",
+ srcs = ["list.rs"],
+)
+
+rust_test(
+ name = "list_test",
+ crate = ":list",
+ use_libtest_harness = False,
+ deps = [
+ "//lib/unittest",
+ "//target:linker_script",
+ ],
+)
diff --git a/lib/list/list.rs b/lib/list/list.rs
new file mode 100644
index 0000000..9e7be6f
--- /dev/null
+++ b/lib/list/list.rs
@@ -0,0 +1,557 @@
+// Copyright 2025 The Pigweed Authors
+//
+// Licensed under the Apache License, Version 2.0 (the "License"); you may not
+// use this file except in compliance with the License. You may obtain a copy of
+// the License at
+//
+// https://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+// License for the specific language governing permissions and limitations under
+// the License.
+#![no_std]
+#![cfg_attr(test, no_main)]
+#![allow(dead_code)]
+use core::cell::UnsafeCell;
+use core::marker::PhantomData;
+use core::ptr::NonNull;
+
+// Intrusive link structures are particularly tricky in Rust because mutable
+// references are expected to be globally unique. Accessing the data through
+// other methods is UB. There is a good writeup of Tokio's soundness challenges
+// at: https://gist.github.com/Darksonn/1567538f56af1a8038ecc3c664a42462.
+//
+// Here we adapt the strategy that Tokio uses:
+// * The link pointer structure is marked with `PhantomPinned`. This does two
+// things. First it "poisons" the containing structure so that it's
+// unpinnable (immovable). Second it triggers the heuristic from
+// https://github.com/rust-lang/rust/pull/82834 which will cause the compiler
+// to omit emitting a `noalias` annotation on mutable references to disable
+// compiler optimization that assume the mutable reference is unique.
+// * `next` and `prev` themselves are accessed by `Link` through direct pointer
+// math on the `LinkInner` struct. This avoids creating mutable references to
+// those fields themselves which can not be annotated with `PhantomPinned`.
+// `LinkInner` is `#[repr(C)]` to make the pointer math deterministic.
+// `LinkInner` is declared in an `inner` module so that `next` and `prev` can
+// not be accessed directly be the rest of the code.
+//
+// TODO: konkers - Understand if we need to annotate the alignment of LinkInner.
+mod inner {
+ use core::{marker::PhantomPinned, mem::offset_of, ptr::NonNull};
+
+ use super::Link;
+
+ #[repr(C)]
+ pub struct LinkInner {
+ #[allow(dead_code)]
+ next: Option<NonNull<Link>>,
+ #[allow(dead_code)]
+ prev: Option<NonNull<Link>>,
+ _pin: PhantomPinned,
+ }
+
+ impl LinkInner {
+ pub const NEXT_OFFSET: usize = offset_of!(LinkInner, next);
+ pub const PREV_OFFSET: usize = offset_of!(LinkInner, prev);
+
+ pub const fn new() -> Self {
+ Self {
+ next: None,
+ prev: None,
+ _pin: PhantomPinned,
+ }
+ }
+ }
+}
+use inner::LinkInner;
+
+pub struct Link {
+ // UnsafeCell here is used to allow the code to access the data mutably.
+ // Bare mutable pointer access is unsound without this.
+ inner: UnsafeCell<LinkInner>,
+}
+
+#[inline]
+unsafe fn get_element(inner: &UnsafeCell<LinkInner>, offset: usize) -> Option<NonNull<Link>> {
+ let inner_ptr = inner.get() as *const Option<NonNull<Link>>;
+ let element_ptr = inner_ptr.byte_add(offset);
+ core::ptr::read(element_ptr)
+}
+
+#[inline]
+unsafe fn set_element(inner: &UnsafeCell<LinkInner>, offset: usize, value: Option<NonNull<Link>>) {
+ let inner_ptr = inner.get() as *mut Option<NonNull<Link>>;
+ let element_ptr = inner_ptr.byte_add(offset);
+ core::ptr::write(element_ptr, value);
+}
+
+impl Link {
+ pub const fn new() -> Self {
+ Self {
+ inner: UnsafeCell::new(LinkInner::new()),
+ }
+ }
+
+ pub fn is_unlinked(&self) -> bool {
+ self.get_next().is_none() && self.get_prev().is_none()
+ }
+
+ pub fn is_linked(&self) -> bool {
+ !self.is_unlinked()
+ }
+
+ #[inline]
+ fn get_next(&self) -> Option<NonNull<Link>> {
+ unsafe { get_element(&self.inner, LinkInner::NEXT_OFFSET) }
+ }
+
+ #[inline]
+ fn set_next(&mut self, value: Option<NonNull<Link>>) {
+ unsafe { set_element(&self.inner, LinkInner::NEXT_OFFSET, value) }
+ }
+
+ #[inline]
+ fn get_prev(&self) -> Option<NonNull<Link>> {
+ unsafe { get_element(&self.inner, LinkInner::PREV_OFFSET) }
+ }
+
+ #[inline]
+ fn set_prev(&mut self, value: Option<NonNull<Link>>) {
+ unsafe { set_element(&self.inner, LinkInner::PREV_OFFSET, value) }
+ }
+}
+
+impl Default for Link {
+ fn default() -> Self {
+ Self::new()
+ }
+}
+
+// `UnsafeList` uses None to mark the beginning and end of lists as opposed to
+// pointers to the base list node. This means that there are never pointers to
+// `UnsafeList` and the same care is not needed to avoid mutable references as
+// is taken with the `Link` structure.
+pub struct UnsafeList<T, A: Adapter> {
+ head: Option<NonNull<Link>>,
+ tail: Option<NonNull<Link>>,
+ _phantom_type: PhantomData<T>,
+ _phantom_adapter: PhantomData<A>,
+}
+
+pub trait Adapter {
+ const LINK_OFFSET: usize;
+}
+
+impl<T, A: Adapter> UnsafeList<T, A> {
+ pub const fn new() -> Self {
+ Self {
+ head: None,
+ tail: None,
+ _phantom_type: PhantomData,
+ _phantom_adapter: PhantomData,
+ }
+ }
+
+ /// # Safety
+ /// It is up to the caller to ensure exclusive access to the list and its
+ /// members.
+ pub unsafe fn is_empty(&self) -> bool {
+ self.head.is_none()
+ }
+
+ unsafe fn get_link_ptr(element: &T) -> NonNull<Link> {
+ let element_ptr: NonNull<Link> = core::mem::transmute::<&T, NonNull<Link>>(element);
+ element_ptr.byte_sub(A::LINK_OFFSET)
+ }
+
+ unsafe fn get_element_ptr(link: NonNull<Link>) -> *const T {
+ link.byte_add(A::LINK_OFFSET).as_ptr() as *const T
+ }
+
+ unsafe fn get_element_mut(link: NonNull<Link>) -> *mut T {
+ link.byte_add(A::LINK_OFFSET).as_ptr() as *mut T
+ }
+
+ /// unchecked means we don't `assert!((*element_ptr.as_ptr()).is_unlinked());`
+ ///
+ /// # Safety
+ /// It is up to the caller to ensure exclusive access to the list and its
+ /// members.
+ /// It is up to the caller to ensure the element is not in a list
+ pub unsafe fn push_front_unchecked(&mut self, element: &mut T) {
+ let element_ptr = Self::get_link_ptr(element);
+
+ // Link up the added element.
+ (*element_ptr.as_ptr()).set_next(self.head);
+ (*element_ptr.as_ptr()).set_prev(None);
+
+ match self.head {
+ // If `head` was `None`, the list is empty and `tail` should point
+ // to the added element.
+ None => self.tail = Some(element_ptr),
+
+ // If `head` is not `None`, point the previous `head` to the added
+ // element.
+ Some(head) => (*head.as_ptr()).set_prev(Some(element_ptr)),
+ }
+
+ // Finally point `head` to the added element.
+ self.head = Some(element_ptr);
+ }
+
+ /// unlinks element from the linked list.
+ ///
+ /// Precondition: element is in the link list.
+ unsafe fn unlink_element(&mut self, element: &T) {
+ let element_ptr = Self::get_link_ptr(element);
+
+ let prev = (*element_ptr.as_ptr()).get_prev();
+ let next = (*element_ptr.as_ptr()).get_next();
+
+ match prev {
+ // Element is at the head of the list
+ None => self.head = next,
+
+ // Element has elements before it in the list.
+ Some(prev_ptr) => (*prev_ptr.as_ptr()).set_next(next),
+ }
+
+ match next {
+ // Element is at the tail of the list
+ None => self.tail = prev,
+
+ // Element has elements after it in the list.
+ Some(next_ptr) => (*next_ptr.as_ptr()).set_prev(prev),
+ }
+ }
+
+ /// # Safety
+ /// It is up to the caller to ensure exclusive access to the list and its
+ /// members.
+ pub unsafe fn for_each<E, F: FnMut(&T) -> Result<(), E>>(
+ &self,
+ mut callback: F,
+ ) -> Result<(), E> {
+ let mut cur = self.head;
+
+ loop {
+ let Some(cur_ptr) = cur else {
+ break;
+ };
+
+ let element = Self::get_element_ptr(cur_ptr);
+ callback(&*element)?;
+
+ cur = (*cur_ptr.as_ptr()).get_next();
+ }
+
+ Ok(())
+ }
+
+ /// Filter iterates over every element in the list calling `callback` on
+ /// each one. If `callback` returns false, the element will be removed
+ /// from the list without modifying the element itself. It is safe to
+ /// add the element to the another linked list within `callback` if it
+ /// returns false.
+ ///
+ /// # Safety
+ /// It is up to the caller to ensure exclusive access to the list and its
+ /// members.
+ pub unsafe fn filter<F: FnMut(&mut T) -> bool>(&mut self, mut callback: F) {
+ let mut cur = self.head;
+
+ loop {
+ let Some(cur_ptr) = cur else {
+ break;
+ };
+
+ let element = Self::get_element_mut(cur_ptr);
+
+ // Cache the next element so that we don't rely on `element` staying
+ // coherent across calls to `callback`.
+ let next = (*cur_ptr.as_ptr()).get_next();
+
+ if !callback(&mut *element) {
+ self.unlink_element(&*element);
+ }
+
+ cur = next;
+ }
+ }
+}
+
+impl<T, A: Adapter> Default for UnsafeList<T, A> {
+ fn default() -> Self {
+ Self::new()
+ }
+}
+
+#[cfg(test)]
+mod tests {
+ use core::mem::offset_of;
+
+ use super::*;
+ use unittest::test;
+
+ struct TestMember {
+ value: u32,
+ link: Link,
+ }
+
+ struct TestAdapter {}
+ impl Adapter for TestAdapter {
+ const LINK_OFFSET: usize = offset_of!(TestMember, link);
+ }
+
+ unsafe fn validate_list(
+ list: &UnsafeList<TestMember, TestAdapter>,
+ expected_values: &[u32],
+ ) -> unittest::Result<()> {
+ let mut index = 0;
+ list.for_each(|element| {
+ unittest::assert_eq!(element.value, expected_values[index]);
+ index += 1;
+ Ok(())
+ })?;
+
+ unittest::assert_eq!(index, expected_values.len());
+ Ok(())
+ }
+
+ #[test]
+ fn new_link_is_not_linked() -> unittest::Result<()> {
+ let link = Link::new();
+ unittest::assert_false!(link.is_linked());
+ unittest::assert_true!(link.is_unlinked());
+ Ok(())
+ }
+
+ #[test]
+ fn new_list_is_empty() -> unittest::Result<()> {
+ let list = UnsafeList::<TestMember, TestAdapter>::new();
+ unittest::assert_true!(unsafe { list.is_empty() });
+ Ok(())
+ }
+
+ #[test]
+ fn push_front_adds_in_correct_order() -> unittest::Result<()> {
+ let mut element1 = TestMember {
+ value: 1,
+ link: Link::new(),
+ };
+ let mut element2 = TestMember {
+ value: 2,
+ link: Link::new(),
+ };
+
+ let mut list = UnsafeList::<TestMember, TestAdapter>::new();
+ unsafe { list.push_front_unchecked(&mut element2) };
+ unsafe { list.push_front_unchecked(&mut element1) };
+
+ unittest::assert_false!(unsafe { list.is_empty() });
+
+ unsafe { validate_list(&list, &[1, 2]) }
+ }
+
+ #[test]
+ fn unlink_removes_head_correctly() -> unittest::Result<()> {
+ let mut element1 = TestMember {
+ value: 1,
+ link: Link::new(),
+ };
+ let mut element2 = TestMember {
+ value: 2,
+ link: Link::new(),
+ };
+ let mut element3 = TestMember {
+ value: 3,
+ link: Link::new(),
+ };
+
+ let mut list = UnsafeList::<TestMember, TestAdapter>::new();
+ unsafe { list.push_front_unchecked(&mut element3) };
+ unsafe { list.push_front_unchecked(&mut element2) };
+ unsafe { list.push_front_unchecked(&mut element1) };
+
+ unsafe { list.unlink_element(&element1) };
+
+ unsafe { validate_list(&list, &[2, 3]) }
+ }
+
+ #[test]
+ fn unlink_removes_tail_correctly() -> unittest::Result<()> {
+ let mut element1 = TestMember {
+ value: 1,
+ link: Link::new(),
+ };
+ let mut element2 = TestMember {
+ value: 2,
+ link: Link::new(),
+ };
+ let mut element3 = TestMember {
+ value: 3,
+ link: Link::new(),
+ };
+
+ let mut list = UnsafeList::<TestMember, TestAdapter>::new();
+ unsafe { list.push_front_unchecked(&mut element3) };
+ unsafe { list.push_front_unchecked(&mut element2) };
+ unsafe { list.push_front_unchecked(&mut element1) };
+
+ unsafe { list.unlink_element(&element3) };
+
+ unsafe { validate_list(&list, &[1, 2]) }
+ }
+
+ #[test]
+ fn unlink_removes_middle_correctly() -> unittest::Result<()> {
+ let mut element1 = TestMember {
+ value: 1,
+ link: Link::new(),
+ };
+ let mut element2 = TestMember {
+ value: 2,
+ link: Link::new(),
+ };
+ let mut element3 = TestMember {
+ value: 3,
+ link: Link::new(),
+ };
+
+ let mut list = UnsafeList::<TestMember, TestAdapter>::new();
+ unsafe { list.push_front_unchecked(&mut element3) };
+ unsafe { list.push_front_unchecked(&mut element2) };
+ unsafe { list.push_front_unchecked(&mut element1) };
+
+ unsafe { list.unlink_element(&element2) };
+
+ unsafe { validate_list(&list, &[1, 3]) }
+ }
+
+ #[test]
+ fn filter_removes_nothing_correctly() -> unittest::Result<()> {
+ let mut element1 = TestMember {
+ value: 1,
+ link: Link::new(),
+ };
+ let mut element2 = TestMember {
+ value: 2,
+ link: Link::new(),
+ };
+ let mut element3 = TestMember {
+ value: 3,
+ link: Link::new(),
+ };
+
+ let mut list = UnsafeList::<TestMember, TestAdapter>::new();
+ unsafe { list.push_front_unchecked(&mut element3) };
+ unsafe { list.push_front_unchecked(&mut element2) };
+ unsafe { list.push_front_unchecked(&mut element1) };
+
+ unsafe { list.filter(|_| true) };
+
+ unsafe { validate_list(&list, &[1, 2, 3]) }
+ }
+
+ #[test]
+ fn filter_removes_everything_correctly() -> unittest::Result<()> {
+ let mut element1 = TestMember {
+ value: 1,
+ link: Link::new(),
+ };
+ let mut element2 = TestMember {
+ value: 2,
+ link: Link::new(),
+ };
+ let mut element3 = TestMember {
+ value: 3,
+ link: Link::new(),
+ };
+
+ let mut list = UnsafeList::<TestMember, TestAdapter>::new();
+ unsafe { list.push_front_unchecked(&mut element3) };
+ unsafe { list.push_front_unchecked(&mut element2) };
+ unsafe { list.push_front_unchecked(&mut element1) };
+
+ unsafe { list.filter(|_| false) };
+
+ unsafe { validate_list(&list, &[]) }
+ }
+
+ #[test]
+ fn filter_removes_head_correctly() -> unittest::Result<()> {
+ let mut element1 = TestMember {
+ value: 1,
+ link: Link::new(),
+ };
+ let mut element2 = TestMember {
+ value: 2,
+ link: Link::new(),
+ };
+ let mut element3 = TestMember {
+ value: 3,
+ link: Link::new(),
+ };
+
+ let mut list = UnsafeList::<TestMember, TestAdapter>::new();
+ unsafe { list.push_front_unchecked(&mut element3) };
+ unsafe { list.push_front_unchecked(&mut element2) };
+ unsafe { list.push_front_unchecked(&mut element1) };
+
+ unsafe { list.filter(|element| element.value != 1) };
+
+ unsafe { validate_list(&list, &[2, 3]) }
+ }
+
+ #[test]
+ fn filter_removes_middle_correctly() -> unittest::Result<()> {
+ let mut element1 = TestMember {
+ value: 1,
+ link: Link::new(),
+ };
+ let mut element2 = TestMember {
+ value: 2,
+ link: Link::new(),
+ };
+ let mut element3 = TestMember {
+ value: 3,
+ link: Link::new(),
+ };
+
+ let mut list = UnsafeList::<TestMember, TestAdapter>::new();
+ unsafe { list.push_front_unchecked(&mut element3) };
+ unsafe { list.push_front_unchecked(&mut element2) };
+ unsafe { list.push_front_unchecked(&mut element1) };
+
+ unsafe { list.filter(|element| element.value != 2) };
+
+ unsafe { validate_list(&list, &[1, 3]) }
+ }
+
+ #[test]
+ fn filter_removes_tail_correctly() -> unittest::Result<()> {
+ let mut element1 = TestMember {
+ value: 1,
+ link: Link::new(),
+ };
+ let mut element2 = TestMember {
+ value: 2,
+ link: Link::new(),
+ };
+ let mut element3 = TestMember {
+ value: 3,
+ link: Link::new(),
+ };
+
+ let mut list = UnsafeList::<TestMember, TestAdapter>::new();
+ unsafe { list.push_front_unchecked(&mut element3) };
+ unsafe { list.push_front_unchecked(&mut element2) };
+ unsafe { list.push_front_unchecked(&mut element1) };
+
+ unsafe { list.filter(|element| element.value != 3) };
+
+ unsafe { validate_list(&list, &[1, 2]) }
+ }
+}
