lock_free_buddy_allocator 0.2.1

Scalable lock-free buddy system allocator
Documentation 
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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125

use core::ops::Deref;

const COALESCE_LEFT: usize = 0x8;
const COALESCE_RIGHT: usize = 0x4;

const LEFT_OCCUPIED: usize = 0x2;
const RIGHT_OCCUPIED: usize = 0x1;

#[derive(Copy, Clone, Debug, PartialEq)]
#[repr(transparent)]
pub struct NodeState(usize);

impl NodeState {
    fn is_leaf(pos: u8) -> bool {
        pos >= 8
    }

    fn leaf_offset(pos: u8) -> usize {
        debug_assert!(pos >= 8);
        // 7 bits for FREE / OCCUPIED state in non-leaf nodes and 5 bits per-leaf node
        7 + (5 * (pos as usize - 8))
    }

    pub fn is_allocable(&self, pos: u8) -> bool {
        if pos < 8 {
            (self.0 & (0x1 << (pos - 1))) == 0
        } else {
            self.0 & ((0x1F << 7) << (5 * (pos - 8))) == 0
        }
    }

    pub fn lock_not_leaf(&self, pos: u8) -> Self {
        (self.0 | (0x1 << (pos as usize - 1))).into()
    }

    pub fn lock_leaf(&self, pos: u8) -> Self {
        (self.0 | (0x13 << Self::leaf_offset(pos))).into()
    }

    pub fn unlock(&self, pos: u8) -> Self {
        if Self::is_leaf(pos) {
            self.unlock_leaf(pos)
        } else {
            self.unlock_not_leaf(pos)
        }
    }

    pub fn unlock_not_leaf(&self, pos: u8) -> Self {
        (self.0 & !(0x1 << (pos as usize - 1))).into()
    }

    fn unlock_leaf(&self, pos: u8) -> Self {
        (self.0 & !(0x13 << Self::leaf_offset(pos))).into()
    }

    pub fn is_occupied(&self, pos: u8) -> bool {
        if pos < 8 {
            (self.0 & (0x1 << (pos - 1))) != 0
        } else {
            self.0 & ((0x1 << 6) << (5 * (pos - 7))) != 0
        }
    }

    pub fn clean_left_coalesce(&self, pos: u8) -> Self {
        (self.0 & !(COALESCE_LEFT << Self::leaf_offset(pos))).into()
    }

    pub fn clean_rigth_coalesce(&self, pos: u8) -> Self {
        (self.0 & !(COALESCE_RIGHT << Self::leaf_offset(pos))).into()
    }

    pub fn left_coalesce(&self, pos: u8) -> Self {
        (self.0 | (COALESCE_LEFT << Self::leaf_offset(pos))).into()
    }

    pub fn rigth_coalesce(&self, pos: u8) -> Self {
        (self.0 | (COALESCE_RIGHT << Self::leaf_offset(pos))).into()
    }

    pub fn occupy_left(&self, pos: u8) -> Self {
        (self.0 | (LEFT_OCCUPIED << Self::leaf_offset(pos))).into()
    }

    pub fn occupy_rigth(&self, pos: u8) -> Self {
        (self.0 | (RIGHT_OCCUPIED << Self::leaf_offset(pos))).into()
    }

    pub fn is_left_coalescing(&self, pos: u8) -> bool {
        *self == self.left_coalesce(pos)
    }

    pub fn is_right_coalescing(&self, pos: u8) -> bool {
        *self == self.rigth_coalesce(pos)
    }

    pub fn clean_left_occupy(&self, pos: u8) -> Self {
        (self.0 & !(LEFT_OCCUPIED << Self::leaf_offset(pos))).into()
    }

    pub fn clean_rigth_occupy(&self, pos: u8) -> Self {
        (self.0 & !(RIGHT_OCCUPIED << Self::leaf_offset(pos))).into()
    }

    pub fn is_occupied_rigth(&self, pos: u8) -> bool {
        *self == self.occupy_rigth(pos)
    }

    pub fn is_occupied_left(&self, pos: u8) -> bool {
        *self == self.occupy_left(pos)
    }
}

impl From<usize> for NodeState {
    fn from(value: usize) -> Self {
        Self(value)
    }
}

impl Deref for NodeState {
    type Target = usize;

    fn deref(&self) -> &Self::Target {
        &self.0
    }
}