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    /// Compile-time panic if `N == 0`.
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    /// Compile-time panic if `N == 0`.
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    /// Inserts a key-value pair into the cache.
259    ///
260    /// If the key already exists, the value is updated (no eviction occurs).
261    /// If the cache is at capacity and the key is new, the oldest entry is evicted.
262    pub fn insert(&mut self, key: K, value: V) {
263        if self.index.contains_key(&key) {
264            self.index.insert(key, value);
265            return;
266        }
267
268        if self.order.len() == N
269            && let Some(evicted) = self.order.pop_back()
270        {
271            self.index.remove(&evicted);
272        }
273
274        self.order.push_front(key.clone());
275        self.index.insert(key, value);
276    }
277
278    /// Removes a key from the cache, returning the value if present.
279    pub fn remove(&mut self, key: &K) -> Option<V> {
280        if let Some(value) = self.index.remove(key) {
281            self.order.retain(|x| x != key);
282            Some(value)
283        } else {
284            None
285        }
286    }
287
288    /// Clears all entries from the cache.
289    pub fn clear(&mut self) {
290        self.order.clear();
291        self.index.clear();
292    }
293}
294
295impl<K, V, const N: usize> Default for FifoCacheMap<K, V, N>
296where
297    K: Clone + Debug + Eq + Hash,
298{
299    fn default() -> Self {
300        Self::new()
301    }
302}
303
304#[cfg(test)]
305mod tests {
306    use rstest::rstest;
307
308    use super::*;
309
310    #[rstest]
311    fn test_add_and_contains() {
312        let mut cache: FifoCache<u32, 4> = FifoCache::new();
313        cache.add(1);
314        cache.add(2);
315        cache.add(3);
316
317        assert!(cache.contains(&1));
318        assert!(cache.contains(&2));
319        assert!(cache.contains(&3));
320        assert!(!cache.contains(&4));
321        assert_eq!(cache.len(), 3);
322    }
323
324    #[rstest]
325    fn test_insert_reports_whether_id_is_new() {
326        let mut cache: FifoCache<u32, 4> = FifoCache::new();
327
328        assert!(cache.insert(1));
329        assert!(!cache.insert(1));
330        assert!(cache.insert(2));
331        assert_eq!(cache.len(), 2);
332    }
333
334    #[rstest]
335    fn test_eviction_at_capacity() {
336        let mut cache: FifoCache<u32, 3> = FifoCache::new();
337        cache.add(1);
338        cache.add(2);
339        cache.add(3);
340        assert_eq!(cache.len(), 3);
341
342        // Adding a 4th should evict the oldest (1)
343        cache.add(4);
344        assert_eq!(cache.len(), 3);
345        assert!(!cache.contains(&1));
346        assert!(cache.contains(&2));
347        assert!(cache.contains(&3));
348        assert!(cache.contains(&4));
349    }
350
351    #[rstest]
352    fn test_duplicate_add_is_noop() {
353        let mut cache: FifoCache<u32, 3> = FifoCache::new();
354        cache.add(1);
355        cache.add(2);
356        cache.add(1); // duplicate
357
358        assert_eq!(cache.len(), 2);
359        assert!(cache.contains(&1));
360        assert!(cache.contains(&2));
361    }
362
363    #[rstest]
364    fn test_remove() {
365        let mut cache: FifoCache<u32, 4> = FifoCache::new();
366        cache.add(1);
367        cache.add(2);
368        cache.add(3);
369
370        cache.remove(&2);
371        assert_eq!(cache.len(), 2);
372        assert!(cache.contains(&1));
373        assert!(!cache.contains(&2));
374        assert!(cache.contains(&3));
375    }
376
377    #[rstest]
378    fn test_remove_nonexistent_is_noop() {
379        let mut cache: FifoCache<u32, 4> = FifoCache::new();
380        cache.add(1);
381        cache.remove(&99);
382        assert_eq!(cache.len(), 1);
383    }
384
385    #[rstest]
386    fn test_capacity() {
387        let cache: FifoCache<u32, 10> = FifoCache::new();
388        assert_eq!(cache.capacity(), 10);
389    }
390
391    #[rstest]
392    fn test_is_empty() {
393        let mut cache: FifoCache<u32, 4> = FifoCache::new();
394        assert!(cache.is_empty());
395        cache.add(1);
396        assert!(!cache.is_empty());
397    }
398
399    #[rstest]
400    fn test_capacity_one_evicts_immediately() {
401        let mut cache: FifoCache<u32, 1> = FifoCache::new();
402        cache.add(1);
403        assert!(cache.contains(&1));
404        assert_eq!(cache.len(), 1);
405
406        cache.add(2);
407        assert!(!cache.contains(&1));
408        assert!(cache.contains(&2));
409        assert_eq!(cache.len(), 1);
410    }
411
412    #[rstest]
413    fn test_sequential_eviction_order() {
414        let mut cache: FifoCache<u32, 3> = FifoCache::new();
415
416        // Fill: [3, 2, 1] (front to back)
417        cache.add(1);
418        cache.add(2);
419        cache.add(3);
420
421        // Add 4: evicts 1 -> [4, 3, 2]
422        cache.add(4);
423        assert!(!cache.contains(&1));
424        assert!(cache.contains(&2));
425
426        // Add 5: evicts 2 -> [5, 4, 3]
427        cache.add(5);
428        assert!(!cache.contains(&2));
429        assert!(cache.contains(&3));
430
431        // Add 6: evicts 3 -> [6, 5, 4]
432        cache.add(6);
433        assert!(!cache.contains(&3));
434        assert!(cache.contains(&4));
435        assert!(cache.contains(&5));
436        assert!(cache.contains(&6));
437    }
438
439    #[rstest]
440    fn test_remove_then_readd() {
441        let mut cache: FifoCache<u32, 3> = FifoCache::new();
442        cache.add(1);
443        cache.add(2);
444        cache.remove(&1);
445        assert!(!cache.contains(&1));
446        assert_eq!(cache.len(), 1);
447
448        cache.add(1);
449        assert!(cache.contains(&1));
450        assert_eq!(cache.len(), 2);
451    }
452
453    #[rstest]
454    fn test_remove_frees_slot_for_new_element() {
455        let mut cache: FifoCache<u32, 3> = FifoCache::new();
456
457        cache.add(1);
458        cache.add(2);
459        cache.add(3);
460        cache.remove(&2);
461        assert_eq!(cache.len(), 2);
462
463        // Add new element - should not evict anyone
464        cache.add(4);
465        assert_eq!(cache.len(), 3);
466        assert!(cache.contains(&1));
467        assert!(cache.contains(&3));
468        assert!(cache.contains(&4));
469    }
470
471    #[rstest]
472    fn test_duplicate_insert_does_not_refresh_position() {
473        let mut cache: FifoCache<u32, 3> = FifoCache::new();
474
475        // Add 1, 2, 3 (1 is oldest)
476        assert!(cache.insert(1));
477        assert!(cache.insert(2));
478        assert!(cache.insert(3));
479
480        // Re-add 1 (should be no-op, 1 stays oldest)
481        assert!(!cache.insert(1));
482
483        // Add 4: should evict 1 (still oldest), not 2
484        assert!(cache.insert(4));
485        assert!(!cache.contains(&1));
486        assert!(cache.contains(&2));
487        assert!(cache.contains(&3));
488        assert!(cache.contains(&4));
489    }
490
491    #[rstest]
492    fn test_interleaved_add_remove() {
493        let mut cache: FifoCache<u32, 4> = FifoCache::new();
494
495        cache.add(1);
496        cache.add(2);
497        cache.remove(&1);
498        cache.add(3);
499        cache.add(4);
500        cache.remove(&3);
501        cache.add(5);
502
503        assert!(!cache.contains(&1));
504        assert!(cache.contains(&2));
505        assert!(!cache.contains(&3));
506        assert!(cache.contains(&4));
507        assert!(cache.contains(&5));
508        assert_eq!(cache.len(), 3);
509    }
510
511    #[rstest]
512    fn test_remove_all_elements() {
513        let mut cache: FifoCache<u32, 3> = FifoCache::new();
514        cache.add(1);
515        cache.add(2);
516        cache.add(3);
517
518        cache.remove(&1);
519        cache.remove(&2);
520        cache.remove(&3);
521
522        assert!(cache.is_empty());
523        assert_eq!(cache.len(), 0);
524    }
525
526    #[rstest]
527    fn test_string_type() {
528        let mut cache: FifoCache<String, 2> = FifoCache::new();
529        cache.add("hello".to_string());
530        cache.add("world".to_string());
531
532        assert!(cache.contains(&"hello".to_string()));
533        assert!(cache.contains(&"world".to_string()));
534
535        cache.add("foo".to_string());
536        assert!(!cache.contains(&"hello".to_string()));
537    }
538
539    #[rstest]
540    fn test_map_insert_and_get() {
541        let mut cache: FifoCacheMap<u32, String, 4> = FifoCacheMap::new();
542        cache.insert(1, "one".to_string());
543        cache.insert(2, "two".to_string());
544        cache.insert(3, "three".to_string());
545
546        assert_eq!(cache.get(&1), Some(&"one".to_string()));
547        assert_eq!(cache.get(&2), Some(&"two".to_string()));
548        assert_eq!(cache.get(&3), Some(&"three".to_string()));
549        assert_eq!(cache.get(&4), None);
550        assert_eq!(cache.len(), 3);
551    }
552
553    #[rstest]
554    fn test_map_eviction_at_capacity() {
555        let mut cache: FifoCacheMap<u32, &str, 3> = FifoCacheMap::new();
556        cache.insert(1, "one");
557        cache.insert(2, "two");
558        cache.insert(3, "three");
559        assert_eq!(cache.len(), 3);
560
561        // Adding a 4th should evict the oldest (1)
562        cache.insert(4, "four");
563        assert_eq!(cache.len(), 3);
564        assert_eq!(cache.get(&1), None);
565        assert_eq!(cache.get(&2), Some(&"two"));
566        assert_eq!(cache.get(&3), Some(&"three"));
567        assert_eq!(cache.get(&4), Some(&"four"));
568    }
569
570    #[rstest]
571    fn test_map_update_existing_key() {
572        let mut cache: FifoCacheMap<u32, &str, 3> = FifoCacheMap::new();
573        cache.insert(1, "one");
574        cache.insert(2, "two");
575        cache.insert(3, "three");
576
577        // Update existing key - should not evict
578        cache.insert(1, "ONE");
579        assert_eq!(cache.len(), 3);
580        assert_eq!(cache.get(&1), Some(&"ONE"));
581        assert_eq!(cache.get(&2), Some(&"two"));
582        assert_eq!(cache.get(&3), Some(&"three"));
583    }
584
585    #[rstest]
586    fn test_map_remove() {
587        let mut cache: FifoCacheMap<u32, &str, 4> = FifoCacheMap::new();
588        cache.insert(1, "one");
589        cache.insert(2, "two");
590        cache.insert(3, "three");
591
592        let removed = cache.remove(&2);
593        assert_eq!(removed, Some("two"));
594        assert_eq!(cache.len(), 2);
595        assert!(cache.contains_key(&1));
596        assert!(!cache.contains_key(&2));
597        assert!(cache.contains_key(&3));
598    }
599
600    #[rstest]
601    fn test_map_remove_nonexistent() {
602        let mut cache: FifoCacheMap<u32, &str, 4> = FifoCacheMap::new();
603        cache.insert(1, "one");
604        let removed = cache.remove(&99);
605        assert_eq!(removed, None);
606        assert_eq!(cache.len(), 1);
607    }
608
609    #[rstest]
610    fn test_map_get_mut() {
611        let mut cache: FifoCacheMap<u32, String, 4> = FifoCacheMap::new();
612        cache.insert(1, "one".to_string());
613
614        if let Some(value) = cache.get_mut(&1) {
615            value.push_str("_modified");
616        }
617
618        assert_eq!(cache.get(&1), Some(&"one_modified".to_string()));
619    }
620
621    #[rstest]
622    fn test_map_capacity() {
623        let cache: FifoCacheMap<u32, &str, 10> = FifoCacheMap::new();
624        assert_eq!(cache.capacity(), 10);
625    }
626
627    #[rstest]
628    fn test_map_is_empty() {
629        let mut cache: FifoCacheMap<u32, &str, 4> = FifoCacheMap::new();
630        assert!(cache.is_empty());
631        cache.insert(1, "one");
632        assert!(!cache.is_empty());
633    }
634
635    #[rstest]
636    fn test_map_capacity_one() {
637        let mut cache: FifoCacheMap<u32, &str, 1> = FifoCacheMap::new();
638        cache.insert(1, "one");
639        assert_eq!(cache.get(&1), Some(&"one"));
640
641        cache.insert(2, "two");
642        assert_eq!(cache.get(&1), None);
643        assert_eq!(cache.get(&2), Some(&"two"));
644        assert_eq!(cache.len(), 1);
645    }
646
647    #[rstest]
648    fn test_map_sequential_eviction() {
649        let mut cache: FifoCacheMap<u32, u32, 3> = FifoCacheMap::new();
650
651        cache.insert(1, 10);
652        cache.insert(2, 20);
653        cache.insert(3, 30);
654
655        // Add 4: evicts 1
656        cache.insert(4, 40);
657        assert!(!cache.contains_key(&1));
658        assert!(cache.contains_key(&2));
659
660        // Add 5: evicts 2
661        cache.insert(5, 50);
662        assert!(!cache.contains_key(&2));
663        assert!(cache.contains_key(&3));
664    }
665
666    #[rstest]
667    fn test_map_update_does_not_change_eviction_order() {
668        let mut cache: FifoCacheMap<u32, &str, 3> = FifoCacheMap::new();
669
670        cache.insert(1, "one");
671        cache.insert(2, "two");
672        cache.insert(3, "three");
673
674        // Update key 1 - should NOT move it to front
675        cache.insert(1, "ONE");
676
677        // Add new key - should still evict 1 (oldest by insertion order)
678        cache.insert(4, "four");
679        assert!(!cache.contains_key(&1));
680        assert!(cache.contains_key(&2));
681        assert!(cache.contains_key(&3));
682        assert!(cache.contains_key(&4));
683    }
684
685    #[rstest]
686    fn test_map_remove_frees_slot() {
687        let mut cache: FifoCacheMap<u32, &str, 3> = FifoCacheMap::new();
688
689        cache.insert(1, "one");
690        cache.insert(2, "two");
691        cache.insert(3, "three");
692
693        cache.remove(&2);
694        assert_eq!(cache.len(), 2);
695
696        // Add new element - should not evict anyone
697        cache.insert(4, "four");
698        assert_eq!(cache.len(), 3);
699        assert!(cache.contains_key(&1));
700        assert!(cache.contains_key(&3));
701        assert!(cache.contains_key(&4));
702    }
703
704    use ahash::AHashMap;
705    use proptest::prelude::*;
706
707    #[derive(Clone, Debug)]
708    enum SetOperation {
709        Add(u8),
710        Remove(u8),
711    }
712
713    fn set_operation_strategy() -> impl Strategy<Value = SetOperation> {
714        prop_oneof![
715            (0..50u8).prop_map(SetOperation::Add),
716            (0..50u8).prop_map(SetOperation::Remove),
717        ]
718    }
719
720    fn set_operations_strategy() -> impl Strategy<Value = Vec<SetOperation>> {
721        proptest::collection::vec(set_operation_strategy(), 0..100)
722    }
723
724    #[derive(Clone, Debug)]
725    enum MapOperation {
726        Insert(u8, u8),
727        Remove(u8),
728    }
729
730    fn map_operation_strategy() -> impl Strategy<Value = MapOperation> {
731        prop_oneof![
732            (0..50u8, any::<u8>()).prop_map(|(key, value)| MapOperation::Insert(key, value)),
733            (0..50u8).prop_map(MapOperation::Remove),
734        ]
735    }
736
737    fn map_operations_strategy() -> impl Strategy<Value = Vec<MapOperation>> {
738        proptest::collection::vec(map_operation_strategy(), 0..100)
739    }
740
741    proptest! {
742        #[rstest]
743        fn prop_set_operations_match_reference(operations in set_operations_strategy()) {
744            let mut cache: FifoCache<u8, 8> = FifoCache::new();
745            let mut expected_order = Vec::new();
746
747            for operation in operations {
748                match operation {
749                    SetOperation::Add(id) => {
750                        cache.add(id);
751                        if !expected_order.contains(&id) {
752                            if expected_order.len() == cache.capacity() {
753                                expected_order.pop();
754                            }
755                            expected_order.insert(0, id);
756                        }
757                    }
758                    SetOperation::Remove(id) => {
759                        cache.remove(&id);
760                        expected_order.retain(|expected| *expected != id);
761                    }
762                }
763
764                prop_assert_eq!(cache.len(), expected_order.len());
765                prop_assert_eq!(cache.is_empty(), expected_order.is_empty());
766                for id in 0..50u8 {
767                    prop_assert_eq!(cache.contains(&id), expected_order.contains(&id));
768                }
769            }
770        }
771
772        #[rstest]
773        fn prop_map_operations_match_reference(operations in map_operations_strategy()) {
774            let mut cache: FifoCacheMap<u8, u8, 4> = FifoCacheMap::new();
775            let mut expected_order = Vec::new();
776            let mut expected_values = AHashMap::new();
777
778            for operation in operations {
779                match operation {
780                    MapOperation::Insert(key, value) => {
781                        cache.insert(key, value);
782                        if expected_values.contains_key(&key) {
783                            expected_values.insert(key, value);
784                        } else {
785                            if expected_order.len() == cache.capacity() {
786                                let evicted = expected_order.pop().unwrap();
787                                expected_values.remove(&evicted);
788                            }
789                            expected_order.insert(0, key);
790                            expected_values.insert(key, value);
791                        }
792                    }
793                    MapOperation::Remove(key) => {
794                        cache.remove(&key);
795                        if expected_values.remove(&key).is_some() {
796                            expected_order.retain(|expected| *expected != key);
797                        }
798                    }
799                }
800
801                prop_assert_eq!(cache.len(), expected_values.len());
802                prop_assert_eq!(cache.is_empty(), expected_values.is_empty());
803                for key in 0..50u8 {
804                    prop_assert_eq!(cache.get(&key).copied(), expected_values.get(&key).copied());
805                }
806            }
807        }
808    }
809}
nautilus_common/cache/fifo.rs

nautilus_common/cache/
fifo.rs
