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
|
use contracts::requires;
use core::fmt;
/// 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 {
/// 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 the number of bits in the bitset.
pub fn len(&self) -> usize {
self.0.len() * usize::BITS as usize
}
/// Replaces a bit in the bitset.
#[requires(i < self.len())]
pub fn replace(
&mut self,
i: usize,
status_before: SubregionStatus,
status_after: SubregionStatus,
) -> Result<(), UnexpectedBitsetState> {
if self.get(i) == status_before {
self.set(i, status_after);
Ok(())
} else {
Err(UnexpectedBitsetState)
}
}
/// 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 i in 0..self.len() {
write!(
fmt,
"{}",
match self.get(i) {
SubregionStatus::NotInFreeList => '0',
SubregionStatus::InFreeList => '1',
}
)?;
}
write!(fmt, ")")
}
}
/// An error returned when the `replace` method does not find the expected bit.
pub struct UnexpectedBitsetState;
/// 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,
}
|
