Lines Matching +full:map +full:- +full:cache
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
11 //! A cache that holds a limited number of key-value pairs. When the
12 //! capacity of the cache is exceeded, the least-recently-used
13 //! (where "used" means a look-up or putting the pair into the cache)
21 //! let mut cache = LruCache::new(2);
23 //! cache.insert(1, 10);
24 //! cache.insert(2, 20);
25 //! cache.insert(3, 30);
26 //! assert!(cache.get_mut(&1).is_none());
27 //! assert_eq!(*cache.get_mut(&2).unwrap(), 20);
28 //! assert_eq!(*cache.get_mut(&3).unwrap(), 30);
30 //! cache.insert(2, 22);
31 //! assert_eq!(*cache.get_mut(&2).unwrap(), 22);
33 //! cache.insert(6, 60);
34 //! assert!(cache.get_mut(&3).is_none());
36 //! cache.set_capacity(1);
37 //! assert!(cache.get_mut(&2).is_none());
54 /// An LRU cache.
57 map: LinkedHashMap<K, V, S>, field
62 /// Creates an empty cache that can hold at most `capacity` items.
68 /// let mut cache: LruCache<i32, &str> = LruCache::new(10);
70 pub fn new(capacity: usize) -> Self { in new()
72 map: LinkedHashMap::new(), in new()
79 /// Creates an empty cache that can hold at most `capacity` items with the given hash builder.
80 pub fn with_hasher(capacity: usize, hash_builder: S) -> Self { in with_hasher()
81 LruCache { map: LinkedHashMap::with_hasher(hash_builder), max_size: capacity } in with_hasher()
84 /// Checks if the map contains the given key.
91 /// let mut cache = LruCache::new(1);
93 /// cache.insert(1, "a");
94 /// assert_eq!(cache.contains_key(&1), true);
96 pub fn contains_key<Q: ?Sized>(&mut self, key: &Q) -> bool in contains_key()
103 /// Inserts a key-value pair into the cache. If the key already existed, the old value is
111 /// let mut cache = LruCache::new(2);
113 /// cache.insert(1, "a");
114 /// cache.insert(2, "b");
115 /// assert_eq!(cache.get_mut(&1), Some(&mut "a"));
116 /// assert_eq!(cache.get_mut(&2), Some(&mut "b"));
118 pub fn insert(&mut self, k: K, v: V) -> Option<V> { in insert()
119 let old_val = self.map.insert(k, v); in insert()
126 /// Returns a mutable reference to the value corresponding to the given key in the cache, if
134 /// let mut cache = LruCache::new(2);
136 /// cache.insert(1, "a");
137 /// cache.insert(2, "b");
138 /// cache.insert(2, "c");
139 /// cache.insert(3, "d");
141 /// assert_eq!(cache.get_mut(&1), None);
142 /// assert_eq!(cache.get_mut(&2), Some(&mut "c"));
144 pub fn get_mut<Q: ?Sized>(&mut self, k: &Q) -> Option<&mut V> in get_mut()
148 self.map.get_refresh(k) in get_mut()
151 /// Removes the given key from the cache and returns its corresponding value.
158 /// let mut cache = LruCache::new(2);
160 /// cache.insert(2, "a");
162 /// assert_eq!(cache.remove(&1), None);
163 /// assert_eq!(cache.remove(&2), Some("a"));
164 /// assert_eq!(cache.remove(&2), None);
165 /// assert_eq!(cache.len(), 0);
167 pub fn remove<Q: ?Sized>(&mut self, k: &Q) -> Option<V> in remove()
171 self.map.remove(k) in remove()
174 /// Returns the maximum number of key-value pairs the cache can hold.
180 /// let mut cache: LruCache<i32, &str> = LruCache::new(2);
181 /// assert_eq!(cache.capacity(), 2);
183 pub fn capacity(&self) -> usize { in capacity()
187 /// Sets the number of key-value pairs the cache can hold. Removes
188 /// least-recently-used key-value pairs if necessary.
195 /// let mut cache = LruCache::new(2);
197 /// cache.insert(1, "a");
198 /// cache.insert(2, "b");
199 /// cache.insert(3, "c");
201 /// assert_eq!(cache.get_mut(&1), None);
202 /// assert_eq!(cache.get_mut(&2), Some(&mut "b"));
203 /// assert_eq!(cache.get_mut(&3), Some(&mut "c"));
205 /// cache.set_capacity(3);
206 /// cache.insert(1, "a");
207 /// cache.insert(2, "b");
209 /// assert_eq!(cache.get_mut(&1), Some(&mut "a"));
210 /// assert_eq!(cache.get_mut(&2), Some(&mut "b"));
211 /// assert_eq!(cache.get_mut(&3), Some(&mut "c"));
213 /// cache.set_capacity(1);
215 /// assert_eq!(cache.get_mut(&1), None);
216 /// assert_eq!(cache.get_mut(&2), None);
217 /// assert_eq!(cache.get_mut(&3), Some(&mut "c"));
226 /// Removes and returns the least recently used key-value pair as a tuple.
233 /// let mut cache = LruCache::new(2);
235 /// cache.insert(1, "a");
236 /// cache.insert(2, "b");
238 /// assert_eq!(cache.remove_lru(), Some((1, "a")));
239 /// assert_eq!(cache.len(), 1);
242 pub fn remove_lru(&mut self) -> Option<(K, V)> { in remove_lru()
243 self.map.pop_front() in remove_lru()
246 /// Returns the number of key-value pairs in the cache.
247 pub fn len(&self) -> usize { self.map.len() } in len()
249 /// Returns `true` if the cache contains no key-value pairs.
250 pub fn is_empty(&self) -> bool { self.map.is_empty() } in is_empty()
252 /// Removes all key-value pairs from the cache.
253 pub fn clear(&mut self) { self.map.clear(); } in clear()
255 /// Returns an iterator over the cache's key-value pairs in least- to most-recently-used order.
257 /// Accessing the cache through the iterator does _not_ affect the cache's LRU state.
264 /// let mut cache = LruCache::new(2);
266 /// cache.insert(1, 10);
267 /// cache.insert(2, 20);
268 /// cache.insert(3, 30);
270 /// let kvs: Vec<_> = cache.iter().collect();
273 pub fn iter(&self) -> Iter<K, V> { Iter(self.map.iter()) } in iter()
275 /// Returns an iterator over the cache's key-value pairs in least- to most-recently-used order,
278 /// Accessing the cache through the iterator does _not_ affect the cache's LRU state.
285 /// let mut cache = LruCache::new(2);
287 /// cache.insert(1, 10);
288 /// cache.insert(2, 20);
289 /// cache.insert(3, 30);
293 /// for (k, v) in cache.iter_mut() {
301 /// assert_eq!(cache.get_mut(&2), Some(&mut 200));
302 /// assert_eq!(cache.get_mut(&3), Some(&mut 300));
304 pub fn iter_mut(&mut self) -> IterMut<K, V> { IterMut(self.map.iter_mut()) } in iter_mut()
316 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { in fmt()
325 fn into_iter(self) -> IntoIter<K, V> { in into_iter()
326 IntoIter(self.map.into_iter()) in into_iter()
333 fn into_iter(self) -> Iter<'a, K, V> { self.iter() } in into_iter()
339 fn into_iter(self) -> IterMut<'a, K, V> { self.iter_mut() } in into_iter()
342 /// An iterator over a cache's key-value pairs in least- to most-recently-used order.
349 /// let mut cache = LruCache::new(2);
351 /// cache.insert(1, 10);
352 /// cache.insert(2, 20);
353 /// cache.insert(3, 30);
357 /// for (k, v) in cache {
371 fn next(&mut self) -> Option<(K, V)> { in next()
375 fn size_hint(&self) -> (usize, Option<usize>) { in size_hint()
381 fn next_back(&mut self) -> Option<(K, V)> { in next_back()
387 fn len(&self) -> usize { in len()
392 /// An iterator over a cache's key-value pairs in least- to most-recently-used order.
394 /// Accessing a cache through the iterator does _not_ affect the cache's LRU state.
398 fn clone(&self) -> Iter<'a, K, V> { Iter(self.0.clone()) } in clone()
403 fn next(&mut self) -> Option<(&'a K, &'a V)> { self.0.next() } in next()
404 fn size_hint(&self) -> (usize, Option<usize>) { self.0.size_hint() } in size_hint()
408 fn next_back(&mut self) -> Option<(&'a K, &'a V)> { self.0.next_back() } in next_back()
412 fn len(&self) -> usize { self.0.len() } in len()
415 /// An iterator over a cache's key-value pairs in least- to most-recently-used order with mutable
418 /// Accessing a cache through the iterator does _not_ affect the cache's LRU state.
423 fn next(&mut self) -> Option<(&'a K, &'a mut V)> { self.0.next() } in next()
424 fn size_hint(&self) -> (usize, Option<usize>) { self.0.size_hint() } in size_hint()
428 fn next_back(&mut self) -> Option<(&'a K, &'a mut V)> { self.0.next_back() } in next_back()
432 fn len(&self) -> usize { self.0.len() } in len()
441 let mut cache = LruCache::new(2); in test_put_and_get() localVariable
442 cache.insert(1, 10); in test_put_and_get()
443 cache.insert(2, 20); in test_put_and_get()
444 assert_eq!(cache.get_mut(&1), Some(&mut 10)); in test_put_and_get()
445 assert_eq!(cache.get_mut(&2), Some(&mut 20)); in test_put_and_get()
446 assert_eq!(cache.len(), 2); in test_put_and_get()
451 let mut cache = LruCache::new(1); in test_put_update() localVariable
452 cache.insert("1", 10); in test_put_update()
453 cache.insert("1", 19); in test_put_update()
454 assert_eq!(cache.get_mut("1"), Some(&mut 19)); in test_put_update()
455 assert_eq!(cache.len(), 1); in test_put_update()
460 let mut cache = LruCache::new(1); in test_contains_key() localVariable
461 cache.insert("1", 10); in test_contains_key()
462 assert_eq!(cache.contains_key("1"), true); in test_contains_key()
467 let mut cache = LruCache::new(2); in test_expire_lru() localVariable
468 cache.insert("foo1", "bar1"); in test_expire_lru()
469 cache.insert("foo2", "bar2"); in test_expire_lru()
470 cache.insert("foo3", "bar3"); in test_expire_lru()
471 assert!(cache.get_mut("foo1").is_none()); in test_expire_lru()
472 cache.insert("foo2", "bar2update"); in test_expire_lru()
473 cache.insert("foo4", "bar4"); in test_expire_lru()
474 assert!(cache.get_mut("foo3").is_none()); in test_expire_lru()
479 let mut cache = LruCache::new(2); in test_pop() localVariable
480 cache.insert(1, 10); in test_pop()
481 cache.insert(2, 20); in test_pop()
482 assert_eq!(cache.len(), 2); in test_pop()
483 let opt1 = cache.remove(&1); in test_pop()
486 assert!(cache.get_mut(&1).is_none()); in test_pop()
487 assert_eq!(cache.len(), 1); in test_pop()
492 let mut cache = LruCache::new(2); in test_change_capacity() localVariable
493 assert_eq!(cache.capacity(), 2); in test_change_capacity()
494 cache.insert(1, 10); in test_change_capacity()
495 cache.insert(2, 20); in test_change_capacity()
496 cache.set_capacity(1); in test_change_capacity()
497 assert!(cache.get_mut(&1).is_none()); in test_change_capacity()
498 assert_eq!(cache.capacity(), 1); in test_change_capacity()
503 let mut cache = LruCache::new(3); in test_debug() localVariable
504 cache.insert(1, 10); in test_debug()
505 cache.insert(2, 20); in test_debug()
506 cache.insert(3, 30); in test_debug()
507 assert_eq!(format!("{:?}", cache), "{3: 30, 2: 20, 1: 10}"); in test_debug()
508 cache.insert(2, 22); in test_debug()
509 assert_eq!(format!("{:?}", cache), "{2: 22, 3: 30, 1: 10}"); in test_debug()
510 cache.insert(6, 60); in test_debug()
511 assert_eq!(format!("{:?}", cache), "{6: 60, 2: 22, 3: 30}"); in test_debug()
512 cache.get_mut(&3); in test_debug()
513 assert_eq!(format!("{:?}", cache), "{3: 30, 6: 60, 2: 22}"); in test_debug()
514 cache.set_capacity(2); in test_debug()
515 assert_eq!(format!("{:?}", cache), "{3: 30, 6: 60}"); in test_debug()
520 let mut cache = LruCache::new(3); in test_remove() localVariable
521 cache.insert(1, 10); in test_remove()
522 cache.insert(2, 20); in test_remove()
523 cache.insert(3, 30); in test_remove()
524 cache.insert(4, 40); in test_remove()
525 cache.insert(5, 50); in test_remove()
526 cache.remove(&3); in test_remove()
527 cache.remove(&4); in test_remove()
528 assert!(cache.get_mut(&3).is_none()); in test_remove()
529 assert!(cache.get_mut(&4).is_none()); in test_remove()
530 cache.insert(6, 60); in test_remove()
531 cache.insert(7, 70); in test_remove()
532 cache.insert(8, 80); in test_remove()
533 assert!(cache.get_mut(&5).is_none()); in test_remove()
534 assert_eq!(cache.get_mut(&6), Some(&mut 60)); in test_remove()
535 assert_eq!(cache.get_mut(&7), Some(&mut 70)); in test_remove()
536 assert_eq!(cache.get_mut(&8), Some(&mut 80)); in test_remove()
541 let mut cache = LruCache::new(2); in test_clear() localVariable
542 cache.insert(1, 10); in test_clear()
543 cache.insert(2, 20); in test_clear()
544 cache.clear(); in test_clear()
545 assert!(cache.get_mut(&1).is_none()); in test_clear()
546 assert!(cache.get_mut(&2).is_none()); in test_clear()
547 assert_eq!(format!("{:?}", cache), "{}"); in test_clear()
552 let mut cache = LruCache::new(3); in test_iter() localVariable
553 cache.insert(1, 10); in test_iter()
554 cache.insert(2, 20); in test_iter()
555 cache.insert(3, 30); in test_iter()
556 cache.insert(4, 40); in test_iter()
557 cache.insert(5, 50); in test_iter()
558 assert_eq!(cache.iter().collect::<Vec<_>>(), in test_iter()
560 assert_eq!(cache.iter_mut().collect::<Vec<_>>(), in test_iter()
562 assert_eq!(cache.iter().rev().collect::<Vec<_>>(), in test_iter()
564 assert_eq!(cache.iter_mut().rev().collect::<Vec<_>>(), in test_iter()