1 /** 2 2Q cache is variant of multi-level LRU cache. Original paper http://www.vldb.org/conf/1994/P439.PDF 3 It is adaptive, scan-resistant and can give more hits than plain LRU. 4 $(P This cache consists from three parts (In, Out and Main) where 'In' receive all new elements, 'Out' receives all 5 overflows from 'In', and 'Main' is LRU cache which hold all long-lived data.) 6 **/ 7 module cachetools.cache2q; 8 9 /// Implements Q2 cache 10 /// http://www.vldb.org/conf/1994/P439.PDF 11 12 private import std.experimental.allocator; 13 private import std.experimental.allocator.mallocator : Mallocator; 14 private import std.typecons; 15 16 private import cachetools.internal; 17 private import cachetools.interfaces; 18 private import cachetools.containers.hashmap; 19 private import cachetools.containers.lists; 20 21 /* Pseudocode from the paper 22 // If there is space, we give it to X. 23 // If there is no space, we free a page slot to 24 // make room for page X. 25 reclaimfor(page X) 26 begin 27 if there are free page slots then 28 put X into a free page slot 29 else if( |Alin| > Kin) 30 page out the tail of Alin, call it Y 31 add identifier of Y to the head of Alout 32 if(]Alout] >Kout) 33 remove identifier of Z from 34 the tail of Alout 35 end if 36 put X into the reclaimed page slot 37 else 38 page out the tail of Am, call it Y 39 // do not put it on Alout; it hasn’t been 40 // accessed for a while 41 put X into the reclaimed page slot 42 end if 43 end 44 45 On accessing a page X : 46 begin 47 if X is in Am then 48 move X to the head of Am 49 else if (X is in Alout) then 50 reclaimfor(Х) 51 add X to the head of Am 52 else if (X is in Alin) // do nothing 53 else // X is in no queue 54 reclaimfor(X) 55 add X to the head of Alin 56 end if 57 end 58 */ 59 60 61 /// 62 class Cache2Q(K, V, Allocator=Mallocator) 63 { 64 private 65 { 66 private import core.time; 67 68 private alias TimeType = MonoTimeImpl!(ClockType.coarse); 69 70 struct ListElement { 71 StoredType!K key; // we keep key here so we can remove element from map when we evict with LRU or TTL) 72 } 73 alias ListType = CompressedList!(ListElement, Allocator); 74 alias ListElementPtrType = ListType.NodePointer; 75 alias DListType = DList!(ListElement, Allocator); 76 alias DListElementPtrType = DListType.Node!ListElement*; 77 78 struct MapElement 79 { 80 StoredType!V value; 81 ListElementPtrType list_element_ptr; 82 TimeType expired_at; 83 } 84 struct MainMapElement 85 { 86 StoredType!V value; 87 DListElementPtrType list_element_ptr; 88 TimeType expired_at; 89 } 90 91 int _kin, _kout, _km; 92 93 CompressedList!(ListElement, Allocator) _InList; 94 CompressedList!(ListElement, Allocator) _OutList; 95 DList!(ListElement, Allocator) _MainList; 96 97 HashMap!(K, MapElement, Allocator) _InMap; 98 HashMap!(K, MapElement, Allocator) _OutMap; 99 HashMap!(K, MainMapElement, Allocator) _MainMap; 100 101 Duration _ttl; // global ttl (if > 0) 102 103 bool __reportCacheEvents; 104 SList!(CacheEvent!(K, V), Allocator) __events; // unbounded list of cache events 105 106 } 107 final this() @safe { 108 _kin = 1080 / 6; 109 _kout = 1080 / 6; 110 _km = 2 * 1080 / 3; 111 _InMap.grow_factor(4); 112 _OutMap.grow_factor(4); 113 _MainMap.grow_factor(4); 114 } 115 final this(int s) @safe { 116 _kin = s/6; 117 _kout = s/6; 118 _km = 2*s/3; 119 _InMap.grow_factor(4); 120 _OutMap.grow_factor(4); 121 _MainMap.grow_factor(4); 122 } 123 /// 124 /// Set total cache size. 'In' and 'Out' gets 1/6 of total size, Main gets 2/3 of size. 125 /// 126 final auto size(uint s) @safe 127 { 128 _kin = 1*s/6; 129 _kout = 1*s/6; 130 _km = 4*s/6; 131 return this; 132 } 133 /// 134 /// Set In queue size 135 /// 136 final auto sizeIn(uint s) @safe 137 { 138 _kin = s; 139 return this; 140 } 141 142 /// 143 /// Set Out queue size 144 /// 145 final auto sizeOut(uint s) @safe 146 { 147 _kout = s; 148 return this; 149 } 150 151 /// 152 /// Set Main queue size 153 /// 154 final auto sizeMain(uint s) @safe 155 { 156 _km = s; 157 return this; 158 } 159 160 /// 161 /// Number of elements in cache. 162 /// 163 final int length() @safe 164 { 165 return _InMap.length + _OutMap.length + _MainMap.length; 166 } 167 /// 168 /// Drop all elements from cache. 169 /// 170 final void clear() 171 { 172 _InList.clear(); 173 _OutList.clear(); 174 _MainList.clear(); 175 if ( __reportCacheEvents ) { 176 foreach(p; _InMap.byPair) { 177 __events.insertBack(CacheEvent!(K, V)(EventType.Removed, p.key, p.value.value)); 178 } 179 foreach(p; _OutMap.byPair){ 180 __events.insertBack(CacheEvent!(K, V)(EventType.Removed, p.key, p.value.value)); 181 } 182 foreach(p; _MainMap.byPair){ 183 __events.insertBack(CacheEvent!(K, V)(EventType.Removed, p.key, p.value.value)); 184 } 185 } 186 _InMap.clear(); 187 _OutMap.clear(); 188 _MainMap.clear(); 189 } 190 /// 191 /// Set default ttl (seconds) 192 /// 193 final void ttl(Duration v) @safe 194 { 195 _ttl = v; 196 } 197 deprecated("Use ttl(Duration)") 198 final void ttl(int v) @safe 199 { 200 _ttl = v.seconds; 201 } 202 /// 203 auto enableCacheEvents() pure nothrow @safe @nogc 204 { 205 __reportCacheEvents = true; 206 return this; 207 } 208 /// 209 final auto cacheEvents() 210 { 211 auto r = CacheEventRange!(K, V)(__events); 212 __events.clear; 213 return r; 214 } 215 216 struct CacheEventRange(K, V) 217 { 218 219 private SList!(CacheEvent!(K, V), Allocator) __events; 220 221 void opAssign(CacheEventRange!(K, V) other) 222 { 223 __events.clear(); 224 __events = other.__events; 225 } 226 227 this(ref SList!(CacheEvent!(K, V), Allocator) events) 228 { 229 __events = events; 230 } 231 232 bool empty() const nothrow @safe 233 { 234 return __events.empty(); 235 } 236 237 void popFront() nothrow 238 { 239 __events.popFront(); 240 } 241 242 auto front() @safe 243 { 244 return __events.front(); 245 } 246 247 auto length() pure const nothrow @safe 248 { 249 return __events.length; 250 } 251 auto save() { 252 return CacheEventRange!(K, V)(__events); 253 } 254 } 255 /// 256 /// Get element from cache. 257 /// 258 final Nullable!V get(K k) 259 { 260 debug(cachetools) safe_tracef("get %s", k); 261 262 MainMapElement* keyInMain = k in _MainMap; 263 if ( keyInMain ) 264 { 265 debug(cachetools) safe_tracef("%s in main cache: %s", k, *keyInMain); 266 if ( keyInMain.expired_at > TimeType.init && keyInMain.expired_at <= TimeType.currTime ) 267 { 268 // expired 269 if (__reportCacheEvents) 270 { 271 __events.insertBack(CacheEvent!(K, V)(EventType.Expired, k, keyInMain.value)); 272 } 273 _MainList.remove(keyInMain.list_element_ptr); 274 _MainMap.remove(k); 275 return Nullable!V(); 276 } 277 _MainList.move_to_head(keyInMain.list_element_ptr); 278 return Nullable!V(keyInMain.value); 279 } 280 debug(cachetools) safe_tracef("%s not in main cache", k); 281 282 auto keyInOut = k in _OutMap; 283 if ( keyInOut ) 284 { 285 debug(cachetools) safe_tracef("%s in A1Out cache: %s", k, *keyInOut); 286 if (keyInOut.expired_at > TimeType.init && keyInOut.expired_at <= TimeType.currTime) 287 { 288 // expired 289 if (__reportCacheEvents) 290 { 291 __events.insertBack(CacheEvent!(K, V)(EventType.Expired, k, keyInOut.value)); 292 } 293 delegate void() @trusted { 294 _OutList.remove(keyInOut.list_element_ptr); 295 }(); 296 _OutMap.remove(k); 297 return Nullable!V(); 298 } 299 // move from Out to Main 300 auto value = keyInOut.value; 301 auto expired_at = keyInOut.expired_at; 302 303 delegate void() @trusted 304 { 305 assert((*keyInOut.list_element_ptr).key == k); 306 _OutList.remove(keyInOut.list_element_ptr); 307 }(); 308 309 bool removed = _OutMap.remove(k); 310 assert(removed); 311 debug(cachetools) safe_tracef("%s removed from A1Out cache", k); 312 313 auto mlp = _MainList.insertFront(ListElement(k)); 314 _MainMap.put(k, MainMapElement(value, mlp, expired_at)); 315 debug(cachetools) safe_tracef("%s placed to Main cache", k); 316 if ( _MainList.length > _km ) 317 { 318 debug(cachetools) safe_tracef("Main cache overflowed, pop %s", _MainList.tail().key); 319 if (__reportCacheEvents) 320 { 321 auto key_to_evict = _MainList.tail().key; 322 auto mptr = key_to_evict in _MainMap; 323 __events.insertBack(CacheEvent!(K, V)(EventType.Evicted, key_to_evict, mptr.value)); 324 } 325 _MainMap.remove(_MainList.tail().key); 326 _MainList.popBack(); 327 } 328 return Nullable!V(value); 329 } 330 debug(cachetools) safe_tracef("%s not in Out cache", k); 331 332 auto keyInIn = k in _InMap; 333 if ( keyInIn ) 334 { 335 debug(cachetools) safe_tracef("%s in In cache", k); 336 if (keyInIn.expired_at > TimeType.init && keyInIn.expired_at <= TimeType.currTime) 337 { 338 // expired 339 if (__reportCacheEvents) { 340 __events.insertBack(CacheEvent!(K, V)(EventType.Expired, k, keyInIn.value)); 341 } 342 delegate void () @trusted { 343 _InList.remove(keyInIn.list_element_ptr); 344 }(); 345 _InMap.remove(k); 346 return Nullable!V(); 347 } 348 // just return value 349 return Nullable!V(keyInIn.value); 350 } 351 debug(cachetools) safe_tracef("%s not in In cache", k); 352 353 return Nullable!V(); 354 } 355 356 /// 357 /// Put element to cache. 358 /// 359 /// Evict something if we have to. 360 /// 361 final PutResult put(K k, V v, TTL ttl = TTL()) 362 out 363 { 364 assert(__result != PutResult(PutResultFlag.None)); 365 } 366 do 367 { 368 TimeType exp_time; 369 370 if ( _ttl > 0.seconds && ttl.useDefault ) { 371 exp_time = TimeType.currTime + _ttl; 372 } 373 374 if ( ttl.value > 0.seconds ) { 375 exp_time = TimeType.currTime + ttl.value; 376 } 377 378 auto keyInMain = k in _MainMap; 379 if ( keyInMain ) 380 { 381 if ( __reportCacheEvents ) { 382 __events.insertBack(CacheEvent!(K, V)(EventType.Updated, k, keyInMain.value)); 383 } 384 keyInMain.value = v; 385 keyInMain.expired_at = exp_time; 386 debug(cachetools) safe_tracef("%s in Main cache", k); 387 return PutResult(PutResultFlag.Replaced); 388 } 389 debug(cachetools) safe_tracef("%s not in Main cache", k); 390 391 auto keyInOut = k in _OutMap; 392 if ( keyInOut ) 393 { 394 if ( __reportCacheEvents ) { 395 __events.insertBack(CacheEvent!(K, V)(EventType.Updated, k, keyInOut.value)); 396 } 397 keyInOut.value = v; 398 keyInOut.expired_at = exp_time; 399 debug(cachetools) safe_tracef("%s in Out cache", k); 400 return PutResult(PutResultFlag.Replaced); 401 } 402 debug(cachetools) safe_tracef("%s not in Out cache", k); 403 404 auto keyInIn = k in _InMap; 405 if ( keyInIn ) 406 { 407 if ( __reportCacheEvents ) { 408 __events.insertBack(CacheEvent!(K, V)(EventType.Updated, k, keyInIn.value)); 409 } 410 keyInIn.value = v; 411 keyInIn.expired_at = exp_time; 412 debug(cachetools) safe_tracef("%s in In cache", k); 413 return PutResult(PutResultFlag.Replaced); 414 } 415 else 416 { 417 debug(cachetools) safe_tracef("insert %s in A1InFifo", k); 418 auto lp = _InList.insertBack(ListElement(k)); 419 _InMap.put(k, MapElement(v, lp, exp_time)); 420 if ( _InList.length <= _kin ) 421 { 422 return PutResult(PutResultFlag.Inserted); 423 } 424 425 debug(cachetools) safe_tracef("pop %s from InLlist", _InList.front.key); 426 427 auto toOutK = _InList.front.key; 428 _InList.popFront(); 429 430 auto in_ptr = toOutK in _InMap; 431 432 auto toOutV = in_ptr.value; 433 auto toOutE = in_ptr.expired_at; 434 bool removed = _InMap.remove(toOutK); 435 436 assert(removed); 437 assert(_InList.length == _InMap.length); 438 439 if ( toOutE > TimeType.init && toOutE <= TimeType.currTime ) 440 { 441 // expired, we done 442 if (__reportCacheEvents) { 443 __events.insertBack(CacheEvent!(K, V)(EventType.Expired, toOutK, toOutV)); 444 } 445 return PutResult(PutResultFlag.Inserted|PutResultFlag.Evicted); 446 } 447 448 // and push to Out 449 lp = _OutList.insertBack(ListElement(toOutK)); 450 _OutMap.put(toOutK, MapElement(toOutV, lp, toOutE)); 451 if ( _OutList.length <= _kout ) 452 { 453 return PutResult(PutResultFlag.Inserted|PutResultFlag.Evicted); 454 } 455 // 456 // Out overflowed - throw away head 457 // 458 debug(cachetools) safe_tracef("pop %s from Out", _OutList.front.key); 459 460 if (__reportCacheEvents) 461 { 462 // store in event list 463 auto evicted_key = _OutList.front.key; 464 auto mptr = evicted_key in _OutMap; 465 __events.insertBack(CacheEvent!(K,V)(EventType.Evicted, evicted_key, mptr.value)); 466 } 467 468 removed = _OutMap.remove(_OutList.front.key); 469 _OutList.popFront(); 470 471 assert(removed); 472 assert(_OutList.length == _OutMap.length); 473 474 return PutResult(PutResultFlag.Inserted|PutResultFlag.Evicted); 475 } 476 } 477 /// 478 /// Remove element from cache. 479 /// 480 final bool remove(K k) 481 { 482 debug(cachetools) safe_tracef("remove from 2qcache key %s", k); 483 auto inIn = k in _InMap; 484 if ( inIn ) 485 { 486 auto lp = inIn.list_element_ptr; 487 488 if (__reportCacheEvents) 489 { 490 __events.insertBack(CacheEvent!(K, V)(EventType.Removed, k, inIn.value)); 491 } 492 493 () @trusted 494 { 495 _InList.remove(lp); 496 }(); 497 _InMap.remove(k); 498 return true; 499 } 500 auto inOut = k in _OutMap; 501 if ( inOut ) 502 { 503 504 if (__reportCacheEvents) 505 { 506 __events.insertBack(CacheEvent!(K, V)(EventType.Removed, k, inOut.value)); 507 } 508 509 auto lp = inOut.list_element_ptr; 510 () @trusted 511 { 512 _OutList.remove(lp); 513 }(); 514 _OutMap.remove(k); 515 return true; 516 } 517 auto inMain = k in _MainMap; 518 if ( inMain ) 519 { 520 521 if (__reportCacheEvents) 522 { 523 __events.insertBack(CacheEvent!(K, V)(EventType.Removed, k, inMain.value)); 524 } 525 526 auto lp = inMain.list_element_ptr; 527 _MainList.remove(lp); 528 _MainMap.remove(k); 529 return true; 530 } 531 return false; 532 } 533 } 534 535 @safe unittest 536 { 537 import std.stdio, std.format; 538 import std.datetime; 539 import core.thread; 540 import std.algorithm; 541 import std.experimental.logger; 542 globalLogLevel = LogLevel.info; 543 info("Testing 2Q"); 544 auto cache = new Cache2Q!(int, int); 545 cache.size = 12; 546 foreach(i;0..11) 547 { 548 cache.put(i,i); 549 cache.get(i-3); 550 } 551 cache.put(11,11); 552 // In: [11, 10] 553 // Out: [8, 9] 554 // Main: [0, 6, 7, 2, 3, 1, 5, 4] 555 assert(cache._InMap.length == 2); 556 assert(cache._OutMap.length == 2); 557 assert(cache._MainMap.length == 8); 558 assert(cache.length==12, "expected 12, got %d".format(cache.length)); 559 foreach(i;0..12) 560 { 561 assert(cache.get(i) == i, "missed %s".format(i)); 562 } 563 cache.clear(); 564 assert(cache.length==0); 565 foreach(i;0..11) 566 { 567 cache.put(i,i); 568 cache.get(i-3); 569 } 570 cache.put(11,11); 571 foreach(i;0..12) 572 { 573 assert(cache.remove(i), "failed to remove %s".format(i)); 574 } 575 assert(cache.length==0); 576 foreach(i;0..11) 577 { 578 cache.put(i,i); 579 cache.get(i-3); 580 } 581 cache.put(11,11); 582 // In: [11, 10] 583 // Out: [8, 9] 584 // Main: [0, 6, 7, 2, 3, 1, 5, 4] 585 cache.put(11,22); 586 cache.put(8, 88); 587 cache.put(5,55); 588 assert(cache.get(5) == 55); 589 assert(cache.get(11) == 22); 590 assert(cache.length==12, "expected 12, got %d".format(cache.length)); 591 assert(cache.get(8) == 88); // 8 moved from Out to Main 592 assert(cache.length==11, "expected 11, got %d".format(cache.length)); 593 cache.put(12,12); // in iverflowed, out filled 594 cache.put(13, 13); // in overflowed, out overflowed to main 595 assert(cache.length==12, "expected 12, got %d".format(cache.length)); 596 globalLogLevel = LogLevel.info; 597 } 598 599 unittest 600 { 601 // testing ttl 602 import std.stdio, std.format; 603 import std.datetime; 604 import std.range; 605 import std.algorithm; 606 import core.thread; 607 import std.experimental.logger; 608 609 globalLogLevel = LogLevel.info; 610 auto cache = new Cache2Q!(int, int); 611 cache.sizeIn = 2; 612 cache.sizeOut = 2; 613 cache.sizeMain = 4; 614 cache.enableCacheEvents; 615 616 cache.put(1, 1, TTL(1.seconds)); 617 cache.put(2, 2, TTL(1.seconds)); 618 // in: 1, 2 619 cache.put(3,3); 620 cache.put(4,4); 621 // in: 3, 4 622 // out 1, 2 623 cache.get(1); 624 // in: 3, 4 625 // out 2 626 // main: 1 627 cache.put(5,5, TTL(1.seconds)); 628 // In: 4(-), 5(1) // 629 // Out: 2(1), 3(-) // TTL in parens 630 // Main: 1(1) // 631 assert(4 in cache._InMap && 5 in cache._InMap); 632 assert(2 in cache._OutMap && 3 in cache._OutMap); 633 assert(1 in cache._MainMap); 634 Thread.sleep(1500.msecs); 635 assert(cache.get(1).isNull); 636 assert(cache.get(2).isNull); 637 assert(cache.get(5).isNull); 638 assert(cache.get(3) == 3); 639 assert(cache.get(4) == 4); 640 cache.clear; 641 auto e = cache.cacheEvents; 642 assert(e.filter!(a => a.event == EventType.Removed).count == 2); 643 assert(e.filter!(a => a.event == EventType.Expired).count == 3); 644 cache.ttl = 1.seconds; 645 cache.put(1, 1); // default TTL - this must not survive 1s sleep 646 cache.put(2, 2, ~TTL()); // no TTL, ignore default - this must survive any time 647 cache.put(3, 3, TTL(2.seconds)); // set TTL for this item - this must not survive 2s 648 Thread.sleep(1200.msecs); 649 assert(cache.get(1).isNull); // expired 650 assert(cache.get(2) == 2); 651 assert(cache.get(3) == 3); 652 Thread.sleep(1000.msecs); 653 assert(cache.get(2) == 2); 654 assert(cache.get(3).isNull); // expired 655 e = cache.cacheEvents; 656 assert(e.map!(a => a.event).all!(a => a == EventType.Expired)); 657 cache.remove(2); 658 e = cache.cacheEvents; 659 assert(e.length == 1 && e.front.key == 2); 660 // test cache events after clear 661 cache.sizeIn = 10; 662 iota(5).each!(i => cache.put(i,i)); 663 cache.clear; 664 e = cache.cacheEvents; 665 assert(e.length == 5); 666 assert(e.map!(a => a.event).all!(a => a == EventType.Removed)); 667 668 // test for clear from all queues 669 cache.sizeIn = 2; 670 cache.sizeOut = 2; 671 cache.sizeMain = 1; 672 cache.ttl = 0.seconds; 673 cache.put(1, 1); 674 cache.put(2, 2); 675 // in: 1, 2 676 cache.put(3, 3); 677 cache.put(4, 4); 678 // in: 3, 4 679 // out 1, 2 680 cache.get(1); 681 // in: 3, 4 682 // out 2 683 // main: 1 684 cache.put(5, 5); 685 // In: 4, 5 686 // Out: 2, 3 687 // Main: 1 688 cache.clear; 689 e = cache.cacheEvents; 690 assert(e.length == 5); 691 // test for eviction events from all queues 692 cache.put(1, 1); 693 cache.put(2, 2); 694 // in: 1, 2 695 cache.put(3, 3); 696 cache.put(4, 4); 697 // in: 3, 4 698 // out 1, 2 699 cache.get(1); 700 // in: 3, 4 701 // out 2 702 // main: 1 703 cache.put(5, 5); 704 // In: 4, 5 705 // Out: 2, 3 706 // Main: 1 707 cache.get(2); // 1 evicted and replaced by 2 708 // In: 4, 5 709 // Out: 3 710 // Main: 2 711 e = cache.cacheEvents; 712 assert(e.length == 1); 713 assert(e.front.key == 1); 714 assert(e.front.event == EventType.Evicted); 715 cache.put(4, 44, TTL(1.seconds)); // create 'updated' event in In queue 716 e = cache.cacheEvents; 717 assert(e.length == 1); 718 assert(e.front.key == 4); 719 assert(e.front.event == EventType.Updated); 720 cache.put(3, 33); // create 'updated' event in Out queue 721 e = cache.cacheEvents; 722 assert(e.length == 1); 723 assert(e.front.key == 3); 724 assert(e.front.event == EventType.Updated); 725 cache.put(2, 22); // create 'updated' event in In queue 726 e = cache.cacheEvents; 727 assert(e.length == 1); 728 assert(e.front.key == 2); 729 assert(e.front.event == EventType.Updated); 730 Thread.sleep(1500.msecs); 731 // In: 4, 5 732 // Out: 3 733 // Main: 2 734 cache.put(6,6); // now key '4' expired and must be dropped from In queue 735 e = cache.cacheEvents; 736 assert(e.length == 1); 737 assert(e.front.key == 4); 738 assert(e.front.event == EventType.Expired); 739 // In: 5, 6 740 // Out: 3 741 // Main: 2 742 cache.put(7, 7); 743 // In: 6, 7 744 // Out: 3, 5 745 // Main: 2 746 cache.put(8, 8); 747 // In: 7, 8 748 // Out: 5, 6 -> 3 evicted 749 // Main: 2 750 e = cache.cacheEvents; 751 assert(e.length == 1); 752 assert(e.front.key == 3); 753 assert(e.front.event == EventType.Evicted); 754 cache.remove(7); // remove from In 755 cache.remove(5); // remove from Out 756 cache.remove(2); // remove from main 757 cache.remove(0); // remove something that were not in cache 758 e = cache.cacheEvents; 759 assert(e.length == 3); 760 assert(e.all!(a => a.event == EventType.Removed)); 761 assert(e.map!"a.key".array == [7,5,2]); 762 } 763 764 /// 765 /// 766 /// 767 unittest 768 { 769 770 // create cache with total size 1024 771 auto allocator = Mallocator.instance; 772 auto cache = () @trusted { 773 return allocator.make!(Cache2Q!(int, string))(1024); 774 }(); 775 () @safe @nogc nothrow { 776 cache.sizeIn = 10; // if you need, later you can set any size for In queue 777 cache.sizeOut = 55; // and for out quque 778 cache.sizeMain = 600; // and for main cache 779 cache.put(1, "one"); 780 assert(cache.get(1) == "one"); // key 1 is in cache 781 assert(cache.get(2).isNull); // key 2 not in cache 782 assert(cache.length == 1); // # of elements in cache 783 cache.clear; // clear cache 784 }(); 785 dispose(allocator, cache); 786 } 787 788 // test unsafe types 789 unittest { 790 import std.variant; 791 import std.stdio; 792 793 alias UnsafeType = Algebraic!(int, string); 794 795 auto c = new Cache2Q!(UnsafeType, int); 796 c.enableCacheEvents; 797 798 UnsafeType abc = "abc"; 799 UnsafeType def = "abc"; 800 UnsafeType one = 1; 801 c.put(abc, 1); 802 c.put(one, 2); 803 assert(abc == def); 804 assert(c.get(def) == 1); 805 assert(c.get(one) == 2); 806 c.remove(abc); 807 auto r = c.cacheEvents; 808 c.sizeMain = 100; 809 c.sizeIn = 100; 810 c.sizeOut = 100; 811 c.length; 812 813 814 import std.json; 815 auto csj = new Cache2Q!(string, JSONValue); 816 auto cjs = new Cache2Q!(JSONValue, string); 817 818 class C { 819 // bool opEquals(const C other) { 820 // return other is this; 821 // } 822 } 823 auto c1 = new Cache2Q!(C, string); 824 auto cob1 = new C(); 825 auto cob2 = new C(); 826 c1.put(cob1, "cob1"); 827 c1.put(cob2, "cob2"); 828 assert(c1.get(cob1) == "cob1"); 829 assert(c1.get(cob2) == "cob2"); 830 }