nautilus_common/cache/
fifo.rs

1// -------------------------------------------------------------------------------------------------
2//  Copyright (C) 2015-2026 Nautech Systems Pty Ltd. All rights reserved.
3//  https://nautechsystems.io
4//
5//  Licensed under the GNU Lesser General Public License Version 3.0 (the "License");
6//  You may not use this file except in compliance with the License.
7//  You may obtain a copy of the License at https://www.gnu.org/licenses/lgpl-3.0.en.html
8//
9//  Unless required by applicable law or agreed to in writing, software
10//  distributed under the License is distributed on an "AS IS" BASIS,
11//  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12//  See the License for the specific language governing permissions and
13//  limitations under the License.
14// -------------------------------------------------------------------------------------------------
15
16//! Bounded FIFO caches for tracking IDs and key-value pairs with O(1) lookups.
17
18use std::{collections::VecDeque, fmt::Debug, hash::Hash};
19
20use ahash::{AHashMap, AHashSet};
21
22/// A bounded cache that maintains a set of IDs with O(1) lookups.
23///
24/// Uses a `VecDeque` for FIFO ordering and an `AHashSet` for fast membership checks.
25/// When capacity is exceeded, the oldest entry is automatically evicted.
26///
27/// # Examples
28///
29/// ```
30/// use nautilus_common::cache::fifo::FifoCache;
31///
32/// let mut cache: FifoCache<u32, 3> = FifoCache::new();
33/// cache.add(1);
34/// cache.add(2);
35/// cache.add(3);
36/// assert!(cache.contains(&1));
37///
38/// // Adding beyond capacity evicts the oldest
39/// cache.add(4);
40/// assert!(!cache.contains(&1));
41/// assert!(cache.contains(&4));
42/// ```
43///
44/// Zero capacity is a compile-time error:
45///
46/// ```compile_fail
47/// use nautilus_common::cache::fifo::FifoCache;
48///
49/// // This fails to compile: capacity must be > 0
50/// let cache: FifoCache<u32, 0> = FifoCache::new();
51/// ```
52///
53/// Default also enforces non-zero capacity:
54///
55/// ```compile_fail
56/// use nautilus_common::cache::fifo::FifoCache;
57///
58/// // This also fails to compile
59/// let cache: FifoCache<u32, 0> = FifoCache::default();
60/// ```
61#[derive(Debug)]
62pub struct FifoCache<T, const N: usize>
63where
64    T: Clone + Debug + Eq + Hash,
65{
66    order: VecDeque<T>,
67    index: AHashSet<T>,
68}
69
70impl<T, const N: usize> FifoCache<T, N>
71where
72    T: Clone + Debug + Eq + Hash,
73{
74    /// Creates a new empty [`FifoCache`] with capacity `N`.
75    ///
76    /// # Panics
77    ///
78    /// Panics if `N == 0`. The panic occurs at compile time.
79    #[must_use]
80    pub fn new() -> Self {
81        const { assert!(N > 0, "FifoCache capacity must be greater than zero") };
82
83        Self {
84            order: VecDeque::with_capacity(N),
85            index: AHashSet::with_capacity(N),
86        }
87    }
88
89    /// Returns the capacity of the cache.
90    #[must_use]
91    pub const fn capacity(&self) -> usize {
92        N
93    }
94
95    /// Returns the number of IDs in the cache.
96    #[must_use]
97    pub fn len(&self) -> usize {
98        self.index.len()
99    }
100
101    /// Returns whether the cache is empty.
102    #[must_use]
103    pub fn is_empty(&self) -> bool {
104        self.index.is_empty()
105    }
106
107    /// Returns whether the cache contains the given ID (O(1) lookup).
108    #[must_use]
109    pub fn contains(&self, id: &T) -> bool {
110        self.index.contains(id)
111    }
112
113    /// Inserts an ID into the cache.
114    ///
115    /// Returns `true` when the ID was newly inserted and `false` when it was already present.
116    /// A duplicate does not change the eviction order. If the cache is at capacity, inserting a
117    /// new ID evicts the oldest entry.
118    #[must_use]
119    pub fn insert(&mut self, id: T) -> bool {
120        if !self.index.insert(id.clone()) {
121            return false;
122        }
123
124        if self.order.len() == N
125            && let Some(evicted) = self.order.pop_back()
126        {
127            self.index.remove(&evicted);
128        }
129
130        self.order.push_front(id);
131        true
132    }
133
134    /// Adds an ID to the cache.
135    ///
136    /// If the ID already exists, this is a no-op.
137    /// If the cache is at capacity, the oldest entry is evicted.
138    pub fn add(&mut self, id: T) {
139        let _ = self.insert(id);
140    }
141
142    /// Removes an ID from the cache.
143    pub fn remove(&mut self, id: &T) {
144        if self.index.remove(id) {
145            self.order.retain(|x| x != id);
146        }
147    }
148
149    /// Clears all entries from the cache.
150    pub fn clear(&mut self) {
151        self.order.clear();
152        self.index.clear();
153    }
154}
155
156impl<T, const N: usize> Default for FifoCache<T, N>
157where
158    T: Clone + Debug + Eq + Hash,
159{
160    fn default() -> Self {
161        Self::new()
162    }
163}
164
165/// A bounded cache that maintains key-value pairs with O(1) lookups.
166///
167/// Uses a `VecDeque` for FIFO ordering and an `AHashMap` for fast key-value access.
168/// When capacity is exceeded, the oldest entry is automatically evicted.
169///
170/// # Examples
171///
172/// ```
173/// use nautilus_common::cache::fifo::FifoCacheMap;
174///
175/// let mut cache: FifoCacheMap<u32, String, 3> = FifoCacheMap::new();
176/// cache.insert(1, "one".to_string());
177/// cache.insert(2, "two".to_string());
178/// cache.insert(3, "three".to_string());
179/// assert_eq!(cache.get(&1), Some(&"one".to_string()));
180///
181/// // Adding beyond capacity evicts the oldest
182/// cache.insert(4, "four".to_string());
183/// assert_eq!(cache.get(&1), None);
184/// assert_eq!(cache.get(&4), Some(&"four".to_string()));
185/// ```
186///
187/// Zero capacity is a compile-time error:
188///
189/// ```compile_fail
190/// use nautilus_common::cache::fifo::FifoCacheMap;
191///
192/// // This fails to compile: capacity must be > 0
193/// let cache: FifoCacheMap<u32, String, 0> = FifoCacheMap::new();
194/// ```
195#[derive(Debug)]
196pub struct FifoCacheMap<K, V, const N: usize>
197where
198    K: Clone + Debug + Eq + Hash,
199{
200    order: VecDeque<K>,
201    index: AHashMap<K, V>,
202}
203
204impl<K, V, const N: usize> FifoCacheMap<K, V, N>
205where
206    K: Clone + Debug + Eq + Hash,
207{
208    /// Creates a new empty [`FifoCacheMap`] with capacity `N`.
209    ///
210    /// # Panics
211    ///
212    /// Panics if `N == 0`. The panic occurs at compile time.
213    #[must_use]
214    pub fn new() -> Self {
215        const { assert!(N > 0, "FifoCacheMap capacity must be greater than zero") };
216
217        Self {
218            order: VecDeque::with_capacity(N),
219            index: AHashMap::with_capacity(N),
220        }
221    }
222
223    /// Returns the capacity of the cache.
224    #[must_use]
225    pub const fn capacity(&self) -> usize {
226        N
227    }
228
229    /// Returns the number of entries in the cache.
230    #[must_use]
231    pub fn len(&self) -> usize {
232        self.index.len()
233    }
234
235    /// Returns whether the cache is empty.
236    #[must_use]
237    pub fn is_empty(&self) -> bool {
238        self.index.is_empty()
239    }
240
241    /// Returns whether the cache contains the given key (O(1) lookup).
242    #[must_use]
243    pub fn contains_key(&self, key: &K) -> bool {
244        self.index.contains_key(key)
245    }
246
247    /// Returns a reference to the value for the given key (O(1) lookup).
248    #[must_use]
249    pub fn get(&self, key: &K) -> Option<&V> {
250        self.index.get(key)
251    }
252
253    /// Returns a mutable reference to the value for the given key (O(1) lookup).
254    pub fn get_mut(&mut self, key: &K) -> Option<&mut V> {
255        self.index.get_mut(key)
256    }
257
258    /// Returns an iterator over the key-value pairs in arbitrary order.
259    pub fn iter(&self) -> impl Iterator<Item = (&K, &V)> {
260        self.index.iter()
261    }
262
263    /// Inserts a key-value pair into the cache.
264    ///
265    /// If the key already exists, the value is updated (no eviction occurs).
266    /// If the cache is at capacity and the key is new, the oldest entry is evicted.
267    pub fn insert(&mut self, key: K, value: V) {
268        if self.index.contains_key(&key) {
269            self.index.insert(key, value);
270            return;
271        }
272
273        if self.order.len() == N
274            && let Some(evicted) = self.order.pop_back()
275        {
276            self.index.remove(&evicted);
277        }
278
279        self.order.push_front(key.clone());
280        self.index.insert(key, value);
281    }
282
283    /// Removes a key from the cache, returning the value if present.
284    pub fn remove(&mut self, key: &K) -> Option<V> {
285        if let Some(value) = self.index.remove(key) {
286            self.order.retain(|x| x != key);
287            Some(value)
288        } else {
289            None
290        }
291    }
292
293    /// Clears all entries from the cache.
294    pub fn clear(&mut self) {
295        self.order.clear();
296        self.index.clear();
297    }
298
299    /// Removes all entries from the cache and returns them oldest first.
300    pub fn drain(&mut self) -> Vec<(K, V)> {
301        self.order
302            .drain(..)
303            .rev()
304            .filter_map(|key| self.index.remove_entry(&key))
305            .collect()
306    }
307}
308
309impl<K, V, const N: usize> Default for FifoCacheMap<K, V, N>
310where
311    K: Clone + Debug + Eq + Hash,
312{
313    fn default() -> Self {
314        Self::new()
315    }
316}
317
318#[cfg(test)]
319mod tests {
320    use rstest::rstest;
321
322    use super::*;
323
324    #[rstest]
325    fn test_add_and_contains() {
326        let mut cache: FifoCache<u32, 4> = FifoCache::new();
327        cache.add(1);
328        cache.add(2);
329        cache.add(3);
330
331        assert!(cache.contains(&1));
332        assert!(cache.contains(&2));
333        assert!(cache.contains(&3));
334        assert!(!cache.contains(&4));
335        assert_eq!(cache.len(), 3);
336    }
337
338    #[rstest]
339    fn test_insert_reports_whether_id_is_new() {
340        let mut cache: FifoCache<u32, 4> = FifoCache::new();
341
342        assert!(cache.insert(1));
343        assert!(!cache.insert(1));
344        assert!(cache.insert(2));
345        assert_eq!(cache.len(), 2);
346    }
347
348    #[rstest]
349    fn test_eviction_at_capacity() {
350        let mut cache: FifoCache<u32, 3> = FifoCache::new();
351        cache.add(1);
352        cache.add(2);
353        cache.add(3);
354        assert_eq!(cache.len(), 3);
355
356        // Adding a 4th should evict the oldest (1)
357        cache.add(4);
358        assert_eq!(cache.len(), 3);
359        assert!(!cache.contains(&1));
360        assert!(cache.contains(&2));
361        assert!(cache.contains(&3));
362        assert!(cache.contains(&4));
363    }
364
365    #[rstest]
366    fn test_duplicate_add_is_noop() {
367        let mut cache: FifoCache<u32, 3> = FifoCache::new();
368        cache.add(1);
369        cache.add(2);
370        cache.add(1); // duplicate
371
372        assert_eq!(cache.len(), 2);
373        assert!(cache.contains(&1));
374        assert!(cache.contains(&2));
375    }
376
377    #[rstest]
378    fn test_remove() {
379        let mut cache: FifoCache<u32, 4> = FifoCache::new();
380        cache.add(1);
381        cache.add(2);
382        cache.add(3);
383
384        cache.remove(&2);
385        assert_eq!(cache.len(), 2);
386        assert!(cache.contains(&1));
387        assert!(!cache.contains(&2));
388        assert!(cache.contains(&3));
389    }
390
391    #[rstest]
392    fn test_remove_nonexistent_is_noop() {
393        let mut cache: FifoCache<u32, 4> = FifoCache::new();
394        cache.add(1);
395        cache.remove(&99);
396        assert_eq!(cache.len(), 1);
397    }
398
399    #[rstest]
400    fn test_capacity() {
401        let cache: FifoCache<u32, 10> = FifoCache::new();
402        assert_eq!(cache.capacity(), 10);
403    }
404
405    #[rstest]
406    fn test_is_empty() {
407        let mut cache: FifoCache<u32, 4> = FifoCache::new();
408        assert!(cache.is_empty());
409        cache.add(1);
410        assert!(!cache.is_empty());
411    }
412
413    #[rstest]
414    fn test_capacity_one_evicts_immediately() {
415        let mut cache: FifoCache<u32, 1> = FifoCache::new();
416        cache.add(1);
417        assert!(cache.contains(&1));
418        assert_eq!(cache.len(), 1);
419
420        cache.add(2);
421        assert!(!cache.contains(&1));
422        assert!(cache.contains(&2));
423        assert_eq!(cache.len(), 1);
424    }
425
426    #[rstest]
427    fn test_sequential_eviction_order() {
428        let mut cache: FifoCache<u32, 3> = FifoCache::new();
429
430        // Fill: [3, 2, 1] (front to back)
431        cache.add(1);
432        cache.add(2);
433        cache.add(3);
434
435        // Add 4: evicts 1 -> [4, 3, 2]
436        cache.add(4);
437        assert!(!cache.contains(&1));
438        assert!(cache.contains(&2));
439
440        // Add 5: evicts 2 -> [5, 4, 3]
441        cache.add(5);
442        assert!(!cache.contains(&2));
443        assert!(cache.contains(&3));
444
445        // Add 6: evicts 3 -> [6, 5, 4]
446        cache.add(6);
447        assert!(!cache.contains(&3));
448        assert!(cache.contains(&4));
449        assert!(cache.contains(&5));
450        assert!(cache.contains(&6));
451    }
452
453    #[rstest]
454    fn test_remove_then_readd() {
455        let mut cache: FifoCache<u32, 3> = FifoCache::new();
456        cache.add(1);
457        cache.add(2);
458        cache.remove(&1);
459        assert!(!cache.contains(&1));
460        assert_eq!(cache.len(), 1);
461
462        cache.add(1);
463        assert!(cache.contains(&1));
464        assert_eq!(cache.len(), 2);
465    }
466
467    #[rstest]
468    fn test_remove_frees_slot_for_new_element() {
469        let mut cache: FifoCache<u32, 3> = FifoCache::new();
470
471        cache.add(1);
472        cache.add(2);
473        cache.add(3);
474        cache.remove(&2);
475        assert_eq!(cache.len(), 2);
476
477        // Add new element - should not evict anyone
478        cache.add(4);
479        assert_eq!(cache.len(), 3);
480        assert!(cache.contains(&1));
481        assert!(cache.contains(&3));
482        assert!(cache.contains(&4));
483    }
484
485    #[rstest]
486    fn test_duplicate_insert_does_not_refresh_position() {
487        let mut cache: FifoCache<u32, 3> = FifoCache::new();
488
489        // Add 1, 2, 3 (1 is oldest)
490        assert!(cache.insert(1));
491        assert!(cache.insert(2));
492        assert!(cache.insert(3));
493
494        // Re-add 1 (should be no-op, 1 stays oldest)
495        assert!(!cache.insert(1));
496
497        // Add 4: should evict 1 (still oldest), not 2
498        assert!(cache.insert(4));
499        assert!(!cache.contains(&1));
500        assert!(cache.contains(&2));
501        assert!(cache.contains(&3));
502        assert!(cache.contains(&4));
503    }
504
505    #[rstest]
506    fn test_interleaved_add_remove() {
507        let mut cache: FifoCache<u32, 4> = FifoCache::new();
508
509        cache.add(1);
510        cache.add(2);
511        cache.remove(&1);
512        cache.add(3);
513        cache.add(4);
514        cache.remove(&3);
515        cache.add(5);
516
517        assert!(!cache.contains(&1));
518        assert!(cache.contains(&2));
519        assert!(!cache.contains(&3));
520        assert!(cache.contains(&4));
521        assert!(cache.contains(&5));
522        assert_eq!(cache.len(), 3);
523    }
524
525    #[rstest]
526    fn test_remove_all_elements() {
527        let mut cache: FifoCache<u32, 3> = FifoCache::new();
528        cache.add(1);
529        cache.add(2);
530        cache.add(3);
531
532        cache.remove(&1);
533        cache.remove(&2);
534        cache.remove(&3);
535
536        assert!(cache.is_empty());
537        assert_eq!(cache.len(), 0);
538    }
539
540    #[rstest]
541    fn test_string_type() {
542        let mut cache: FifoCache<String, 2> = FifoCache::new();
543        cache.add("hello".to_string());
544        cache.add("world".to_string());
545
546        assert!(cache.contains(&"hello".to_string()));
547        assert!(cache.contains(&"world".to_string()));
548
549        cache.add("foo".to_string());
550        assert!(!cache.contains(&"hello".to_string()));
551    }
552
553    #[rstest]
554    fn test_map_insert_and_get() {
555        let mut cache: FifoCacheMap<u32, String, 4> = FifoCacheMap::new();
556        cache.insert(1, "one".to_string());
557        cache.insert(2, "two".to_string());
558        cache.insert(3, "three".to_string());
559
560        assert_eq!(cache.get(&1), Some(&"one".to_string()));
561        assert_eq!(cache.get(&2), Some(&"two".to_string()));
562        assert_eq!(cache.get(&3), Some(&"three".to_string()));
563        assert_eq!(cache.get(&4), None);
564        assert_eq!(cache.len(), 3);
565    }
566
567    #[rstest]
568    fn test_map_eviction_at_capacity() {
569        let mut cache: FifoCacheMap<u32, &str, 3> = FifoCacheMap::new();
570        cache.insert(1, "one");
571        cache.insert(2, "two");
572        cache.insert(3, "three");
573        assert_eq!(cache.len(), 3);
574
575        // Adding a 4th should evict the oldest (1)
576        cache.insert(4, "four");
577        assert_eq!(cache.len(), 3);
578        assert_eq!(cache.get(&1), None);
579        assert_eq!(cache.get(&2), Some(&"two"));
580        assert_eq!(cache.get(&3), Some(&"three"));
581        assert_eq!(cache.get(&4), Some(&"four"));
582    }
583
584    #[rstest]
585    fn test_map_update_existing_key() {
586        let mut cache: FifoCacheMap<u32, &str, 3> = FifoCacheMap::new();
587        cache.insert(1, "one");
588        cache.insert(2, "two");
589        cache.insert(3, "three");
590
591        // Update existing key - should not evict
592        cache.insert(1, "ONE");
593        assert_eq!(cache.len(), 3);
594        assert_eq!(cache.get(&1), Some(&"ONE"));
595        assert_eq!(cache.get(&2), Some(&"two"));
596        assert_eq!(cache.get(&3), Some(&"three"));
597    }
598
599    #[rstest]
600    fn test_map_remove() {
601        let mut cache: FifoCacheMap<u32, &str, 4> = FifoCacheMap::new();
602        cache.insert(1, "one");
603        cache.insert(2, "two");
604        cache.insert(3, "three");
605
606        let removed = cache.remove(&2);
607        assert_eq!(removed, Some("two"));
608        assert_eq!(cache.len(), 2);
609        assert!(cache.contains_key(&1));
610        assert!(!cache.contains_key(&2));
611        assert!(cache.contains_key(&3));
612    }
613
614    #[rstest]
615    fn test_map_remove_nonexistent() {
616        let mut cache: FifoCacheMap<u32, &str, 4> = FifoCacheMap::new();
617        cache.insert(1, "one");
618        let removed = cache.remove(&99);
619        assert_eq!(removed, None);
620        assert_eq!(cache.len(), 1);
621    }
622
623    #[rstest]
624    fn test_map_get_mut() {
625        let mut cache: FifoCacheMap<u32, String, 4> = FifoCacheMap::new();
626        cache.insert(1, "one".to_string());
627
628        if let Some(value) = cache.get_mut(&1) {
629            value.push_str("_modified");
630        }
631
632        assert_eq!(cache.get(&1), Some(&"one_modified".to_string()));
633    }
634
635    #[rstest]
636    fn test_map_iter() {
637        let mut cache: FifoCacheMap<u32, &str, 4> = FifoCacheMap::new();
638        cache.insert(1, "one");
639        cache.insert(2, "two");
640        cache.insert(3, "three");
641
642        let mut entries: Vec<_> = cache.iter().map(|(k, v)| (*k, *v)).collect();
643        entries.sort_unstable();
644
645        assert_eq!(entries, vec![(1, "one"), (2, "two"), (3, "three")]);
646        assert_eq!(cache.len(), 3);
647    }
648
649    #[rstest]
650    fn test_map_drain_returns_oldest_first() {
651        let mut cache: FifoCacheMap<u32, &str, 3> = FifoCacheMap::new();
652        cache.insert(1, "one");
653        cache.insert(2, "two");
654        cache.insert(3, "three");
655        cache.insert(4, "four"); // Evicts 1
656        cache.insert(3, "THREE"); // Updates in place without reordering
657
658        let drained = cache.drain();
659
660        assert_eq!(drained, vec![(2, "two"), (3, "THREE"), (4, "four")]);
661        assert!(cache.is_empty());
662
663        // A stale eviction order would evict the reinserted key before capacity
664        cache.insert(4, "four");
665        cache.insert(5, "five");
666        cache.insert(6, "six");
667        let mut entries: Vec<_> = cache.iter().map(|(k, v)| (*k, *v)).collect();
668        entries.sort_unstable();
669
670        assert_eq!(entries, vec![(4, "four"), (5, "five"), (6, "six")]);
671    }
672
673    #[rstest]
674    fn test_map_capacity() {
675        let cache: FifoCacheMap<u32, &str, 10> = FifoCacheMap::new();
676        assert_eq!(cache.capacity(), 10);
677    }
678
679    #[rstest]
680    fn test_map_is_empty() {
681        let mut cache: FifoCacheMap<u32, &str, 4> = FifoCacheMap::new();
682        assert!(cache.is_empty());
683        cache.insert(1, "one");
684        assert!(!cache.is_empty());
685    }
686
687    #[rstest]
688    fn test_map_capacity_one() {
689        let mut cache: FifoCacheMap<u32, &str, 1> = FifoCacheMap::new();
690        cache.insert(1, "one");
691        assert_eq!(cache.get(&1), Some(&"one"));
692
693        cache.insert(2, "two");
694        assert_eq!(cache.get(&1), None);
695        assert_eq!(cache.get(&2), Some(&"two"));
696        assert_eq!(cache.len(), 1);
697    }
698
699    #[rstest]
700    fn test_map_sequential_eviction() {
701        let mut cache: FifoCacheMap<u32, u32, 3> = FifoCacheMap::new();
702
703        cache.insert(1, 10);
704        cache.insert(2, 20);
705        cache.insert(3, 30);
706
707        // Add 4: evicts 1
708        cache.insert(4, 40);
709        assert!(!cache.contains_key(&1));
710        assert!(cache.contains_key(&2));
711
712        // Add 5: evicts 2
713        cache.insert(5, 50);
714        assert!(!cache.contains_key(&2));
715        assert!(cache.contains_key(&3));
716    }
717
718    #[rstest]
719    fn test_map_update_does_not_change_eviction_order() {
720        let mut cache: FifoCacheMap<u32, &str, 3> = FifoCacheMap::new();
721
722        cache.insert(1, "one");
723        cache.insert(2, "two");
724        cache.insert(3, "three");
725
726        // Update key 1 - should NOT move it to front
727        cache.insert(1, "ONE");
728
729        // Add new key - should still evict 1 (oldest by insertion order)
730        cache.insert(4, "four");
731        assert!(!cache.contains_key(&1));
732        assert!(cache.contains_key(&2));
733        assert!(cache.contains_key(&3));
734        assert!(cache.contains_key(&4));
735    }
736
737    #[rstest]
738    fn test_map_remove_frees_slot() {
739        let mut cache: FifoCacheMap<u32, &str, 3> = FifoCacheMap::new();
740
741        cache.insert(1, "one");
742        cache.insert(2, "two");
743        cache.insert(3, "three");
744
745        cache.remove(&2);
746        assert_eq!(cache.len(), 2);
747
748        // Add new element - should not evict anyone
749        cache.insert(4, "four");
750        assert_eq!(cache.len(), 3);
751        assert!(cache.contains_key(&1));
752        assert!(cache.contains_key(&3));
753        assert!(cache.contains_key(&4));
754    }
755
756    use ahash::AHashMap;
757    use proptest::prelude::*;
758
759    #[derive(Clone, Debug)]
760    enum SetOperation {
761        Add(u8),
762        Remove(u8),
763    }
764
765    fn set_operation_strategy() -> impl Strategy<Value = SetOperation> {
766        prop_oneof![
767            (0..50u8).prop_map(SetOperation::Add),
768            (0..50u8).prop_map(SetOperation::Remove),
769        ]
770    }
771
772    fn set_operations_strategy() -> impl Strategy<Value = Vec<SetOperation>> {
773        proptest::collection::vec(set_operation_strategy(), 0..100)
774    }
775
776    #[derive(Clone, Debug)]
777    enum MapOperation {
778        Insert(u8, u8),
779        Remove(u8),
780    }
781
782    fn map_operation_strategy() -> impl Strategy<Value = MapOperation> {
783        prop_oneof![
784            (0..50u8, any::<u8>()).prop_map(|(key, value)| MapOperation::Insert(key, value)),
785            (0..50u8).prop_map(MapOperation::Remove),
786        ]
787    }
788
789    fn map_operations_strategy() -> impl Strategy<Value = Vec<MapOperation>> {
790        proptest::collection::vec(map_operation_strategy(), 0..100)
791    }
792
793    proptest! {
794        #[rstest]
795        fn prop_set_operations_match_reference(operations in set_operations_strategy()) {
796            let mut cache: FifoCache<u8, 8> = FifoCache::new();
797            let mut expected_order = Vec::new();
798
799            for operation in operations {
800                match operation {
801                    SetOperation::Add(id) => {
802                        cache.add(id);
803                        if !expected_order.contains(&id) {
804                            if expected_order.len() == cache.capacity() {
805                                expected_order.pop();
806                            }
807                            expected_order.insert(0, id);
808                        }
809                    }
810                    SetOperation::Remove(id) => {
811                        cache.remove(&id);
812                        expected_order.retain(|expected| *expected != id);
813                    }
814                }
815
816                prop_assert_eq!(cache.len(), expected_order.len());
817                prop_assert_eq!(cache.is_empty(), expected_order.is_empty());
818                for id in 0..50u8 {
819                    prop_assert_eq!(cache.contains(&id), expected_order.contains(&id));
820                }
821            }
822        }
823
824        #[rstest]
825        fn prop_map_operations_match_reference(operations in map_operations_strategy()) {
826            let mut cache: FifoCacheMap<u8, u8, 4> = FifoCacheMap::new();
827            let mut expected_order = Vec::new();
828            let mut expected_values = AHashMap::new();
829
830            for operation in operations {
831                match operation {
832                    MapOperation::Insert(key, value) => {
833                        cache.insert(key, value);
834                        if expected_values.contains_key(&key) {
835                            expected_values.insert(key, value);
836                        } else {
837                            if expected_order.len() == cache.capacity() {
838                                let evicted = expected_order.pop().unwrap();
839                                expected_values.remove(&evicted);
840                            }
841                            expected_order.insert(0, key);
842                            expected_values.insert(key, value);
843                        }
844                    }
845                    MapOperation::Remove(key) => {
846                        cache.remove(&key);
847                        if expected_values.remove(&key).is_some() {
848                            expected_order.retain(|expected| *expected != key);
849                        }
850                    }
851                }
852
853                prop_assert_eq!(cache.len(), expected_values.len());
854                prop_assert_eq!(cache.is_empty(), expected_values.is_empty());
855                for key in 0..50u8 {
856                    prop_assert_eq!(cache.get(&key).copied(), expected_values.get(&key).copied());
857                }
858            }
859        }
860    }
861}
nautilus_common/cache/fifo.rs

nautilus_common/cache/
fifo.rs
