toasty_core/stmt/
hash_index.rs

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

toasty_core/stmt/
hash_index.rs
