priority_expiry_cache/
lib.rs

1extern crate lru;
2
3use std::collections::{BTreeMap, BTreeSet,HashMap};
4use std::hash::Hash;
5use lru::LruCache;
6
7struct Page<K,V,P,E> {
8    key: K,
9    value: V,
10    priority: P,
11    expiry: E,
12}
13
14#[derive(Ord,PartialOrd, PartialEq, Eq)]
15struct ItemExpiry<E,K> {
16    expiry: E,
17    key: K,
18}
19
20pub struct PECache<K,V,P,E> {
21    access_map: HashMap<K, Page<K,V,P,E>>,
22    evict_expiry: BTreeSet<ItemExpiry<E,K>>,
23    evict_priority: BTreeMap<P, LruCache<K, bool>>,
24}
25
26impl <K:Clone+Hash+Ord,
27    V: Clone+Eq+Hash+PartialEq,
28    P: Clone + Ord,
29    E: Clone + Ord + Eq,
30>PECache<K,V,P,E> {
31    /// Creates a new PE Cache.
32    ///
33    /// # Examples
34    /// ```
35    /// use priority_expiry_cache::PECache;
36    /// let mut new_cache:PECache<String,String,u32,u32>= PECache::new();
37    /// ```
38    pub fn new() -> Self {
39        Self {
40            access_map: Default::default(),
41            evict_expiry: Default::default(),
42            evict_priority: Default::default(),
43        }
44    }
45
46    /// Add a new item to the cache or override the existing one if present in O(1) time.
47    ///
48    /// # Examples
49    /// ```
50    /// use priority_expiry_cache::PECache;
51    /// let mut new_cache:PECache<String,String,u32,u32>= PECache::new();
52    ///     let (key, value, priority, expiry) = (
53    ///         String::from("key"),
54    ///         String::from("value"), 1, 1);
55    /// new_cache.set(key.clone(),value.clone(), priority, expiry);
56    ///
57    /// ```
58    pub fn set(&mut self, key: K, value: V,priority: P, expiry: E) {
59        // addition to the btree for time
60        let key_expiry: ItemExpiry<E, K> = ItemExpiry {
61            expiry: expiry.clone(),
62            key: key.clone(),
63        };
64        self.evict_expiry.insert(key_expiry);
65        // addition to the btree for priority
66        self.evict_priority.entry(priority.clone())
67            .or_insert(LruCache::unbounded()).push(key.clone(), true);
68        // add to the map
69        let page = Page { key: key.clone(), value, expiry, priority };
70        self.access_map.insert(key, page);
71        return;
72    }
73    /// Gat the value associated with the key if present or None if not in O(1) time.
74    ///
75    /// # Examples
76    /// ```
77    /// use priority_expiry_cache::PECache;
78    /// let mut new_cache:PECache<String,String,u32,u32>= PECache::new();
79    ///
80    /// // the get operation
81    /// let extracted_value = new_cache.get("key".to_string());
82    /// ```
83    pub fn get(&mut self, key: K) -> Option<V> {
84        if let Some(page) = self.access_map.get(&key) {
85            // change the order in the last recently data structure
86            self.evict_priority.get_mut(&page.priority).unwrap().promote(&page.key);
87            return Some(page.value.clone());
88        }
89        None
90    }
91    /// Evict 1 element following this policy if at least one element is present in O(1).
92    ///
93    /// Policy:
94    /// - If an expired item is available. Remove it. If multiple items have the same expiry, removing any one suffices.
95    /// - If condition #1 can’t be satisfied, remove an item with the least priority.
96    /// - If more than one item satisfies condition #2, remove the least recently used one.
97    /// - Multiple items can have the same priority and expiry.
98    ///
99    /// # Examples
100    /// ```
101    /// use priority_expiry_cache::PECache;
102    /// let mut new_cache:PECache<String,String,u32,u32>= PECache::new();
103    ///
104    ///
105    /// let extracted_value = new_cache.evict(10);
106    /// ```
107    pub fn evict(&mut self, barrier: E) {
108        if self.access_map.len() == 0 {
109            return;
110        }
111        // get key by check firs by time and then by priority/lru
112        let target_item = self.evict_expiry.first().unwrap();
113
114        let key_target = if target_item.expiry <= barrier { target_item.key.clone() } else {
115            let target_item = self.evict_priority.first_entry().unwrap();
116            let (key,_) = target_item.get().peek_lru().unwrap();
117            key.clone()
118        };
119        // delete from the map
120        let page = self.access_map.remove(&key_target).unwrap();
121        // delete from the expiry tree
122        self.evict_expiry.remove(&ItemExpiry{expiry: page.expiry.clone(),key: page.key.clone()});
123        // delete from priority tree
124        let node_priority = self.evict_priority.get_mut(&page.priority).unwrap();
125        node_priority.pop(&page.key);
126        // delete the node if empty after the item removal
127        if node_priority.len() == 0 {
128            self.evict_priority.remove(&page.priority);
129        }
130        return
131    }
132    /// Return the Length of Cache items in O(1).
133    ///
134    /// # Examples
135    /// ```
136    /// use priority_expiry_cache::PECache;
137    /// let mut new_cache:PECache<String,String,u32,u32>= PECache::new();
138    ///
139    ///
140    /// let cache_n_size = new_cache.len();
141    /// ```
142
143    pub fn len(&self)->usize{
144        self.access_map.len()
145    }
146}
priority_expiry_cache/lib.rs

priority_expiry_cache/
lib.rs
