osom_lib_hash_tables/
traits.rs

1//! Defines hash table traits.
2
3use core::borrow::Borrow;
4use core::hash::Hash;
5
6use osom_lib_primitives::length::Length;
7
8/// Represents an immutable hash table.
9pub trait ImmutableHashTable<TKey, TValue>
10where
11    TKey: Hash + Eq,
12{
13    /// Returns the number of `(TKey, TValue)` pairs the table
14    /// contains. This typically **does not** correspond to the actual
15    /// size of the table in bytes.
16    fn length(&self) -> Length;
17
18    /// Checks if the table contains the corresponding `key`.
19    ///
20    /// # Notes
21    ///
22    /// The borrowed `Q` type's `Hash` and `Eq` must match those for `TKey`.
23    fn contains<Q>(&self, key: &Q) -> bool
24    where
25        TKey: Borrow<Q>,
26        Q: Eq + Hash + ?Sized;
27
28    /// Checks if the table contains the corresponding `key`, and if so then returns
29    /// the reference to the `TValue`, or `None` otherwise.
30    ///
31    /// # Notes
32    ///
33    /// The borrowed `Q` type's `Hash` and `Eq` must match those for `TKey`.
34    fn get<Q>(&self, key: &Q) -> Option<&TValue>
35    where
36        TKey: Borrow<Q>,
37        Q: Eq + Hash + ?Sized;
38
39    /// Checks if the table contains the corresponding `key`, and if so then returns
40    /// the `(&TKey, &TValue)` pair or `None` otherwise.
41    ///
42    /// # Notes
43    ///
44    /// The borrowed `Q` type's `Hash` and `Eq` must match those for `TKey`.
45    fn get_key_value<Q>(&self, key: &Q) -> Option<(&TKey, &TValue)>
46    where
47        TKey: Borrow<Q>,
48        Q: Eq + Hash + ?Sized;
49
50    /// Checks if the table is empty. This does not mean that it doesn't take space
51    /// in memory. Equivalent to `self.length() == 0` check.
52    fn is_empty(&self) -> bool {
53        self.length() == Length::ZERO
54    }
55
56    /// Returns an iterator over the key-value pairs in the table.
57    ///
58    /// # Notes
59    ///
60    /// The iterator yields `(&TKey, &TValue)` tuples representing each key-value pair
61    /// in the hash table.
62    fn iter<'a>(&'a self) -> impl Iterator<Item = (&'a TKey, &'a TValue)>
63    where
64        TKey: 'a,
65        TValue: 'a,
66        Self: 'a;
67}
68
69/// An extension of [`ImmutableHashTable`] that allows the actual modifications
70/// to the table.
71pub trait MutableHashTable<TKey, TValue>: ImmutableHashTable<TKey, TValue>
72where
73    TKey: Hash + Eq,
74{
75    /// Inserts given `(TKey, TValue)` pair into the table.
76    ///
77    /// Return `None` if the `key` didn't already exist in the table.
78    ///
79    /// Otherwise returns the old `TValue`.
80    fn insert(&mut self, key: TKey, value: TValue) -> Option<TValue>;
81
82    /// Removes entire entry from the table. Returns `(TKey, TValue)` pair
83    /// for the matching `key` or `None` if there is no match.
84    ///
85    /// # Notes
86    ///
87    /// The borrowed `Q` type's `Hash` and `Eq` must match those for `TKey`.
88    fn remove_entry<Q>(&mut self, key: &Q) -> Option<(TKey, TValue)>
89    where
90        TKey: Borrow<Q>,
91        Q: Eq + Hash + ?Sized;
92
93    /// Searches the table for a given `key`. If the table contains it, then
94    /// it runs `updater` on the corresponding `TValue`. Otherwise runs `adder`
95    /// to add a new `TValue` to the table. Returns the mutable reference to the
96    /// final `TValue`.
97    ///
98    /// # Notes
99    ///
100    /// The implementation has to guarantee that one of: `adder` or `updater` will be called
101    /// during its execution, but not both.
102    fn insert_or_update_with<FAdd, FUpdate>(&mut self, key: TKey, adder: FAdd, updater: FUpdate) -> &mut TValue
103    where
104        FAdd: FnOnce() -> TValue,
105        FUpdate: FnOnce(&mut TValue);
106
107    /// Removes entire entry from the table. Similar to [`MutableHashTable::remove_entry`],
108    /// but returns `TValue` only for the matching `key` or `None` if there is no match.
109    ///
110    /// # Notes
111    ///
112    /// The borrowed `Q` type's `Hash` and `Eq` must match those for `TKey`.
113    #[inline(always)]
114    fn remove<Q>(&mut self, key: &Q) -> Option<TValue>
115    where
116        TKey: Borrow<Q>,
117        Q: Eq + Hash + ?Sized,
118    {
119        if let Some((_, value)) = self.remove_entry(key) {
120            Some(value)
121        } else {
122            None
123        }
124    }
125
126    /// Retrieves an existing `TValue`, or inserts a default one.
127    ///
128    /// Internally equivalent to `self.insert_or_update_with(key, TValue::default, |_| {})`.
129    #[inline(always)]
130    fn get_or_insert_default(&mut self, key: TKey) -> &mut TValue
131    where
132        TValue: Default,
133    {
134        self.insert_or_update_with(key, TValue::default, |_| {})
135    }
136
137    /// Retrieves an existing `TValue`, or inserts the passed one.
138    ///
139    /// Internally equivalent to `self.insert_or_update_with(key, || value, || {})`.
140    #[inline(always)]
141    fn get_or_insert(&mut self, key: TKey, value: TValue) -> &mut TValue {
142        self.insert_or_update_with(key, || value, |_| {})
143    }
144
145    /// Returns a mutable iterator over the key-value pairs in the table.
146    ///
147    /// # Notes
148    ///
149    /// The iterator yields `(&TKey, &mut TValue)` tuples representing each key-value pair
150    /// in the hash table.
151    fn iter_mut<'a>(&'a mut self) -> impl Iterator<Item = (&'a TKey, &'a mut TValue)>
152    where
153        TKey: 'a,
154        TValue: 'a,
155        Self: 'a;
156}
osom_lib_hash_tables/traits.rs

osom_lib_hash_tables/
traits.rs
