uqa_core/memory/
hash_set.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! Insert-only membership sets retain the complete bucket allocation under one allowance.
8
9use std::{
10    collections::hash_map::RandomState,
11    hash::{BuildHasher, Hash},
12};
13
14use super::{BudgetedVec, MemoryBudget, MemoryError};
15
16#[derive(Debug)]
17struct Entry<T> {
18    hash: u64,
19    value: T,
20}
21
22/// A linear-probing set with reserved bucket layouts, including hashes, occupancy and alignment. Element-owned allocations remain the caller's responsibility. Growth retains both bucket buffers until every entry has moved; it never rehashes user values while publishing the replacement.
23#[derive(Debug)]
24pub struct BudgetedHashSet<T> {
25    buckets: BudgetedVec<Option<Entry<T>>>,
26    hasher: RandomState,
27    len: usize,
28}
29
30impl<T> BudgetedHashSet<T> {
31    pub fn new(budget: &MemoryBudget) -> Self {
32        Self {
33            buckets: BudgetedVec::new(budget),
34            hasher: RandomState::new(),
35            len: 0,
36        }
37    }
38
39    pub fn len(&self) -> usize {
40        self.len
41    }
42
43    pub fn is_empty(&self) -> bool {
44        self.len == 0
45    }
46
47    pub fn reserve(&mut self, additional: usize) -> Result<(), MemoryError> {
48        let required = self
49            .len
50            .checked_add(additional)
51            .ok_or(MemoryError::SizeOverflow)?;
52        // Keep at least half the buckets empty to limit clustering with linear probing.
53        if required <= self.buckets.len() / 2 {
54            return Ok(());
55        }
56        let capacity = required
57            .checked_mul(2)
58            .and_then(usize::checked_next_power_of_two)
59            .ok_or(MemoryError::SizeOverflow)?;
60        let mut replacement = BudgetedVec::new(self.buckets.budget());
61        replacement.reserve(capacity)?;
62        for _ in 0..capacity {
63            replacement.push(None)?;
64        }
65        // Everything fallible, including allocation, finishes before the first move. Cached hashes avoid invoking application code during replacement.
66        for bucket in self.buckets.iter_mut() {
67            if let Some(entry) = bucket.take() {
68                insert_vacant(&mut replacement, entry);
69            }
70        }
71        self.buckets = replacement;
72        Ok(())
73    }
74}
75
76impl<T: Eq + Hash> BudgetedHashSet<T> {
77    pub fn contains(&self, value: &T) -> bool {
78        self.contains_hashed(self.hasher.hash_one(value), value)
79    }
80
81    pub fn insert(&mut self, value: T) -> Result<bool, MemoryError> {
82        let hash = self.hasher.hash_one(&value);
83        if self.contains_hashed(hash, &value) {
84            return Ok(false);
85        }
86        self.reserve(1)?;
87        insert_vacant(&mut self.buckets, Entry { hash, value });
88        self.len += 1;
89        Ok(true)
90    }
91
92    fn contains_hashed(&self, hash: u64, value: &T) -> bool {
93        if self.buckets.is_empty() {
94            return false;
95        }
96        let mask = self.buckets.len() - 1;
97        let mut position = hash as usize & mask;
98        while let Some(entry) = &self.buckets[position] {
99            if entry.hash == hash && entry.value == *value {
100                return true;
101            }
102            position = (position + 1) & mask;
103        }
104        false
105    }
106}
107
108fn insert_vacant<T>(buckets: &mut [Option<Entry<T>>], entry: Entry<T>) {
109    let mask = buckets.len() - 1;
110    let mut position = entry.hash as usize & mask;
111    while buckets[position].is_some() {
112        position = (position + 1) & mask;
113    }
114    buckets[position] = Some(entry);
115}
116
117#[cfg(test)]
118mod tests;
uqa_core/memory/hash_set.rs

uqa_core/memory/
hash_set.rs
