1 // Copyright 2013 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
12 //! A cache that holds a limited number of key-value pairs. When the
13 //! capacity of the cache is exceeded, the least-recently-used
14 //! (where "used" means a look-up or putting the pair into the cache)
15 //! pair is automatically removed.
20 //! use collections::LruCache;
22 //! let mut cache: LruCache<int, int> = LruCache::new(2);
26 //! assert!(cache.get(&1).is_none());
27 //! assert_eq!(*cache.get(&2).unwrap(), 20);
28 //! assert_eq!(*cache.get(&3).unwrap(), 30);
31 //! assert_eq!(*cache.get(&2).unwrap(), 22);
34 //! assert!(cache.get(&3).is_none());
36 //! cache.change_capacity(1);
37 //! assert!(cache.get(&2).is_none());
41 use std::container::Container;
48 struct KeyRef<K> { k: *K }
50 struct LruEntry<K, V> {
53 next: *mut LruEntry<K, V>,
54 prev: *mut LruEntry<K, V>,
58 pub struct LruCache<K, V> {
59 priv map: HashMap<KeyRef<K>, ~LruEntry<K, V>>,
61 priv head: *mut LruEntry<K, V>,
62 priv tail: *mut LruEntry<K, V>,
65 impl<S, K: Hash<S>> Hash<S> for KeyRef<K> {
66 fn hash(&self, state: &mut S) {
67 unsafe { (*self.k).hash(state) }
71 impl<K: Eq> Eq for KeyRef<K> {
72 fn eq(&self, other: &KeyRef<K>) -> bool {
73 unsafe{ (*self.k).eq(&*other.k) }
77 impl<K: TotalEq> TotalEq for KeyRef<K> {}
79 impl<K, V> LruEntry<K, V> {
80 fn new() -> LruEntry<K, V> {
84 next: ptr::mut_null(),
85 prev: ptr::mut_null(),
89 fn with_key_value(k: K, v: V) -> LruEntry<K, V> {
93 next: ptr::mut_null(),
94 prev: ptr::mut_null(),
99 impl<K: Hash + TotalEq, V> LruCache<K, V> {
100 /// Create an LRU Cache that holds at most `capacity` items.
101 pub fn new(capacity: uint) -> LruCache<K, V> {
102 let cache = LruCache {
105 head: unsafe{ cast::transmute(~LruEntry::<K, V>::new()) },
106 tail: unsafe{ cast::transmute(~LruEntry::<K, V>::new()) },
109 (*cache.head).next = cache.tail;
110 (*cache.tail).prev = cache.head;
115 /// Put a key-value pair into cache.
116 pub fn put(&mut self, k: K, v: V) {
117 let mut key_existed = false;
118 let (node_ptr, node_opt) = match self.map.find_mut(&KeyRef{k: &k}) {
121 node.value = Some(v);
122 let node_ptr: *mut LruEntry<K, V> = &mut **node;
126 let mut node = ~LruEntry::with_key_value(k, v);
127 let node_ptr: *mut LruEntry<K, V> = &mut *node;
128 (node_ptr, Some(node))
132 self.detach(node_ptr);
133 self.attach(node_ptr);
135 let keyref = unsafe { (*node_ptr).key.as_ref().unwrap() };
136 self.map.swap(KeyRef{k: keyref}, node_opt.unwrap());
137 self.attach(node_ptr);
138 if self.len() > self.capacity() {
144 /// Return a value corresponding to the key in the cache.
145 pub fn get<'a>(&'a mut self, k: &K) -> Option<&'a V> {
146 let (value, node_ptr_opt) = match self.map.find_mut(&KeyRef{k: k}) {
147 None => (None, None),
149 let node_ptr: *mut LruEntry<K, V> = &mut **node;
151 match (*node_ptr).value {
152 None => (None, None),
153 Some(ref value) => (Some(value), Some(node_ptr))
161 self.detach(node_ptr);
162 self.attach(node_ptr);
168 /// Remove and return a value corresponding to the key from the cache.
169 pub fn pop(&mut self, k: &K) -> Option<V> {
170 match self.map.pop(&KeyRef{k: k}) {
172 Some(lru_entry) => lru_entry.value
176 /// Return the maximum number of key-value pairs the cache can hold.
177 pub fn capacity(&self) -> uint {
181 /// Change the number of key-value pairs the cache can hold. Remove
182 /// least-recently-used key-value pairs if necessary.
183 pub fn change_capacity(&mut self, capacity: uint) {
184 for _ in range(capacity, self.len()) {
187 self.max_size = capacity;
191 fn remove_lru(&mut self) {
193 let lru = unsafe { (*self.tail).prev };
198 Some(ref k) => { self.map.pop(&KeyRef{k: k}); }
205 fn detach(&mut self, node: *mut LruEntry<K, V>) {
207 (*(*node).prev).next = (*node).next;
208 (*(*node).next).prev = (*node).prev;
213 fn attach(&mut self, node: *mut LruEntry<K, V>) {
215 (*node).next = (*self.head).next;
216 (*node).prev = self.head;
217 (*self.head).next = node;
218 (*(*node).next).prev = node;
223 impl<A: fmt::Show + Hash + TotalEq, B: fmt::Show> fmt::Show for LruCache<A, B> {
224 /// Return a string that lists the key-value pairs from most-recently
225 /// used to least-recently used.
226 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
227 try!(write!(f.buf, r"\{"));
228 let mut cur = self.head;
229 for i in range(0, self.len()) {
230 if i > 0 { try!(write!(f.buf, ", ")) }
234 // should never print nil
235 None => try!(write!(f.buf, "nil")),
236 Some(ref k) => try!(write!(f.buf, "{}", *k)),
239 try!(write!(f.buf, ": "));
242 // should never print nil
243 None => try!(write!(f.buf, "nil")),
244 Some(ref value) => try!(write!(f.buf, "{}", *value)),
252 impl<K: Hash + TotalEq, V> Container for LruCache<K, V> {
253 /// Return the number of key-value pairs in the cache.
254 fn len(&self) -> uint {
259 impl<K: Hash + TotalEq, V> Mutable for LruCache<K, V> {
260 /// Clear the cache of all key-value pairs.
261 fn clear(&mut self) {
267 impl<K, V> Drop for LruCache<K, V> {
270 let _: ~LruEntry<K, V> = cast::transmute(self.head);
271 let _: ~LruEntry<K, V> = cast::transmute(self.tail);
280 fn assert_opt_eq<V: Eq>(opt: Option<&V>, v: V) {
281 assert!(opt.is_some());
282 assert!(opt.unwrap() == &v);
286 fn test_put_and_get() {
287 let mut cache: LruCache<int, int> = LruCache::new(2);
290 assert_opt_eq(cache.get(&1), 10);
291 assert_opt_eq(cache.get(&2), 20);
292 assert_eq!(cache.len(), 2);
296 fn test_put_update() {
297 let mut cache: LruCache<~str, ~[u8]> = LruCache::new(1);
298 cache.put(~"1", ~[10, 10]);
299 cache.put(~"1", ~[10, 19]);
300 assert_opt_eq(cache.get(&~"1"), ~[10, 19]);
301 assert_eq!(cache.len(), 1);
305 fn test_expire_lru() {
306 let mut cache: LruCache<~str, ~str> = LruCache::new(2);
307 cache.put(~"foo1", ~"bar1");
308 cache.put(~"foo2", ~"bar2");
309 cache.put(~"foo3", ~"bar3");
310 assert!(cache.get(&~"foo1").is_none());
311 cache.put(~"foo2", ~"bar2update");
312 cache.put(~"foo4", ~"bar4");
313 assert!(cache.get(&~"foo3").is_none());
318 let mut cache: LruCache<int, int> = LruCache::new(2);
321 assert_eq!(cache.len(), 2);
322 let opt1 = cache.pop(&1);
323 assert!(opt1.is_some());
324 assert_eq!(opt1.unwrap(), 10);
325 assert!(cache.get(&1).is_none());
326 assert_eq!(cache.len(), 1);
330 fn test_change_capacity() {
331 let mut cache: LruCache<int, int> = LruCache::new(2);
332 assert_eq!(cache.capacity(), 2);
335 cache.change_capacity(1);
336 assert!(cache.get(&1).is_none());
337 assert_eq!(cache.capacity(), 1);
342 let mut cache: LruCache<int, int> = LruCache::new(3);
346 assert_eq!(cache.to_str(), ~"{3: 30, 2: 20, 1: 10}");
348 assert_eq!(cache.to_str(), ~"{2: 22, 3: 30, 1: 10}");
350 assert_eq!(cache.to_str(), ~"{6: 60, 2: 22, 3: 30}");
352 assert_eq!(cache.to_str(), ~"{3: 30, 6: 60, 2: 22}");
353 cache.change_capacity(2);
354 assert_eq!(cache.to_str(), ~"{3: 30, 6: 60}");
359 let mut cache: LruCache<int, int> = LruCache::new(2);
363 assert!(cache.get(&1).is_none());
364 assert!(cache.get(&2).is_none());
365 assert_eq!(cache.to_str(), ~"{}");