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