halfbrown/
vecmap.rs

1//! A vector based map data structure, mostly for internal use
2mod entry;
3mod iter;
4mod raw_entry;
5
6pub(crate) use self::entry::*;
7pub(crate) use self::raw_entry::*;
8use crate::DefaultHashBuilder;
9use crate::vectypes::VecDrain;
10use std::borrow::Borrow;
11
12#[derive(Debug, Clone)]
13pub(crate) struct VecMap<K, V, const N: usize, S = DefaultHashBuilder> {
14    #[cfg(feature = "arraybackend")]
15    v: arrayvec::ArrayVec<(K, V), N>,
16    #[cfg(not(feature = "arraybackend"))]
17    v: Vec<(K, V)>,
18    hash_builder: S,
19}
20
21impl<K, V, const N: usize, S: Default> Default for VecMap<K, V, N, S> {
22    #[inline]
23    #[allow(clippy::default_trait_access)]
24    fn default() -> Self {
25        Self {
26            v: Default::default(),
27            hash_builder: S::default(),
28        }
29    }
30}
31
32impl<K1, V1, K2, V2, const N: usize, S1, S2> PartialEq<VecMap<K2, V2, N, S2>>
33    for VecMap<K1, V1, N, S1>
34where
35    K1: Eq,
36    K2: Eq + Borrow<K1>,
37    V1: PartialEq,
38    V2: Borrow<V1>,
39{
40    fn eq(&self, other: &VecMap<K2, V2, N, S2>) -> bool {
41        if self.len() != other.len() {
42            return false;
43        }
44
45        self.iter()
46            .all(|(key, value)| other.get(key).is_some_and(|v| value == v.borrow()))
47    }
48}
49
50impl<K, V, const N: usize, S> Eq for VecMap<K, V, N, S>
51where
52    K: Eq,
53    V: Eq,
54{
55}
56
57impl<K, V, const N: usize> VecMap<K, V, N, DefaultHashBuilder> {
58    #[cfg(feature = "arraybackend")]
59    #[inline]
60    pub(crate) fn with_capacity(_capacity: usize) -> Self {
61        let v = arrayvec::ArrayVec::new();
62        Self {
63            v,
64            hash_builder: DefaultHashBuilder::default(),
65        }
66    }
67    #[cfg(not(feature = "arraybackend"))]
68    #[inline]
69    pub(crate) fn with_capacity(capacity: usize) -> Self {
70        let v = Vec::with_capacity(capacity);
71        Self {
72            v,
73            hash_builder: DefaultHashBuilder::default(),
74        }
75    }
76}
77
78impl<K, V, const N: usize, S> VecMap<K, V, N, S> {
79    #[inline]
80    pub fn with_hasher(hash_builder: S) -> Self {
81        Self::with_capacity_and_hasher(0, hash_builder)
82    }
83
84    #[cfg(feature = "arraybackend")]
85    #[inline]
86    pub fn with_capacity_and_hasher(_capacity: usize, hash_builder: S) -> Self {
87        let v = arrayvec::ArrayVec::new();
88        Self { v, hash_builder }
89    }
90    #[cfg(not(feature = "arraybackend"))]
91    pub fn with_capacity_and_hasher(capacity: usize, hash_builder: S) -> Self {
92        let v = Vec::with_capacity(capacity);
93        Self { v, hash_builder }
94    }
95
96    #[inline]
97    pub fn retain<F>(&mut self, mut f: F)
98    where
99        F: FnMut(&K, &mut V) -> bool,
100    {
101        let mut new = Self::make_empty_vec_backend();
102        std::mem::swap(&mut new, &mut self.v);
103        self.v = new
104            .into_iter()
105            .filter_map(|(k, mut v)| if f(&k, &mut v) { Some((k, v)) } else { None })
106            .collect();
107    }
108
109    #[inline]
110    pub(crate) fn capacity(&self) -> usize {
111        self.v.capacity()
112    }
113
114    #[inline]
115    pub(crate) fn iter(&self) -> std::slice::Iter<'_, (K, V)> {
116        self.v.iter()
117    }
118
119    #[inline]
120    pub(crate) fn iter_mut(&mut self) -> std::slice::IterMut<'_, (K, V)> {
121        self.v.iter_mut()
122    }
123
124    #[inline]
125    pub(crate) fn len(&self) -> usize {
126        self.v.len()
127    }
128
129    #[inline]
130    pub(crate) fn is_empty(&self) -> bool {
131        self.v.is_empty()
132    }
133
134    #[inline]
135    pub(crate) fn drain(&'_ mut self) -> VecDrain<'_, (K, V), N> {
136        self.v.drain(..)
137    }
138
139    #[inline]
140    #[cfg(not(feature = "arraybackend"))]
141    pub(crate) fn reserve(&mut self, additional: usize) {
142        self.v.reserve(additional);
143    }
144    #[cfg(feature = "arraybackend")]
145    #[allow(clippy::unused_self)]
146    #[inline]
147    pub(crate) fn reserve(&mut self, _additional: usize) {}
148
149    #[cfg(not(feature = "arraybackend"))]
150    #[inline]
151    pub(crate) fn shrink_to_fit(&mut self) {
152        self.v.shrink_to_fit();
153    }
154    #[cfg(feature = "arraybackend")]
155    #[allow(clippy::unused_self)]
156    #[inline]
157    pub(crate) fn shrink_to_fit(&mut self) {}
158    #[inline]
159    pub(crate) fn clear(&mut self) {
160        self.v.clear();
161    }
162}
163
164impl<K, V, const N: usize, S> VecMap<K, V, N, S> {
165    #[inline]
166    pub(crate) fn hasher(&self) -> &S {
167        &self.hash_builder
168    }
169    #[inline]
170    pub(crate) fn insert(&mut self, k: K, mut v: V) -> Option<V>
171    where
172        K: Eq,
173    {
174        for (ak, av) in &mut self.v {
175            if &k == ak {
176                std::mem::swap(av, &mut v);
177                return Some(v);
178            }
179        }
180        self.insert_idx(k, v);
181        None
182    }
183
184    #[inline]
185    pub(crate) fn remove<Q>(&mut self, k: &Q) -> Option<V>
186    where
187        K: Borrow<Q>,
188        Q: Eq + ?Sized,
189    {
190        self.remove_entry(k).map(|e| e.1)
191    }
192
193    #[inline]
194    pub(crate) fn remove_entry<Q>(&mut self, k: &Q) -> Option<(K, V)>
195    where
196        K: Borrow<Q>,
197        Q: Eq + ?Sized,
198    {
199        let mut i = 0;
200        while i != self.v.len() {
201            let (ak, _) = unsafe { self.v.get_unchecked(i) };
202            if k == ak.borrow() {
203                unsafe {
204                    return Some(self.remove_idx(i));
205                }
206            }
207            i += 1;
208        }
209        None
210    }
211
212    #[inline]
213    pub(crate) fn insert_nocheck(&mut self, k: K, v: V) {
214        self.v.push((k, v));
215    }
216
217    pub(crate) fn entry(&'_ mut self, key: K) -> Entry<'_, K, V, N, S>
218    where
219        K: Eq,
220    {
221        for (idx, (ak, _v)) in self.v.iter().enumerate() {
222            if &key == ak {
223                return Entry::Occupied(OccupiedEntry::new(idx, key, self));
224            }
225        }
226        Entry::Vacant(VacantEntry::new(key, self))
227    }
228    #[inline]
229    pub(crate) fn get<Q>(&self, k: &Q) -> Option<&V>
230    where
231        K: Borrow<Q>,
232        Q: Eq + ?Sized,
233    {
234        for (ak, v) in &self.v {
235            if k == ak.borrow() {
236                return Some(v);
237            }
238        }
239        None
240    }
241
242    #[inline]
243    pub(crate) fn contains_key<Q>(&self, k: &Q) -> bool
244    where
245        K: Borrow<Q>,
246        Q: Eq + ?Sized,
247    {
248        for (ak, _v) in &self.v {
249            if k == ak.borrow() {
250                return true;
251            }
252        }
253        false
254    }
255
256    #[inline]
257    pub(crate) fn get_mut<Q>(&mut self, k: &Q) -> Option<&mut V>
258    where
259        K: Borrow<Q>,
260        Q: Eq + ?Sized,
261    {
262        for (ak, v) in &mut self.v {
263            if k.eq((*ak).borrow()) {
264                return Some(v);
265            }
266        }
267        None
268    }
269
270    /// Creates a raw entry builder for the `HashMap`.
271    ///
272    /// Raw entries provide the lowest level of control for searching and
273    /// manipulating a map. They must be manually initialized with a hash and
274    /// then manually searched. After this, insertions into a vacant entry
275    /// still require an owned key to be provided.
276    ///
277    /// Raw entries are useful for such exotic situations as:
278    ///
279    /// * Hash memoization
280    /// * Deferring the creation of an owned key until it is known to be required
281    /// * Using a search key that doesn't work with the Borrow trait
282    /// * Using custom comparison logic without newtype wrappers
283    ///
284    /// Because raw entries provide much more low-level control, it's much easier
285    /// to put the `HashMap` into an inconsistent state which, while memory-safe,
286    /// will cause the map to produce seemingly random results. Higher-level and
287    /// more foolproof APIs like `entry` should be preferred when possible.
288    ///
289    /// In particular, the hash used to initialized the raw entry must still be
290    /// consistent with the hash of the key that is ultimately stored in the entry.
291    /// This is because implementations of `HashMap` may need to recompute hashes
292    /// when resizing, at which point only the keys are available.
293    ///
294    /// Raw entries give mutable access to the keys. This must not be used
295    /// to modify how the key would compare or hash, as the map will not re-evaluate
296    /// where the key should go, meaning the keys may become "lost" if their
297    /// location does not reflect their state. For instance, if you change a key
298    /// so that the map now contains keys which compare equal, search may start
299    /// acting erratically, with two keys randomly masking each other. Implementations
300    /// are free to assume this doesn't happen (within the limits of memory-safety).
301    #[inline]
302    pub fn raw_entry_mut(&mut self) -> RawEntryBuilderMut<'_, K, V, N, S> {
303        RawEntryBuilderMut { map: self }
304    }
305
306    /// Creates a raw immutable entry builder for the `HashMap`.
307    ///
308    /// Raw entries provide the lowest level of control for searching and
309    /// manipulating a map. They must be manually initialized with a hash and
310    /// then manually searched.
311    ///
312    /// This is useful for
313    /// * Hash memoization
314    /// * Using a search key that doesn't work with the Borrow trait
315    /// * Using custom comparison logic without newtype wrappers
316    ///
317    /// Unless you are in such a situation, higher-level and more foolproof APIs like
318    /// `get` should be preferred.
319    ///
320    /// Immutable raw entries have very limited use; you might instead want `raw_entry_mut`.
321    #[inline]
322    pub fn raw_entry(&self) -> RawEntryBuilder<'_, K, V, N, S> {
323        RawEntryBuilder { map: self }
324    }
325
326    /// Removes an element from a given position
327    #[inline]
328    unsafe fn remove_idx(&mut self, idx: usize) -> (K, V) {
329        self.v.swap_remove(idx)
330    }
331
332    /// inserts a non existing element and returns it's position
333    #[inline]
334    fn insert_idx(&mut self, k: K, v: V) -> usize {
335        let pos = self.v.len();
336        self.v.push((k, v));
337        pos
338    }
339    /// inserts a non existing element and returns it's position
340    #[inline]
341    unsafe fn get_mut_idx(&mut self, idx: usize) -> (&mut K, &mut V) {
342        let r = unsafe { self.v.get_unchecked_mut(idx) };
343        (&mut r.0, &mut r.1)
344    }
345    #[cfg(feature = "arraybackend")]
346    #[inline]
347    fn make_empty_vec_backend() -> arrayvec::ArrayVec<(K, V), N> {
348        arrayvec::ArrayVec::new()
349    }
350    #[cfg(not(feature = "arraybackend"))]
351    #[inline]
352    fn make_empty_vec_backend() -> Vec<(K, V)> {
353        Vec::new()
354    }
355}
halfbrown/vecmap.rs

halfbrown/
vecmap.rs
