timed_map/
map.rs

1use super::*;
2
3macro_rules! cfg_std_feature {
4    ($($item:item)*) => {
5        $(
6            #[cfg(feature = "std")]
7            $item
8        )*
9    };
10}
11
12macro_rules! cfg_not_std_feature {
13    ($($item:item)*) => {
14        $(
15            #[cfg(not(feature = "std"))]
16            $item
17        )*
18    };
19}
20
21cfg_not_std_feature! {
22    /// Generic trait for `no_std` keys that is gated by the `std` feature
23    /// and handled at compile time.
24    pub trait GenericKey: Clone + Eq + Ord {}
25    impl<T: Clone + Eq + Ord> GenericKey for T {}
26}
27
28cfg_std_feature! {
29    /// Generic trait for `std` keys that is gated by the `std` feature
30    /// and handled at compile time.
31    pub trait GenericKey: Clone + Eq + Ord + Hash {}
32    impl<T: Clone + Eq + Ord + Hash> GenericKey for T {}
33}
34
35/// Wraps different map implementations and provides a single interface to access them.
36#[allow(clippy::enum_variant_names)]
37#[derive(Debug)]
38enum GenericMap<K, V> {
39    BTreeMap(BTreeMap<K, V>),
40    #[cfg(feature = "std")]
41    HashMap(HashMap<K, V>),
42    #[cfg(all(feature = "std", feature = "rustc-hash"))]
43    FxHashMap(FxHashMap<K, V>),
44}
45
46impl<K, V> Default for GenericMap<K, V> {
47    fn default() -> Self {
48        Self::BTreeMap(BTreeMap::default())
49    }
50}
51
52impl<K, V> GenericMap<K, V>
53where
54    K: GenericKey,
55{
56    #[inline(always)]
57    fn get(&self, k: &K) -> Option<&V> {
58        match self {
59            Self::BTreeMap(inner) => inner.get(k),
60            #[cfg(feature = "std")]
61            Self::HashMap(inner) => inner.get(k),
62            #[cfg(all(feature = "std", feature = "rustc-hash"))]
63            Self::FxHashMap(inner) => inner.get(k),
64        }
65    }
66
67    #[inline(always)]
68    fn get_mut(&mut self, k: &K) -> Option<&mut V> {
69        match self {
70            Self::BTreeMap(inner) => inner.get_mut(k),
71            #[cfg(feature = "std")]
72            Self::HashMap(inner) => inner.get_mut(k),
73            #[cfg(all(feature = "std", feature = "rustc-hash"))]
74            Self::FxHashMap(inner) => inner.get_mut(k),
75        }
76    }
77
78    #[inline(always)]
79    fn len(&self) -> usize {
80        match self {
81            Self::BTreeMap(inner) => inner.len(),
82            #[cfg(feature = "std")]
83            Self::HashMap(inner) => inner.len(),
84            #[cfg(all(feature = "std", feature = "rustc-hash"))]
85            Self::FxHashMap(inner) => inner.len(),
86        }
87    }
88
89    #[inline(always)]
90    fn keys(&self) -> Vec<K> {
91        match self {
92            Self::BTreeMap(inner) => inner.keys().cloned().collect(),
93            #[cfg(feature = "std")]
94            Self::HashMap(inner) => inner.keys().cloned().collect(),
95            #[cfg(all(feature = "std", feature = "rustc-hash"))]
96            Self::FxHashMap(inner) => inner.keys().cloned().collect(),
97        }
98    }
99
100    #[inline(always)]
101    fn is_empty(&self) -> bool {
102        match self {
103            Self::BTreeMap(inner) => inner.is_empty(),
104            #[cfg(feature = "std")]
105            Self::HashMap(inner) => inner.is_empty(),
106            #[cfg(all(feature = "std", feature = "rustc-hash"))]
107            Self::FxHashMap(inner) => inner.is_empty(),
108        }
109    }
110
111    #[inline(always)]
112    fn insert(&mut self, k: K, v: V) -> Option<V> {
113        match self {
114            Self::BTreeMap(inner) => inner.insert(k, v),
115            #[cfg(feature = "std")]
116            Self::HashMap(inner) => inner.insert(k, v),
117            #[cfg(all(feature = "std", feature = "rustc-hash"))]
118            Self::FxHashMap(inner) => inner.insert(k, v),
119        }
120    }
121
122    #[inline(always)]
123    fn clear(&mut self) {
124        match self {
125            Self::BTreeMap(inner) => inner.clear(),
126            #[cfg(feature = "std")]
127            Self::HashMap(inner) => inner.clear(),
128            #[cfg(all(feature = "std", feature = "rustc-hash"))]
129            Self::FxHashMap(inner) => inner.clear(),
130        }
131    }
132
133    #[inline(always)]
134    fn remove(&mut self, k: &K) -> Option<V> {
135        match self {
136            Self::BTreeMap(inner) => inner.remove(k),
137            #[cfg(feature = "std")]
138            Self::HashMap(inner) => inner.remove(k),
139            #[cfg(all(feature = "std", feature = "rustc-hash"))]
140            Self::FxHashMap(inner) => inner.remove(k),
141        }
142    }
143}
144
145/// Specifies the inner map implementation for `TimedMap`.
146#[cfg(feature = "std")]
147#[allow(clippy::enum_variant_names)]
148pub enum MapKind {
149    BTreeMap,
150    HashMap,
151    #[cfg(feature = "rustc-hash")]
152    FxHashMap,
153}
154
155/// Associates keys of type `K` with values of type `V`. Each entry may optionally expire after a
156/// specified duration.
157///
158/// Mutable functions automatically clears expired entries when called.
159///
160/// If no expiration is set, the entry remains constant.
161#[derive(Debug)]
162pub struct TimedMap<K, V, #[cfg(feature = "std")] C = StdClock, #[cfg(not(feature = "std"))] C> {
163    clock: C,
164
165    map: GenericMap<K, ExpirableEntry<V>>,
166    expiries: BTreeMap<u64, BTreeSet<K>>,
167
168    expiration_tick: u16,
169    expiration_tick_cap: u16,
170}
171
172impl<K, V, C> Default for TimedMap<K, V, C>
173where
174    C: Default,
175{
176    fn default() -> Self {
177        Self {
178            clock: Default::default(),
179
180            map: GenericMap::default(),
181            expiries: BTreeMap::default(),
182
183            expiration_tick: 0,
184            expiration_tick_cap: 1,
185        }
186    }
187}
188
189#[cfg(feature = "std")]
190impl<K, V> TimedMap<K, V, StdClock>
191where
192    K: GenericKey,
193{
194    /// Creates an empty map.
195    pub fn new() -> Self {
196        Self::default()
197    }
198
199    /// Creates an empty map based on the chosen map implementation specified by `MapKind`.
200    pub fn new_with_map_kind(map_kind: MapKind) -> Self {
201        let map = match map_kind {
202            MapKind::BTreeMap => GenericMap::<K, ExpirableEntry<V>>::BTreeMap(BTreeMap::default()),
203            MapKind::HashMap => GenericMap::HashMap(HashMap::default()),
204            #[cfg(feature = "rustc-hash")]
205            MapKind::FxHashMap => GenericMap::FxHashMap(FxHashMap::default()),
206        };
207
208        Self {
209            map,
210
211            clock: StdClock::default(),
212            expiries: BTreeMap::default(),
213
214            expiration_tick: 0,
215            expiration_tick_cap: 1,
216        }
217    }
218}
219
220impl<K, V, C> TimedMap<K, V, C>
221where
222    C: Clock,
223    K: GenericKey,
224{
225    /// Creates an empty `TimedMap`.
226    ///
227    /// Uses the provided `clock` to handle expiration times.
228    #[cfg(not(feature = "std"))]
229    pub fn new(clock: C) -> Self {
230        Self {
231            clock,
232            map: GenericMap::default(),
233            expiries: BTreeMap::default(),
234            expiration_tick: 0,
235            expiration_tick_cap: 1,
236        }
237    }
238
239    /// Configures `expiration_tick_cap`, which sets how often `TimedMap::drop_expired_entries`
240    /// is automatically called. The default value is 1.
241    ///
242    /// On each insert (excluding `unchecked` ones), an internal counter `expiration_tick` is incremented.
243    /// When `expiration_tick` meets or exceeds `expiration_tick_cap`, `TimedMap::drop_expired_entries` is
244    /// triggered to remove expired entries.
245    ///
246    /// Use this to control cleanup frequency and optimize performance. For example, if your workload
247    /// involves about 100 inserts within couple seconds, setting `expiration_tick_cap` to 100 can improve
248    /// the performance significantly.
249    #[inline(always)]
250    pub fn expiration_tick_cap(mut self, expiration_tick_cap: u16) -> Self {
251        self.expiration_tick_cap = expiration_tick_cap;
252        self
253    }
254
255    /// Returns the associated value if present and not expired.
256    ///
257    /// To retrieve the value without checking expiration, use `TimedMap::get_unchecked`.
258    pub fn get(&self, k: &K) -> Option<&V> {
259        self.map
260            .get(k)
261            .filter(|v| !v.is_expired(self.clock.elapsed_seconds_since_creation()))
262            .map(|v| v.value())
263    }
264
265    /// Returns a mutable reference to the value corresponding to the key.
266    ///
267    /// To retrieve the value without checking expiration, use `TimedMap::get_mut_unchecked`.
268    pub fn get_mut(&mut self, k: &K) -> Option<&mut V> {
269        self.map
270            .get_mut(k)
271            .filter(|v| !v.is_expired(self.clock.elapsed_seconds_since_creation()))
272            .map(|v| v.value_mut())
273    }
274
275    /// Returns the associated value if present, regardless of whether it is expired.
276    ///
277    /// If you only want non-expired entries, use `TimedMap::get` instead.
278    #[inline(always)]
279    pub fn get_unchecked(&self, k: &K) -> Option<&V> {
280        self.map.get(k).map(|v| v.value())
281    }
282
283    /// Returns a mutable reference to the associated value if present, regardless of
284    /// whether it is expired.
285    ///
286    /// If you only want non-expired entries, use `TimedMap::get_mut` instead.
287    #[inline(always)]
288    pub fn get_mut_unchecked(&mut self, k: &K) -> Option<&mut V> {
289        self.map.get_mut(k).map(|v| v.value_mut())
290    }
291
292    /// Returns the associated value's `Duration` if present and not expired.
293    ///
294    /// Returns `None` if the entry does not exist or is constant.
295    pub fn get_remaining_duration(&self, k: &K) -> Option<Duration> {
296        match self.map.get(k) {
297            Some(v) => {
298                let now = self.clock.elapsed_seconds_since_creation();
299                if v.is_expired(now) {
300                    return None;
301                }
302
303                v.remaining_duration(now)
304            }
305            None => None,
306        }
307    }
308
309    /// Returns the number of unexpired elements in the map.
310    ///
311    /// See `TimedMap::len_expired` and `TimedMap::len_unchecked` for other usages.
312    #[inline(always)]
313    pub fn len(&self) -> usize {
314        self.map.len() - self.len_expired()
315    }
316
317    /// Returns the number of expired elements in the map.
318    ///
319    /// See `TimedMap::len` and `TimedMap::len_unchecked` for other usages.
320    #[inline(always)]
321    pub fn len_expired(&self) -> usize {
322        let now = self.clock.elapsed_seconds_since_creation();
323        self.expiries
324            .iter()
325            .filter_map(
326                |(exp, keys)| {
327                    if exp <= &now {
328                        Some(keys.len())
329                    } else {
330                        None
331                    }
332                },
333            )
334            .sum()
335    }
336
337    /// Returns the total number of elements (including expired ones) in the map.
338    ///
339    /// See `TimedMap::len` and `TimedMap::len_expired` for other usages.
340    #[inline(always)]
341    pub fn len_unchecked(&self) -> usize {
342        self.map.len()
343    }
344
345    /// Returns keys of the map
346    #[inline(always)]
347    pub fn keys(&self) -> Vec<K> {
348        self.map.keys()
349    }
350
351    /// Returns true if the map contains no elements.
352    #[inline(always)]
353    pub fn is_empty(&self) -> bool {
354        self.map.is_empty()
355    }
356
357    /// Inserts a key-value pair with an expiration duration. If duration is `None`,
358    /// entry will be stored in a non-expirable way.
359    ///
360    /// If a value already exists for the given key, it will be updated and then
361    /// the old one will be returned.
362    #[inline(always)]
363    fn insert(&mut self, k: K, v: V, expires_at: Option<u64>) -> Option<V> {
364        let entry = ExpirableEntry::new(v, expires_at);
365        match self.map.insert(k.clone(), entry) {
366            Some(old) => {
367                // Remove the old expiry record
368                if let EntryStatus::ExpiresAtSeconds(e) = old.status() {
369                    self.drop_key_from_expiry(e, &k)
370                }
371
372                Some(old.owned_value())
373            }
374            None => None,
375        }
376    }
377
378    /// Inserts a key-value pair with an expiration duration, and then drops the
379    /// expired entries.
380    ///
381    /// If a value already exists for the given key, it will be updated and then
382    /// the old one will be returned.
383    ///
384    /// If you don't want to the check expired entries, consider using `TimedMap::insert_expirable_unchecked`
385    /// instead.
386    pub fn insert_expirable(&mut self, k: K, v: V, duration: Duration) -> Option<V> {
387        self.expiration_tick += 1;
388
389        let now = self.clock.elapsed_seconds_since_creation();
390        if self.expiration_tick >= self.expiration_tick_cap {
391            self.drop_expired_entries_inner(now);
392            self.expiration_tick = 0;
393        }
394
395        let expires_at = now + duration.as_secs();
396
397        let res = self.insert(k.clone(), v, Some(expires_at));
398
399        self.expiries.entry(expires_at).or_default().insert(k);
400
401        res
402    }
403
404    /// Inserts a key-value pair with an expiration duration, without checking the expired
405    /// entries.
406    ///
407    /// If a value already exists for the given key, it will be updated and then
408    /// the old one will be returned.
409    ///
410    /// If you want to check the expired entries, consider using `TimedMap::insert_expirable`
411    /// instead.
412    pub fn insert_expirable_unchecked(&mut self, k: K, v: V, duration: Duration) -> Option<V> {
413        let now = self.clock.elapsed_seconds_since_creation();
414        let expires_at = now + duration.as_secs();
415
416        let res = self.insert(k.clone(), v, Some(expires_at));
417
418        self.expiries.entry(expires_at).or_default().insert(k);
419
420        res
421    }
422
423    /// Inserts a key-value pair with that doesn't expire, and then drops the
424    /// expired entries.
425    ///
426    /// If a value already exists for the given key, it will be updated and then
427    /// the old one will be returned.
428    ///
429    /// If you don't want to check the expired entries, consider using `TimedMap::insert_constant_unchecked`
430    /// instead.
431    pub fn insert_constant(&mut self, k: K, v: V) -> Option<V> {
432        self.expiration_tick += 1;
433
434        let now = self.clock.elapsed_seconds_since_creation();
435        if self.expiration_tick >= self.expiration_tick_cap {
436            self.drop_expired_entries_inner(now);
437            self.expiration_tick = 0;
438        }
439
440        self.insert(k, v, None)
441    }
442
443    /// Inserts a key-value pair with that doesn't expire without checking the expired
444    /// entries.
445    ///
446    /// If a value already exists for the given key, it will be updated and then
447    /// the old one will be returned.
448    ///
449    /// If you want to check the expired entries, consider using `TimedMap::insert_constant`
450    /// instead.
451    pub fn insert_constant_unchecked(&mut self, k: K, v: V) -> Option<V> {
452        self.expiration_tick += 1;
453        self.insert(k, v, None)
454    }
455
456    /// Removes a key-value pair from the map and returns the associated value if present
457    /// and not expired.
458    ///
459    /// If you want to retrieve the entry after removal even if it is expired, consider using
460    /// `TimedMap::remove_unchecked`.
461    #[inline(always)]
462    pub fn remove(&mut self, k: &K) -> Option<V> {
463        self.map
464            .remove(k)
465            .filter(|v| {
466                if let EntryStatus::ExpiresAtSeconds(expires_at_seconds) = v.status() {
467                    self.drop_key_from_expiry(expires_at_seconds, k);
468                }
469
470                !v.is_expired(self.clock.elapsed_seconds_since_creation())
471            })
472            .map(|v| v.owned_value())
473    }
474
475    /// Removes a key-value pair from the map and returns the associated value if present,
476    /// regardless of expiration status.
477    ///
478    /// If you only want the entry when it is not expired, consider using `TimedMap::remove`.
479    #[inline(always)]
480    pub fn remove_unchecked(&mut self, k: &K) -> Option<V> {
481        self.map
482            .remove(k)
483            .filter(|v| {
484                if let EntryStatus::ExpiresAtSeconds(expires_at_seconds) = v.status() {
485                    self.drop_key_from_expiry(expires_at_seconds, k);
486                }
487
488                true
489            })
490            .map(|v| v.owned_value())
491    }
492
493    /// Clears the map, removing all elements.
494    #[inline(always)]
495    pub fn clear(&mut self) {
496        self.map.clear()
497    }
498
499    /// Updates the expiration status of an entry and returns the old status.
500    ///
501    /// If the entry does not exist, returns Err.
502    /// If the entry's old status is `EntryStatus::Constant`, returns None.
503    pub fn update_expiration_status(
504        &mut self,
505        key: K,
506        duration: Duration,
507    ) -> Result<Option<EntryStatus>, &'static str> {
508        match self.map.get_mut(&key) {
509            Some(entry) => {
510                let old_status = *entry.status();
511                let now = self.clock.elapsed_seconds_since_creation();
512                let expires_at = now + duration.as_secs();
513
514                entry.update_status(EntryStatus::ExpiresAtSeconds(expires_at));
515
516                if let EntryStatus::ExpiresAtSeconds(t) = &old_status {
517                    self.drop_key_from_expiry(t, &key);
518                }
519                self.expiries
520                    .entry(expires_at)
521                    .or_default()
522                    .insert(key.clone());
523
524                Ok(Some(old_status))
525            }
526            None => Err("entry not found"),
527        }
528    }
529
530    /// Clears expired entries from the map.
531    ///
532    /// Call this function when using `*_unchecked` inserts, as these do not
533    /// automatically clear expired entries.
534    #[inline(always)]
535    pub fn drop_expired_entries(&mut self) {
536        let now = self.clock.elapsed_seconds_since_creation();
537        self.drop_expired_entries_inner(now);
538    }
539
540    fn drop_expired_entries_inner(&mut self, now: u64) {
541        // Iterates through `expiries` in order and drops expired ones.
542        while let Some((exp, keys)) = self.expiries.pop_first() {
543            // It's safe to do early-break here as keys are sorted by expiration.
544            if exp > now {
545                self.expiries.insert(exp, keys);
546                break;
547            }
548
549            for key in keys {
550                self.map.remove(&key);
551            }
552        }
553    }
554
555    fn drop_key_from_expiry(&mut self, expiry_key: &u64, map_key: &K) {
556        if let Some(list) = self.expiries.get_mut(expiry_key) {
557            list.remove(map_key);
558
559            if list.is_empty() {
560                self.expiries.remove(expiry_key);
561            }
562        }
563    }
564
565    /// Returns `true` if the map contains a non-expired value for the given key.
566    ///
567    /// To include expired entries as well, use [`TimedMap::contains_key_unchecked`].
568    #[inline(always)]
569    pub fn contains_key(&self, k: &K) -> bool {
570        self.get(k).is_some()
571    }
572
573    /// Returns `true` if the map contains a value for the given key regardless of expiration status.
574    ///
575    /// To exclude expired entries, use [`TimedMap::contains_key`] instead.
576    #[inline(always)]
577    pub fn contains_key_unchecked(&self, k: &K) -> bool {
578        self.map.keys().contains(k)
579    }
580}
581
582#[cfg(test)]
583#[cfg(not(feature = "std"))]
584mod tests {
585    use super::*;
586
587    struct MockClock {
588        current_time: u64,
589    }
590
591    impl Clock for MockClock {
592        fn elapsed_seconds_since_creation(&self) -> u64 {
593            self.current_time
594        }
595    }
596
597    #[test]
598    fn nostd_insert_and_get_constant_entry() {
599        let clock = MockClock { current_time: 1000 };
600        let mut map = TimedMap::new(clock);
601
602        map.insert_constant(1, "constant value");
603
604        assert_eq!(map.get(&1), Some(&"constant value"));
605        assert_eq!(map.get_remaining_duration(&1), None);
606    }
607
608    #[test]
609    fn nostd_insert_and_get_expirable_entry() {
610        let clock = MockClock { current_time: 1000 };
611        let mut map = TimedMap::new(clock);
612        let duration = Duration::from_secs(60);
613
614        map.insert_expirable(1, "expirable value", duration);
615
616        assert_eq!(map.get(&1), Some(&"expirable value"));
617        assert_eq!(map.get_remaining_duration(&1), Some(duration));
618    }
619
620    #[test]
621    fn nostd_expired_entry() {
622        let clock = MockClock { current_time: 1000 };
623        let mut map = TimedMap::new(clock);
624        let duration = Duration::from_secs(60);
625
626        // Insert entry that expires in 60 seconds
627        map.insert_expirable(1, "expirable value", duration);
628
629        // Simulate time passage beyond expiration
630        let clock = MockClock { current_time: 1070 };
631        map.clock = clock;
632
633        // The entry should be considered expired
634        assert_eq!(map.get(&1), None);
635        assert_eq!(map.get_remaining_duration(&1), None);
636    }
637
638    #[test]
639    fn nostd_remove_entry() {
640        let clock = MockClock { current_time: 1000 };
641        let mut map = TimedMap::new(clock);
642
643        map.insert_constant(1, "constant value");
644
645        assert_eq!(map.remove(&1), Some("constant value"));
646        assert_eq!(map.get(&1), None);
647    }
648
649    #[test]
650    fn nostd_drop_expired_entries() {
651        let clock = MockClock { current_time: 1000 };
652        let mut map = TimedMap::new(clock);
653
654        // Insert one constant and 2 expirable entries
655        map.insert_expirable(1, "expirable value1", Duration::from_secs(50));
656        map.insert_expirable(2, "expirable value2", Duration::from_secs(70));
657        map.insert_constant(3, "constant value");
658
659        // Simulate time passage beyond the expiration of the first entry
660        let clock = MockClock { current_time: 1055 };
661        map.clock = clock;
662
663        // Entry 1 should be removed and entry 2 and 3 should still exist
664        assert_eq!(map.get(&1), None);
665        assert_eq!(map.get(&2), Some(&"expirable value2"));
666        assert_eq!(map.get(&3), Some(&"constant value"));
667
668        // Simulate time passage again to expire second expirable entry
669        let clock = MockClock { current_time: 1071 };
670        map.clock = clock;
671
672        assert_eq!(map.get(&1), None);
673        assert_eq!(map.get(&2), None);
674        assert_eq!(map.get(&3), Some(&"constant value"));
675    }
676
677    #[test]
678    fn nostd_update_existing_entry() {
679        let clock = MockClock { current_time: 1000 };
680        let mut map = TimedMap::new(clock);
681
682        map.insert_constant(1, "initial value");
683        assert_eq!(map.get(&1), Some(&"initial value"));
684
685        // Update the value of the existing key and make it expirable
686        map.insert_expirable(1, "updated value", Duration::from_secs(15));
687        assert_eq!(map.get(&1), Some(&"updated value"));
688
689        // Simulate time passage and expire the updated entry
690        let clock = MockClock { current_time: 1016 };
691        map.clock = clock;
692
693        assert_eq!(map.get(&1), None);
694    }
695
696    #[test]
697    fn nostd_update_expirable_entry_status() {
698        let clock = MockClock { current_time: 1000 };
699        let mut map = TimedMap::new(clock);
700
701        map.insert_constant(1, "initial value");
702        assert_eq!(map.get(&1), Some(&"initial value"));
703
704        // Update the value of the existing key and make it expirable
705        map.update_expiration_status(1, Duration::from_secs(16))
706            .expect("entry update shouldn't fail");
707        assert_eq!(map.get(&1), Some(&"initial value"));
708
709        // Simulate time passage and expire the updated entry
710        let clock = MockClock { current_time: 1017 };
711        map.clock = clock;
712        assert_eq!(map.get(&1), None);
713    }
714
715    #[test]
716    fn nostd_update_expirable_entry_status_with_previou_time() {
717        let clock = MockClock { current_time: 1000 };
718        let mut map = TimedMap::new(clock);
719
720        // Insert map entry followed by immediately updating expiration time
721        map.insert_expirable(1, "expirable value", Duration::from_secs(15));
722        map.update_expiration_status(1, Duration::from_secs(15))
723            .expect("entry update shouldn't fail");
724
725        // We should still have our entry.
726        assert_eq!(map.get(&1), Some(&"expirable value"));
727        assert!(map.expiries.contains_key(&1015));
728    }
729
730    #[test]
731    fn nostd_contains_key() {
732        let clock = MockClock { current_time: 1000 };
733        let mut map = TimedMap::new(clock);
734
735        // Insert map entry and check if exists
736        map.insert_expirable(1, "expirable value", Duration::from_secs(5));
737        assert!(map.contains_key(&1));
738    }
739}
740
741#[cfg(feature = "std")]
742#[cfg(test)]
743mod std_tests {
744    use core::ops::Add;
745
746    use super::*;
747
748    #[test]
749    fn std_expirable_and_constant_entries() {
750        let mut map = TimedMap::new();
751
752        map.insert_constant(1, "constant value");
753        map.insert_expirable(2, "expirable value", Duration::from_secs(2));
754
755        assert_eq!(map.get(&1), Some(&"constant value"));
756        assert_eq!(map.get(&2), Some(&"expirable value"));
757
758        assert_eq!(map.get_remaining_duration(&1), None);
759        assert!(map.get_remaining_duration(&2).is_some());
760    }
761
762    #[test]
763    fn std_expired_entry_removal() {
764        let mut map = TimedMap::new();
765        let duration = Duration::from_secs(2);
766
767        map.insert_expirable(1, "expirable value", duration);
768
769        // Wait for expiration
770        std::thread::sleep(Duration::from_secs(3));
771
772        // Entry should now be expired
773        assert_eq!(map.get(&1), None);
774        assert_eq!(map.get_remaining_duration(&1), None);
775    }
776
777    #[test]
778    fn std_remove_entry() {
779        let mut map = TimedMap::new();
780
781        map.insert_constant(1, "constant value");
782        map.insert_expirable(2, "expirable value", Duration::from_secs(2));
783
784        assert_eq!(map.remove(&1), Some("constant value"));
785        assert_eq!(map.remove(&2), Some("expirable value"));
786
787        assert_eq!(map.get(&1), None);
788        assert_eq!(map.get(&2), None);
789    }
790
791    #[test]
792    fn std_drop_expired_entries() {
793        let mut map = TimedMap::new();
794
795        map.insert_expirable(1, "expirable value1", Duration::from_secs(2));
796        map.insert_expirable(2, "expirable value2", Duration::from_secs(4));
797
798        // Wait for expiration
799        std::thread::sleep(Duration::from_secs(3));
800
801        // Entry 1 should be removed and entry 2 should still exist
802        assert_eq!(map.get(&1), None);
803        assert_eq!(map.get(&2), Some(&"expirable value2"));
804    }
805
806    #[test]
807    fn std_update_existing_entry() {
808        let mut map = TimedMap::new();
809
810        map.insert_constant(1, "initial value");
811        assert_eq!(map.get(&1), Some(&"initial value"));
812
813        // Update the value of the existing key and make it expirable
814        map.insert_expirable(1, "updated value", Duration::from_secs(1));
815        assert_eq!(map.get(&1), Some(&"updated value"));
816
817        std::thread::sleep(Duration::from_secs(2));
818
819        // Should be expired now
820        assert_eq!(map.get(&1), None);
821    }
822
823    #[test]
824    fn std_insert_constant_and_expirable_combined() {
825        let mut map = TimedMap::new();
826
827        // Insert a constant entry and an expirable entry
828        map.insert_constant(1, "constant value");
829        map.insert_expirable(2, "expirable value", Duration::from_secs(2));
830
831        // Check both entries exist
832        assert_eq!(map.get(&1), Some(&"constant value"));
833        assert_eq!(map.get(&2), Some(&"expirable value"));
834
835        // Simulate passage of time beyond expiration
836        std::thread::sleep(Duration::from_secs(3));
837
838        // Constant entry should still exist, expirable should be expired
839        assert_eq!(map.get(&1), Some(&"constant value"));
840        assert_eq!(map.get(&2), None);
841    }
842
843    #[test]
844    fn std_expirable_entry_still_valid_before_expiration() {
845        let mut map = TimedMap::new();
846
847        // Insert an expirable entry with a duration of 3 seconds
848        map.insert_expirable(1, "expirable value", Duration::from_secs(3));
849
850        // Simulate a short sleep of 2 seconds (still valid)
851        std::thread::sleep(Duration::from_secs(2));
852
853        // The entry should still be valid
854        assert_eq!(map.get(&1), Some(&"expirable value"));
855        assert!(map.get_remaining_duration(&1).unwrap().as_secs() == 1);
856    }
857
858    #[test]
859    fn std_length_functions() {
860        let mut map = TimedMap::new();
861
862        map.insert_expirable(1, "expirable value", Duration::from_secs(1));
863        map.insert_expirable(2, "expirable value", Duration::from_secs(1));
864        map.insert_expirable(3, "expirable value", Duration::from_secs(3));
865        map.insert_expirable(4, "expirable value", Duration::from_secs(3));
866        map.insert_expirable(5, "expirable value", Duration::from_secs(3));
867        map.insert_expirable(6, "expirable value", Duration::from_secs(3));
868
869        std::thread::sleep(Duration::from_secs(2).add(Duration::from_millis(1)));
870
871        assert_eq!(map.len(), 4);
872        assert_eq!(map.len_expired(), 2);
873        assert_eq!(map.len_unchecked(), 6);
874    }
875
876    #[test]
877    fn std_update_expirable_entry() {
878        let mut map = TimedMap::new();
879
880        map.insert_expirable(1, "expirable value", Duration::from_secs(1));
881        map.insert_expirable(1, "expirable value", Duration::from_secs(5));
882
883        std::thread::sleep(Duration::from_secs(2));
884
885        assert!(!map.expiries.contains_key(&1));
886        assert!(map.expiries.contains_key(&5));
887        assert_eq!(map.get(&1), Some(&"expirable value"));
888    }
889
890    #[test]
891    fn std_update_expirable_entry_status() {
892        let mut map = TimedMap::new();
893
894        map.insert_expirable(1, "expirable value", Duration::from_secs(1));
895        map.update_expiration_status(1, Duration::from_secs(5))
896            .expect("entry update shouldn't fail");
897
898        std::thread::sleep(Duration::from_secs(3));
899        assert!(!map.expiries.contains_key(&1));
900        assert!(map.expiries.contains_key(&5));
901        assert_eq!(map.get(&1), Some(&"expirable value"));
902    }
903
904    #[test]
905    fn std_update_expirable_entry_status_with_previou_time() {
906        let mut map = TimedMap::new();
907
908        // Insert map entry followed by immediately updating expiration time
909        map.insert_expirable(1, "expirable value", Duration::from_secs(5));
910        map.update_expiration_status(1, Duration::from_secs(5))
911            .expect("entry update shouldn't fail");
912
913        // We should still have our entry.
914        assert_eq!(map.get(&1), Some(&"expirable value"));
915        assert!(map.expiries.contains_key(&5));
916    }
917
918    #[test]
919    fn std_contains_key() {
920        let mut map = TimedMap::new();
921
922        // Insert map entry and check if exists
923        map.insert_expirable(1, "expirable value", Duration::from_secs(1));
924        assert!(map.contains_key(&1));
925    }
926
927    #[test]
928    fn std_does_not_contain_key_anymore() {
929        let mut map = TimedMap::new();
930
931        // Insert map entry and check if still exists after expiry
932        map.insert_expirable(1, "expirable value", Duration::from_secs(1));
933        std::thread::sleep(Duration::from_secs(2));
934        assert!(!map.contains_key(&1));
935    }
936
937    #[test]
938    fn std_contains_key_unchecked() {
939        let mut map = TimedMap::new();
940
941        map.insert_expirable(1, "expirable value", Duration::from_secs(1));
942        std::thread::sleep(Duration::from_secs(2));
943        assert!(map.contains_key_unchecked(&1));
944    }
945}
timed_map/map.rs

timed_map/
map.rs
