composable_indexes/index/
hashtable.rs

1//! An index backed by [`std::collections::HashMap`]. Provides efficient
2//! lookups by key with O(1) average time complexity.
3
4use alloc::vec::Vec;
5use core::hash::Hash;
6use hashbrown::HashMap;
7
8use crate::core::{DefaultHasher, Index, Insert, Key, Remove, Seal};
9use crate::index::generic::{DefaultKeySet, KeySet};
10
11/// An index for equivalence lookups backed by a hash table.
12#[derive(Clone)]
13pub struct HashTable<T, S = DefaultHasher, KeySet = DefaultKeySet> {
14    data: HashMap<T, KeySet, S>,
15}
16
17impl<T, S, KeySet_> Default for HashTable<T, S, KeySet_>
18where
19    T: Eq + Hash,
20    S: core::hash::BuildHasher + Default,
21    KeySet_: KeySet,
22{
23    fn default() -> Self {
24        HashTable {
25            data: HashMap::with_hasher(S::default()),
26        }
27    }
28}
29
30impl<T, S, KeySet_> HashTable<T, S, KeySet_>
31where
32    T: Eq + Hash,
33    S: core::hash::BuildHasher + Default,
34    KeySet_: KeySet,
35{
36    pub fn new() -> Self {
37        Self::default()
38    }
39
40    pub fn with_hasher(hasher: S) -> Self {
41        HashTable {
42            data: HashMap::with_hasher(hasher),
43        }
44    }
45}
46
47impl<In, S, KeySet_> Index<In> for HashTable<In, S, KeySet_>
48where
49    In: Eq + Hash + Clone,
50    S: core::hash::BuildHasher,
51    KeySet_: KeySet,
52{
53    #[inline]
54    fn insert(&mut self, _seal: Seal, op: &Insert<In>) {
55        self.data
56            .raw_entry_mut()
57            .from_key(op.new)
58            .or_insert_with(|| (op.new.clone(), KeySet_::default()))
59            .1
60            .insert(op.key);
61    }
62
63    #[inline]
64    fn remove(&mut self, _seal: Seal, op: &Remove<In>) {
65        let existing = self.data.get_mut(op.existing).unwrap();
66        existing.remove(&op.key);
67        if existing.is_empty() {
68            self.data.remove(op.existing);
69        }
70    }
71}
72
73impl<In, S, KeySet_> HashTable<In, S, KeySet_>
74where
75    S: core::hash::BuildHasher,
76    KeySet_: KeySet,
77{
78    #[inline]
79    pub fn contains(&self, key: &In) -> bool
80    where
81        In: Eq + Hash,
82    {
83        self.data.contains_key(key)
84    }
85
86    #[inline]
87    pub fn count_distinct(&self) -> usize
88    where
89        In: Eq + Hash,
90    {
91        self.data.len()
92    }
93
94    #[inline]
95    pub fn get_one(&self, key: &In) -> Option<Key>
96    where
97        In: Eq + Hash,
98    {
99        self.data.get(key).and_then(|v| v.iter().next())
100    }
101
102    #[inline]
103    pub fn get_all(&self, key: &In) -> Vec<Key>
104    where
105        In: Eq + Hash,
106    {
107        self.data
108            .get(key)
109            .map(|v| v.iter().collect())
110            .unwrap_or_default()
111    }
112
113    pub fn all(&self) -> hashbrown::HashSet<Key> {
114        self.data.values().flat_map(|keys| keys.iter()).collect()
115    }
116}
117
118#[cfg(test)]
119mod tests {
120    use std::collections::HashSet;
121
122    use crate::testutils::prop_assert_reference;
123
124    use super::*;
125
126    #[test]
127    fn test_lookup() {
128        prop_assert_reference(
129            HashTable::<u8>::new,
130            |db| db.query(|ix| ix.contains(&1)),
131            |xs| xs.contains(&1),
132            None,
133        );
134    }
135
136    #[test]
137    fn test_count_distinct() {
138        prop_assert_reference(
139            HashTable::<u8>::new,
140            |db| db.query(|ix| ix.count_distinct()),
141            |xs| xs.iter().cloned().collect::<HashSet<u8>>().len(),
142            None,
143        );
144    }
145}
composable_indexes/index/hashtable.rs

composable_indexes/index/
hashtable.rs
