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
|
use contracts::requires;
use core::{fmt, mem::transmute};
/// A fixed-length vector of bits used for determining whether a subregion is in the free lists or
/// not.
pub struct Bitset([usize]);
impl Bitset {
fn from_mut(words: &mut [usize]) -> &mut Bitset {
// SAFETY: The types have a newtype relationship.
unsafe { transmute(words) }
}
fn from_ref(words: &[usize]) -> &Bitset {
// SAFETY: The types have a newtype relationship.
unsafe { transmute(words) }
}
/// Retrieves the value of a bit from the Bitset.
#[requires(i < self.len())]
pub fn get(&self, i: usize) -> SubregionStatus {
let word_index = i / usize::BITS as usize;
let subword_index = i % usize::BITS as usize;
let one_hot = 1 << subword_index;
if (self.0[word_index] & one_hot) == 0 {
SubregionStatus::NotInFreeList
} else {
SubregionStatus::InFreeList
}
}
/// Returns whether the Bitset is empty.
pub fn is_empty(&self) -> bool {
self.0.is_empty()
}
/// Returns the number of bits in the Bitset.
pub fn len(&self) -> usize {
self.0.len() * usize::BITS as usize
}
/// Sets the value of a bit in the Bitset.
#[requires(i < self.len())]
pub fn set(&mut self, i: usize, status: SubregionStatus) {
let word_index = i / usize::BITS as usize;
let subword_index = i % usize::BITS as usize;
let one_hot = 1 << subword_index;
match status {
SubregionStatus::NotInFreeList => {
self.0[word_index] &= !one_hot;
}
SubregionStatus::InFreeList => {
self.0[word_index] |= one_hot;
}
}
}
}
impl fmt::Debug for Bitset {
fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
write!(fmt, "Bitset(")?;
for word in &self.0 {
write!(fmt, "{word:064b}")?;
}
write!(fmt, ")")
}
}
/// The status of a subregion, as tracked by `Bitset`.
#[derive(Clone, Copy, Debug, Eq, Ord, PartialEq, PartialOrd)]
pub enum SubregionStatus {
/// The region is not in the free list.
NotInFreeList = 0,
/// The region is in the free list.
InFreeList = 1,
}
|
