1 //! Sorted Linked List
2
3 use std::{cell::Cell, cmp::Ordering, ptr};
4
5 use crate::utility_types::Delta;
6 pub(crate) unsafe trait Elem {
prev(&self) -> &Cell<*const Self>7 fn prev(&self) -> &Cell<*const Self>;
next(&self) -> &Cell<*const Self>8 fn next(&self) -> &Cell<*const Self>;
key(&self) -> &Cell<u32>9 fn key(&self) -> &Cell<u32>;
10 }
11
12 pub(crate) enum AddToSllResult<'a, E: Elem> {
13 NoHead,
14 EmptyHead(&'a Cell<*const E>),
15 SmallerThanHead(&'a Cell<*const E>),
16 SmallerThanNotHead(*const E),
17 AlreadyInSll(*const E),
18 }
19
20 impl<'a, E: Elem> AddToSllResult<'a, E> {
add_to_sll(&self, elem_ptr: *const E)21 pub(crate) fn add_to_sll(&self, elem_ptr: *const E) {
22 unsafe {
23 (*elem_ptr).prev().set(elem_ptr);
24 (*elem_ptr).next().set(elem_ptr);
25
26 match self {
27 // Case 1: empty head, replace it.
28 AddToSllResult::EmptyHead(head) => head.set(elem_ptr),
29
30 // Case 2: we are smaller than the head, replace it.
31 AddToSllResult::SmallerThanHead(head) => {
32 let old_head = head.get();
33 let prev = (*old_head).prev().replace(elem_ptr);
34 (*prev).next().set(elem_ptr);
35 (*elem_ptr).next().set(old_head);
36 (*elem_ptr).prev().set(prev);
37 head.set(elem_ptr);
38 }
39
40 // Case 3: insert in place found by looping
41 AddToSllResult::SmallerThanNotHead(curr) => {
42 let next = (**curr).next().replace(elem_ptr);
43 (*next).prev().set(elem_ptr);
44 (*elem_ptr).prev().set(*curr);
45 (*elem_ptr).next().set(next);
46 }
47 AddToSllResult::NoHead | AddToSllResult::AlreadyInSll(_) => (),
48 }
49 }
50 }
51 }
52
53 #[cold]
init<'a, E: Elem>( head: Option<&'a Cell<*const E>>, elem: &E, ) -> AddToSllResult<'a, E>54 pub(crate) fn init<'a, E: Elem>(
55 head: Option<&'a Cell<*const E>>,
56 elem: &E,
57 ) -> AddToSllResult<'a, E> {
58 if let Some(head) = head {
59 link(head, elem)
60 } else {
61 AddToSllResult::NoHead
62 }
63 }
64
65 #[cold]
unlink<E: Elem>(head: &Cell<*const E>, elem: &E)66 pub(crate) fn unlink<E: Elem>(head: &Cell<*const E>, elem: &E) {
67 debug_assert!(!head.get().is_null(), "invalid linked list head");
68
69 let elem_ptr: *const E = elem;
70
71 let prev = elem.prev().replace(elem_ptr);
72 let next = elem.next().replace(elem_ptr);
73 unsafe {
74 debug_assert_eq!((*prev).next().get(), elem_ptr, "invalid linked list links");
75 debug_assert_eq!((*next).prev().get(), elem_ptr, "invalid linked list links");
76 (*prev).next().set(next);
77 (*next).prev().set(prev);
78 }
79
80 if head.get() == elem_ptr {
81 head.set(if next == elem_ptr { ptr::null() } else { next })
82 }
83 }
84
85 #[cold]
link<'a, E: Elem>(head: &'a Cell<*const E>, elem: &E) -> AddToSllResult<'a, E>86 pub(crate) fn link<'a, E: Elem>(head: &'a Cell<*const E>, elem: &E) -> AddToSllResult<'a, E> {
87 unsafe {
88 let old_head = head.get();
89 // Case 1: empty head, replace it.
90 if old_head.is_null() {
91 return AddToSllResult::EmptyHead(head);
92 }
93
94 // Case 2: we are smaller than the head, replace it.
95 if elem.key() < (*old_head).key() {
96 return AddToSllResult::SmallerThanHead(head);
97 }
98
99 // Case 3: loop *backward* until we find insertion place. Because of
100 // Case 2, we can't loop beyond the head.
101 let mut curr = (*old_head).prev().get();
102 loop {
103 match (*curr).key().cmp(elem.key()) {
104 Ordering::Less => return AddToSllResult::SmallerThanNotHead(curr),
105 Ordering::Equal => return AddToSllResult::AlreadyInSll(curr),
106 Ordering::Greater => curr = (*curr).prev().get(),
107 }
108 }
109 }
110 }
111
adjust<E: Elem>(elem: &E, from: u32, by: Delta<u32>)112 pub(crate) fn adjust<E: Elem>(elem: &E, from: u32, by: Delta<u32>) {
113 let elem_ptr: *const E = elem;
114
115 unsafe {
116 let mut curr = elem_ptr;
117 loop {
118 let mut key = (*curr).key().get();
119 if key >= from {
120 key += by;
121 (*curr).key().set(key);
122 }
123 curr = (*curr).next().get();
124 if curr == elem_ptr {
125 break;
126 }
127 }
128 }
129 }
130