libblobd_direct/object/
tail.rs

1use off64::u8;
2
3// Two benefits of this over Vec<u8>:
4// - Length type is u8, which is the type for `tail_page_count`.
5// - No heap allocations; small enough to copy.
6// How it works:
7// - Page sizes can only be from `2^8` to `2^32` (see `{MIN,MAX}_PAGE_SIZE_POW2`).
8// - There are only `32 - 8 = 24` page sizes.
9// - It takes 5 bits to represent 24 distinct values.
10// - There can be up to 24 entries, each taking 5 bits. It will take 5 bits to represent the length.
11// - We can't fit 125 bits neatly, so we split up into two shards (64-bit ints), and use 4 bits in each int to represent the length of up to 12 entries covered by its int, using exactly `4 + 12 * 5 = 64` bits.
12#[derive(Clone, Copy)]
13pub struct TailPageSizes(u64, u64);
14
15impl TailPageSizes {
16  pub fn new() -> Self {
17    Self(0, 0)
18  }
19
20  fn shard_get_len(shard: u64) -> u8 {
21    u8!((shard & (0b1111 << 60)) >> 60)
22  }
23
24  fn shard_set_len(shard: &mut u64, len: u8) {
25    assert!(len <= 12);
26    *shard &= !(0b1111 << 60);
27    *shard |= u64::from(len) << 60;
28  }
29
30  fn shard_get(shard: u64, idx: u8) -> u8 {
31    assert!(idx < 12);
32    let shift = idx * 5;
33    u8!((shard & (0b11111 << shift)) >> shift)
34  }
35
36  fn shard_set(shard: &mut u64, idx: u8, val: u8) {
37    assert!(val < (1 << 5));
38    let shift = idx * 5;
39    *shard &= !(0b11111 << shift);
40    *shard |= u64::from(val) << shift;
41  }
42
43  pub fn len(&self) -> u8 {
44    Self::shard_get_len(self.0) + Self::shard_get_len(self.1)
45  }
46
47  pub fn get(&self, idx: u8) -> Option<u8> {
48    if idx >= self.len() {
49      return None;
50    };
51    Some(if idx < 12 {
52      Self::shard_get(self.0, idx)
53    } else {
54      Self::shard_get(self.1, idx - 12)
55    })
56  }
57
58  pub fn push(&mut self, pow2: u8) {
59    let idx = self.len();
60    if idx < 12 {
61      Self::shard_set(&mut self.0, idx, pow2);
62      Self::shard_set_len(&mut self.0, idx + 1);
63    } else {
64      Self::shard_set(&mut self.1, idx - 12, pow2);
65      Self::shard_set_len(&mut self.1, idx - 12 + 1);
66    };
67  }
68}
69
70impl IntoIterator for TailPageSizes {
71  type IntoIter = TailPageSizesIter;
72  type Item = (u8, u8);
73
74  fn into_iter(self) -> Self::IntoIter {
75    TailPageSizesIter(self, 0)
76  }
77}
78
79// Convenient iterator that provides `u8` indices instead of `.enumerate()` and `u8!(idx)`.
80pub struct TailPageSizesIter(TailPageSizes, u8);
81
82impl Iterator for TailPageSizesIter {
83  type Item = (u8, u8);
84
85  fn next(&mut self) -> Option<Self::Item> {
86    let idx = self.1;
87    let entry = self.0.get(idx)?;
88    self.1 += 1;
89    Some((idx, entry))
90  }
91}
92
93#[cfg(test)]
94mod tests {
95  use super::TailPageSizes;
96  use itertools::Itertools;
97
98  #[test]
99  fn test_tail_page_sizes() {
100    let mut tail = TailPageSizes::new();
101    // Check iterator/state is correct when empty.
102    assert_eq!(tail.into_iter().collect_vec(), vec![]);
103
104    tail.push(5);
105    assert_eq!(tail.into_iter().collect_vec(), vec![(0, 5)]);
106
107    tail.push(3);
108    assert_eq!(tail.into_iter().collect_vec(), vec![(0, 5), (1, 3)]);
109
110    tail.push(8);
111    assert_eq!(tail.into_iter().collect_vec(), vec![(0, 5), (1, 3), (2, 8)]);
112    assert_eq!(tail.get(1), Some(3));
113    assert_eq!(tail.get(3), None);
114
115    tail.push(9);
116    assert_eq!(tail.into_iter().collect_vec(), vec![
117      (0, 5),
118      (1, 3),
119      (2, 8),
120      (3, 9),
121    ]);
122    assert_eq!(tail.len(), 4);
123    assert_eq!(tail.get(0), Some(5));
124    assert_eq!(tail.get(4), None);
125
126    tail.push(4);
127    assert_eq!(tail.into_iter().collect_vec(), vec![
128      (0, 5),
129      (1, 3),
130      (2, 8),
131      (3, 9),
132      (4, 4)
133    ]);
134    assert_eq!(tail.len(), 5);
135    assert_eq!(tail.get(3), Some(9));
136    assert_eq!(tail.get(5), None);
137
138    tail.push(11);
139    assert_eq!(tail.into_iter().collect_vec(), vec![
140      (0, 5),
141      (1, 3),
142      (2, 8),
143      (3, 9),
144      (4, 4),
145      (5, 11),
146    ]);
147    assert_eq!(tail.len(), 6);
148    assert_eq!(tail.get(0), Some(5));
149    assert_eq!(tail.get(4), Some(4));
150    assert_eq!(tail.get(5), Some(11));
151    assert_eq!(tail.get(6), None);
152
153    tail.push(14);
154    assert_eq!(tail.into_iter().collect_vec(), vec![
155      (0, 5),
156      (1, 3),
157      (2, 8),
158      (3, 9),
159      (4, 4),
160      (5, 11),
161      (6, 14),
162    ]);
163    assert_eq!(tail.len(), 7);
164    assert_eq!(tail.get(0), Some(5));
165    assert_eq!(tail.get(4), Some(4));
166    assert_eq!(tail.get(5), Some(11));
167    assert_eq!(tail.get(6), Some(14));
168
169    tail.push(2);
170    assert_eq!(tail.into_iter().collect_vec(), vec![
171      (0, 5),
172      (1, 3),
173      (2, 8),
174      (3, 9),
175      (4, 4),
176      (5, 11),
177      (6, 14),
178      (7, 2),
179    ]);
180    assert_eq!(tail.len(), 8);
181    assert_eq!(tail.get(0), Some(5));
182    assert_eq!(tail.get(4), Some(4));
183    assert_eq!(tail.get(5), Some(11));
184    assert_eq!(tail.get(6), Some(14));
185    assert_eq!(tail.get(7), Some(2));
186    assert_eq!(tail.get(8), None);
187  }
188}
libblobd_direct/object/tail.rs

libblobd_direct/object/
tail.rs
