1 /// 2 /// CacheLRU contains maximum `size` items 3 /// 4 /// Eviction policy: 5 /// $(UL evict TTL-ed entry (if TTL enabled), otherwise) 6 /// $(UL if oldest entry not expired - evict oldest accessed (LRU)) 7 /// 8 /// User can be informed about evicted entries via cache event list. 9 /// 10 /// 11 /// Implemented as HashMap and multi-dlist. 12 /// 13 /// $(B HashMap) keeps $(OL 14 /// $(LI cached value.) 15 /// $(LI pointer to dlist element.) 16 /// $(LI creation time (to check expiration and purge expired entry on get() without access to dlist).) 17 /// ) 18 /// 19 /// $(B dlist) keep key, creation timestamp (to check expiration) $(OL 20 /// $(LI key, so that we can remove entries from hashmap for lists heads (AccessIndex and TimeIndex)) 21 /// $(LI creation time, so that we can check expiration for 'TimeIndex') 22 /// ) 23 /// Each element in dlist have two sets of double-links - first set create order by access time, second set 24 /// for creation time. 25 /// 26 module cachetools.cachelru; 27 28 import std.typecons; 29 import std.exception; 30 31 private import std.experimental.allocator; 32 private import std.experimental.allocator.mallocator : Mallocator; 33 34 private import cachetools.internal; 35 private import cachetools.interfaces; 36 private import cachetools.containers.hashmap; 37 private import cachetools.containers.lists; 38 39 40 41 42 /// 43 class CacheLRU(K, V, Allocator = Mallocator) 44 { 45 private import core.time; 46 47 private alias TimeType = MonoTimeImpl!(ClockType.coarse); 48 49 private 50 { 51 enum size_t AccessIndex = 0; 52 enum size_t TimeIndex = 1; 53 struct ListElement { 54 K key; // we keep key here so we can remove element from map when we evict with LRU or TTL) 55 TimeType expired_at; // creation (we keep it here to check expiration for oldest element) 56 } 57 struct MapElement { 58 StoredType!V value; // value 59 TimeType expired_at; // expiration time or null 60 ListElementPtr list_element_ptr; 61 } 62 63 alias allocator = Allocator.instance; 64 alias ListElementPtr = __elements.Node*; 65 66 MultiDList!(ListElement, 2, Allocator) __elements; // keeps order by creation time and by access time 67 HashMap!(K, MapElement, Allocator) __map; // keeps MapElement by key 68 SList!(CacheEvent!(K,V), Allocator) __events; // unbounded list of cache events 69 70 // configuration 71 size_t __size = 1024; // limit num of elements in cache 72 Duration __ttl; // use TTL if __ttl > 0 73 bool __reportCacheEvents; // will user read cache events? 74 } 75 final this() { 76 __map.grow_factor(4); 77 } 78 struct CacheEventRange(K, V) 79 { 80 81 private SList!(CacheEvent!(K, V), Allocator) __events; 82 83 void opAssign(CacheEventRange!(K, V) other) 84 { 85 __events.clear(); 86 __events = other.__events; 87 } 88 89 this(ref SList!(CacheEvent!(K, V), Allocator) events) 90 { 91 __events = events; 92 } 93 94 bool empty() @safe const nothrow pure 95 { 96 return __events.empty(); 97 } 98 99 void popFront() @safe nothrow 100 { 101 __events.popFront(); 102 } 103 104 auto front() @safe 105 { 106 return __events.front(); 107 } 108 109 auto length() pure const nothrow @safe 110 { 111 return __events.length; 112 } 113 114 auto save() 115 { 116 return CacheEventRange!(K, V)(__events); 117 } 118 } 119 /// 120 final Nullable!V get(K k) 121 { 122 debug(cachetools) safe_tracef("get %s", k); 123 auto store_ptr = k in __map; 124 if ( !store_ptr ) 125 { 126 return Nullable!V(); 127 } 128 if (store_ptr.expired_at > TimeType.init && TimeType.currTime >= store_ptr.expired_at ) 129 { 130 debug(cachetools) safe_tracef("remove expired entry"); 131 // remove expired entry 132 if ( __reportCacheEvents ) 133 { 134 // store in event list 135 CacheEvent!(K,V) cache_event = {EventType.Expired, k, store_ptr.value}; 136 __events.insertBack(cache_event); 137 } 138 // and remove from storage and list 139 __map.remove(k); 140 __elements.remove(store_ptr.list_element_ptr); 141 return Nullable!V(); 142 } 143 //store_ptr.hits++; 144 auto order_p = store_ptr.list_element_ptr; 145 __elements.move_to_tail(order_p, AccessIndex); 146 return Nullable!V(store_ptr.value); 147 } 148 /// 149 final PutResult put(K k, V v, TTL ttl = TTL()) 150 out 151 { 152 assert(__result != PutResult(PutResultFlag.None)); 153 } 154 do 155 { 156 TimeType exp_time; 157 TimeType ts = TimeType.currTime; 158 159 if ( __ttl > 0.seconds && ttl.useDefault ) 160 { 161 exp_time = ts + __ttl; 162 } 163 if (ttl.value > 0.seconds) 164 { 165 exp_time = ts + ttl.value; 166 } 167 PutResult result; 168 auto store_ptr = k in __map; 169 if ( !store_ptr ) // insert element 170 { 171 result = PutResultFlag.Inserted; 172 if (__elements.length >= __size ) 173 { 174 ListElementPtr e; 175 // we have to purge 176 // 1. check if oldest element is ttled 177 if ( __elements.head(TimeIndex).expired_at >= TimeType.init && __elements.head(TimeIndex).expired_at <= ts ) 178 { 179 // purge ttl-ed element 180 e = __elements.head(TimeIndex); 181 debug(cachetools) safe_tracef("purging ttled %s, %s", *e, ts); 182 } 183 else 184 { 185 // purge lru element 186 e = __elements.head(AccessIndex); 187 debug(cachetools) safe_tracef("purging lru %s", *e); 188 } 189 assert(e !is null); 190 if ( __reportCacheEvents ) 191 { 192 auto value_ptr = e.key in __map; 193 CacheEvent!(K,V) cache_event = {EventType.Evicted, e.key, value_ptr.value}; 194 __events.insertBack(cache_event); 195 } 196 __map.remove(e.key); 197 __elements.remove(e); 198 result |= PutResultFlag.Evicted; 199 } 200 auto order_node = __elements.insert_last(ListElement(k, exp_time)); 201 MapElement e = {value:v, expired_at: exp_time, list_element_ptr: order_node}; 202 __map.put(k, e); 203 } 204 else // update element 205 { 206 result = PutResultFlag.Replaced; 207 debug(cachetools) safe_tracef("update %s", *store_ptr); 208 ListElementPtr e = store_ptr.list_element_ptr; 209 e.expired_at = exp_time; 210 __elements.move_to_tail(e, TimeIndex); 211 if ( __reportCacheEvents ) 212 { 213 auto v_ptr = e.key in __map; 214 CacheEvent!(K,V) cache_event = {EventType.Updated, e.key, v_ptr.value}; 215 __events.insertBack(cache_event); 216 } 217 store_ptr.value = v; 218 store_ptr.expired_at = exp_time; 219 } 220 return result; 221 } 222 223 /// 224 final bool remove(K k) 225 { 226 debug(cachetools) safe_tracef("remove from cache %s", k); 227 auto map_ptr = k in __map; 228 if ( !map_ptr ) // do nothing 229 { 230 return false; 231 } 232 ListElementPtr e = map_ptr.list_element_ptr; 233 if ( __reportCacheEvents ) 234 { 235 auto v_ptr = e.key in __map; 236 CacheEvent!(K,V) cache_event = {EventType.Removed, e.key, v_ptr.value}; 237 __events.insertBack(cache_event); 238 } 239 __map.remove(e.key); 240 __elements.remove(e); 241 return true; 242 } 243 244 /// 245 final void clear() 246 { 247 if ( __reportCacheEvents ) 248 { 249 foreach(pair; __map.byPair) 250 { 251 CacheEvent!(K,V) cache_event = {EventType.Removed, pair.key, pair.value.value}; 252 __events.insertBack(cache_event); 253 } 254 } 255 __map.clear(); 256 __elements.clear(); 257 } 258 259 size_t length() pure nothrow const @safe @nogc 260 { 261 return __elements.length; 262 } 263 264 auto size(size_t s) pure nothrow @safe @nogc 265 { 266 __size = s; 267 return this; 268 } 269 270 /// 271 size_t size() pure nothrow const @safe @nogc 272 { 273 return __size; 274 } 275 276 deprecated("Use ttl(Durauion) insteda") 277 final auto ttl(uint d) pure nothrow @safe @nogc 278 { 279 __ttl = d.seconds; 280 return this; 281 } 282 283 final auto ttl(Duration d) pure nothrow @safe @nogc 284 { 285 __ttl = d; 286 return this; 287 } 288 289 /// 290 final Duration ttl() pure nothrow const @safe @nogc 291 { 292 return __ttl; 293 } 294 /// 295 final auto enableCacheEvents() pure nothrow @safe @nogc 296 { 297 __reportCacheEvents = true; 298 return this; 299 } 300 /// 301 final auto cacheEvents() 302 { 303 auto r = CacheEventRange!(K, V)(__events); 304 __events.clear; 305 return r; 306 } 307 } 308 309 /// 310 unittest 311 { 312 import core.thread; 313 314 // very basic example 315 auto lru = new CacheLRU!(int, string); 316 317 lru.size(4).ttl(1.seconds); 318 assert(lru.size == 4); 319 assert(lru.ttl == 1.seconds); 320 321 assert(lru.length == 0); 322 lru.put(1, "one"); 323 lru.put(2, "two"); 324 lru.put(3, "three"); 325 lru.put(4, "four"); 326 327 auto v = lru.get(2); 328 assert(v=="two"); 329 v = lru.get(4); 330 assert(v=="four"); 331 332 assert(lru.length == 4); 333 // As we reached cache capacity, next `put` must evict oldest never accessed key '1' 334 lru.put(5, "five"); 335 assert(lru.length == 4); // length did not changed 336 assert(lru.get(1).isNull); // really evicted 337 338 Thread.sleep(2.seconds); 339 v = lru.get(2); // it must be expired by ttl 340 assert(v.isNull); 341 assert(lru.length == 3); 342 v = lru.get(3); // it must be expired by ttl too 343 assert(v.isNull); 344 assert(lru.length == 2); 345 } 346 347 @safe unittest 348 { 349 import std.stdio; 350 import std.datetime; 351 import core.thread; 352 import std.algorithm; 353 import std.experimental.logger; 354 globalLogLevel = LogLevel.info; 355 info("Testing LRU"); 356 PutResult r; 357 358 auto lru = new CacheLRU!(int, string); 359 lru.size(4).ttl(1.seconds).enableCacheEvents(); 360 assert(lru.size == 4); 361 assert(lru.ttl == 1.seconds); 362 assert(lru.length == 0); 363 364 r = lru.put(1, "one"); assert(r == PutResult(PutResultFlag.Inserted)); 365 r = lru.put(2, "two"); assert(r == PutResult(PutResultFlag.Inserted)); 366 auto v = lru.get(1); // "1" should move to head 367 assert(v=="one"); 368 r = lru.put(3, "three"); assert(r & PutResultFlag.Inserted); 369 r = lru.put(4, "four"); assert(r & PutResultFlag.Inserted); 370 assert(lru.length == 4); 371 // next put should evict "2" 372 r = lru.put(5, "five"); assert(r == PutResult(PutResultFlag.Evicted, PutResultFlag.Inserted)); 373 () @trusted {Thread.sleep(2.seconds);}(); 374 v = lru.get(1); // it must be expired by ttl 375 assert(v.isNull); 376 assert(lru.length == 3); 377 r = lru.put(6, "six"); assert(r == PutResult(PutResultFlag.Inserted)); 378 assert(lru.length == 4); 379 r = lru.put(7, "seven"); assert(r == PutResult(PutResultFlag.Evicted, PutResultFlag.Inserted)); 380 assert(lru.length == 4); 381 lru.put(7, "7"); 382 assert(lru.length == 4); 383 assert(lru.get(7) == "7"); 384 lru.clear(); 385 assert(lru.length == 0); 386 assert(lru.get(7).isNull); 387 auto events = lru.cacheEvents(); 388 assert(!events.empty); 389 assert(events.length() == 8); 390 assert(equal(events.map!"a.key", [2,1,3,7,6,7,5,4])); 391 assert(equal(events.map!"a.val", ["two","one","three","seven", "six", "7", "five", "four"])); 392 } 393 394 // check if we can cache with immutable struct keys 395 @safe unittest 396 { 397 struct S {int s;} 398 CacheLRU!(immutable S, string) cache = new CacheLRU!(immutable S, string); 399 immutable S s1 = immutable S(1); 400 cache.put(s1, "one"); 401 auto s11 = cache.get(s1); 402 assert(s11 == "one"); 403 assert(cache.remove(s1)); 404 assert(!cache.remove(S(2))); 405 } 406 407 // check if we can cache with immutable struct values 408 @safe unittest 409 { 410 struct S 411 { 412 int s; 413 } 414 auto cache = new CacheLRU!(string, immutable S); 415 immutable S s1 = immutable S(1); 416 cache.put("one", s1); 417 auto s11 = cache.get("one"); 418 assert(s11 == s1); 419 immutable S s12 = immutable S(12); 420 cache.put("one", s12); 421 auto s121 = cache.get("one"); 422 assert(s121 == s12); 423 } 424 425 // check if we can cache with immutable class keys and values 426 @safe unittest 427 { 428 import cachetools.hash: hash_function; 429 class C 430 { 431 int s; 432 this(int v) 433 { 434 s = v; 435 } 436 override hash_t toHash() const 437 { 438 return hash_function(s); 439 } 440 bool opEquals(const C other) pure const @safe 441 { 442 auto i = [1,2]; 443 return s == other.s; 444 } 445 } 446 CacheLRU!(immutable C, string) ick = new CacheLRU!(immutable C, string); 447 immutable C s1 = new immutable C(1); 448 ick.put(s1, "one"); 449 auto s11 = ick.get(s1); 450 assert(s11 == "one"); 451 452 CacheLRU!(string, immutable C) icv = new CacheLRU!(string, immutable C); 453 immutable C s1v = new immutable C(1); 454 icv.put("one", s1v); 455 auto s11v = icv.get("one"); 456 assert(s11v is s1v); 457 } 458 459 unittest 460 { 461 import std.experimental.allocator.mallocator; 462 import core.time; 463 464 alias allocator = Mallocator.instance; 465 alias Cache = CacheLRU!(int, string); 466 467 auto lru = make!(Cache)(allocator); 468 469 lru.size = 2048; // keep 2048 elements in cache 470 lru.ttl = 60.seconds; // set 60 seconds TTL for items in cache 471 472 lru.put(1, "one"); 473 auto v = lru.get(0); 474 assert(v.isNull); // no such item in cache 475 v = lru.get(1); 476 assert(v == "one"); // 1 is in cache 477 lru.remove(1); 478 dispose(allocator, lru); 479 } 480 481 /// 482 @safe nothrow unittest 483 { 484 auto lru = new CacheLRU!(int, string); 485 () @nogc @safe nothrow { 486 lru.enableCacheEvents(); 487 lru.put(1, "one"); 488 assert(lru.get(1) == "one"); 489 lru.put(1, "next one"); 490 assert(lru.get(1) == "next one"); 491 auto events = lru.cacheEvents(); 492 assert(events.length == 1); // replaced old value 493 lru.put(2, "two"); 494 lru.clear(); 495 events = lru.cacheEvents(); 496 assert(events.length == 2); // removed keys 1 and 2 during clear() 497 }(); 498 } 499 500 // test unsafe types 501 unittest 502 { 503 import std.variant; 504 import std.stdio; 505 import std.experimental.logger; 506 507 alias UnsafeType = Algebraic!(int, string); 508 509 auto c = new CacheLRU!(UnsafeType, int); 510 c.enableCacheEvents; 511 512 UnsafeType abc = "abc"; 513 UnsafeType def = "abc"; 514 UnsafeType one = 1; 515 c.put(abc, 1); 516 c.put(one, 2); 517 assert(abc == def); 518 assert(c.get(def) == 1); 519 assert(c.get(one) == 2); 520 c.remove(abc); 521 auto r = c.cacheEvents; 522 523 import std.json; 524 auto csj = new CacheLRU!(string, JSONValue); 525 auto cjs = new CacheLRU!(JSONValue, string); 526 527 class C 528 { 529 } 530 531 auto c1 = new CacheLRU!(C, string); 532 auto cob1 = new C(); 533 auto cob2 = new C(); 534 c1.put(cob1, "cob1"); 535 c1.put(cob2, "cob2"); 536 assert(c1.get(cob1) == "cob1"); 537 assert(c1.get(cob2) == "cob2"); 538 }