customizable_buddy/
linked_list.rs

1use crate::{BuddyCollection, BuddyLine, OligarchyCollection, Order};
2use core::{fmt, ptr::NonNull};
3
4/// 侵入式链表伙伴行。
5pub struct LinkedListBuddy {
6    free_list: Node,
7    order: Order,
8}
9
10/// 必须实现 [`Send`] 才能加锁。
11unsafe impl Send for LinkedListBuddy {}
12
13impl BuddyLine for LinkedListBuddy {
14    const INTRUSIVE_META_SIZE: usize = core::mem::size_of::<Node>();
15
16    const EMPTY: Self = Self {
17        free_list: Node { next: None },
18        order: Order::new(0),
19    };
20
21    #[inline]
22    fn init(&mut self, order: usize, _base: usize) {
23        self.order = Order::new(order);
24    }
25
26    fn take(&mut self, _idx: usize) -> bool {
27        // TODO 可以实现，但没有效率
28        unimplemented!("not efficient")
29    }
30}
31
32impl OligarchyCollection for LinkedListBuddy {
33    #[inline]
34    fn take_any(&mut self, align_order: usize, count: usize) -> Option<usize> {
35        if count > 1 || align_order > 0 {
36            // TODO 不支持
37            None
38        } else {
39            self.free_list
40                .take_any()
41                .map(|ptr| self.order.ptr_to_idx(ptr))
42        }
43    }
44
45    #[inline]
46    fn put(&mut self, idx: usize) {
47        self.free_list
48            .insert_unordered(unsafe { self.order.idx_to_ptr(idx) });
49    }
50}
51
52impl BuddyCollection for LinkedListBuddy {
53    #[inline]
54    fn take_any(&mut self, align_order: usize) -> Option<usize> {
55        if align_order != 0 {
56            // TODO 需要支持对齐吗？没效率，似乎没必要
57            None
58        } else {
59            self.free_list
60                .take_any()
61                .map(|ptr| self.order.ptr_to_idx(ptr))
62        }
63    }
64
65    fn put(&mut self, idx: usize) -> Option<usize> {
66        // 伙伴和当前结点存在链表的同一个位置。
67        let node = unsafe { self.order.idx_to_ptr(idx) };
68        let buddy = unsafe { self.order.idx_to_ptr(idx ^ 1) };
69        if self.free_list.insert(node, buddy) {
70            None
71        } else {
72            // 插入失败说明伙伴已碰头
73            Some(idx >> 1)
74        }
75    }
76}
77
78impl fmt::Debug for LinkedListBuddy {
79    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
80        write!(f, "[")?;
81        let mut cursor = &self.free_list;
82        while let Some(next) = cursor.next {
83            write!(f, "{:#x}, ", self.order.ptr_to_idx(next))?;
84            cursor = unsafe { next.as_ref() };
85        }
86        write!(f, "]")
87    }
88}
89
90#[repr(transparent)]
91struct Node {
92    next: Option<NonNull<Node>>,
93}
94
95impl Node {
96    /// 插入结点，如果插入成功返回 `true`。
97    /// 如果目标结点存在，则返回 `false`，且存在的结点也被移除。
98    ///
99    /// # Notice
100    ///
101    /// 这个函数可以尾递归的，但 Rust 并不支持优化尾递归。
102    #[inline]
103    fn insert(&mut self, mut node: NonNull<Node>, buddy: NonNull<Node>) -> bool {
104        let mut cursor = self;
105        loop {
106            if let Some(mut next) = cursor.next {
107                use core::cmp::Ordering::*;
108                match next.cmp(&buddy) {
109                    // 新结点更大，找下一个
110                    Less => cursor = unsafe { next.as_mut() },
111                    // 相等，移除这一个
112                    Equal => {
113                        cursor.next = unsafe { next.as_ref().next };
114                        unsafe { node.as_mut() }.next = None;
115                        break false;
116                    }
117                    // 新结点更小，插入
118                    Greater => {
119                        cursor.next = Some(node);
120                        unsafe { node.as_mut() }.next = Some(next);
121                        break true;
122                    }
123                }
124            } else {
125                // 没有下一个，插入
126                cursor.next = Some(node);
127                unsafe { node.as_mut() }.next = None;
128                break true;
129            }
130        }
131    }
132
133    /// 直接在头结点插入。
134    #[inline]
135    fn insert_unordered(&mut self, mut node: NonNull<Node>) {
136        unsafe { node.as_mut() }.next = core::mem::replace(&mut self.next, Some(node));
137    }
138
139    /// 直接取下头结点。
140    #[inline]
141    fn take_any(&mut self) -> Option<NonNull<Node>> {
142        let root = self.next;
143        self.next = root.and_then(|node| unsafe { node.as_ref().next });
144        root
145    }
146}
customizable_buddy/linked_list.rs

customizable_buddy/
linked_list.rs
