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
use std::collections::HashSet;
/// A table for allocating inode numbers and file handles.
#[derive(Debug, PartialEq, Eq, Clone, Default)]
pub struct IdPool {
/// The highest used ID value (the high water mark).
highest: u64,
/// A set of unused ID values below the high water mark.
unused: HashSet<u64>,
/// The set of ID values which cannot ever be allocated.
reserved: HashSet<u64>,
}
impl IdPool {
/// Return a new empty `IdTable` with the given `reserved` IDs.
pub fn new(reserved: impl IntoIterator<Item = u64>) -> Self {
Self {
highest: 0,
unused: HashSet::new(),
reserved: reserved.into_iter().collect::<HashSet<_>>(),
}
}
/// Return the next unused ID from the table.
pub fn next(&mut self) -> u64 {
match self.unused.iter().next().copied() {
Some(id) => {
self.unused.remove(&id);
id
}
None => {
self.highest += 1;
while self.reserved.contains(&self.highest) {
self.highest += 1;
}
self.highest
}
}
}
/// Return whether the given `id` is in the table.
pub fn contains(&self, id: u64) -> bool {
id <= self.highest && !self.unused.contains(&id)
}
/// Return the given `id` back to the table.
///
/// This returns `true` if the value was returned or `false` if it was unused or reserved.
pub fn recycle(&mut self, id: u64) -> bool {
if !self.contains(id) || self.reserved.contains(&id) {
return false;
}
self.unused.insert(id);
true
}
}