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