Nothing to see here, move along meow
1use crate::header::NONE_SENTINEL;
2
3pub trait ListLinks<Tag> {
4 fn link_next(&self, id: u32) -> u32;
5 fn link_prev(&self, id: u32) -> u32;
6 fn set_link_next(&mut self, id: u32, next: u32);
7 fn set_link_prev(&mut self, id: u32, prev: u32);
8}
9
10#[derive(Clone, Copy)]
11pub struct IntrusiveList {
12 head: u32,
13 tail: u32,
14}
15
16impl IntrusiveList {
17 pub const fn empty() -> Self {
18 Self {
19 head: NONE_SENTINEL,
20 tail: NONE_SENTINEL,
21 }
22 }
23
24 pub fn is_empty(&self) -> bool {
25 self.head == NONE_SENTINEL
26 }
27
28 pub fn head(&self) -> u32 {
29 self.head
30 }
31
32 pub fn append<Tag>(&mut self, id: u32, store: &mut impl ListLinks<Tag>) {
33 store.set_link_next(id, NONE_SENTINEL);
34 store.set_link_prev(id, self.tail);
35
36 match self.tail {
37 NONE_SENTINEL => {
38 self.head = id;
39 }
40 tail => {
41 store.set_link_next(tail, id);
42 }
43 }
44
45 self.tail = id;
46 }
47
48 pub fn pop_head<Tag>(&mut self, store: &mut impl ListLinks<Tag>) -> Option<u32> {
49 match self.head {
50 NONE_SENTINEL => None,
51 head => {
52 let next = store.link_next(head);
53 self.head = next;
54
55 match next {
56 NONE_SENTINEL => {
57 self.tail = NONE_SENTINEL;
58 }
59 n => {
60 store.set_link_prev(n, NONE_SENTINEL);
61 }
62 }
63
64 store.set_link_next(head, NONE_SENTINEL);
65 store.set_link_prev(head, NONE_SENTINEL);
66
67 Some(head)
68 }
69 }
70 }
71
72 pub fn unlink<Tag>(&mut self, id: u32, store: &mut impl ListLinks<Tag>) -> bool {
73 let prev = store.link_prev(id);
74 let next = store.link_next(id);
75
76 let is_linked = prev != NONE_SENTINEL || next != NONE_SENTINEL || self.head == id;
77 if !is_linked {
78 return false;
79 }
80
81 match prev {
82 NONE_SENTINEL => {
83 self.head = next;
84 }
85 prev_id => {
86 store.set_link_next(prev_id, next);
87 }
88 }
89
90 match next {
91 NONE_SENTINEL => {
92 self.tail = prev;
93 }
94 next_id => {
95 store.set_link_prev(next_id, prev);
96 }
97 }
98
99 store.set_link_next(id, NONE_SENTINEL);
100 store.set_link_prev(id, NONE_SENTINEL);
101
102 true
103 }
104
105 pub fn take_all(&mut self) -> u32 {
106 let head = self.head;
107 self.head = NONE_SENTINEL;
108 self.tail = NONE_SENTINEL;
109 head
110 }
111}