fixed_map/map/
storage.rs

1//! Module that defines the [`MapStorage`] trait.
2
3mod boolean;
4pub(crate) use self::boolean::BooleanMapStorage;
5
6#[cfg(feature = "hashbrown")]
7mod hashbrown;
8#[cfg(feature = "hashbrown")]
9pub(crate) use self::hashbrown::HashbrownMapStorage;
10
11mod option;
12pub(crate) use self::option::OptionMapStorage;
13
14mod singleton;
15pub(crate) use self::singleton::SingletonMapStorage;
16
17use crate::map::Entry;
18
19/// The trait defining how storage works.
20///
21/// # Type Arguments
22///
23/// - `K` is the key being stored.
24/// - `V` is the value being stored.
25pub trait MapStorage<K, V>: Sized {
26    /// Immutable iterator over storage.
27    type Iter<'this>: Iterator<Item = (K, &'this V)>
28    where
29        Self: 'this,
30        V: 'this;
31
32    /// Immutable iterator over keys in storage.
33    type Keys<'this>: Iterator<Item = K>
34    where
35        Self: 'this;
36
37    /// Immutable iterator over values in storage.
38    type Values<'this>: Iterator<Item = &'this V>
39    where
40        Self: 'this,
41        V: 'this;
42
43    /// Mutable iterator over storage.
44    type IterMut<'this>: Iterator<Item = (K, &'this mut V)>
45    where
46        Self: 'this,
47        V: 'this;
48
49    /// Mutable iterator over values in storage.
50    type ValuesMut<'this>: Iterator<Item = &'this mut V>
51    where
52        Self: 'this,
53        V: 'this;
54
55    /// Consuming iterator.
56    type IntoIter: Iterator<Item = (K, V)>;
57
58    /// An occupied entry.
59    type Occupied<'this>: OccupiedEntry<'this, K, V>
60    where
61        Self: 'this;
62
63    /// A vacant entry.
64    type Vacant<'this>: VacantEntry<'this, K, V>
65    where
66        Self: 'this;
67
68    /// Construct empty storage.
69    fn empty() -> Self;
70
71    /// Get the length of storage.
72    fn len(&self) -> usize;
73
74    /// Check if storage is empty.
75    fn is_empty(&self) -> bool;
76
77    /// This is the storage abstraction for [`Map::insert`][crate::Map::insert].
78    fn insert(&mut self, key: K, value: V) -> Option<V>;
79
80    /// This is the storage abstraction for [`Map::contains_key`][crate::Map::contains_key].
81    fn contains_key(&self, key: K) -> bool;
82
83    /// This is the storage abstraction for [`Map::get`][crate::Map::get].
84    fn get(&self, key: K) -> Option<&V>;
85
86    /// This is the storage abstraction for [`Map::get_mut`][crate::Map::get_mut].
87    fn get_mut(&mut self, key: K) -> Option<&mut V>;
88
89    /// This is the storage abstraction for [`Map::remove`][crate::Map::remove].
90    fn remove(&mut self, key: K) -> Option<V>;
91
92    /// This is the storage abstraction for [`Map::retain`][crate::Map::retain].
93    fn retain<F>(&mut self, f: F)
94    where
95        F: FnMut(K, &mut V) -> bool;
96
97    /// This is the storage abstraction for [`Map::clear`][crate::Map::clear].
98    fn clear(&mut self);
99
100    /// This is the storage abstraction for [`Map::iter`][crate::Map::iter].
101    fn iter(&self) -> Self::Iter<'_>;
102
103    /// This is the storage abstraction for [`Map::keys`][crate::Map::keys].
104    fn keys(&self) -> Self::Keys<'_>;
105
106    /// This is the storage abstraction for [`Map::values`][crate::Map::values].
107    fn values(&self) -> Self::Values<'_>;
108
109    /// This is the storage abstraction for [`Map::iter_mut`][crate::Map::iter_mut].
110    fn iter_mut(&mut self) -> Self::IterMut<'_>;
111
112    /// This is the storage abstraction for [`Map::values_mut`][crate::Map::values_mut].
113    fn values_mut(&mut self) -> Self::ValuesMut<'_>;
114
115    /// This is the storage abstraction for [`Map::into_iter`][crate::Map::into_iter].
116    fn into_iter(self) -> Self::IntoIter;
117
118    /// This is the storage abstraction for [`Map::entry`][crate::Map::entry].
119    fn entry(&mut self, key: K) -> Entry<'_, Self, K, V>;
120}
121
122/// A view into an occupied entry in a [`Map`][crate::Map]. It is part of the
123/// [`Entry`] enum.
124pub trait OccupiedEntry<'a, K, V> {
125    /// Gets a copy of the key in the entry.
126    ///
127    /// # Examples
128    ///
129    /// ```
130    /// use fixed_map::{Key, Map};
131    /// use fixed_map::map::{Entry, OccupiedEntry};
132    ///
133    /// #[derive(Clone, Copy, Key, Debug, PartialEq)]
134    /// enum MyKey {
135    ///     First,
136    ///     Second,
137    /// }
138    ///
139    /// let mut map: Map<MyKey, i32> = Map::new();
140    /// map.insert(MyKey::First, 12);
141    ///
142    /// let occupied = match map.entry(MyKey::First) {
143    ///     Entry::Occupied(entry) => entry,
144    ///     _ => unreachable!(),
145    /// };
146    ///
147    /// assert_eq!(occupied.key(), MyKey::First);
148    /// ```
149    ///
150    /// Using a composite key:
151    ///
152    /// ```
153    /// use fixed_map::{Key, Map};
154    /// use fixed_map::map::{Entry, OccupiedEntry};
155    ///
156    /// #[derive(Clone, Copy, Key, Debug, PartialEq)]
157    /// enum MyKey {
158    ///     First(bool),
159    ///     Second,
160    /// }
161    ///
162    /// let mut map: Map<MyKey, i32> = Map::new();
163    /// map.insert(MyKey::First(false), 12);
164    ///
165    /// let occupied = match map.entry(MyKey::First(false)) {
166    ///     Entry::Occupied(entry) => entry,
167    ///     _ => unreachable!(),
168    /// };
169    ///
170    /// assert_eq!(occupied.key(), MyKey::First(false));
171    /// ```
172    fn key(&self) -> K;
173
174    /// Gets a reference to the value in the entry.
175    ///
176    /// # Examples
177    ///
178    /// ```
179    /// use fixed_map::{Key, Map};
180    /// use fixed_map::map::{Entry, OccupiedEntry};
181    ///
182    /// #[derive(Clone, Copy, Key)]
183    /// enum MyKey {
184    ///     First,
185    ///     Second,
186    /// }
187    ///
188    /// let mut map: Map<MyKey, i32> = Map::new();
189    /// map.insert(MyKey::First, 12);
190    ///
191    /// let occupied = match map.entry(MyKey::First) {
192    ///     Entry::Occupied(entry) => entry,
193    ///     _ => unreachable!(),
194    /// };
195    ///
196    /// assert_eq!(occupied.get(), &12);
197    /// ```
198    ///
199    /// Using a composite key:
200    ///
201    /// ```
202    /// use fixed_map::{Key, Map};
203    /// use fixed_map::map::{Entry, OccupiedEntry};
204    ///
205    /// #[derive(Clone, Copy, Key)]
206    /// enum MyKey {
207    ///     First(bool),
208    ///     Second,
209    /// }
210    ///
211    /// let mut map: Map<MyKey, i32> = Map::new();
212    /// map.insert(MyKey::First(false), 12);
213    ///
214    /// let occupied = match map.entry(MyKey::First(false)) {
215    ///     Entry::Occupied(entry) => entry,
216    ///     _ => unreachable!(),
217    /// };
218    ///
219    /// assert_eq!(occupied.get(), &12);
220    /// ```
221    fn get(&self) -> &V;
222
223    /// Gets a mutable reference to the value in the entry.
224    ///
225    /// If you need a reference to the `OccupiedEntry` which may
226    /// outlive the destruction of the `Entry` value, see [`into_mut`][Self::into_mut].
227    ///
228    /// # Examples
229    ///
230    /// ```
231    /// use fixed_map::{Key, Map};
232    /// use fixed_map::map::{Entry, OccupiedEntry};
233    ///
234    /// #[derive(Clone, Copy, Key)]
235    /// enum MyKey {
236    ///     First,
237    ///     Second,
238    /// }
239    ///
240    /// let mut map: Map<MyKey, i32> = Map::new();
241    /// map.insert(MyKey::First, 12);
242    ///
243    /// let mut occupied = match map.entry(MyKey::First) {
244    ///     Entry::Occupied(entry) => entry,
245    ///     _ => unreachable!(),
246    /// };
247    ///
248    /// assert_eq!(occupied.get_mut(), &12);
249    /// ```
250    ///
251    /// Using a composite key:
252    ///
253    /// ```
254    /// use fixed_map::{Key, Map};
255    /// use fixed_map::map::{Entry, OccupiedEntry};
256    ///
257    /// #[derive(Clone, Copy, Key)]
258    /// enum MyKey {
259    ///     First(bool),
260    ///     Second,
261    /// }
262    ///
263    /// let mut map: Map<MyKey, i32> = Map::new();
264    /// map.insert(MyKey::First(false), 12);
265    ///
266    /// let mut occupied = match map.entry(MyKey::First(false)) {
267    ///     Entry::Occupied(entry) => entry,
268    ///     _ => unreachable!(),
269    /// };
270    ///
271    /// *occupied.get_mut() *= 2;
272    /// assert_eq!(occupied.get(), &24);
273    /// // We can use the same Entry multiple times.
274    /// *occupied.get_mut() -= 10;
275    /// assert_eq!(occupied.get(), &14);
276    /// ```
277    fn get_mut(&mut self) -> &mut V;
278
279    /// Converts the `OccupiedEntry` into a mutable reference to the value in the entry
280    /// with a lifetime bound to the map itself.
281    ///
282    /// If you need multiple references to the `OccupiedEntry`, see [`get_mut`][Self::get_mut].
283    ///
284    /// # Examples
285    ///
286    /// ```
287    /// use fixed_map::{Key, Map};
288    /// use fixed_map::map::{Entry, OccupiedEntry};
289    ///
290    /// #[derive(Clone, Copy, Key)]
291    /// enum MyKey {
292    ///     First,
293    ///     Second,
294    /// }
295    ///
296    /// let mut map: Map<MyKey, i32> = Map::new();
297    /// map.insert(MyKey::First, 12);
298    ///
299    /// if let Entry::Occupied(occupied) = map.entry(MyKey::First) {
300    ///     *occupied.into_mut() += 10;
301    /// };
302    ///
303    /// assert_eq!(map.get(MyKey::First), Some(&22));
304    /// ```
305    ///
306    /// Using a composite key:
307    ///
308    /// ```
309    /// use fixed_map::{Key, Map};
310    /// use fixed_map::map::{Entry, OccupiedEntry};
311    ///
312    /// #[derive(Clone, Copy, Key)]
313    /// enum MyKey {
314    ///     First(bool),
315    ///     Second,
316    /// }
317    ///
318    /// let mut map: Map<MyKey, i32> = Map::new();
319    /// map.insert(MyKey::First(false), 12);
320    ///
321    /// if let Entry::Occupied(occupied) = map.entry(MyKey::First(false)) {
322    ///     *occupied.into_mut() += 10;
323    /// };
324    ///
325    /// assert_eq!(map.get(MyKey::First(false)), Some(&22));
326    /// ```
327    fn into_mut(self) -> &'a mut V;
328
329    /// Sets the value of the entry, and returns the entry's old value.
330    ///
331    /// # Examples
332    ///
333    /// ```
334    /// use fixed_map::{Key, Map};
335    /// use fixed_map::map::{Entry, OccupiedEntry};
336    ///
337    /// #[derive(Clone, Copy, Key)]
338    /// enum MyKey {
339    ///     First,
340    ///     Second,
341    /// }
342    ///
343    /// let mut map: Map<MyKey, i32> = Map::new();
344    /// map.insert(MyKey::First, 12);
345    ///
346    /// if let Entry::Occupied(mut occupied) = map.entry(MyKey::First) {
347    ///     assert_eq!(occupied.insert(10), 12);
348    /// };
349    ///
350    /// assert_eq!(map.get(MyKey::First), Some(&10));
351    /// ```
352    ///
353    /// Using a composite key:
354    ///
355    /// ```
356    /// use fixed_map::{Key, Map};
357    /// use fixed_map::map::{Entry, OccupiedEntry};
358    ///
359    /// #[derive(Clone, Copy, Key)]
360    /// enum MyKey {
361    ///     First(bool),
362    ///     Second,
363    /// }
364    ///
365    /// let mut map: Map<MyKey, i32> = Map::new();
366    /// map.insert(MyKey::First(false), 12);
367    ///
368    /// if let Entry::Occupied(mut occupied) = map.entry(MyKey::First(false)) {
369    ///     assert_eq!(occupied.insert(10), 12);
370    /// };
371    ///
372    /// assert_eq!(map.get(MyKey::First(false)), Some(&10));
373    /// ```
374    fn insert(&mut self, value: V) -> V;
375
376    /// Takes the value out of the entry, and returns it.
377    ///
378    /// # Examples
379    ///
380    /// ```
381    /// use fixed_map::{Key, Map};
382    /// use fixed_map::map::{Entry, OccupiedEntry};
383    ///
384    /// #[derive(Clone, Copy, Key)]
385    /// enum MyKey {
386    ///     First,
387    ///     Second,
388    /// }
389    ///
390    /// let mut map: Map<MyKey, i32> = Map::new();
391    /// map.insert(MyKey::First, 12);
392    ///
393    /// if let Entry::Occupied(occupied) = map.entry(MyKey::First) {
394    ///     assert_eq!(occupied.remove(), 12);
395    /// };
396    ///
397    /// assert_eq!(map.contains_key(MyKey::First), false);
398    /// ```
399    ///
400    /// Using a composite key:
401    ///
402    /// ```
403    /// use fixed_map::{Key, Map};
404    /// use fixed_map::map::{Entry, OccupiedEntry};
405    ///
406    /// #[derive(Clone, Copy, Key)]
407    /// enum MyKey {
408    ///     First(bool),
409    ///     Second,
410    /// }
411    ///
412    /// let mut map: Map<MyKey, i32> = Map::new();
413    /// map.insert(MyKey::First(true), 12);
414    ///
415    /// if let Entry::Occupied(occupied) = map.entry(MyKey::First(true)) {
416    ///     assert_eq!(occupied.remove(), 12);
417    /// };
418    ///
419    /// assert_eq!(map.contains_key(MyKey::First(true)), false);
420    /// ```
421    fn remove(self) -> V;
422}
423
424/// A view into a vacant entry in a [`Map`][crate::Map].
425/// It is part of the [`Entry`] enum.
426pub trait VacantEntry<'a, K, V> {
427    /// Gets a copy of the key that would be used
428    /// when inserting a value through the `VacantEntry`.
429    ///
430    /// # Examples
431    ///
432    /// ```
433    /// use fixed_map::{Key, Map};
434    /// use fixed_map::map::{Entry, VacantEntry};
435    ///
436    /// #[derive(Clone, Copy, Key, Debug, PartialEq)]
437    /// enum MyKey {
438    ///     First,
439    ///     Second,
440    /// }
441    ///
442    /// let mut map: Map<MyKey, i32> = Map::new();
443    /// let vacant = match map.entry(MyKey::First) {
444    ///     Entry::Vacant(entry) => entry,
445    ///     _ => unreachable!(),
446    /// };
447    ///
448    /// assert_eq!(vacant.key(), MyKey::First);
449    /// ```
450    ///
451    /// Using a composite key:
452    ///
453    /// ```
454    /// use fixed_map::{Key, Map};
455    /// use fixed_map::map::{Entry, VacantEntry};
456    ///
457    /// #[derive(Clone, Copy, Key, Debug, PartialEq)]
458    /// enum MyKey {
459    ///     First(bool),
460    ///     Second,
461    /// }
462    ///
463    /// let mut map: Map<MyKey, i32> = Map::new();
464    /// let vacant = match map.entry(MyKey::First(false)) {
465    ///     Entry::Vacant(entry) => entry,
466    ///     _ => unreachable!(),
467    /// };
468    ///
469    /// assert_eq!(vacant.key(), MyKey::First(false));
470    /// ```
471    fn key(&self) -> K;
472
473    /// Sets the value of the entry with the `VacantEntry`’s key,
474    /// and returns a mutable reference to it.
475    ///
476    /// # Examples
477    ///
478    /// ```
479    /// use fixed_map::{Key, Map};
480    /// use fixed_map::map::{Entry, VacantEntry};
481    ///
482    /// #[derive(Clone, Copy, Key)]
483    /// enum MyKey {
484    ///     First,
485    ///     Second,
486    /// }
487    ///
488    /// let mut map: Map<MyKey, i32> = Map::new();
489    ///
490    /// if let Entry::Vacant(vacant) = map.entry(MyKey::First) {
491    ///     assert_eq!(vacant.insert(37), &37);
492    /// }
493    ///
494    /// assert_eq!(map.get(MyKey::First), Some(&37));
495    /// ```
496    ///
497    /// Using a composite key:
498    ///
499    /// ```
500    /// use fixed_map::{Key, Map};
501    /// use fixed_map::map::{Entry, VacantEntry};
502    ///
503    /// #[derive(Clone, Copy, Key)]
504    /// enum MyKey {
505    ///     First(bool),
506    ///     Second,
507    /// }
508    ///
509    /// let mut map: Map<MyKey, i32> = Map::new();
510    ///
511    /// if let Entry::Vacant(vacant) = map.entry(MyKey::First(false)) {
512    ///     assert_eq!(vacant.insert(37), &37);
513    /// }
514    ///
515    /// assert_eq!(map.get(MyKey::First(false)), Some(&37));
516    /// ```
517    fn insert(self, value: V) -> &'a mut V;
518}
fixed_map/map/storage.rs

fixed_map/map/
storage.rs
