slabbable_hash/
lib.rs

1#![warn(
2    clippy::unwrap_used,
3    missing_docs,
4    rust_2018_idioms,
5    unused_lifetimes,
6    unused_qualifications
7)]
8#![allow(clippy::single_match, rustdoc::bare_urls)]
9#![cfg_attr(all(not(feature = "std"), not(test)), no_std)]
10#![doc = include_str!("../README.md")]
11
12#[cfg(not(slabbable_hasmap = "_somethingelse"))]
13use hashbrown::HashMap as SelectedHashMap;
14
15#[cfg(not(slabbable_hasher = "_somethingelse"))]
16use nohash_hasher::BuildNoHashHasher as SelectedHasher;
17
18use slabbable::{ReservedSlot, Slabbable, SlabbableError};
19
20#[derive(Debug)]
21enum ReserveStatus<Item> {
22    Reserved,
23    Taken(Item),
24}
25
26/// Holder
27#[derive(Debug)]
28pub struct HashSlab<Item> {
29    inner: SelectedHashMap<usize, ReserveStatus<Item>, SelectedHasher<usize>>,
30    // HashBrown seems to report wrong capacity() for guaranteed no-realloc
31    // so we have to track our own to ensure it doesn't move things around.
32    max_capacity: usize,
33    // wraps
34    cur: usize,
35    // wraps
36    rev: usize,
37}
38
39impl<Item> HashSlab<Item> {
40    fn _take_next_cur(&mut self) -> usize {
41        let spot = self.cur;
42        if self.cur == usize::MAX {
43            self.cur = 0;
44            self.rev = match self.rev {
45                usize::MAX => 0,
46                _ => self.rev + 1,
47            };
48        } else {
49            self.cur += 1;
50        }
51        spot
52    }
53}
54
55impl<Item> Slabbable<HashSlab<Item>, Item> for HashSlab<Item>
56where
57    Item: core::fmt::Debug + Clone,
58{
59    type Error = SlabbableError;
60    /// See trait
61    fn with_fixed_capacity(cap: usize) -> Result<Self, Self::Error> {
62        let inner: SelectedHashMap<usize, ReserveStatus<Item>, SelectedHasher<usize>> =
63            SelectedHashMap::<usize, ReserveStatus<Item>, SelectedHasher<usize>>::with_capacity_and_hasher(
64                cap,
65                SelectedHasher::default(),
66            );
67        Ok(Self {
68            inner,
69            max_capacity: cap,
70            cur: 0,
71            rev: 0,
72        })
73    }
74    #[inline]
75    fn reserve_next(&mut self) -> Result<ReservedSlot, Self::Error> {
76        // Slab re-allocators upon grow - we want stable addresses
77        if self.max_capacity < self.inner.len() + 1 {
78            return Err(SlabbableError::AtCapacity(self.max_capacity));
79        }
80        let slot = self._take_next_cur();
81        // TOOD: std hashmap try_insert is experimental
82        match self.inner.try_insert(slot, ReserveStatus::Reserved) {
83            Ok(_) => Ok(ReservedSlot::issue(slot)),
84            _ => Err(SlabbableError::Bug(
85                "Next entry by _take_next_cur() already occupied.",
86            )),
87        }
88    }
89    #[inline]
90    fn take_reserved_with(&mut self, slot: ReservedSlot, with: Item) -> Result<usize, Self::Error> {
91        let id = slot.id();
92
93        match self.inner.insert(id, ReserveStatus::Taken(with)) {
94            Some(v) => match v {
95                ReserveStatus::Reserved => Ok(id),
96                _ => Err(SlabbableError::Bug("Key was already occupied.")),
97            },
98            None => Err(SlabbableError::Bug("Key was not reserved correctly.")),
99        }
100    }
101    /// See trait
102    #[inline]
103    fn take_next_with(&mut self, with: Item) -> Result<usize, Self::Error> {
104        let reserved_slot = self.reserve_next()?;
105        self.take_reserved_with(reserved_slot, with)
106    }
107    /// See trait
108    #[inline]
109    fn mark_for_reuse(&mut self, slot: usize) -> Result<Item, Self::Error> {
110        match self.inner.remove(&slot) {
111            Some(ReserveStatus::Taken(i)) => Ok(i),
112            _ => Err(SlabbableError::InvalidIndex(slot)),
113        }
114    }
115    /// See trait
116    #[inline]
117    fn slot_get_mut(&mut self, slot: usize) -> Result<Option<&mut Item>, Self::Error> {
118        match self.inner.get_mut(&slot) {
119            Some(ReserveStatus::Taken(itm_ref)) => Ok(Some(itm_ref)),
120            _ => Err(SlabbableError::InvalidIndex(slot)),
121        }
122    }
123    /// See trait
124    #[inline]
125    fn slot_get_ref(&self, slot: usize) -> Result<Option<&Item>, Self::Error> {
126        match self.inner.get(&slot) {
127            Some(ReserveStatus::Taken(itm_ref)) => Ok(Some(itm_ref)),
128            _ => Err(SlabbableError::InvalidIndex(slot)),
129        }
130    }
131    /// See trait
132    #[inline]
133    fn capacity(&self) -> usize {
134        self.max_capacity
135    }
136    /// See trait
137    #[inline]
138    fn remaining(&self) -> Option<usize> {
139        let rem = self.max_capacity - self.inner.len();
140        match rem {
141            0 => None,
142            1_usize.. => Some(rem),
143        }
144    }
145    /// See trait
146    fn reap(&mut self) -> Option<usize> {
147        // We don't support it
148        None
149    }
150}
slabbable_hash/lib.rs

slabbable_hash/
lib.rs
