toasty_core/stmt/
hash_index.rs

1use super::value_set::{HashableValue, HashableValueSlice};
2use super::{Entry, Projection, Value};
3
4use hashbrown::HashMap;
5
6/// A unique hash index over a borrowed slice of [`Value`]s.
7///
8/// Keys are extracted from each value using a set of [`Projection`]s. The key is
9/// the composite of the projected field values. Only equality lookup is supported.
10///
11/// Both construction and lookup are O(1) amortized (hash map operations).
12///
13/// # Uniqueness
14///
15/// The index requires each extracted key to be unique across the source slice.
16/// An `assert!` fires on duplicate keys at build time so release builds surface
17/// the invariant violation rather than silently stomping existing entries.
18///
19/// # Cloning
20///
21/// Key fields are cloned into owned [`Value`]s for use as map keys. Full records
22/// are never cloned -- the map values are `&'a Value` references into the source slice.
23///
24/// # Examples
25///
26/// ```
27/// use toasty_core::stmt::{HashIndex, Projection, Value, ValueRecord};
28///
29/// let records = vec![
30///     Value::record_from_vec(vec![Value::from(1_i64), Value::from("a")]),
31///     Value::record_from_vec(vec![Value::from(2_i64), Value::from("b")]),
32/// ];
33/// let index = HashIndex::new(&records, &[Projection::single(0)]);
34/// let found = index.find(&[Value::from(2_i64)]);
35/// assert!(found.is_some());
36/// ```
37pub struct HashIndex<'a> {
38    map: HashMap<Vec<HashableValue>, &'a Value>,
39}
40
41impl<'a> HashIndex<'a> {
42    /// Build an index over `values`, keyed by the fields selected by `projections`.
43    ///
44    /// Each projection navigates into a value to extract one key component. Multiple
45    /// projections produce a composite key compared lexicographically.
46    pub fn new(values: &'a [Value], projections: &[Projection]) -> Self {
47        let mut map = HashMap::with_capacity(values.len());
48
49        for value in values {
50            let key = extract_key(value, projections);
51            let prev = map.insert(key, value);
52            assert!(prev.is_none(), "HashIndex: duplicate key detected");
53        }
54
55        Self { map }
56    }
57
58    /// Look up the value whose key equals `key`.
59    ///
60    /// `key` must be a slice of values with one entry per projection used at build time.
61    /// Returns `None` if no value matches.
62    pub fn find(&self, key: &[Value]) -> Option<&'a Value> {
63        self.map.get(&HashableValueSlice(key)).copied()
64    }
65}
66
67/// Extract the composite key from `value` using `projections`.
68///
69/// Each projection is applied to `value` in sequence, collecting the resulting
70/// field references into an owned `Vec<HashableValue>`.
71fn extract_key(value: &Value, projections: &[Projection]) -> Vec<HashableValue> {
72    projections
73        .iter()
74        .map(|proj| match value.entry(proj) {
75            Entry::Value(v) => HashableValue(v.clone()),
76            Entry::Expr(_) => panic!("projection yielded an expression, not a value"),
77        })
78        .collect()
79}
toasty_core/stmt/hash_index.rs

toasty_core/stmt/
hash_index.rs
