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.
4 //
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.
10
11
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.
16 //!
17 //! # Example
18 //!
19 //! ```rust
20 //! use collections::LruCache;
21 //!
22 //! let mut cache: LruCache<int, int> = LruCache::new(2);
23 //! cache.put(1, 10);
24 //! cache.put(2, 20);
25 //! cache.put(3, 30);
26 //! assert!(cache.get(&1).is_none());
27 //! assert_eq!(*cache.get(&2).unwrap(), 20);
28 //! assert_eq!(*cache.get(&3).unwrap(), 30);
29 //!
30 //! cache.put(2, 22);
31 //! assert_eq!(*cache.get(&2).unwrap(), 22);
32 //!
33 //! cache.put(6, 60);
34 //! assert!(cache.get(&3).is_none());
35 //!
36 //! cache.change_capacity(1);
37 //! assert!(cache.get(&2).is_none());
38 //! ```
39
40 use std::cast;
41 use std::container::Container;
42 use std::hash::Hash;
43 use std::fmt;
44 use std::mem;
45 use std::ptr;
46
47 use HashMap;
48
49 struct KeyRef<K> { k: *K }
50
51 struct LruEntry<K, V> {
52 next: *mut LruEntry<K, V>,
53 prev: *mut LruEntry<K, V>,
54 key: K,
55 value: V,
56 }
57
58 /// An LRU Cache.
59 pub struct LruCache<K, V> {
60 map: HashMap<KeyRef<K>, Box<LruEntry<K, V>>>,
61 max_size: uint,
62 head: *mut LruEntry<K, V>,
63 }
64
65 impl<S, K: Hash<S>> Hash<S> for KeyRef<K> {
66 fn hash(&self, state: &mut S) {
67 unsafe { (*self.k).hash(state) }
68 }
69 }
70
71 impl<K: Eq> Eq for KeyRef<K> {
72 fn eq(&self, other: &KeyRef<K>) -> bool {
73 unsafe{ (*self.k).eq(&*other.k) }
74 }
75 }
76
77 impl<K: TotalEq> TotalEq for KeyRef<K> {}
78
79 impl<K, V> LruEntry<K, V> {
80 fn new(k: K, v: V) -> LruEntry<K, V> {
81 LruEntry {
82 key: k,
83 value: v,
84 next: ptr::mut_null(),
85 prev: ptr::mut_null(),
86 }
87 }
88 }
89
90 impl<K: Hash + TotalEq, V> LruCache<K, V> {
91 /// Create an LRU Cache that holds at most `capacity` items.
92 pub fn new(capacity: uint) -> LruCache<K, V> {
93 let cache = LruCache {
94 map: HashMap::new(),
95 max_size: capacity,
96 head: unsafe{ cast::transmute(box mem::uninit::<LruEntry<K, V>>()) },
97 };
98 unsafe {
99 (*cache.head).next = cache.head;
100 (*cache.head).prev = cache.head;
101 }
102 return cache;
103 }
104
105 /// Put a key-value pair into cache.
106 pub fn put(&mut self, k: K, v: V) {
107 let (node_ptr, node_opt) = match self.map.find_mut(&KeyRef{k: &k}) {
108 Some(node) => {
109 node.value = v;
110 let node_ptr: *mut LruEntry<K, V> = &mut **node;
111 (node_ptr, None)
112 }
113 None => {
114 let mut node = box LruEntry::new(k, v);
115 let node_ptr: *mut LruEntry<K, V> = &mut *node;
116 (node_ptr, Some(node))
117 }
118 };
119 match node_opt {
120 None => {
121 // Existing node, just update LRU position
122 self.detach(node_ptr);
123 self.attach(node_ptr);
124 }
125 Some(node) => {
126 let keyref = unsafe { &(*node_ptr).key };
127 self.map.swap(KeyRef{k: keyref}, node);
128 self.attach(node_ptr);
129 if self.len() > self.capacity() {
130 self.remove_lru();
131 }
132 }
133 }
134 }
135
136 /// Return a value corresponding to the key in the cache.
137 pub fn get<'a>(&'a mut self, k: &K) -> Option<&'a V> {
138 let (value, node_ptr_opt) = match self.map.find_mut(&KeyRef{k: k}) {
139 None => (None, None),
140 Some(node) => {
141 let node_ptr: *mut LruEntry<K, V> = &mut **node;
142 (Some(unsafe { &(*node_ptr).value }), Some(node_ptr))
143 }
144 };
145 match node_ptr_opt {
146 None => (),
147 Some(node_ptr) => {
148 self.detach(node_ptr);
149 self.attach(node_ptr);
150 }
151 }
152 return value;
153 }
154
155 /// Remove and return a value corresponding to the key from the cache.
156 pub fn pop(&mut self, k: &K) -> Option<V> {
157 match self.map.pop(&KeyRef{k: k}) {
158 None => None,
159 Some(lru_entry) => Some(lru_entry.value)
160 }
161 }
162
163 /// Return the maximum number of key-value pairs the cache can hold.
164 pub fn capacity(&self) -> uint {
165 self.max_size
166 }
167
168 /// Change the number of key-value pairs the cache can hold. Remove
169 /// least-recently-used key-value pairs if necessary.
170 pub fn change_capacity(&mut self, capacity: uint) {
171 for _ in range(capacity, self.len()) {
172 self.remove_lru();
173 }
174 self.max_size = capacity;
175 }
176
177 #[inline]
178 fn remove_lru(&mut self) {
179 if self.len() > 0 {
180 let lru = unsafe { (*self.head).prev };
181 self.detach(lru);
182 self.map.pop(&KeyRef{k: unsafe { &(*lru).key }});
183 }
184 }
185
186 #[inline]
187 fn detach(&mut self, node: *mut LruEntry<K, V>) {
188 unsafe {
189 (*(*node).prev).next = (*node).next;
190 (*(*node).next).prev = (*node).prev;
191 }
192 }
193
194 #[inline]
195 fn attach(&mut self, node: *mut LruEntry<K, V>) {
196 unsafe {
197 (*node).next = (*self.head).next;
198 (*node).prev = self.head;
199 (*self.head).next = node;
200 (*(*node).next).prev = node;
201 }
202 }
203 }
204
205 impl<A: fmt::Show + Hash + TotalEq, B: fmt::Show> fmt::Show for LruCache<A, B> {
206 /// Return a string that lists the key-value pairs from most-recently
207 /// used to least-recently used.
208 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
209 try!(write!(f.buf, r"\{"));
210 let mut cur = self.head;
211 for i in range(0, self.len()) {
212 if i > 0 { try!(write!(f.buf, ", ")) }
213 unsafe {
214 cur = (*cur).next;
215 try!(write!(f.buf, "{}", (*cur).key));
216 }
217 try!(write!(f.buf, ": "));
218 unsafe {
219 try!(write!(f.buf, "{}", (*cur).value));
220 }
221 }
222 write!(f.buf, r"\}")
223 }
224 }
225
226 impl<K: Hash + TotalEq, V> Container for LruCache<K, V> {
227 /// Return the number of key-value pairs in the cache.
228 fn len(&self) -> uint {
229 self.map.len()
230 }
231 }
232
233 impl<K: Hash + TotalEq, V> Mutable for LruCache<K, V> {
234 /// Clear the cache of all key-value pairs.
235 fn clear(&mut self) {
236 self.map.clear();
237 }
238 }
239
240 #[unsafe_destructor]
241 impl<K, V> Drop for LruCache<K, V> {
242 fn drop(&mut self) {
243 unsafe {
244 let node: Box<LruEntry<K, V>> = cast::transmute(self.head);
245 // Prevent compiler from trying to drop the un-initialized field in the sigil node.
246 let box LruEntry { key: k, value: v, .. } = node;
247 cast::forget(k);
248 cast::forget(v);
249 }
250 }
251 }
252
253 #[cfg(test)]
254 mod tests {
255 use super::LruCache;
256
257 fn assert_opt_eq<V: Eq>(opt: Option<&V>, v: V) {
258 assert!(opt.is_some());
259 assert!(opt.unwrap() == &v);
260 }
261
262 #[test]
263 fn test_put_and_get() {
264 let mut cache: LruCache<int, int> = LruCache::new(2);
265 cache.put(1, 10);
266 cache.put(2, 20);
267 assert_opt_eq(cache.get(&1), 10);
268 assert_opt_eq(cache.get(&2), 20);
269 assert_eq!(cache.len(), 2);
270 }
271
272 #[test]
273 fn test_put_update() {
274 let mut cache: LruCache<~str, Vec<u8>> = LruCache::new(1);
275 cache.put("1".to_owned(), vec![10, 10]);
276 cache.put("1".to_owned(), vec![10, 19]);
277 assert_opt_eq(cache.get(&"1".to_owned()), vec![10, 19]);
278 assert_eq!(cache.len(), 1);
279 }
280
281 #[test]
282 fn test_expire_lru() {
283 let mut cache: LruCache<~str, ~str> = LruCache::new(2);
284 cache.put("foo1".to_owned(), "bar1".to_owned());
285 cache.put("foo2".to_owned(), "bar2".to_owned());
286 cache.put("foo3".to_owned(), "bar3".to_owned());
287 assert!(cache.get(&"foo1".to_owned()).is_none());
288 cache.put("foo2".to_owned(), "bar2update".to_owned());
289 cache.put("foo4".to_owned(), "bar4".to_owned());
290 assert!(cache.get(&"foo3".to_owned()).is_none());
291 }
292
293 #[test]
294 fn test_pop() {
295 let mut cache: LruCache<int, int> = LruCache::new(2);
296 cache.put(1, 10);
297 cache.put(2, 20);
298 assert_eq!(cache.len(), 2);
299 let opt1 = cache.pop(&1);
300 assert!(opt1.is_some());
301 assert_eq!(opt1.unwrap(), 10);
302 assert!(cache.get(&1).is_none());
303 assert_eq!(cache.len(), 1);
304 }
305
306 #[test]
307 fn test_change_capacity() {
308 let mut cache: LruCache<int, int> = LruCache::new(2);
309 assert_eq!(cache.capacity(), 2);
310 cache.put(1, 10);
311 cache.put(2, 20);
312 cache.change_capacity(1);
313 assert!(cache.get(&1).is_none());
314 assert_eq!(cache.capacity(), 1);
315 }
316
317 #[test]
318 fn test_to_str() {
319 let mut cache: LruCache<int, int> = LruCache::new(3);
320 cache.put(1, 10);
321 cache.put(2, 20);
322 cache.put(3, 30);
323 assert_eq!(cache.to_str(), "{3: 30, 2: 20, 1: 10}".to_owned());
324 cache.put(2, 22);
325 assert_eq!(cache.to_str(), "{2: 22, 3: 30, 1: 10}".to_owned());
326 cache.put(6, 60);
327 assert_eq!(cache.to_str(), "{6: 60, 2: 22, 3: 30}".to_owned());
328 cache.get(&3);
329 assert_eq!(cache.to_str(), "{3: 30, 6: 60, 2: 22}".to_owned());
330 cache.change_capacity(2);
331 assert_eq!(cache.to_str(), "{3: 30, 6: 60}".to_owned());
332 }
333
334 #[test]
335 fn test_clear() {
336 let mut cache: LruCache<int, int> = LruCache::new(2);
337 cache.put(1, 10);
338 cache.put(2, 20);
339 cache.clear();
340 assert!(cache.get(&1).is_none());
341 assert!(cache.get(&2).is_none());
342 assert_eq!(cache.to_str(), "{}".to_owned());
343 }
344 }
libcollections/lru_cache.rs:58:18-58:18 -struct- definition:
/// An LRU Cache.
pub struct LruCache<K, V> {
map: HashMap<KeyRef<K>, Box<LruEntry<K, V>>>,
references:- 792: pub fn new(capacity: uint) -> LruCache<K, V> {
93: let cache = LruCache {
94: map: HashMap::new(),
--
241: impl<K, V> Drop for LruCache<K, V> {
242: fn drop(&mut self) {
libcollections/lru_cache.rs:50:1-50:1 -struct- definition:
struct LruEntry<K, V> {
next: *mut LruEntry<K, V>,
prev: *mut LruEntry<K, V>,
references:- 1580: fn new(k: K, v: V) -> LruEntry<K, V> {
81: LruEntry {
82: key: k,
--
194: #[inline]
195: fn attach(&mut self, node: *mut LruEntry<K, V>) {
196: unsafe {
--
243: unsafe {
244: let node: Box<LruEntry<K, V>> = cast::transmute(self.head);
245: // Prevent compiler from trying to drop the un-initialized field in the sigil node.
246: let box LruEntry { key: k, value: v, .. } = node;
247: cast::forget(k);
libcollections/lru_cache.rs:48:1-48:1 -struct- definition:
struct KeyRef<K> { k: *K }
struct LruEntry<K, V> {
next: *mut LruEntry<K, V>,
references:- 10181: self.detach(lru);
182: self.map.pop(&KeyRef{k: unsafe { &(*lru).key }});
183: }