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::kvp::KVP;
7use osom_lib_primitives::length::Length;
8
9use crate::errors::HashTableError;
10
11/// Represents an immutable hash table.
12pub trait ImmutableHashTable<TKey, TValue>: Sized
13where
14    TKey: Hash + Eq,
15{
16    /// Returns the number of `(TKey, TValue)` pairs the table
17    /// contains. This typically **does not** correspond to the actual
18    /// size of the table in bytes.
19    fn length(&self) -> Length;
20
21    /// Checks if the table contains the corresponding `key`.
22    ///
23    /// # Notes
24    ///
25    /// The borrowed `Q` type's `Hash` and `Eq` must match those for `TKey`.
26    fn contains<Q>(&self, key: &Q) -> bool
27    where
28        TKey: Borrow<Q>,
29        Q: Eq + Hash + ?Sized;
30
31    /// Checks if the table contains the corresponding `key`, and if so then returns
32    /// the reference to the `TValue`, or `None` otherwise.
33    ///
34    /// # Notes
35    ///
36    /// The borrowed `Q` type's `Hash` and `Eq` must match those for `TKey`.
37    fn get<Q>(&self, key: &Q) -> Option<&TValue>
38    where
39        TKey: Borrow<Q>,
40        Q: Eq + Hash + ?Sized;
41
42    /// Checks if the table contains the corresponding `key`, and if so then returns
43    /// the `(&TKey, &TValue)` pair or `None` otherwise.
44    ///
45    /// # Notes
46    ///
47    /// The borrowed `Q` type's `Hash` and `Eq` must match those for `TKey`.
48    fn get_key_value<Q>(&self, key: &Q) -> Option<KVP<&TKey, &TValue>>
49    where
50        TKey: Borrow<Q>,
51        Q: Eq + Hash + ?Sized;
52
53    /// Checks if the table is empty. This does not mean that it doesn't take space
54    /// in memory. Equivalent to `self.length() == 0` check.
55    fn is_empty(&self) -> bool {
56        self.length() == Length::ZERO
57    }
58
59    /// Returns an iterator over the key-value pairs in the table.
60    ///
61    /// # Notes
62    ///
63    /// The iterator yields `(&TKey, &TValue)` tuples representing each key-value pair
64    /// in the hash table.
65    fn iter<'a>(&'a self) -> impl Iterator<Item = KVP<&'a TKey, &'a TValue>> + 'a
66    where
67        TKey: 'a,
68        TValue: 'a,
69        Self: 'a;
70}
71
72/// An extension of [`ImmutableHashTable`] that allows the actual modifications
73/// to the table.
74pub trait MutableHashTable<TKey, TValue>: ImmutableHashTable<TKey, TValue>
75where
76    TKey: Hash + Eq,
77{
78    /// Checks if the table contains the corresponding `key`, and if so then returns
79    /// a mutable reference to the `TValue`, or `None` otherwise.
80    ///
81    /// # Notes
82    ///
83    /// The borrowed `Q` type's `Hash` and `Eq` must match those for `TKey`.
84    fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut TValue>
85    where
86        TKey: Borrow<Q>,
87        Q: Eq + Hash + ?Sized;
88
89    /// Checks if the table contains the corresponding `key`, and if so then returns
90    /// a mutable reference to the `TValue`, or `None` otherwise.
91    ///
92    /// # Notes
93    ///
94    /// The borrowed `Q` type's `Hash` and `Eq` must match those for `TKey`.
95    fn get_key_value_mut<Q>(&mut self, key: &Q) -> Option<KVP<&TKey, &mut TValue>>
96    where
97        TKey: Borrow<Q>,
98        Q: Eq + Hash + ?Sized;
99
100    /// Inserts given `(TKey, TValue)` pair into the table.
101    ///
102    /// Return `None` if the `key` didn't already exist in the table.
103    ///
104    /// Otherwise returns the old `TValue`.
105    ///
106    /// # Panics
107    ///
108    /// Whenever the corresponding [`MutableHashTable::try_insert`] would fail.
109    fn insert(&mut self, key: TKey, value: TValue) -> Option<TValue> {
110        self.try_insert(key, value)
111            .expect("[MutableHashTable::try_insert] failure")
112    }
113
114    /// Tries to insert given `(TKey, TValue)` pair into the table.
115    ///
116    /// Return `None` if the `key` didn't already exist in the table.
117    ///
118    /// Otherwise returns the old `TValue`.
119    ///
120    /// # Errors
121    ///
122    /// For details see [`HashTableError`].
123    fn try_insert(&mut self, key: TKey, value: TValue) -> Result<Option<TValue>, HashTableError> {
124        let value_ptr = &raw const value;
125        let adder = || unsafe { value_ptr.read() };
126
127        let mut result: Option<TValue> = None;
128        let updater = |current: &mut TValue| {
129            let value = unsafe { value_ptr.read() };
130            let old_value = core::mem::replace(current, value);
131            result = Some(old_value);
132        };
133
134        let _ = self.try_insert_or_update_with(key, adder, updater)?;
135        core::mem::forget(value);
136        Ok(result)
137    }
138
139    /// Removes entire entry from the table. Returns `(TKey, TValue)` pair
140    /// for the matching `key` or `None` if there is no match.
141    ///
142    /// # Notes
143    ///
144    /// The borrowed `Q` type's `Hash` and `Eq` must match those for `TKey`.
145    fn remove_entry<Q>(&mut self, key: &Q) -> Option<KVP<TKey, TValue>>
146    where
147        TKey: Borrow<Q>,
148        Q: Eq + Hash + ?Sized;
149
150    /// Searches the table for a given `key`. If the table contains it, then
151    /// it runs `updater` on the corresponding `TValue`. Otherwise runs `adder`
152    /// to add a new `TValue` to the table. Returns the mutable reference to the
153    /// final `TValue`.
154    ///
155    /// # Notes
156    ///
157    /// The implementation has to guarantee that one of: `adder` or `updater` will be called
158    /// during its execution, but not both.
159    ///
160    /// # Panics
161    ///
162    /// Whenever the corresponding [`MutableHashTable::try_insert_or_update_with`] would fail.
163    fn insert_or_update_with<FAdd, FUpdate>(&mut self, key: TKey, adder: FAdd, updater: FUpdate) -> &mut TValue
164    where
165        FAdd: FnOnce() -> TValue,
166        FUpdate: FnOnce(&mut TValue),
167    {
168        self.try_insert_or_update_with(key, adder, updater)
169            .expect("[MutableHashTable::try_insert_or_update_with] failure")
170    }
171
172    /// Searches the table for a given `key`. If the table contains it, then
173    /// it runs `updater` on the corresponding `TValue`. Otherwise runs `adder`
174    /// to add a new `TValue` to the table. Returns the mutable reference to the
175    /// final `TValue`.
176    ///
177    /// # Notes
178    ///
179    /// The implementation has to guarantee that one of: `adder` or `updater` will be called
180    /// during its execution, but not both.
181    ///
182    /// # Errors
183    ///
184    /// For details see [`HashTableError`].
185    fn try_insert_or_update_with<FAdd, FUpdate>(
186        &mut self,
187        key: TKey,
188        adder: FAdd,
189        updater: FUpdate,
190    ) -> Result<&mut TValue, HashTableError>
191    where
192        FAdd: FnOnce() -> TValue,
193        FUpdate: FnOnce(&mut TValue);
194
195    /// Removes entire entry from the table. Similar to [`MutableHashTable::remove_entry`],
196    /// but returns `TValue` only for the matching `key` or `None` if there is no match.
197    ///
198    /// # Notes
199    ///
200    /// The borrowed `Q` type's `Hash` and `Eq` must match those for `TKey`.
201    #[inline(always)]
202    fn remove<Q>(&mut self, key: &Q) -> Option<TValue>
203    where
204        TKey: Borrow<Q>,
205        Q: Eq + Hash + ?Sized,
206    {
207        if let Some(kvp) = self.remove_entry(key) {
208            let (_, value) = kvp.unpack();
209            Some(value)
210        } else {
211            None
212        }
213    }
214
215    /// Retrieves an existing `TValue`, or inserts a default one.
216    ///
217    /// Internally equivalent to `self.try_get_or_insert_default(key)`.
218    ///
219    /// # Panics
220    ///
221    /// Whenever the corresponding [`MutableHashTable::try_get_or_insert_default`] would fail.
222    #[inline(always)]
223    fn get_or_insert_default(&mut self, key: TKey) -> &mut TValue
224    where
225        TValue: Default,
226    {
227        self.try_get_or_insert_default(key)
228            .expect("[MutableHashTable::try_get_or_insert_default] failure")
229    }
230
231    /// Retrieves an existing `TValue`, or inserts a default one.
232    ///
233    /// Internally equivalent to `self.try_insert_or_update_with(key, TValue::default, |_| {})`.
234    ///
235    /// # Errors
236    ///
237    /// For details see [`HashTableError`].
238    #[inline(always)]
239    fn try_get_or_insert_default(&mut self, key: TKey) -> Result<&mut TValue, HashTableError>
240    where
241        TValue: Default,
242    {
243        self.try_insert_or_update_with(key, TValue::default, |_| {})
244    }
245
246    /// Retrieves an existing `TValue`, or inserts the passed one.
247    ///
248    /// Internally equivalent to `self.try_get_or_insert(key, value)`.
249    ///
250    /// # Panics
251    ///
252    /// Whenever the corresponding [`MutableHashTable::try_get_or_insert`] would fail.
253    #[inline(always)]
254    fn get_or_insert(&mut self, key: TKey, value: TValue) -> &mut TValue {
255        self.try_get_or_insert(key, value)
256            .expect("[MutableHashTable::try_get_or_insert] failure")
257    }
258
259    /// Retrieves an existing `TValue`, or inserts the passed one.
260    ///
261    /// Internally equivalent to `self.try_insert_or_update_with(key, || value, || {})`.
262    ///
263    /// # Errors
264    ///
265    /// For details see [`HashTableError`].
266    #[inline(always)]
267    fn try_get_or_insert(&mut self, key: TKey, value: TValue) -> Result<&mut TValue, HashTableError> {
268        self.try_insert_or_update_with(key, || value, |_| {})
269    }
270
271    /// Returns a mutable iterator over the key-value pairs in the table.
272    ///
273    /// # Notes
274    ///
275    /// The iterator yields `(&TKey, &mut TValue)` tuples representing each key-value pair
276    /// in the hash table.
277    fn iter_mut<'a>(&'a mut self) -> impl Iterator<Item = KVP<&'a TKey, &'a mut TValue>> + 'a
278    where
279        TKey: 'a,
280        TValue: 'a,
281        Self: 'a;
282}
osom_lib_hash_tables/traits.rs

osom_lib_hash_tables/
traits.rs
