gbp_core/
bounded.rs

1//! LRU-bounded set for per-epoch deduplication.
2//!
3//! Each sub-protocol client (GTP, GSP, GAP) maintains a deduplication set
4//! that MUST NOT grow unboundedly within a single epoch. This type provides
5//! a `HashSet` with insertion-order eviction: when capacity is exceeded the
6//! oldest entry is dropped.
7
8use std::collections::{HashSet, VecDeque};
9use std::hash::Hash;
10
11/// A set with a bounded capacity that evicts the oldest entry on overflow.
12///
13/// Insertion (`insert`) returns `true` when the item is new and was added,
14/// `false` when it was already present. When `len() == cap`, the least
15/// recently inserted item is removed before the new item is added.
16#[derive(Clone, Debug)]
17pub struct BoundedSeen<T> {
18    set: HashSet<T>,
19    order: VecDeque<T>,
20    cap: usize,
21}
22
23impl<T: Eq + Hash + Clone> BoundedSeen<T> {
24    /// Creates a new set with the given capacity limit.
25    ///
26    /// N=10000 is the recommended default per epoch (GTP §5, GSP §5).
27    pub fn new(cap: usize) -> Self {
28        Self { set: HashSet::with_capacity(cap.min(1024)), order: VecDeque::with_capacity(cap.min(1024)), cap }
29    }
30
31    /// Inserts an item. Returns `true` if the item is new and was added,
32    /// `false` if it was already present.
33    ///
34    /// When the set is at capacity, the oldest entry is evicted.
35    pub fn insert(&mut self, item: T) -> bool {
36        if !self.set.insert(item.clone()) {
37            return false;
38        }
39        self.order.push_back(item);
40        if self.order.len() > self.cap {
41            if let Some(old) = self.order.pop_front() {
42                self.set.remove(&old);
43            }
44        }
45        true
46    }
47
48    /// Returns the number of entries currently in the set.
49    pub fn len(&self) -> usize {
50        self.set.len()
51    }
52
53    /// Returns `true` if the set is empty.
54    pub fn is_empty(&self) -> bool {
55        self.set.is_empty()
56    }
57
58    /// Clears the set.
59    pub fn clear(&mut self) {
60        self.set.clear();
61        self.order.clear();
62    }
63}
64
65#[cfg(test)]
66mod tests {
67    use super::*;
68
69    #[test]
70    fn insert_new_returns_true() {
71        let mut s = BoundedSeen::new(10);
72        assert!(s.insert(1));
73    }
74
75    #[test]
76    fn insert_duplicate_returns_false() {
77        let mut s = BoundedSeen::new(10);
78        s.insert(1);
79        assert!(!s.insert(1));
80    }
81
82    #[test]
83    fn evicts_oldest_on_overflow() {
84        let mut s = BoundedSeen::new(3);
85        s.insert(1);
86        s.insert(2);
87        s.insert(3);
88        // At capacity; next insert evicts 1 (oldest).
89        s.insert(4);
90        // 1 was evicted, fresh again — but this evicts 2.
91        assert!(s.insert(1));
92        // 4 was second-newest, still present.
93        assert!(!s.insert(4));
94        assert_eq!(s.len(), 3);
95    }
96
97    #[test]
98    fn clear_resets() {
99        let mut s = BoundedSeen::new(100);
100        s.insert("a");
101        s.clear();
102        assert!(s.is_empty());
103        assert!(s.insert("a")); // fresh after clear
104    }
105}
gbp_core/bounded.rs

gbp_core/
bounded.rs
