1 // Copyright (c) 2023 Huawei Device Co., Ltd.
2 // Licensed under the Apache License, Version 2.0 (the "License");
3 // you may not use this file except in compliance with the License.
4 // You may obtain a copy of the License at
5 //
6 //     http://www.apache.org/licenses/LICENSE-2.0
7 //
8 // Unless required by applicable law or agreed to in writing, software
9 // distributed under the License is distributed on an "AS IS" BASIS,
10 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11 // See the License for the specific language governing permissions and
12 // limitations under the License.
13 
14 //! This linked list does not have ownership of nodes, and it treats the
15 //! structure passed in by the user as a node for storage, so the `clear`
16 //! operation does not release memory, and the `remove` operation needs to
17 //! ensure that the node is in any linked list held by a caller to ensure the
18 //! memory validity of pointers within the node. Users need to manage the memory
19 //! of the instances associated with each node themselves.
20 
21 #![cfg_attr(feature = "ffrt", allow(unused))]
22 
23 use std::ptr::NonNull;
24 
25 #[derive(Default)]
26 #[repr(C)]
27 pub(crate) struct Node<T> {
28     prev: Option<NonNull<T>>,
29     next: Option<NonNull<T>>,
30 }
31 
32 impl<T> Node<T> {
new() -> Node<T>33     pub(crate) fn new() -> Node<T> {
34         Node {
35             prev: None,
36             next: None,
37         }
38     }
39 }
40 
41 impl<T: Link> Node<T> {
remove_node(node: NonNull<T>) -> Option<NonNull<T>>42     unsafe fn remove_node(node: NonNull<T>) -> Option<NonNull<T>> {
43         let prev = T::node(node).as_ref().prev;
44         let next = T::node(node).as_ref().next;
45         match prev {
46             None => return None,
47             Some(prev) => T::node(prev).as_mut().next = next,
48         }
49         match next {
50             None => return None,
51             Some(next) => T::node(next).as_mut().prev = prev,
52         }
53         T::node(node).as_mut().prev = None;
54         T::node(node).as_mut().next = None;
55         Some(node)
56     }
57 }
58 
59 unsafe impl<T: Send> Send for Node<T> {}
60 unsafe impl<T: Sync> Sync for Node<T> {}
61 
62 pub(crate) struct LinkedList<L: Link + Default> {
63     head: NonNull<L>,
64 }
65 
66 unsafe impl<L: Link + Default + Send> Send for LinkedList<L> {}
67 unsafe impl<L: Link + Default + Sync> Sync for LinkedList<L> {}
68 
69 /// Defines the structure of a linked list node.
70 /// Provides methods for converting between nodes and instances.
71 ///
72 /// # Safety
73 ///
74 /// The implementation must ensure that the inserted data does not move in
75 /// memory.
76 pub(crate) unsafe trait Link {
node(ptr: NonNull<Self>) -> NonNull<Node<Self>> where Self: Sized77     unsafe fn node(ptr: NonNull<Self>) -> NonNull<Node<Self>>
78     where
79         Self: Sized;
80 }
81 
82 impl<L: Link + Default> LinkedList<L> {
83     /// Constructs a new linked list.
new() -> LinkedList<L>84     pub(crate) fn new() -> LinkedList<L> {
85         let head = Box::<L>::default();
86         let head_ptr = unsafe { NonNull::new_unchecked(Box::into_raw(head)) };
87         let node = unsafe { L::node(head_ptr).as_mut() };
88         node.prev = Some(head_ptr);
89         node.next = Some(head_ptr);
90         LinkedList { head: head_ptr }
91     }
92 
93     /// Inserts an element to the front of the list.
push_front(&mut self, val: NonNull<L>)94     pub(crate) fn push_front(&mut self, val: NonNull<L>) {
95         unsafe {
96             let head = L::node(self.head).as_mut();
97             L::node(val).as_mut().next = head.next;
98             L::node(val).as_mut().prev = Some(self.head);
99 
100             let node = Some(val);
101             if let Some(first) = head.next {
102                 L::node(first).as_mut().prev = node;
103             }
104             head.next = node;
105         }
106     }
107 
108     /// Pops an element from the back of the list.
pop_back(&mut self) -> Option<NonNull<L>>109     pub(crate) fn pop_back(&mut self) -> Option<NonNull<L>> {
110         unsafe {
111             let head = L::node(self.head).as_mut();
112             if head.prev != Some(self.head) {
113                 // the queue is not empty, so prev must be some
114                 let node = head.prev.take().unwrap();
115                 Node::remove_node(node);
116                 Some(node)
117             } else {
118                 None
119             }
120         }
121     }
122 
123     /// Deletes an element in list.
124     ///
125     /// # Safety
126     ///
127     /// This method can be safely used when the node is in a guarded linked list
128     /// that the caller has unique access to or the node is not in any
129     /// linked list.
130     #[cfg(any(feature = "time", feature = "net"))]
remove(&mut self, node: NonNull<L>) -> Option<NonNull<L>>131     pub(crate) unsafe fn remove(&mut self, node: NonNull<L>) -> Option<NonNull<L>> {
132         Node::remove_node(node)
133     }
134 
135     /// Checks whether the list is empty.
136     #[cfg(feature = "time")]
is_empty(&self) -> bool137     pub(crate) fn is_empty(&self) -> bool {
138         unsafe { L::node(self.head).as_ref().next == Some(self.head) }
139     }
140 
141     /// Traverses the list and applies the closure on each element. If the
142     /// element meets the condition, removes it from the list.
143     #[cfg(feature = "net")]
drain_filtered<F>(&mut self, mut f: F) where F: FnMut(&mut L) -> bool,144     pub(crate) fn drain_filtered<F>(&mut self, mut f: F)
145     where
146         F: FnMut(&mut L) -> bool,
147     {
148         unsafe {
149             let head = L::node(self.head).as_ref();
150             let mut p = head.next;
151             while p != Some(self.head) {
152                 // p is not head, therefore it must be some
153                 let node = p.unwrap();
154                 let next = L::node(node).as_ref().next;
155                 if f(&mut *node.as_ptr()) {
156                     Node::remove_node(node);
157                 }
158                 p = next;
159             }
160         }
161     }
162 }
163 
164 impl<L: Link + Default> Default for LinkedList<L> {
default() -> Self165     fn default() -> Self {
166         LinkedList::new()
167     }
168 }
169 
170 impl<L: Link + Default> Drop for LinkedList<L> {
drop(&mut self)171     fn drop(&mut self) {
172         let _ = unsafe { Box::from_raw(self.head.as_ptr()) };
173     }
174 }
175 
176 #[cfg(test)]
177 mod tests {
178     use std::ptr::{addr_of_mut, NonNull};
179 
180     use crate::util::linked_list::{Link, LinkedList, Node};
181 
182     #[derive(Default)]
183     struct Entry {
184         val: usize,
185         node: Node<Entry>,
186     }
187 
188     impl Entry {
new(val: usize) -> Entry189         fn new(val: usize) -> Entry {
190             Entry {
191                 val,
192                 node: Node::new(),
193             }
194         }
195 
get_ptr(&self) -> NonNull<Self>196         fn get_ptr(&self) -> NonNull<Self> {
197             NonNull::from(self)
198         }
199     }
200 
address_of_node(mut ptr: NonNull<Entry>) -> NonNull<Node<Entry>>201     unsafe fn address_of_node(mut ptr: NonNull<Entry>) -> NonNull<Node<Entry>> {
202         let node_ptr = addr_of_mut!(ptr.as_mut().node);
203         NonNull::new_unchecked(node_ptr)
204     }
205 
get_val(ptr: NonNull<Entry>) -> usize206     fn get_val(ptr: NonNull<Entry>) -> usize {
207         unsafe { ptr.as_ref().val }
208     }
209 
210     unsafe impl Link for Entry {
node(ptr: NonNull<Self>) -> NonNull<Node<Self>>211         unsafe fn node(ptr: NonNull<Self>) -> NonNull<Node<Self>> {
212             address_of_node(ptr)
213         }
214     }
215 
216     /// UT test cases for `is_empty()` and `clear()`.
217     ///
218     /// # Brief
219     /// 1. Create a linked list.
220     /// 2. Check if the list is empty before and after pushing nodes into the
221     /// list.
222     /// 3. Check if the list is empty before and after clear the list.
223     #[test]
224     #[cfg(feature = "time")]
ut_link_list_is_empty()225     fn ut_link_list_is_empty() {
226         let mut list = LinkedList::<Entry>::new();
227         assert!(list.is_empty());
228         let node1 = Entry::new(1);
229         let node1 = node1.get_ptr();
230         list.push_front(node1);
231         assert!(!list.is_empty());
232     }
233 
234     /// UT test cases for `push_front()` and `pop_back()`.
235     ///
236     /// # Brief
237     /// 1. Create a linked list.
238     /// 2. Push nodes into the list.
239     /// 3. Pop nodes from the list and check the value.
240     #[test]
ut_link_list_push_and_pop()241     fn ut_link_list_push_and_pop() {
242         let mut list = LinkedList::<Entry>::new();
243         let node1 = Entry::new(1);
244         let node1 = node1.get_ptr();
245         let node2 = Entry::new(2);
246         let node2 = node2.get_ptr();
247         let node3 = Entry::new(3);
248         let node3 = node3.get_ptr();
249         list.push_front(node1);
250         list.push_front(node2);
251         list.push_front(node3);
252         assert_eq!(1, get_val(list.pop_back().unwrap()));
253         assert_eq!(2, get_val(list.pop_back().unwrap()));
254         assert_eq!(3, get_val(list.pop_back().unwrap()));
255         assert!(list.pop_back().is_none());
256     }
257 
258     /// UT test cases for `push_front()` and `remove()`.
259     ///
260     /// # Brief
261     /// 1. Create a linked list.
262     /// 2. Push nodes into the list.
263     /// 3. Remove the first node from the list and check the list.
264     /// 4. Remove the second node from the list and check the list.
265     /// 5. Remove the third node from the list and check the list.
266     #[cfg(any(feature = "time", feature = "net"))]
267     #[test]
ut_link_list_remove()268     fn ut_link_list_remove() {
269         let mut list = LinkedList::<Entry>::new();
270         let node1 = Entry::new(1);
271         let node1_ptr = node1.get_ptr();
272         let node2 = Entry::new(2);
273         let node2_ptr = node2.get_ptr();
274         let node3 = Entry::new(3);
275         let node3_ptr = node3.get_ptr();
276         list.push_front(node1_ptr);
277         list.push_front(node2_ptr);
278         list.push_front(node3_ptr);
279         unsafe {
280             assert!(list.remove(node1_ptr).is_some());
281             assert!(list.remove(node1_ptr).is_none());
282             assert_eq!(Some(node2_ptr), node3.node.next);
283             assert_eq!(Some(node3_ptr), node2.node.prev);
284             assert!(list.remove(node2_ptr).is_some());
285             assert!(list.remove(node2_ptr).is_none());
286             assert!(list.remove(node3_ptr).is_some());
287             assert!(list.remove(node3_ptr).is_none());
288         }
289 
290         list.push_front(node1_ptr);
291         list.push_front(node2_ptr);
292         list.push_front(node3_ptr);
293         unsafe {
294             assert!(list.remove(node2_ptr).is_some());
295             assert!(list.remove(node2_ptr).is_none());
296             assert_eq!(Some(node1_ptr), node3.node.next);
297             assert_eq!(Some(node3_ptr), node1.node.prev);
298             assert!(list.remove(node1_ptr).is_some());
299             assert!(list.remove(node1_ptr).is_none());
300             assert!(list.remove(node3_ptr).is_some());
301             assert!(list.remove(node3_ptr).is_none());
302         }
303 
304         list.push_front(node1_ptr);
305         list.push_front(node2_ptr);
306         list.push_front(node3_ptr);
307         unsafe {
308             assert_eq!(get_val(list.remove(node3_ptr).unwrap()), 3);
309             assert!(list.remove(node3_ptr).is_none());
310             assert_eq!(Some(node1_ptr), node2.node.next);
311             assert_eq!(Some(node2_ptr), node1.node.prev);
312             assert_eq!(get_val(list.remove(node1_ptr).unwrap()), 1);
313             assert!(list.remove(node1_ptr).is_none());
314             assert_eq!(get_val(list.remove(node2_ptr).unwrap()), 2);
315             assert!(list.remove(node2_ptr).is_none());
316         }
317     }
318 
319     /// UT test cases for `drain_filtered()`.
320     ///
321     /// # Brief
322     /// 1. Create a linked list.
323     /// 2. Push nodes into the list.
324     /// 3. Drain filtered the list for node that contains a value of 2.
325     #[test]
326     #[cfg(all(feature = "net", feature = "time"))]
ut_link_list_for_each_mut()327     fn ut_link_list_for_each_mut() {
328         let mut list = LinkedList::<Entry>::new();
329         let node1 = Entry::new(1);
330         let node1_ptr = node1.get_ptr();
331         let node2 = Entry::new(2);
332         let node2_ptr = node2.get_ptr();
333         let node3 = Entry::new(3);
334         let node3_ptr = node3.get_ptr();
335         list.push_front(node1_ptr);
336         list.push_front(node2_ptr);
337         list.push_front(node3_ptr);
338 
339         let mut value = 0;
340         list.drain_filtered(|x| {
341             if x.val == 2 {
342                 value = x.val;
343                 return true;
344             }
345             false
346         });
347         assert_eq!(value, 2);
348         unsafe {
349             let node = list.pop_back();
350             assert_eq!(node.unwrap().as_mut().val, 1);
351             let node = list.pop_back();
352             assert_eq!(node.unwrap().as_mut().val, 3);
353             let node = list.pop_back();
354             assert_eq!(node, None);
355         }
356     }
357 }
358