blob: 5a633c34c2366c18abea45a8aed8e5a76258491b (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
|
//! A doubly-linked list of power-of-two-sized subregions.
use core::{marker::PhantomPinned, pin::Pin, ptr};
/// The magic number a non-sentinel node should have.
const FREE_NODE_MAGIC: u64 = u64::from_ne_bytes(*b"FREENODE");
/// The magic number a sentinel node should have.
const SENTINEL_MAGIC: u64 = u64::from_ne_bytes(*b"SENTINEL");
/// A doubly-linked list of power-of-two-sized subregions.
///
/// This type is valid when zero-initialized.
#[derive(Debug)]
pub struct FreeList {
sentinel: FreeListNode,
}
impl FreeList {
/// Performs self-linking. This must be done before the free list is used in any other way.
pub fn self_link(mut self: Pin<&mut FreeList>) {
assert_eq!(self.sentinel.next, ptr::null_mut());
assert_eq!(self.sentinel.prev, ptr::null_mut());
let self_ptr = &self.sentinel as *const FreeListNode as *mut FreeListNode;
let mut sentinel = self.sentinel_unchecked();
*sentinel.as_mut().next_mut() = self_ptr;
*sentinel.as_mut().prev_mut() = self_ptr;
*sentinel.as_mut().magic_mut() = SENTINEL_MAGIC;
}
/// Projects the sentinel node out of the list.
fn sentinel(self: Pin<&mut FreeList>) -> Pin<&mut FreeListNode> {
let mut sentinel = self.sentinel_unchecked();
assert_eq!(*sentinel.as_mut().magic_mut(), SENTINEL_MAGIC);
sentinel
}
/// Projects the sentinel node out of the list, without checking the magic number.
fn sentinel_unchecked(self: Pin<&mut FreeList>) -> Pin<&mut FreeListNode> {
// SAFETY: sentinel is structurally pinned.
unsafe { self.map_unchecked_mut(|list| &mut list.sentinel) }
}
}
#[derive(Debug)]
struct FreeListNode {
next: *mut FreeListNode,
prev: *mut FreeListNode,
magic: u64,
_phantom: PhantomPinned,
}
impl FreeListNode {
/// Projects the `next` pointer out of the node.
fn next_mut(self: Pin<&mut FreeListNode>) -> &mut *mut FreeListNode {
// SAFETY: next is not structurally pinned.
unsafe { &mut self.get_unchecked_mut().next }
}
/// Projects the `prev` pointer out of the node.
fn prev_mut(self: Pin<&mut FreeListNode>) -> &mut *mut FreeListNode {
// SAFETY: prev is structurally pinned.
unsafe { &mut self.get_unchecked_mut().prev }
}
/// Projects the `magic` number out of the node.
fn magic_mut(self: Pin<&mut FreeListNode>) -> &mut u64 {
// SAFETY: magic is structurally pinned.
unsafe { &mut self.get_unchecked_mut().magic }
}
}
|
