1 module tagion.utils.LRU; 2 3 // EvictCallback is used to get a callback when a cache entry is evicted 4 5 //import std.stdio; 6 import std.algorithm : map; 7 import std.conv; 8 import std.format; 9 import std.traits; 10 import tagion.utils.DList; 11 import tagion.utils.Result; 12 13 @safe: 14 // LRU implements a non-thread safe fixed size LRU cache 15 class LRU(K, V) { 16 enum does_not_have_immutable_members = __traits(compiles, { V v; void f(ref V _v) { 17 _v = v;} }); 18 19 @safe @nogc struct Entry { 20 K key; 21 V value; 22 this(K key, ref V value) pure nothrow { 23 this.key = key; 24 this.value = value; 25 } 26 } 27 28 alias EvictList = DList!(Entry*); 29 alias Element = EvictList.Element; 30 private EvictList evictList; 31 private Element*[K] items; 32 alias void delegate(scope const(K), Element*) @safe nothrow EvictCallback; 33 immutable uint size; 34 private EvictCallback onEvict; 35 36 // NewLRU constructs an LRU of the given size 37 // size zero means unlimited 38 this(EvictCallback onEvict = null, immutable uint size = 0) pure nothrow { 39 this.size = size; 40 //evictList = EvictList; 41 this.onEvict = onEvict; 42 } 43 44 // purge is used to completely clear the cache 45 void purge() { 46 foreach (ref k, ref e; items) { 47 if (onEvict !is null) { 48 onEvict(k, e); 49 } 50 } 51 items = null; 52 evictList = EvictList.init; 53 } 54 55 // add adds a value to the cache. Returns true if an eviction occurred. 56 bool add(const(K) key, ref V value) { 57 // Check for existing item 58 auto ent = key in items; 59 if (ent !is null) { 60 auto element = *ent; 61 evictList.moveToFront(element); 62 // onEvict(element, CallbackType.MOVEFRONT); 63 return false; 64 } 65 66 // Add new item 67 auto entry = new Entry(key, value); 68 auto element = evictList.unshift(entry); 69 items[key] = element; 70 71 bool evict = (size != 0) && (evictList.length > size); 72 // Verify size not exceeded 73 if (evict) { 74 // Remove the oldest element 75 removeOldest; 76 } 77 return evict; 78 } 79 80 // updates the value if exists or inserts if flag pecified 81 bool update(const(K) key, ref V value, bool upsert = false){ 82 auto ent = key in items; 83 if (ent !is null) { 84 auto element = *ent; 85 element.entry.value = value; 86 evictList.moveToFront(element); 87 return true; 88 } 89 return upsert ? add(key,value) : false; 90 } 91 92 // Get looks up a key's value from the cache. 93 static if (does_not_have_immutable_members) { 94 bool get(scope const(K) key, ref V value) nothrow { 95 auto ent = key in items; 96 if (ent !is null) { 97 auto element = *ent; 98 evictList.moveToFront(element); 99 value = element.entry.value; 100 return true; 101 } 102 return false; 103 } 104 } 105 106 V opIndex(scope const(K) key) { 107 static if (does_not_have_immutable_members) { 108 V value; 109 const found = get(key, value); 110 static if (hasMember!(V, "undefined")) { 111 if (!found) { 112 return V.undefined; 113 } 114 } else { 115 if(!found) { 116 return V.init; 117 } 118 } 119 return value; 120 } 121 else { 122 auto ent = key in items; 123 if (ent !is null) { 124 auto element = *ent; 125 evictList.moveToFront(element); 126 return element.entry.value; 127 } 128 static if (hasMember!(V, "undefined")) { 129 return V.undefined; 130 } else { 131 return V.init; 132 } 133 134 } 135 } 136 137 void opIndexAssign(ref V value, const(K) key) { 138 add(key, value); 139 } 140 141 // Check if a key is in the cache, without updating the recent-ness 142 // or deleting it for being stale. 143 @nogc 144 bool contains(scope const(K) key) const pure nothrow { 145 return (key in items) !is null; 146 } 147 148 // Returns the key value (or undefined if not found) without updating 149 // the "recently used"-ness of the key. 150 static if (does_not_have_immutable_members) { 151 @nogc 152 bool peek(const(K) key, ref V value) pure nothrow { 153 auto ent = key in items; 154 if (ent !is null) { 155 value = (*ent).entry.value; 156 return true; 157 } 158 return false; 159 } 160 } 161 162 V peek(const(K) key) { 163 static if (does_not_have_immutable_members) { 164 V value; 165 peek(key, value); 166 return value; 167 } 168 else { 169 auto ent = key in items; 170 if (ent !is null) { 171 return (*ent).entry.value; 172 } 173 static if (hasMember!(V, "undefined")) { 174 return V.undefined; 175 } else { 176 return V.init; 177 } 178 } 179 } 180 181 // Remove removes the provided key from the cache, returning if the 182 // key was contained. 183 184 bool remove(scope const(K) key) nothrow { 185 auto ent = key in items; 186 if (ent !is null) { 187 auto element = *ent; 188 if (onEvict !is null) { 189 onEvict(key, element); 190 } 191 evictList.remove(element); 192 items.remove(key); 193 return true; 194 } 195 return false; 196 } 197 198 @nogc 199 void setEvict(EvictCallback evict) nothrow { 200 onEvict = evict; 201 } 202 203 // RemoveOldest removes the oldest item from the cache. 204 const(Result!(Entry*)) removeOldest() nothrow { 205 const e = evictList.pop; 206 if (!e.error) { 207 auto element = items[e.value.key]; 208 items.remove(e.value.key); 209 if (onEvict !is null) { 210 onEvict(e.value.key, element); 211 } 212 } 213 return e; 214 } 215 216 // GetOldest returns the oldest entry 217 @nogc 218 const(Entry)* getOldest() const pure nothrow { 219 auto last = evictList.last; 220 if (last) { 221 return evictList.last.entry; 222 } 223 else { 224 return null; 225 } 226 } 227 228 /// keys returns a slice of the keys in the cache, from oldest to newest. 229 @nogc 230 auto keys() pure nothrow { 231 return evictList.revert.map!(a => a.key); 232 } 233 234 // length returns the number of items in the cache. 235 @nogc 236 uint length() pure const nothrow { 237 return evictList.length; 238 } 239 240 @nogc EvictList.Range!false opSlice() nothrow { 241 return evictList[]; 242 } 243 244 invariant { 245 assert(items.length == evictList.length); 246 } 247 } 248 249 unittest { 250 alias LRU!(int, int) TestLRU; 251 uint evictCounter; 252 253 void onEvicted(scope const(int) i, TestLRU.Element* e) @safe { 254 assert(e.entry.key == e.entry.value); 255 evictCounter++; 256 } 257 258 enum amount = 8; 259 auto l = new TestLRU(&onEvicted, amount); 260 foreach (i; 0 .. amount) { 261 l.add(i, i); 262 } 263 } 264 265 unittest { 266 alias LRU!(int, int) TestLRU; 267 uint evictCounter; 268 269 void onEvicted(scope const(int) i, TestLRU.Element* e) @safe { 270 assert(e.entry.key == e.entry.value); 271 evictCounter++; 272 } 273 274 enum amount = 8; 275 auto l = new TestLRU(&onEvicted, amount); 276 foreach (i; 0 .. amount * 2) { 277 l.add(i, i); 278 if (i < amount) { 279 assert(i + 1 == l.length); 280 } 281 else { 282 assert(amount == l.length); 283 } 284 } 285 assert(l.length == amount); 286 assert(evictCounter == amount); 287 int v; 288 bool ok; 289 import std.range : enumerate; 290 291 foreach (i, k; l.keys.enumerate) { 292 ok = l.get(k, v); 293 assert(ok); 294 assert(k == v); 295 assert(v == i + amount); 296 } 297 foreach (j; 0 .. amount) { 298 ok = l.get(j, v); 299 assert(!ok, "should be evicted"); 300 } 301 302 foreach (j; amount .. amount * 2) { 303 ok = l.get(j, v); 304 assert(ok, "should not be evicted"); 305 } 306 enum amount2 = (amount + amount / 2); 307 foreach (j; amount .. amount2) { 308 ok = l.remove(j); 309 assert(ok, "should contain j"); 310 ok = l.remove(j); 311 assert(!ok, "should not be contained"); 312 ok = l.get(j, v); 313 assert(!ok, "should be deleted"); 314 } 315 316 l.get(amount2, v); // expect amount2 to be last key in l.Keys() 317 318 foreach (i, k; l.keys.enumerate) { 319 enum amount_i = amount / 2 - 1; 320 bool not_good = ((i < amount_i) && (k != i + amount2 + 1)) || ((i == amount_i) && ( 321 k != amount2)); 322 assert(!not_good, "out of order key: " ~ to!string(k)); 323 } 324 325 l.purge(); 326 assert(l.length == 0); 327 328 ok = l.get(200, v); 329 assert(!ok, "should contain nothing"); 330 } 331 332 unittest { // getOldest removeOldest 333 alias LRU!(int, int) TestLRU; 334 uint evictCounter; 335 void onEvicted(scope const(int) i, TestLRU.Element* e) @safe { 336 assert(e.entry.key == e.entry.value); 337 evictCounter++; 338 } 339 340 enum amount = 8; 341 auto l = new TestLRU(&onEvicted, amount); 342 bool ok; 343 foreach (i; 0 .. amount * 2) { 344 l.add(i, i); 345 } 346 auto e = l.getOldest(); 347 assert(e !is null, "missing"); 348 assert(e.value == amount, "bad value " ~ to!string(e.key)); 349 e = l.removeOldest.value; 350 assert(e !is null, "missing"); 351 assert(e.value == amount, "bad value " ~ to!string(e.key)); 352 e = l.removeOldest.value; 353 assert(e !is null, "missing"); 354 assert(e.value == amount + 1, "bad value " ~ to!string(e.value)); 355 } 356 357 // Test that Add returns true/false if an eviction occurred 358 unittest { // add 359 alias LRU!(int, int) TestLRU; 360 uint evictCounter; 361 void onEvicted(scope const(int) i, TestLRU.Element* e) @safe { 362 assert(e.entry.key == e.entry.value); 363 evictCounter++; 364 } 365 366 bool ok; 367 auto l = new TestLRU(&onEvicted, 1); 368 // evictCounter := 0 369 // onEvicted := func(k interface{}, v interface{}) { 370 // evictCounter += 1 371 // } 372 373 // l := NewLRU(1, onEvicted) 374 int x = 1; 375 ok = l.add(1, x); 376 assert(!ok); 377 assert(evictCounter == 0, "should not have an eviction"); 378 x++; 379 ok = l.add(2, x); 380 assert(ok); 381 assert(evictCounter == 1, "should have an eviction"); 382 } 383 384 // Test that Contains doesn't update recent-ness 385 //func TestLRU_Contains(t *testing.T) { 386 unittest { 387 alias LRU!(int, int) TestLRU; 388 void onEvicted(scope const(int) i, TestLRU.Element* e) @safe { 389 assert(e.entry.key == e.entry.value); 390 } 391 392 auto l = new TestLRU(&onEvicted, 2); 393 // l := NewLRU(2, nil) 394 395 int x = 1; 396 397 l.add(1, x); 398 x++; 399 l.add(2, x); 400 x++; 401 assert(l.contains(1), "1 should be contained"); 402 l.add(3, x); 403 assert(!l.contains(1), "Contains should not have updated recent-ness of 1"); 404 405 } 406 407 // Test that Peek doesn't update recent-ness 408 //func TestLRU_Peek(t *testing.T) { 409 unittest { 410 alias LRU!(int, int) TestLRU; 411 void onEvicted(scope const(int) i, TestLRU.Element* e) @safe { 412 assert(e.entry.key == e.entry.value); 413 } 414 415 auto l = new TestLRU(&onEvicted, 2); 416 // l := NewLRU(2, nil) 417 int x = 1; 418 419 l.add(1, x); 420 x++; 421 l.add(2, x); 422 x++; 423 int v; 424 bool ok; 425 ok = l.peek(1, v); 426 assert(ok); 427 assert(v == 1, "1 should be set to 1 not " ~ to!string(v)); 428 l.add(3, x); 429 assert(!l.contains(1), "should not have updated recent-ness of 1"); 430 } 431 432 unittest { // Test undefined 433 @safe struct E { 434 string x; 435 static E undefined() { 436 return E("Not found"); 437 } 438 } 439 440 alias TestLRU = LRU!(int, E); 441 uint count; 442 443 void onEvicted(scope const(int) i, TestLRU.Element* e) @safe { 444 count++; 445 } 446 447 auto l = new TestLRU(&onEvicted); 448 449 enum N = 4; 450 foreach (int i; 0 .. N) { 451 auto e = E(i.to!string); 452 l[i] = e; 453 } 454 455 assert(l[N] == E.undefined); 456 assert(l[N - 1] != E.undefined); 457 assert(l.length == N); 458 assert(l.remove(2)); 459 assert(count == 1); 460 assert(l.length == N - 1); 461 assert(l[2] == E.undefined); 462 } 463 464 /// Test with a key which is not an atomic value 465 unittest { 466 import std.string : representation; 467 468 alias Key = immutable(ubyte[]); 469 static struct E { 470 string x; 471 static E undefined() { 472 return E("Not found"); 473 } 474 475 } 476 477 alias TestLRU = LRU!(Key, E); 478 uint count; 479 480 void onEvicted(scope const(Key) key, TestLRU.Element* e) @safe { 481 count++; 482 } 483 484 auto l = new TestLRU(&onEvicted); 485 486 Key make_key(size_t num) { 487 return format("data %d", num).representation; 488 } 489 490 enum N = 4; 491 foreach (i; 0 .. N) { 492 auto key = make_key(i); 493 auto e = E(i.to!string); 494 l[key] = e; 495 } 496 497 assert(l[make_key(N)] == E.undefined); 498 assert(l[make_key(N - 1)] != E.undefined); 499 assert(l.length == N); 500 assert(l.remove(make_key(2))); 501 assert(count == 1); 502 assert(l.length == N - 1); 503 assert(l[make_key(2)] == E.undefined); 504 // alias TestSyncLRU = SyncLRU!(Key, E); 505 } 506 507 /// update/upsert test 508 unittest{ 509 alias LRU!(int, int) TestLRU; 510 uint evictCounter; 511 void onEvicted(scope const(int) i, TestLRU.Element* e) @safe { 512 assert(e.entry.key == e.entry.value || e.entry.value == e.entry.key * 7); 513 evictCounter++; 514 } 515 bool ok; 516 auto l = new TestLRU(&onEvicted, 2); 517 int x = 1; 518 ok = l.add(1, x); 519 assert(!ok); 520 assert(evictCounter == 0, "should not have an eviction"); 521 x++; 522 ok = l.add(2, x); 523 assert(!ok); 524 assert(evictCounter == 0, "should still not have an eviction"); 525 ok = l.get(2,x); 526 assert(ok); 527 assert(x == 2, "check inserted"); 528 x = 14; 529 ok = l.update(2,x); 530 assert(ok); 531 ok = l.get(2, x); 532 assert(ok); 533 assert(x == 14, "check updates"); 534 x = 3; 535 ok = l.update(3,x,true); 536 assert(ok); 537 assert(evictCounter == 1, "should have an eviction"); 538 ok = l.get(3, x); 539 assert(ok); 540 assert(x == 3, "check upsert"); 541 } 542 543 /* 544 synchronized 545 class SyncLRU(K, V) { 546 alias LRU_t = LRU!(K, V); 547 protected LRU!(K, V) _lru; 548 549 void opIndexAssign(ref V value, const(K) key) @trusted { 550 pragma(msg, "LRU ", typeof(_lru)); 551 pragma(msg, "LRU_t ", LRU_t); 552 auto tmp_lru = cast(LRU_t) _lru; 553 tmp_lru.add(key, value); 554 } 555 } 556 */ 557 558