hash_trie/
result.rs

1use crate::{node::{CNode, LNode, SNode}, traits::*, *};
2use alloc::sync::Arc;
3
4/// `BitError` enumerates possible error conditions when bitops are used "incorrectly."
5#[derive(Debug)]
6#[must_use]
7pub enum BitError {
8    /// `BitError::CountNotEqualToOne` indicates a word representing a bit contains either 2 or more bits or 0 bits.
9    CountNotEqualToOne,
10    /// `BitError::Found` indicates a bit that is supposed to be absent is present.
11    Found,
12    /// `BitError::NotFound` indicates a bit that is supposed to be present is absent.
13    NotFound,
14    /// `BitError::Range` indicates an index exceeding the word size was used.
15    Range,
16}
17
18/// The only error you'll find is `NotFound`.
19#[derive(Clone, Debug, Eq, PartialEq)]
20pub enum HashTrieError {
21    /// The value was not found.
22    NotFound,
23}
24
25#[must_use]
26pub(crate) enum FindResult<'a, K: Key, V: Value> {
27    NotFound,
28    Found(&'a K, &'a V),
29}
30
31#[must_use]
32pub(crate) enum InsertResult<'a, H: Hashword, F: Flagword<H>, K: Key, V: Value, M: 'static> {
33    Found(&'a K, &'a V),
34    InsertedC(CNode<H, F, K, V, M>, *const K, *const V, Option<(&'a K, &'a V)>),
35    InsertedL(Arc<LNode<K, V>>, *const K, *const V, Option<(&'a K, &'a V)>),
36    InsertedS(Arc<SNode<K, V>>, *const K, *const V, Option<(&'a K, &'a V)>),
37}
38
39#[must_use]
40pub(crate) enum CNodeInsertResult<'a, H: Hashword, F: Flagword<H>, K: Key, V: Value, M: 'static> {
41    Found(&'a K, &'a V),
42    InsertedC(CNode<H, F, K, V, M>, *const K, *const V, Option<(&'a K, &'a V)>),
43}
44
45impl <'a, H: Hashword, F: Flagword<H>, K: Key, V: Value, M: 'static> From<CNodeInsertResult<'a, H, F, K, V, M>> for InsertResult<'a, H, F, K, V, M> {
46    fn from(other: CNodeInsertResult<'a, H, F, K, V, M>) -> Self {
47        match other {
48            CNodeInsertResult::Found(key, value) => InsertResult::Found(key, value),
49            CNodeInsertResult::InsertedC(lnode, key, value, prev) => InsertResult::InsertedC(lnode, key, value, prev),
50        }
51    }
52}
53
54#[must_use]
55pub(crate) enum LNodeInsertResult<'a, H: Hashword, F: Flagword<H>, K: Key, V: Value, M: 'static> {
56    Found(&'a K, &'a V),
57    InsertedC(CNode<H, F, K, V, M>, *const K, *const V, Option<(&'a K, &'a V)>),
58    InsertedL(Arc<LNode<K, V>>, *const K, *const V, Option<(&'a K, &'a V)>),
59}
60
61impl <'a, H: Hashword, F: Flagword<H>, K: Key, V: Value, M: 'static> From<LNodeInsertResult<'a, H, F, K, V, M>> for InsertResult<'a, H, F, K, V, M> {
62    fn from(other: LNodeInsertResult<'a, H, F, K, V, M>) -> Self {
63        match other {
64            LNodeInsertResult::Found(key, value) => InsertResult::Found(key, value),
65            LNodeInsertResult::InsertedC(lnode, key, value, prev) => InsertResult::InsertedC(lnode, key, value, prev),
66            LNodeInsertResult::InsertedL(snode, key, value, prev) => InsertResult::InsertedL(snode, key, value, prev),
67        }
68    }
69}
70
71#[must_use]
72pub(crate) enum RemoveResult<'a, H: Hashword, F: Flagword<H>, K: Key, V: Value, M: 'static> {
73    NotFound,
74    RemovedC(CNode<H, F, K, V, M>, &'a K, &'a V),
75    RemovedL(Arc<LNode<K, V>>, &'a K, &'a V),
76    RemovedS(Arc<SNode<K, V>>, &'a K, &'a V),
77    RemovedZ(&'a K, &'a V),
78}
79
80#[must_use]
81pub(crate) enum LNodeRemoveResult<'a, K: Key, V: Value> {
82    NotFound,
83    RemovedL(Arc<LNode<K, V>>, &'a K, &'a V),
84    RemovedS(Arc<SNode<K, V>>, &'a K, &'a V),
85}
86
87impl <'a, H: Hashword, F: Flagword<H>, K: Key, V: Value, M: 'static> From<LNodeRemoveResult<'a, K, V>> for RemoveResult<'a, H, F, K, V, M> {
88    fn from(other: LNodeRemoveResult<'a, K, V>) -> Self {
89        match other {
90            LNodeRemoveResult::NotFound => RemoveResult::NotFound,
91            LNodeRemoveResult::RemovedL(lnode, key, value) => RemoveResult::RemovedL(lnode, key, value),
92            LNodeRemoveResult::RemovedS(snode, key, value) => RemoveResult::RemovedS(snode, key, value),
93        }
94    }
95}
96
97#[must_use]
98pub(crate) enum SNodeRemoveResult<'a, K: Key, V: Value> {
99    NotFound,
100    RemovedZ(&'a K, &'a V),
101}
102
103impl <'a, H: Hashword, F: Flagword<H>, K: Key, V: Value, M: 'static> From<SNodeRemoveResult<'a, K, V>> for RemoveResult<'a, H, F, K, V, M> {
104    fn from(other: SNodeRemoveResult<'a, K, V>) -> Self {
105        match other {
106            SNodeRemoveResult::NotFound => RemoveResult::NotFound,
107            SNodeRemoveResult::RemovedZ(key, value) => RemoveResult::RemovedZ(key, value),
108        }
109    }
110}
111
112/// SetTransformResult is the result of a transform operation on a single entry of a set.
113#[must_use]
114pub enum SetTransformResult<ReduceT> {
115    /// The value is unchanged.
116    Unchanged(ReduceT),
117    /// The value was removed.
118    Removed(ReduceT),
119}
120
121/// SetJointTransformResult is the result of a transform operation on a pair of entries of a set.
122#[must_use]
123pub enum SetJointTransformResult<ReduceT> {
124    /// The value is unchanged from both left and right.
125    UnchangedLR(ReduceT),
126    /// The value is unchanged from the left.
127    UnchangedL(ReduceT),
128    /// The value is unchanged from the right.
129    UnchangedR(ReduceT),
130    /// The value was removed.
131    Removed(ReduceT),
132}
133
134/// SetTransmuteResult is the result of a transmute operation on a single entry or pair of entries of a set.
135#[must_use]
136pub enum SetTransmuteResult<K, ReduceT> {
137    /// The value has been transmuted.
138    Transmuted(K, ReduceT),
139    /// The value was removed.
140    Removed(ReduceT),
141}
142
143/// MapTransformResult is the result of a transform operation on a single entry of a map.
144#[must_use]
145pub enum MapTransformResult<V, ReduceT> {
146    /// The value is unchanged.
147    Unchanged(ReduceT),
148    /// The value has been transformed.
149    Transformed(V, ReduceT),
150    /// The key-value pair was removed.
151    Removed(ReduceT),
152}
153
154impl <V, ReduceT> From<SetTransformResult<ReduceT>> for MapTransformResult<V, ReduceT> {
155    fn from(other: SetTransformResult<ReduceT>) -> Self {
156        match other {
157            SetTransformResult::Unchanged(reduced) => MapTransformResult::Unchanged(reduced),
158            SetTransformResult::Removed(reduced) => MapTransformResult::Removed(reduced),
159        }
160    }
161}
162
163/// MapJointTransformResult is the result of a transform operation on a pair of entries of a map.
164#[must_use]
165pub enum MapJointTransformResult<V, ReduceT> {
166    /// The value is unchanged from both the left and right.
167    UnchangedLR(ReduceT),
168    /// The value is unchanged from the left.
169    UnchangedL(ReduceT),
170    /// The value is unchanged from the right.
171    UnchangedR(ReduceT),
172    /// The value has been transformed.
173    Transformed(V, ReduceT),
174    /// The key-value pair was removed.
175    Removed(ReduceT),
176}
177
178impl <V, ReduceT> MapJointTransformResult<V, ReduceT> {
179    pub(crate) fn flip(self) -> Self {
180        match self {
181            Self::UnchangedLR(reduced) => Self::UnchangedLR(reduced),
182            Self::UnchangedL(reduced) => Self::UnchangedR(reduced),
183            Self::UnchangedR(reduced) => Self::UnchangedL(reduced),
184            Self::Transformed(value, reduced) => Self::Transformed(value, reduced),
185            Self::Removed(reduced) => Self::Removed(reduced),
186        }
187    }
188}
189
190impl <V, ReduceT> From<SetJointTransformResult<ReduceT>> for MapJointTransformResult<V, ReduceT> {
191    fn from(other: SetJointTransformResult<ReduceT>) -> Self {
192        match other {
193            SetJointTransformResult::UnchangedLR(reduced) => MapJointTransformResult::UnchangedLR(reduced),
194            SetJointTransformResult::UnchangedL(reduced) => MapJointTransformResult::UnchangedL(reduced),
195            SetJointTransformResult::UnchangedR(reduced) => MapJointTransformResult::UnchangedR(reduced),
196            SetJointTransformResult::Removed(reduced) => MapJointTransformResult::Removed(reduced),
197        }
198    }
199}
200
201/// MapTransmuteResult is the result of a transmute operation on a single entry of a map or a pair of entries of a map.
202#[must_use]
203pub enum MapTransmuteResult<K, V, ReduceT> {
204    /// The value has been transmuted.
205    Transmuted(K, V, ReduceT),
206    /// The key-value pair was removed.
207    Removed(ReduceT),
208}
209
210#[must_use]
211pub(crate) enum MNodeTransformResult<H: Hashword, F: Flagword<H>, K: Key, V: Value, M: 'static, ReduceT> {
212    Unchanged(ReduceT),
213    C(CNode<H, F, K, V, M>, ReduceT),
214    L(Arc<LNode<K, V>>, ReduceT),
215    S(Arc<SNode<K, V>>, ReduceT),
216    Removed(ReduceT),
217}
218
219#[must_use]
220pub(crate) enum MNodeJointTransformResult<H: Hashword, F: Flagword<H>, K: Key, V: Value, M: 'static, ReduceT> {
221    UnchangedLR(ReduceT),
222    UnchangedL(ReduceT),
223    UnchangedR(ReduceT),
224    C(CNode<H, F, K, V, M>, ReduceT),
225    L(Arc<LNode<K, V>>, ReduceT),
226    S(Arc<SNode<K, V>>, ReduceT),
227    Removed(ReduceT),
228}
229
230impl <H: Hashword, F: Flagword<H>, K: Key, V: Value, M: 'static, ReduceT> MNodeJointTransformResult<H, F, K, V, M, ReduceT> {
231    pub(crate) fn flip(self) -> Self {
232        match self {
233            Self::UnchangedLR(reduced) => Self::UnchangedLR(reduced),
234            Self::UnchangedL(reduced) => Self::UnchangedR(reduced),
235            Self::UnchangedR(reduced) => Self::UnchangedL(reduced),
236            Self::C(cnode, reduced) => Self::C(cnode, reduced),
237            Self::L(lnode, reduced) => Self::L(lnode, reduced),
238            Self::S(snode, reduced) => Self::S(snode, reduced),
239            Self::Removed(reduced) => Self::Removed(reduced),
240        }
241    }
242}
243
244#[must_use]
245pub(crate) enum MNodeTransmuteResult<H: Hashword, F: Flagword<H>, K: Key, V: Value, M: 'static, ReduceT> {
246    C(CNode<H, F, K, V, M>, ReduceT),
247    L(Arc<LNode<K, V>>, ReduceT),
248    S(Arc<SNode<K, V>>, ReduceT),
249    Removed(ReduceT),
250}
251
252impl <H: Hashword, F: Flagword<H>, K: Key, V: Value, M: 'static, ReduceT> From<MNodeTransmuteResult<H, F, K, V, M, ReduceT>> for MNodeTransformResult<H, F, K, V, M, ReduceT> {
253    fn from(other: MNodeTransmuteResult<H, F, K, V, M, ReduceT>) -> Self {
254        match other {
255            MNodeTransmuteResult::C(cnode, reduced) => MNodeTransformResult::C(cnode, reduced),
256            MNodeTransmuteResult::L(lnode, reduced) => MNodeTransformResult::L(lnode, reduced),
257            MNodeTransmuteResult::S(snode, reduced) => MNodeTransformResult::S(snode, reduced),
258            MNodeTransmuteResult::Removed(reduced) => MNodeTransformResult::Removed(reduced),
259        }
260    }
261}
262
263#[must_use]
264pub(crate) enum LNodeTransformResult<K: Key, V: Value, ReduceT> {
265    Unchanged(ReduceT),
266    L(Arc<LNode<K, V>>, ReduceT),
267    S(Arc<SNode<K, V>>, ReduceT),
268    Removed(ReduceT),
269}
270
271impl <H: Hashword, F: Flagword<H>, K: Key, V: Value, M: 'static, ReduceT> From<LNodeTransformResult<K, V, ReduceT>> for MNodeTransformResult<H, F, K, V, M, ReduceT> {
272    fn from(other: LNodeTransformResult<K, V, ReduceT>) -> Self {
273        match other {
274            LNodeTransformResult::Unchanged(reduced) => MNodeTransformResult::Unchanged(reduced),
275            LNodeTransformResult::L(lnode, reduced) => MNodeTransformResult::L(lnode, reduced),
276            LNodeTransformResult::S(snode, reduced) => MNodeTransformResult::S(snode, reduced),
277            LNodeTransformResult::Removed(reduced) => MNodeTransformResult::Removed(reduced),
278        }
279    }
280}
281
282#[must_use]
283pub(crate) enum LNodeJointTransformResult<K: Key, V: Value, ReduceT> {
284    UnchangedLR(ReduceT),
285    UnchangedL(ReduceT),
286    UnchangedR(ReduceT),
287    L(Arc<LNode<K, V>>, ReduceT),
288    S(Arc<SNode<K, V>>, ReduceT),
289    Removed(ReduceT),
290}
291
292impl <H: Hashword, F: Flagword<H>, K: Key, V: Value, M: 'static, ReduceT> From<LNodeJointTransformResult<K, V, ReduceT>> for MNodeJointTransformResult<H, F, K, V, M, ReduceT> {
293    fn from(other: LNodeJointTransformResult<K, V, ReduceT>) -> Self {
294        match other {
295            LNodeJointTransformResult::UnchangedLR(reduced) => MNodeJointTransformResult::UnchangedLR(reduced),
296            LNodeJointTransformResult::UnchangedL(reduced) => MNodeJointTransformResult::UnchangedL(reduced),
297            LNodeJointTransformResult::UnchangedR(reduced) => MNodeJointTransformResult::UnchangedR(reduced),
298            LNodeJointTransformResult::L(lnode, reduced) => MNodeJointTransformResult::L(lnode, reduced),
299            LNodeJointTransformResult::S(snode, reduced) => MNodeJointTransformResult::S(snode, reduced),
300            LNodeJointTransformResult::Removed(reduced) => MNodeJointTransformResult::Removed(reduced),
301        }
302    }
303}
304
305#[must_use]
306pub(crate) enum LNodeTransmuteResult<K: Key, V: Value, ReduceT> {
307    L(Arc<LNode<K, V>>, ReduceT),
308    S(Arc<SNode<K, V>>, ReduceT),
309    Removed(ReduceT),
310}
311
312impl <H: Hashword, F: Flagword<H>, K: Key, V: Value, M: 'static, ReduceT> From<LNodeTransmuteResult<K, V, ReduceT>> for MNodeTransformResult<H, F, K, V, M, ReduceT> {
313    fn from(other: LNodeTransmuteResult<K, V, ReduceT>) -> Self {
314        match other {
315            LNodeTransmuteResult::L(lnode, reduced) => MNodeTransformResult::L(lnode, reduced),
316            LNodeTransmuteResult::S(snode, reduced) => MNodeTransformResult::S(snode, reduced),
317            LNodeTransmuteResult::Removed(reduced) => MNodeTransformResult::Removed(reduced),
318        }
319    }
320}
321
322impl <H: Hashword, F: Flagword<H>, K: Key, V: Value, M: 'static, ReduceT> From<LNodeTransmuteResult<K, V, ReduceT>> for MNodeTransmuteResult<H, F, K, V, M, ReduceT> {
323    fn from(other: LNodeTransmuteResult<K, V, ReduceT>) -> Self {
324        match other {
325            LNodeTransmuteResult::L(lnode, reduced) => MNodeTransmuteResult::L(lnode, reduced),
326            LNodeTransmuteResult::S(snode, reduced) => MNodeTransmuteResult::S(snode, reduced),
327            LNodeTransmuteResult::Removed(reduced) => MNodeTransmuteResult::Removed(reduced),
328        }
329    }
330}
331
332impl <H: Hashword, F: Flagword<H>, K: Key, V: Value, M: 'static, ReduceT> From<MapTransmuteResult<K, V, ReduceT>> for MNodeTransmuteResult<H, F, K, V, M, ReduceT> {
333    fn from(other: MapTransmuteResult<K, V, ReduceT>) -> Self {
334        match other {
335            MapTransmuteResult::Transmuted(key, value, reduced) => MNodeTransmuteResult::S(SNode::new(key, value), reduced),
336            MapTransmuteResult::Removed(reduced) => MNodeTransmuteResult::Removed(reduced),
337        }
338    }
339}
340
341impl <K: Key, V: Value, ReduceT> From<MapTransmuteResult<K, V, ReduceT>> for LNodeTransmuteResult<K, V, ReduceT> {
342    fn from(other: MapTransmuteResult<K, V, ReduceT>) -> Self {
343        match other {
344            MapTransmuteResult::Transmuted(key, value, reduced) => LNodeTransmuteResult::S(SNode::new(key, value), reduced),
345            MapTransmuteResult::Removed(reduced) => LNodeTransmuteResult::Removed(reduced),
346        }
347    }
348}
349
350#[must_use]
351pub(crate) enum SNodeTransformResult<K: Key, V: Value, ReduceT> {
352    Unchanged(ReduceT),
353    S(Arc<SNode<K, V>>, ReduceT),
354    Removed(ReduceT),
355}
356
357impl <H: Hashword, F: Flagword<H>, K: Key, V: Value, M: 'static, ReduceT> From<SNodeTransformResult<K, V, ReduceT>> for MNodeTransformResult<H, F, K, V, M, ReduceT> {
358    fn from(other: SNodeTransformResult<K, V, ReduceT>) -> Self {
359        match other {
360            SNodeTransformResult::Unchanged(reduced) => MNodeTransformResult::Unchanged(reduced),
361            SNodeTransformResult::S(snode, reduced) => MNodeTransformResult::S(snode, reduced),
362            SNodeTransformResult::Removed(reduced) => MNodeTransformResult::Removed(reduced),
363        }
364    }
365}
366
367impl <K: Key, V: Value, ReduceT> From<SNodeTransformResult<K, V, ReduceT>> for LNodeTransformResult<K, V, ReduceT> {
368    fn from(other: SNodeTransformResult<K, V, ReduceT>) -> Self {
369        match other {
370            SNodeTransformResult::Unchanged(reduced) => LNodeTransformResult::Unchanged(reduced),
371            SNodeTransformResult::S(snode, reduced) => LNodeTransformResult::S(snode, reduced),
372            SNodeTransformResult::Removed(reduced) => LNodeTransformResult::Removed(reduced),
373        }
374    }
375}
376
377#[must_use]
378pub(crate) enum SNodeTransmuteResult<K: Key, V: Value, ReduceT> {
379    S(Arc<SNode<K, V>>, ReduceT),
380    Removed(ReduceT),
381}
382
383impl <H: Hashword, F: Flagword<H>, K: Key, V: Value, M: 'static, ReduceT> From<SNodeTransmuteResult<K, V, ReduceT>> for MNodeTransformResult<H, F, K, V, M, ReduceT> {
384    fn from(other: SNodeTransmuteResult<K, V, ReduceT>) -> Self {
385        match other {
386            SNodeTransmuteResult::S(snode, reduced) => MNodeTransformResult::S(snode, reduced),
387            SNodeTransmuteResult::Removed(reduced) => MNodeTransformResult::Removed(reduced),
388        }
389    }
390}
391
392impl <H: Hashword, F: Flagword<H>, K: Key, V: Value, M: 'static, ReduceT> From<SNodeTransmuteResult<K, V, ReduceT>> for MNodeTransmuteResult<H, F, K, V, M, ReduceT> {
393    fn from(other: SNodeTransmuteResult<K, V, ReduceT>) -> Self {
394        match other {
395            SNodeTransmuteResult::S(snode, reduced) => MNodeTransmuteResult::S(snode, reduced),
396            SNodeTransmuteResult::Removed(reduced) => MNodeTransmuteResult::Removed(reduced),
397        }
398    }
399}
400
401impl <K: Key, V: Value, ReduceT> From<SNodeTransmuteResult<K, V, ReduceT>> for LNodeTransmuteResult<K, V, ReduceT> {
402    fn from(other: SNodeTransmuteResult<K, V, ReduceT>) -> Self {
403        match other {
404            SNodeTransmuteResult::S(snode, reduced) => LNodeTransmuteResult::S(snode, reduced),
405            SNodeTransmuteResult::Removed(reduced) => LNodeTransmuteResult::Removed(reduced),
406        }
407    }
408}
409
410impl <K: Key, V: Value, ReduceT> From<MapTransmuteResult<K, V, ReduceT>> for SNodeTransmuteResult<K, V, ReduceT> {
411    fn from(other: MapTransmuteResult<K, V, ReduceT>) -> Self {
412        match other {
413            MapTransmuteResult::Transmuted(key, value, reduced) => SNodeTransmuteResult::S(SNode::new(key, value), reduced),
414            MapTransmuteResult::Removed(reduced) => SNodeTransmuteResult::Removed(reduced),
415        }
416    }
417}
418
419#[cfg(test)]
420macro_rules! assert_found_eq {
421    ( $found:expr, $expected:expr ) => {
422        match $found {
423            FindResult::Found(key, value) => {
424                assert_eq!(*key, $expected.0);
425                assert_eq!(*value, $expected.1);
426            },
427            FindResult::NotFound => panic!()
428        }
429    };
430}
431
432#[cfg(test)]
433macro_rules! assert_found_none {
434    ( $found:expr ) => {
435        match $found {
436            FindResult::Found(_key, _value) => panic!(),
437            FindResult::NotFound => {}
438        }
439    };
440}
hash_trie/result.rs

hash_trie/
result.rs
