rowan/
sll.rs

1//! Sorted Linked List
2
3use std::{cell::Cell, cmp::Ordering, ptr};
4
5use crate::utility_types::Delta;
6pub(crate) unsafe trait Elem {
7    fn prev(&self) -> &Cell<*const Self>;
8    fn next(&self) -> &Cell<*const Self>;
9    fn key(&self) -> &Cell<u32>;
10}
11
12pub(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
20impl<'a, E: Elem> AddToSllResult<'a, 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]
54pub(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]
66pub(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]
86pub(crate) fn link<'a, E: Elem>(head: &'a Cell<*const E>, elem: &E) -> AddToSllResult<'a, E> {
87    let old_head = head.get();
88    // Case 1: empty head, replace it.
89    if old_head.is_null() {
90        return AddToSllResult::EmptyHead(head);
91    }
92    unsafe {
93        // Case 2: we are smaller than the head, replace it.
94        if elem.key() < (*old_head).key() {
95            return AddToSllResult::SmallerThanHead(head);
96        }
97
98        // Case 3: loop *backward* until we find insertion place. Because of
99        // Case 2, we can't loop beyond the head.
100        let mut curr = (*old_head).prev().get();
101        loop {
102            match (*curr).key().cmp(elem.key()) {
103                Ordering::Less => return AddToSllResult::SmallerThanNotHead(curr),
104                Ordering::Equal => return AddToSllResult::AlreadyInSll(curr),
105                Ordering::Greater => curr = (*curr).prev().get(),
106            }
107        }
108    }
109}
110
111pub(crate) fn adjust<E: Elem>(elem: &E, from: u32, by: Delta<u32>) {
112    let elem_ptr: *const E = elem;
113
114    unsafe {
115        let mut curr = elem_ptr;
116        loop {
117            let mut key = (*curr).key().get();
118            if key >= from {
119                key += by;
120                (*curr).key().set(key);
121            }
122            curr = (*curr).next().get();
123            if curr == elem_ptr {
124                break;
125            }
126        }
127    }
128}
rowan/sll.rs

rowan/
sll.rs
