grafeo_common/types/
property_map.rs

1//! Compact property storage for nodes and edges.
2//!
3//! [`PropertyMap`] replaces `BTreeMap<PropertyKey, Value>` on user-facing
4//! [`Node`](crate::graph::lpg::Node) and [`Edge`](crate::graph::lpg::Edge)
5//! types.  For the typical case of 1–4 properties the data lives entirely
6//! inline (no heap allocation), and lookups use a fast linear scan instead
7//! of tree traversal.
8
9use std::collections::BTreeMap;
10use std::fmt;
11
12use smallvec::SmallVec;
13
14use super::value::{PropertyKey, Value};
15
16/// Inline capacity — entries stored on the stack without allocation.
17///
18/// Covers the common case of 1–4 properties per entity.  Beyond this the
19/// backing `SmallVec` spills to the heap but remains a flat array, so
20/// iteration is still cache-friendly.
21const INLINE_CAP: usize = 4;
22
23/// A compact, ordered property map.
24///
25/// Behaves like a `BTreeMap<PropertyKey, Value>` but stores small maps
26/// inline (up to 4 entries) and uses linear scan for lookups.  For the
27/// sizes typical in graph workloads this is both faster and more
28/// memory-efficient than a tree.
29#[derive(Clone, PartialEq)]
30pub struct PropertyMap {
31    entries: SmallVec<[(PropertyKey, Value); INLINE_CAP]>,
32}
33
34impl PropertyMap {
35    /// Creates an empty property map.
36    #[inline]
37    #[must_use]
38    pub fn new() -> Self {
39        Self {
40            entries: SmallVec::new(),
41        }
42    }
43
44    /// Creates a property map with pre-allocated capacity.
45    #[inline]
46    #[must_use]
47    pub fn with_capacity(cap: usize) -> Self {
48        Self {
49            entries: SmallVec::with_capacity(cap),
50        }
51    }
52
53    /// Returns the number of properties.
54    #[inline]
55    #[must_use]
56    pub fn len(&self) -> usize {
57        self.entries.len()
58    }
59
60    /// Returns `true` if the map contains no properties.
61    #[inline]
62    #[must_use]
63    pub fn is_empty(&self) -> bool {
64        self.entries.is_empty()
65    }
66
67    /// Looks up a property by key.
68    #[must_use]
69    pub fn get(&self, key: &PropertyKey) -> Option<&Value> {
70        self.entries.iter().find(|(k, _)| k == key).map(|(_, v)| v)
71    }
72
73    /// Returns `true` if the map contains the given key.
74    #[must_use]
75    pub fn contains_key(&self, key: &PropertyKey) -> bool {
76        self.entries.iter().any(|(k, _)| k == key)
77    }
78
79    /// Inserts a property, replacing any existing value for the same key.
80    ///
81    /// Returns the previous value if the key was already present.
82    pub fn insert(&mut self, key: PropertyKey, value: Value) -> Option<Value> {
83        for entry in &mut self.entries {
84            if entry.0 == key {
85                let old = std::mem::replace(&mut entry.1, value);
86                return Some(old);
87            }
88        }
89        self.entries.push((key, value));
90        None
91    }
92
93    /// Removes a property by key, returning its value if present.
94    pub fn remove(&mut self, key: &PropertyKey) -> Option<Value> {
95        if let Some(pos) = self.entries.iter().position(|(k, _)| k == key) {
96            Some(self.entries.swap_remove(pos).1)
97        } else {
98            None
99        }
100    }
101
102    /// Iterates over `(key, value)` pairs.
103    pub fn iter(&self) -> impl Iterator<Item = (&PropertyKey, &Value)> {
104        self.entries.iter().map(|(k, v)| (k, v))
105    }
106
107    /// Converts to a `BTreeMap` (e.g. for serialization into `Value::Map`).
108    #[must_use]
109    pub fn to_btree_map(&self) -> BTreeMap<PropertyKey, Value> {
110        self.entries.iter().cloned().collect()
111    }
112}
113
114impl Default for PropertyMap {
115    #[inline]
116    fn default() -> Self {
117        Self::new()
118    }
119}
120
121impl fmt::Debug for PropertyMap {
122    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
123        f.debug_map()
124            .entries(self.entries.iter().map(|(k, v)| (k, v)))
125            .finish()
126    }
127}
128
129impl FromIterator<(PropertyKey, Value)> for PropertyMap {
130    fn from_iter<I: IntoIterator<Item = (PropertyKey, Value)>>(iter: I) -> Self {
131        let iter = iter.into_iter();
132        let (lower, _) = iter.size_hint();
133        let mut map = Self::with_capacity(lower);
134        for (k, v) in iter {
135            map.insert(k, v);
136        }
137        map
138    }
139}
140
141impl IntoIterator for PropertyMap {
142    type Item = (PropertyKey, Value);
143    type IntoIter = smallvec::IntoIter<[(PropertyKey, Value); INLINE_CAP]>;
144
145    fn into_iter(self) -> Self::IntoIter {
146        self.entries.into_iter()
147    }
148}
149
150impl<'a> IntoIterator for &'a PropertyMap {
151    type Item = (&'a PropertyKey, &'a Value);
152    type IntoIter = std::iter::Map<
153        std::slice::Iter<'a, (PropertyKey, Value)>,
154        fn(&'a (PropertyKey, Value)) -> (&'a PropertyKey, &'a Value),
155    >;
156
157    fn into_iter(self) -> Self::IntoIter {
158        self.entries.iter().map(|(k, v)| (k, v))
159    }
160}
161
162#[cfg(test)]
163mod tests {
164    use super::*;
165
166    #[test]
167    fn insert_and_get() {
168        let mut map = PropertyMap::new();
169        map.insert(PropertyKey::new("name"), Value::from("Alice"));
170        map.insert(PropertyKey::new("age"), Value::from(30i64));
171
172        assert_eq!(map.len(), 2);
173        assert_eq!(
174            map.get(&PropertyKey::new("name")).and_then(Value::as_str),
175            Some("Alice")
176        );
177        assert_eq!(
178            map.get(&PropertyKey::new("age")).and_then(Value::as_int64),
179            Some(30)
180        );
181    }
182
183    #[test]
184    fn insert_replaces_existing() {
185        let mut map = PropertyMap::new();
186        map.insert(PropertyKey::new("x"), Value::from(1i64));
187        let old = map.insert(PropertyKey::new("x"), Value::from(2i64));
188        assert_eq!(old, Some(Value::from(1i64)));
189        assert_eq!(map.len(), 1);
190        assert_eq!(
191            map.get(&PropertyKey::new("x")).and_then(Value::as_int64),
192            Some(2)
193        );
194    }
195
196    #[test]
197    fn remove() {
198        let mut map = PropertyMap::new();
199        map.insert(PropertyKey::new("a"), Value::from(1i64));
200        map.insert(PropertyKey::new("b"), Value::from(2i64));
201
202        let removed = map.remove(&PropertyKey::new("a"));
203        assert_eq!(removed, Some(Value::from(1i64)));
204        assert_eq!(map.len(), 1);
205        assert!(map.get(&PropertyKey::new("a")).is_none());
206        assert!(map.get(&PropertyKey::new("b")).is_some());
207    }
208
209    #[test]
210    fn contains_key() {
211        let mut map = PropertyMap::new();
212        map.insert(PropertyKey::new("x"), Value::Null);
213        assert!(map.contains_key(&PropertyKey::new("x")));
214        assert!(!map.contains_key(&PropertyKey::new("y")));
215    }
216
217    #[test]
218    fn from_iterator() {
219        let pairs = vec![
220            (PropertyKey::new("a"), Value::from(1i64)),
221            (PropertyKey::new("b"), Value::from(2i64)),
222        ];
223        let map: PropertyMap = pairs.into_iter().collect();
224        assert_eq!(map.len(), 2);
225    }
226
227    #[test]
228    fn into_iterator() {
229        let mut map = PropertyMap::new();
230        map.insert(PropertyKey::new("x"), Value::from(1i64));
231        map.insert(PropertyKey::new("y"), Value::from(2i64));
232
233        let pairs: Vec<_> = map.into_iter().collect();
234        assert_eq!(pairs.len(), 2);
235    }
236
237    #[test]
238    fn empty() {
239        let map = PropertyMap::new();
240        assert!(map.is_empty());
241        assert_eq!(map.len(), 0);
242        assert!(map.get(&PropertyKey::new("x")).is_none());
243    }
244
245    #[test]
246    fn inline_capacity() {
247        // 4 entries should stay inline (no heap allocation)
248        let mut map = PropertyMap::new();
249        for i in 0..4 {
250            map.insert(PropertyKey::new(format!("k{i}")), Value::from(i as i64));
251        }
252        assert_eq!(map.len(), 4);
253        assert!(!map.entries.spilled());
254    }
255
256    #[test]
257    fn spills_to_heap_beyond_capacity() {
258        let mut map = PropertyMap::new();
259        for i in 0..10 {
260            map.insert(PropertyKey::new(format!("k{i}")), Value::from(i as i64));
261        }
262        assert_eq!(map.len(), 10);
263        assert!(map.entries.spilled());
264        // All entries still accessible
265        for i in 0..10 {
266            assert!(map.contains_key(&PropertyKey::new(format!("k{i}"))));
267        }
268    }
269
270    #[test]
271    fn debug_format() {
272        let mut map = PropertyMap::new();
273        map.insert(PropertyKey::new("name"), Value::from("Alice"));
274        let dbg = format!("{map:?}");
275        assert!(dbg.contains("name"));
276    }
277
278    #[test]
279    fn from_empty_iterator() {
280        let map: PropertyMap = std::iter::empty().collect();
281        assert!(map.is_empty());
282    }
283
284    #[test]
285    fn ref_iterator() {
286        let mut map = PropertyMap::new();
287        map.insert(PropertyKey::new("a"), Value::from(1i64));
288        map.insert(PropertyKey::new("b"), Value::from(2i64));
289        let pairs: Vec<_> = (&map).into_iter().collect();
290        assert_eq!(pairs.len(), 2);
291    }
292
293    #[test]
294    fn default_is_empty() {
295        let map = PropertyMap::default();
296        assert!(map.is_empty());
297    }
298
299    #[test]
300    fn remove_nonexistent() {
301        let mut map = PropertyMap::new();
302        assert_eq!(map.remove(&PropertyKey::new("missing")), None);
303    }
304
305    #[test]
306    fn to_btree_map_round_trip() {
307        let mut map = PropertyMap::new();
308        map.insert(PropertyKey::new("x"), Value::from(1i64));
309        map.insert(PropertyKey::new("y"), Value::from(2i64));
310        let btree = map.to_btree_map();
311        assert_eq!(btree.len(), 2);
312        assert_eq!(btree[&PropertyKey::new("x")], Value::from(1i64));
313    }
314}
grafeo_common/types/property_map.rs

grafeo_common/types/
property_map.rs
