sled/
dll.rs

1#![allow(unsafe_code)]
2
3use std::ptr;
4
5use crate::PageId;
6
7/// A simple doubly linked list for use in the `Lru`
8#[derive(Debug)]
9pub(crate) struct Node {
10    inner: PageId,
11    next: *mut Node,
12    prev: *mut Node,
13}
14
15impl Node {
16    fn unwire(&mut self) {
17        unsafe {
18            if !self.prev.is_null() {
19                (*self.prev).next = self.next;
20            }
21
22            if !self.next.is_null() {
23                (*self.next).prev = self.prev;
24            }
25        }
26
27        self.next = ptr::null_mut();
28        self.prev = ptr::null_mut();
29    }
30}
31
32/// A simple non-cyclical doubly linked
33/// list where items can be efficiently
34/// removed from the middle, for the purposes
35/// of backing an LRU cache.
36pub struct DoublyLinkedList {
37    head: *mut Node,
38    tail: *mut Node,
39    len: usize,
40}
41
42impl Drop for DoublyLinkedList {
43    fn drop(&mut self) {
44        let mut cursor = self.head;
45        while !cursor.is_null() {
46            unsafe {
47                let node = Box::from_raw(cursor);
48
49                // don't need to check for cycles
50                // because this Dll is non-cyclical
51                cursor = node.prev;
52
53                // this happens without the manual drop,
54                // but we keep it for explicitness
55                drop(node);
56            }
57        }
58    }
59}
60
61impl Default for DoublyLinkedList {
62    fn default() -> Self {
63        Self { head: ptr::null_mut(), tail: ptr::null_mut(), len: 0 }
64    }
65}
66
67impl DoublyLinkedList {
68    pub(crate) const fn len(&self) -> usize {
69        self.len
70    }
71
72    pub(crate) fn push_head(&mut self, item: PageId) -> *mut Node {
73        self.len += 1;
74
75        let node = Node { inner: item, next: ptr::null_mut(), prev: self.head };
76
77        let ptr = Box::into_raw(Box::new(node));
78
79        self.push_head_ptr(ptr)
80    }
81
82    fn push_head_ptr(&mut self, ptr: *mut Node) -> *mut Node {
83        if !self.head.is_null() {
84            unsafe {
85                (*self.head).next = ptr;
86                (*ptr).prev = self.head;
87            }
88        }
89
90        if self.tail.is_null() {
91            self.tail = ptr;
92        }
93
94        self.head = ptr;
95
96        ptr
97    }
98
99    #[cfg(test)]
100    pub(crate) fn push_tail(&mut self, item: PageId) {
101        self.len += 1;
102
103        let node = Node { inner: item, next: self.tail, prev: ptr::null_mut() };
104
105        let ptr = Box::into_raw(Box::new(node));
106
107        if !self.tail.is_null() {
108            unsafe {
109                (*self.tail).prev = ptr;
110            }
111        }
112
113        if self.head.is_null() {
114            self.head = ptr;
115        }
116
117        self.tail = ptr;
118    }
119
120    pub(crate) fn promote(&mut self, ptr: *mut Node) -> *mut Node {
121        if self.head == ptr {
122            return ptr;
123        }
124
125        unsafe {
126            if self.tail == ptr {
127                self.tail = (*ptr).next;
128            }
129
130            if self.head == ptr {
131                self.head = (*ptr).prev;
132            }
133
134            (*ptr).unwire();
135
136            self.push_head_ptr(ptr)
137        }
138    }
139
140    #[cfg(test)]
141    pub(crate) fn pop_head(&mut self) -> Option<PageId> {
142        if self.head.is_null() {
143            return None;
144        }
145
146        self.len -= 1;
147
148        unsafe {
149            let mut head = Box::from_raw(self.head);
150
151            if self.head == self.tail {
152                self.tail = ptr::null_mut();
153            }
154
155            self.head = head.prev;
156
157            head.unwire();
158
159            Some(head.inner)
160        }
161    }
162
163    pub(crate) fn pop_tail(&mut self) -> Option<PageId> {
164        if self.tail.is_null() {
165            return None;
166        }
167
168        self.len -= 1;
169
170        unsafe {
171            let mut tail = Box::from_raw(self.tail);
172
173            if self.head == self.tail {
174                self.head = ptr::null_mut();
175            }
176
177            self.tail = tail.next;
178
179            tail.unwire();
180
181            Some(tail.inner)
182        }
183    }
184
185    #[cfg(test)]
186    pub(crate) fn into_vec(mut self) -> Vec<PageId> {
187        let mut res = vec![];
188        while let Some(val) = self.pop_head() {
189            res.push(val);
190        }
191        res
192    }
193}
194
195#[allow(unused_results)]
196#[test]
197fn test_dll() {
198    let mut dll = DoublyLinkedList::default();
199    dll.push_head(5);
200    dll.push_tail(6);
201    dll.push_head(4);
202    dll.push_tail(7);
203    dll.push_tail(8);
204    dll.push_head(3);
205    dll.push_tail(9);
206    dll.push_head(2);
207    dll.push_head(1);
208    assert_eq!(dll.len(), 9);
209    assert_eq!(dll.into_vec(), vec![1, 2, 3, 4, 5, 6, 7, 8, 9]);
210}
sled/dll.rs

sled/
dll.rs
