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