graphos_core/index/
hash.rs

1//! Hash index for primary key lookups.
2
3use graphos_common::types::NodeId;
4use graphos_common::utils::hash::FxHashMap;
5use parking_lot::RwLock;
6use std::hash::Hash;
7
8/// A concurrent hash index for fast key lookups.
9///
10/// This index provides O(1) average-case lookup, insertion, and deletion.
11pub struct HashIndex<K: Hash + Eq, V: Copy> {
12    /// The underlying hash map.
13    map: RwLock<FxHashMap<K, V>>,
14}
15
16impl<K: Hash + Eq, V: Copy> HashIndex<K, V> {
17    /// Creates a new empty hash index.
18    #[must_use]
19    pub fn new() -> Self {
20        Self {
21            map: RwLock::new(FxHashMap::default()),
22        }
23    }
24
25    /// Creates a new hash index with the given capacity.
26    #[must_use]
27    pub fn with_capacity(capacity: usize) -> Self {
28        Self {
29            map: RwLock::new(FxHashMap::with_capacity_and_hasher(
30                capacity,
31                Default::default(),
32            )),
33        }
34    }
35
36    /// Inserts a key-value pair into the index.
37    ///
38    /// Returns the previous value if the key was already present.
39    pub fn insert(&self, key: K, value: V) -> Option<V> {
40        self.map.write().insert(key, value)
41    }
42
43    /// Gets the value for a key.
44    pub fn get(&self, key: &K) -> Option<V> {
45        self.map.read().get(key).copied()
46    }
47
48    /// Removes a key from the index.
49    ///
50    /// Returns the value if the key was present.
51    pub fn remove(&self, key: &K) -> Option<V> {
52        self.map.write().remove(key)
53    }
54
55    /// Checks if a key exists in the index.
56    pub fn contains(&self, key: &K) -> bool {
57        self.map.read().contains_key(key)
58    }
59
60    /// Returns the number of entries in the index.
61    pub fn len(&self) -> usize {
62        self.map.read().len()
63    }
64
65    /// Returns true if the index is empty.
66    pub fn is_empty(&self) -> bool {
67        self.map.read().is_empty()
68    }
69
70    /// Clears all entries from the index.
71    pub fn clear(&self) {
72        self.map.write().clear();
73    }
74}
75
76impl<K: Hash + Eq, V: Copy> Default for HashIndex<K, V> {
77    fn default() -> Self {
78        Self::new()
79    }
80}
81
82/// A hash index from string keys to NodeIds.
83pub type StringKeyIndex = HashIndex<String, NodeId>;
84
85/// A hash index from NodeIds to NodeIds.
86pub type NodeIdIndex = HashIndex<NodeId, NodeId>;
87
88#[cfg(test)]
89mod tests {
90    use super::*;
91
92    #[test]
93    fn test_hash_index_basic() {
94        let index: HashIndex<u64, NodeId> = HashIndex::new();
95
96        index.insert(1, NodeId::new(100));
97        index.insert(2, NodeId::new(200));
98
99        assert_eq!(index.get(&1), Some(NodeId::new(100)));
100        assert_eq!(index.get(&2), Some(NodeId::new(200)));
101        assert_eq!(index.get(&3), None);
102    }
103
104    #[test]
105    fn test_hash_index_update() {
106        let index: HashIndex<u64, NodeId> = HashIndex::new();
107
108        index.insert(1, NodeId::new(100));
109        let old = index.insert(1, NodeId::new(200));
110
111        assert_eq!(old, Some(NodeId::new(100)));
112        assert_eq!(index.get(&1), Some(NodeId::new(200)));
113    }
114
115    #[test]
116    fn test_hash_index_remove() {
117        let index: HashIndex<u64, NodeId> = HashIndex::new();
118
119        index.insert(1, NodeId::new(100));
120        assert!(index.contains(&1));
121
122        let removed = index.remove(&1);
123        assert_eq!(removed, Some(NodeId::new(100)));
124        assert!(!index.contains(&1));
125    }
126
127    #[test]
128    fn test_hash_index_len() {
129        let index: HashIndex<u64, NodeId> = HashIndex::new();
130
131        assert!(index.is_empty());
132        assert_eq!(index.len(), 0);
133
134        index.insert(1, NodeId::new(100));
135        index.insert(2, NodeId::new(200));
136
137        assert!(!index.is_empty());
138        assert_eq!(index.len(), 2);
139    }
140
141    #[test]
142    fn test_hash_index_clear() {
143        let index: HashIndex<u64, NodeId> = HashIndex::new();
144
145        index.insert(1, NodeId::new(100));
146        index.insert(2, NodeId::new(200));
147
148        index.clear();
149
150        assert!(index.is_empty());
151        assert_eq!(index.get(&1), None);
152    }
153
154    #[test]
155    fn test_string_key_index() {
156        let index: StringKeyIndex = HashIndex::new();
157
158        index.insert("alice".to_string(), NodeId::new(1));
159        index.insert("bob".to_string(), NodeId::new(2));
160
161        assert_eq!(index.get(&"alice".to_string()), Some(NodeId::new(1)));
162        assert_eq!(index.get(&"bob".to_string()), Some(NodeId::new(2)));
163    }
164}
graphos_core/index/hash.rs

graphos_core/index/
hash.rs
