1extern crate slab;
2
3use slab::Slab;
4use std::borrow::Borrow;
5use std::cmp::{max, min};
6use std::collections::HashMap;
7use std::collections::VecDeque;
8use std::hash::Hash;
9use std::marker::PhantomData;
10
11type Token = usize;
12
13struct Entry<K, V>
14where
15 K: Eq + Hash,
16{
17 key: K,
18 value: V,
19 prev: Option<Token>,
20 next: Option<Token>,
21 is_history: bool,
22 is_reference: bool,
23 is_longterm: bool,
24}
25
26pub struct CartCache<K, V>
27where
28 K: Eq + Hash,
29{
30 slab: Slab<Entry<K, V>>,
31 map: HashMap<K, Token>,
32 t1: VecDeque<Token>,
33 t2: VecDeque<Token>,
34 b1: XLinkedList<K, V>,
35 b2: XLinkedList<K, V>,
36 c: usize,
37 capacity: usize,
38 p: usize,
39 q: usize,
40 shortterm_count: usize,
41 longterm_count: usize,
42 inserted: u64,
43 evicted: u64,
44}
45
46impl<K: Eq + Hash, V> CartCache<K, V> {
47 pub fn new(capacity: usize) -> Result<CartCache<K, V>, &'static str> {
48 if capacity == 0 {
49 return Err("Cache length cannot be zero");
50 }
51 let c = capacity / 2;
52 let slab = Slab::with_capacity(capacity);
53 let map = HashMap::with_capacity(c);
54 let t1 = VecDeque::with_capacity(c);
55 let t2 = VecDeque::with_capacity(c);
56 let b1 = XLinkedList::new();
57 let b2 = XLinkedList::new();
58
59 let cache = CartCache {
60 slab,
61 map,
62 t1,
63 t2,
64 b1,
65 b2,
66 c,
67 capacity,
68 p: 0,
69 q: 0,
70 shortterm_count: 0,
71 longterm_count: 0,
72 inserted: 0,
73 evicted: 0,
74 };
75 Ok(cache)
76 }
77
78 pub fn capacity(&self) -> usize {
79 self.capacity
80 }
81
82 pub fn len(&self) -> usize {
83 self.map.len()
84 }
85
86 pub fn is_empty(&self) -> bool {
87 self.len() == 0
88 }
89
90 pub fn frequent_len(&self) -> usize {
91 self.longterm_count + self.b2.len()
92 }
93
94 pub fn recent_len(&self) -> usize {
95 self.shortterm_count + self.b1.len()
96 }
97
98 pub fn inserted(&self) -> u64 {
99 self.inserted
100 }
101
102 pub fn evicted(&self) -> u64 {
103 self.evicted
104 }
105
106 pub fn clear(&mut self) {
107 self.slab.clear();
108 self.map.clear();
109 self.t1.clear();
110 self.t2.clear();
111 self.b1.clear();
112 self.b2.clear();
113 self.p = 0;
114 self.q = 0;
115 self.shortterm_count = 0;
116 self.longterm_count = 0;
117 self.inserted = 0;
118 self.evicted = 0;
119 }
120
121 pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool
122 where
123 Q: Hash + Eq,
124 K: Borrow<Q>,
125 {
126 self.map.contains_key(key)
127 }
128
129 pub fn get<Q: ?Sized>(&mut self, key: &Q) -> Option<&V>
130 where
131 Q: Hash + Eq,
132 K: Borrow<Q>,
133 {
134 match self.map.get(key) {
135 Some(&token) => {
136 let cached_entry = &mut self.slab[token];
137 cached_entry.is_reference = true;
138 Some(&cached_entry.value)
139 }
140 None => None,
141 }
142 }
143
144 pub fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V>
145 where
146 Q: Hash + Eq,
147 K: Borrow<Q>,
148 {
149 match self.map.get(key) {
150 Some(&token) => {
151 let cached_entry = &mut self.slab[token];
152 cached_entry.is_reference = true;
153 Some(&mut cached_entry.value)
154 }
155 None => None,
156 }
157 }
158
159 fn evict_if_full(&mut self, is_history: bool) {
160 if self.t1.len() + self.t2.len() >= self.c {
161 self.replace();
162 if !is_history && self.b1.len() + self.b2.len() >= self.c + 1 {
163 if self.b1.len() > max(0, self.q) || self.b2.is_empty() {
164 let token = self
165 .b1
166 .pop_front(&mut self.slab)
167 .expect("Front element vanished");
168 self.map.remove(&self.slab[token].key);
169 self.slab.remove(token);
170 } else if !self.b2.is_empty() {
171 let token = self
172 .b2
173 .pop_front(&mut self.slab)
174 .expect("Front element vanished");
175 self.map.remove(&self.slab[token].key);
176 self.slab.remove(token);
177 }
178 }
179 self.evicted += 1;
180 }
181 }
182
183 fn insert_new_entry(&mut self, key: K, value: V)
184 where
185 K: Hash + Eq + Clone,
186 {
187 let entry = Entry {
188 key: key.clone(),
189 value,
190 prev: None,
191 next: None,
192 is_history: false,
193 is_reference: false,
194 is_longterm: false,
195 };
196 let token = self.slab.insert(entry);
197 self.t1.push_back(token);
198 self.shortterm_count += 1;
199 self.map.insert(key, token);
200 self.inserted += 1;
201 }
202
203 fn promote_from_b1(&mut self, token: Token) {
204 self.p = min(
205 self.p + max(1, self.shortterm_count / self.b1.len()),
206 self.c,
207 );
208 {
209 let cached_entry = &mut self.slab[token];
210 cached_entry.is_history = false;
211 cached_entry.is_reference = false;
212 cached_entry.is_longterm = true;
213 self.longterm_count += 1;
214 }
215 self.b1.remove(&mut self.slab, token);
216 self.t1.push_back(token);
217 }
218
219 fn promote_from_b2(&mut self, token: Token) {
220 let t = max(1, self.longterm_count / self.b2.len());
221 self.p = if self.p > t { self.p - t } else { 0 };
222 {
223 let cached_entry = &mut self.slab[token];
224 cached_entry.is_history = false;
225 cached_entry.is_reference = false;
226 assert!(cached_entry.is_longterm);
227 self.longterm_count += 1;
228 }
229 self.b2.remove(&mut self.slab, token);
230 self.t1.push_back(token);
231 if self.t2.len() + self.b2.len() + self.t1.len() - self.shortterm_count >= self.c {
232 self.q = min(self.q + 1, self.capacity - self.t1.len());
233 }
234 }
235
236 pub fn insert(&mut self, key: K, value: V) -> bool
237 where
238 K: Hash + Eq + Clone,
239 {
240 let (token, is_history, is_longterm) = match self.map.get_mut(&key) {
241 Some(&mut token) => {
242 let cached_entry = &mut self.slab[token];
243 if !cached_entry.is_history {
244 cached_entry.is_reference = true;
245 cached_entry.value = value;
246 return true;
247 }
248 (
249 Some(token),
250 cached_entry.is_history,
251 cached_entry.is_longterm,
252 )
253 }
254 None => (None, false, false),
255 };
256 self.evict_if_full(is_history);
257 if !is_history {
258 self.insert_new_entry(key, value);
259 } else if !is_longterm {
260 self.promote_from_b1(token.unwrap());
261 } else {
262 self.promote_from_b2(token.unwrap());
263 }
264 false
265 }
266
267 fn replace_t2(&mut self) {
268 loop {
269 match self.t2.front() {
270 None => break,
271 Some(&token) => {
272 if !self.slab[token].is_reference {
273 break;
274 }
275 }
276 }
277 let token = self.t2.pop_front().expect("Front element vanished");
278 let found = &mut self.slab[token];
279 found.is_reference = false;
280 self.t1.push_back(token);
281 if self.t2.len() + self.b2.len() + self.t1.len() - self.shortterm_count >= self.c {
282 self.q = min(self.q + 1, self.capacity - self.t1.len())
283 }
284 }
285 }
286
287 fn replace_t1(&mut self) {
288 loop {
289 match self.t1.front() {
290 None => break,
291 Some(&token) => {
292 let found = &mut self.slab[token];
293 if !(found.is_longterm || found.is_reference) {
294 break;
295 }
296 }
297 }
298 let token = self.t1.pop_front().expect("Front element vanished");
299 let found = &mut self.slab[token];
300 if found.is_reference {
301 found.is_reference = false;
302 self.t1.push_back(token);
303 if self.t1.len() >= min(self.p + 1, self.b1.len()) && !found.is_longterm {
304 assert!(!found.is_longterm);
305 found.is_longterm = true;
306 self.shortterm_count -= 1;
307 self.longterm_count += 1;
308 }
309 } else {
310 self.t2.push_back(token);
311 if self.q > 0 {
312 self.q = max(self.q - 1, self.c - self.t1.len());
313 } else {
314 self.q = self.c - self.t1.len();
315 }
316 }
317 }
318 }
319
320 fn demote(&mut self) {
321 if self.t1.len() >= max(1, self.p) {
322 if let Some(token) = self.t1.pop_front() {
323 {
324 let demoted = &mut self.slab[token];
325 assert!(!demoted.is_history);
326 demoted.is_history = true;
327 assert!(!demoted.is_longterm);
328 self.shortterm_count -= 1;
329 }
330 self.b1.push_back(&mut self.slab, token);
331 }
332 } else if let Some(token) = self.t2.pop_front() {
333 {
334 let demoted = &mut self.slab[token];
335 assert!(!demoted.is_history);
336 demoted.is_history = true;
337 assert!(demoted.is_longterm);
338 self.longterm_count -= 1;
339 }
340 self.b2.push_back(&mut self.slab, token);
341 }
342 }
343
344 fn replace(&mut self) {
345 self.replace_t2();
346 self.replace_t1();
347 self.demote();
348 }
349}
350
351trait XLinkedNode {
352 fn prev(&self) -> Option<Token>;
353 fn next(&self) -> Option<Token>;
354 fn set_prev(&mut self, prev: Option<Token>);
355 fn set_next(&mut self, next: Option<Token>);
356}
357
358impl<K, V> XLinkedNode for Entry<K, V>
359where
360 K: Eq + Hash,
361{
362 #[inline]
363 fn prev(&self) -> Option<Token> {
364 self.prev
365 }
366
367 #[inline]
368 fn next(&self) -> Option<Token> {
369 self.next
370 }
371
372 #[inline]
373 fn set_prev(&mut self, prev: Option<Token>) {
374 self.prev = prev;
375 }
376
377 #[inline]
378 fn set_next(&mut self, next: Option<Token>) {
379 self.next = next;
380 }
381}
382
383struct XLinkedList<K, V>
384where
385 K: Eq + Hash,
386{
387 head: Option<Token>,
388 tail: Option<Token>,
389 len: usize,
390 phantom_k: PhantomData<K>,
391 phantom_v: PhantomData<V>,
392}
393
394impl<K, V> XLinkedList<K, V>
395where
396 K: Eq + Hash,
397{
398 fn new() -> Self {
399 XLinkedList {
400 head: None,
401 tail: None,
402 len: 0,
403 phantom_k: PhantomData,
404 phantom_v: PhantomData,
405 }
406 }
407
408 #[inline]
409 fn len(&self) -> usize {
410 self.len
411 }
412
413 #[inline]
414 fn is_empty(&self) -> bool {
415 self.len == 0
416 }
417
418 #[inline]
419 fn clear(&mut self) {
420 self.len = 0;
421 self.head = None;
422 self.tail = None;
423 }
424
425 fn remove(&mut self, slab: &mut Slab<Entry<K, V>>, token: Token) {
426 let (prev_token, next_token) = {
427 let elt = &mut slab[token];
428 let prev_token = elt.prev();
429 elt.set_prev(None);
430 let next_token = elt.next();
431 elt.set_next(None);
432 (prev_token, next_token)
433 };
434 if let Some(prev_token) = prev_token {
435 slab[prev_token].set_next(next_token);
436 } else {
437 self.head = next_token;
438 }
439 if let Some(next_token) = next_token {
440 slab[next_token].set_prev(prev_token);
441 } else {
442 self.tail = prev_token;
443 }
444 self.len -= 1;
445 }
446
447 fn push_back(&mut self, slab: &mut Slab<Entry<K, V>>, token: Token) {
448 {
449 let elt = &mut slab[token];
450 elt.set_prev(self.tail);
451 elt.set_next(None);
452 }
453 if let Some(tail_token) = self.tail {
454 slab[tail_token].set_next(Some(token));
455 }
456 self.tail = Some(token);
457 self.head = self.head.or(self.tail);
458 self.len += 1;
459 }
460
461 pub fn pop_front(&mut self, slab: &mut Slab<Entry<K, V>>) -> Option<Token> {
462 let head_token = self.head;
463 if let Some(head_token) = head_token {
464 let new_head_token = {
465 let former_head = &mut slab[head_token];
466 let next_token = former_head.next();
467 former_head.set_next(None);
468 next_token
469 };
470 match new_head_token {
471 None => self.clear(),
472 Some(new_head_token) => {
473 slab[new_head_token].set_prev(None);
474 self.head = Some(new_head_token);
475 self.len -= 1;
476 }
477 }
478 }
479 head_token
480 }
481}
482
483#[cfg(test)]
484mod tests {
485 extern crate rand;
486 use self::rand::prelude::*;
487 use crate::CartCache;
488
489 #[test]
490 fn random_inserts() {
491 let count = 1_000_000;
492 let mut cached: u64 = 0;
493 let mut cache: CartCache<u8, u8> = CartCache::new(128).unwrap();
494 let mut rng = thread_rng();
495
496 for _ in 0..count {
497 let key: u8 = rng.gen();
498 cache.insert(key, key);
499 let key: u8 = rng.gen();
500 if cache.get(&key).is_some() {
501 cached += 1;
502 }
503 }
504 assert!(cached > count / 3);
505 }
506}