1 /*******************************************************************************
2 3 Cache class, caches raw data of either fixed or dynamic length
4 5 Cache of raw data (ubyte[] / void[]) items of either fixed or variable
6 length. The cache is initialised with a fixed capacity (the number of items
7 that can be stored). When the cache reaches its full capacity, any newly
8 added items will replace older items in the cache. The cache keeps track of
9 the last time each item was written or read, and will replace the oldest
10 items first.
11 12 The basic Cache template is used to store raw data. A second template exists
13 which takes a type as its parameter. This implements a thin wrapper around
14 the basic Cache, allowing the transparent storage of (no-op) serialized
15 values of the specified type.
16 17 18 Note that with variable value length anything stored in the cache is
19 invisible to the garbage collector because the internal value data type of
20 the cache is ubyte[]. So if you store references (objects, pointers, slices
21 to dynamic arrays) in the cache with variable value length, make sure your
22 application keeps a reference to it. Otherwise the object referenced to may
23 be garbage collected and attempting to use it after getting it from the
24 cache will make your program go to HELL.
25 26 27 When a cache element is removed explicitly (by calling remove()), the value
28 of the removed element is kept in the cache in a spare location. If required
29 it is possible to erase the value by overriding Cache.replaceRemovedItem(),
30 see the description of this method for an example.
31 32 When a cache element is removed automatically if the cache is full and a new
33 element is added, Cache.whenCacheItemDropped(size_t index) will be called. If
34 required it is possible to be notified of this occurrence by overriding
35 Cache.whenCacheItemDropped method.
36 37 Cache.createRaw() and Cache.getOrCreateRaw() return a reference to a record
38 value in the cache. Cache.getRaw() behaves like Cache.getOrCreateRaw() if
39 the record was found in the cache or returns null otherwise.
40 For fixed length values the record value reference is a slice to the record
41 value.
42 Usage example:
43 44 ---
45 46 import ocean.util.container.Cache;
47 48 // Create a fixed-size cache which can store 2 items, each of length 3.
49 auto cache = new Cache!(3)(2);
50 51 // Add an item using createRaw(). createRaw() returns a void[] array
52 // with length 3 which references the value in the cache.
53 54 hash_t key = 0x12345678;
55 56 char[3] val = "abc";
57 58 cache.createRaw(key)[] = val[];
59 60 // Obtain an item using getRaw(). If found, getRaw() returns a value
61 // slice just like createRaw() or null if not found.
62 63 char[] val_got = cache.getRaw(key);
64 65 if (val_got !is null)
66 {
67 // val_got contains the value that corresponds to key.
68 // The value in the cache can be modified in-place by setting array
69 // elements or copying to the whole array:
70 71 (cast(char[])val_got)[2] = '!'; // Set the third value byte to '!'.
72 73 (cast(char[])val_got)[] = "def"; // Set the value to "def".
74 }
75 else
76 {
77 // not found
78 }
79 80 ---
81 82 For variable length arrays it is a pointer to the Cache.Value struct which
83 encapsulates the value, which is void[], providing access to the value via
84 operator overloading:
85 86 - opAssign sets the value array instance to an input array slice
87 (overwriting the previous array instance),
88 - opSliceAssign treats the value array as an allocated buffer and copies
89 the content of the an input array slice into the value array,
90 - opSlice returns the value array.
91 92 opSliceAssign reuses an existing buffer and is therefore memory-friendly as
93 long as opAssign is not used with the same value instance.
94 95 Rule of thumb: For each cache instance with variable value size use either
96 opAssign or opSliceAssign with the values, never both.
97 98 Usage Example 1: Store string slices in a cache using Value.opAssign.
99 100 ---
101 102 auto cache = new Cache!()(100);
103 104 char[] str1 = "Hello World",
105 str2 = "Eggs and Spam";
106 107 {
108 auto val = cache.createRaw(4711);
109 110 // Store a slice to str1 in the array using (*val).opAssign.
111 112 *val = str1;
113 }
114 115 {
116 auto val = cache.getRaw(4711);
117 118 // (*val)[] ((*val).opSlice) now returns a slice to str1.
119 120 // Replace this value with a slice to str2 using (*val).opAssign.
121 122 *val = str2;
123 }
124 125 ---
126 127 Usage Example 2: Store copies of strings in a cache using
128 Value.opSliceAssign.
129 130 ---
131 132 auto cache = new Cache!()(100);
133 134 char[] str1 = "Hello World",
135 str2 = "Eggs and Spam";
136 137 {
138 auto val = cache.createRaw(4711);
139 140 // Allocate a value array buffer with str1.length and copy the
141 // content of str1 into that value buffer.
142 143 (*val)[] = str1;
144 }
145 146 {
147 auto val = cache.getRaw(4711);
148 149 // (*val)[] ((*val).opSlice) now returns the value array buffer
150 // which contains a copy of the content of str1.
151 152 // Use (*val)[] = str2 ((*val).opSliceAssign(x)) to resize the value
153 // array buffer to str2.length and copy the content of str2 into it.
154 155 (*val)[] = str2;
156 }
157 158 ---
159 160 For special situations it is possible to obtain a pointer to the value
161 array. One such situation is when the value array needs to be modified by
162 an external function which doesn't know about the cache.
163 164 ---
165 166 void setValue ( ref void[] value )
167 {
168 value = "Hello World!";
169 }
170 171 auto cache = new Cache!()(100);
172 173 auto val = cache.createRaw(4711);
174 175 void[]* val_array = cast (void[]*) (*s);
176 177 setValue(*val_array);
178 179 ---
180 181 Link with:
182 -Llibebtree.a
183 184 TODO:
185 Extend the cache by making values visible to the GC by default and
186 provide GC hiding as an option.
187 188 Copyright:
189 Copyright (c) 2009-2016 dunnhumby Germany GmbH.
190 All rights reserved.
191 192 License:
193 Boost Software License Version 1.0. See LICENSE_BOOST.txt for details.
194 Alternatively, this file may be distributed under the terms of the Tango
195 3-Clause BSD License (see LICENSE_BSD.txt for details).
196 197 *******************************************************************************/198 199 moduleocean.util.container.cache.Cache;
200 201 202 203 204 importocean.util.container.cache.model.ICache;
205 importocean.util.container.cache.model.ITrackCreateTimesCache;
206 importocean.util.container.cache.model.Value;
207 importcore.stdc.time: time_t;
208 importocean.core.Test;
209 210 importcore.memory;
211 212 debugimportocean.io.Stdout;
213 214 debug (CacheTimes)
215 {
216 importocean.core.Array: concat;
217 importcore.stdc.stdio: FILE, fopen, fclose, fprintf, perror;
218 importcore.sys.posix.time: ctime_r;
219 }
220 221 version (unittest)
222 {
223 importocean.core.Test;
224 }
225 226 227 /*******************************************************************************
228 229 Evaluates to either ICache or ITrackCreateTimesCache, depending on
230 TrackCreateTimes.
231 232 *******************************************************************************/233 234 templateCacheBase ( boolTrackCreateTimes = false )
235 {
236 staticif (TrackCreateTimes)
237 {
238 aliasITrackCreateTimesCacheCacheBase;
239 }
240 else241 {
242 aliasICacheCacheBase;
243 }
244 }
245 246 /*******************************************************************************
247 248 Data cache class template. Stores items of raw data, either of fixed or
249 dynamic size.
250 251 Params:
252 ValueSize = size of a data item. If 0 is specified (the default), the
253 items stored in the cache are of variable (dynamic) size
254 TrackCreateTimes = if true, each cache item is stored with its create
255 time, in addition to its last access time
256 257 *******************************************************************************/258 259 classCache ( size_tValueSize = 0, boolTrackCreateTimes = false ) : CacheBase!(TrackCreateTimes)
260 {
261 importocean.core.Verify;
262 263 /***************************************************************************
264 265 Mixin the type definition for the values.
266 267 ***************************************************************************/268 269 mixinValue!(ValueSize);
270 271 /***************************************************************************
272 273 Cached item struct, storing a key and value.
274 275 ***************************************************************************/276 277 structCacheItem278 {
279 hash_tkey;
280 Valuevalue;
281 282 staticif ( TrackCreateTimes )
283 {
284 time_tcreate_time;
285 }
286 287 /***********************************************************************
288 289 Copies value to this.value.
290 291 Params:
292 value = value to copy
293 294 Returns:
295 this.value
296 297 ***********************************************************************/298 299 ValueRefsetValue ( Valuevalue )
300 {
301 staticif ( is_dynamic )
302 {
303 this.value = value;
304 return &this.value;
305 }
306 else307 {
308 returnthis.value[] = value[];
309 }
310 }
311 312 staticif ( is_dynamic )
313 {
314 ValueRefvalue_ref ( )
315 {
316 return &this.value;
317 }
318 }
319 else320 {
321 ValueRefvalue_ref ( )
322 {
323 returnthis.value[];
324 }
325 }
326 }
327 328 329 /***************************************************************************
330 331 Array of cached items.
332 333 ***************************************************************************/334 335 privateCacheItem[] items;
336 337 338 /***************************************************************************
339 340 Constructor.
341 342 Params:
343 max_items = maximum number of items in the cache, set once, cannot
344 be changed
345 346 ***************************************************************************/347 348 publicthis ( size_tmax_items )
349 {
350 super(max_items);
351 352 this.items = newCacheItem[max_items];
353 }
354 355 /***************************************************************************
356 357 Creates an item in the cache and sets its create time. If the cache is
358 full, the oldest item is replaced with the new item. (In the case where
359 several items are equally old, the choice of which one to be replaced is
360 made arbitrarily.)
361 362 Params:
363 key = item key
364 365 Returns:
366 a reference to the value of the created item. If an existing item
367 was replaced, this reference refers to its current value, otherwise
368 it may refer to the value of a previously removed element.
369 370 Out:
371 The returned reference is never null; for values of fixed size the
372 slice length is ValueSize.
373 374 ***************************************************************************/375 376 publicValueRefcreateRaw ( hash_tkey )
377 out (val)
378 {
379 staticif (is_dynamic)
380 {
381 assert (val !isnull);
382 }
383 else384 {
385 assert (val.length == ValueSize);
386 }
387 }
388 do389 {
390 boolexisted;
391 392 time_taccess_time;
393 394 with (*this.getOrAdd(key, existed, access_time))
395 {
396 staticif ( TrackCreateTimes )
397 {
398 create_time = access_time;
399 }
400 401 returnvalue_ref;
402 }
403 }
404 405 /***************************************************************************
406 407 Gets an item from the cache. If the item was found in the cache, its
408 access time is updated.
409 410 Note that, if you change the value referenced by the returned reference,
411 the create time will not be updated.
412 413 Params:
414 key = key to lookup
415 416 Returns:
417 a reference to item value or null if no such item was found.
418 419 Out:
420 For values of fixed size the slice length is ValueSize unless the
421 returned reference is null.
422 423 ***************************************************************************/424 425 publicValueRefgetRaw ( hash_tkey )
426 out (val)
427 {
428 staticif (!is_dynamic)
429 {
430 if (val !isnull)
431 {
432 assert (val.length == ValueSize);
433 }
434 }
435 }
436 do437 {
438 time_taccess_time;
439 440 CacheItem* item = this.get__(key, access_time);
441 442 return (item !isnull)? item.value_ref : null;
443 }
444 445 /***************************************************************************
446 447 Gets an item from the cache or creates it if not already existing. If
448 the item was found in the cache, its access time is updated, otherwise
449 its create time is set.
450 451 Note that the create time is set only if an item is created, not if it
452 already existed and you change the value referenced by the returned
453 reference.
454 455 Params:
456 key = key to lookup
457 existed = true: the item already existed,
458 false: the item was created
459 460 Returns:
461 a reference to the value of the obtained or created item. If an item
462 was created, the returned reference may refer to the value of a
463 previously removed element.
464 465 Out:
466 The returned reference is never null; for values of fixed size the
467 slice length is ValueSize.
468 469 ***************************************************************************/470 471 publicValueRefgetOrCreateRaw ( hash_tkey, outboolexisted )
472 out (val)
473 {
474 staticif (is_dynamic)
475 {
476 assert (val !isnull);
477 }
478 else479 {
480 assert (val.length == ValueSize);
481 }
482 }
483 do484 {
485 time_taccess_time;
486 487 with (*this.getOrAdd(key, existed, access_time))
488 {
489 staticif ( TrackCreateTimes ) if (!existed)
490 {
491 create_time = access_time;
492 }
493 494 returnvalue_ref;
495 }
496 }
497 498 /***************************************************************************
499 500 Checks whether an item exists in the cache and returns its create time.
501 502 Params:
503 key = key to lookup
504 505 Returns:
506 item's create time, or 0 if the item doesn't exist
507 508 ***************************************************************************/509 510 staticif ( TrackCreateTimes )
511 {
512 publicoverridetime_tcreateTime ( hash_tkey )
513 {
514 TimeToIndex.Node** node = keyinthis;
515 516 returnnode? this.items[(*node).key.lo].create_time : 0;
517 }
518 }
519 520 /***************************************************************************
521 522 Obtains the key of the cache item corresponding to index.
523 524 Params:
525 index = cache item index, guaranteed to be below length
526 527 Returns:
528 cache item key
529 530 ***************************************************************************/531 532 protectedoverridehash_tkeyByIndex ( size_tindex )
533 {
534 verify (index <= this.length);
535 536 returnthis.items[index].key;
537 }
538 539 /***************************************************************************
540 541 Called when a cache element is removed, replaces the cache items at
542 index "replaced" with the one at index "replace" by swapping the items.
543 544 Unlike all other situations where indices and are used, "replaced" and
545 "replace" must be always valid, i.e. less than length.
546 547 Note: A subclass may erase removed elements by overriding this method as
548 follows:
549 550 ---
551 protected override hash_t replaceRemovedItem ( size_t replaced,
552 size_t replace )
553 {
554 scope (success) this.items[replace] = this.items[replace].init;
555 556 return (this.items[replaced] = this.items[replace]).key;
557 }
558 ---
559 560 Params:
561 replaced = index of the cache item that is to be replaced
562 replace = index of the cache item that will replace the replaced
563 item
564 565 Returns:
566 the key of the cache item that was at index "replace" before and is
567 at index "replaced" now.
568 569 In:
570 "replaced" and "replace" must be different and be valid cache item
571 indices, i.e. less than this.length.
572 573 Out:
574 The returned key must be the key of this.items[replaced].
575 576 ***************************************************************************/577 578 protectedoverridehash_treplaceRemovedItem ( size_treplaced, size_treplace )
579 out (key)
580 {
581 assert(key == this.items[replaced].key);
582 }
583 do584 {
585 verify(replaced != replace);
586 587 size_tlength = this.length;
588 589 verify(replaced < length);
590 verify(replace < length);
591 592 CacheItemtmp = this.items[replace];
593 this.items[replace] = this.items[replaced];
594 595 return (this.items[replaced] = tmp).key;
596 }
597 598 /***************************************************************************
599 600 Obtains the cache item that corresponds to node and updates the access
601 time.
602 If realtime is enabled, time is expected to be equal to or
603 greater than the time stored in node. If disabled and the access time is
604 less, the node will not be updated and null returned.
605 606 607 Params:
608 node = time-to-index tree node
609 access_time = access time
610 611 Returns:
612 the cache item or a null if realtime is disabled and the access time
613 is less than the access time in the node.
614 615 Out:
616 If realtime is enabled, the returned pointer is never null.
617 618 ***************************************************************************/619 620 protectedCacheItem* access ( refTimeToIndex.Nodenode, outtime_taccess_time )
621 out (item)
622 {
623 assert (item !isnull);
624 }
625 do626 {
627 returnthis.getItem(this.accessIndex(node, access_time));
628 }
629 630 /***************************************************************************
631 632 Obtains the cache item that corresponds to node and updates the access
633 time.
634 If realtime is enabled and key could be found, time is expected to be at
635 least the time value stored in node. If disabled and access_time is
636 less, the result is the same as if key could not be found.
637 638 639 Params:
640 key = time-to-index tree node key
641 access_time = access time
642 643 Returns:
644 the corresponding cache item or null if key could not be found or
645 realtime is disabled and the access time is less than the access
646 time in the cache element.
647 648 ***************************************************************************/649 650 protectedCacheItem* get__ ( hash_tkey, outtime_taccess_time )
651 {
652 returnthis.getItem(this.get_(key, access_time));
653 }
654 655 /***************************************************************************
656 657 Obtains the cache item that corresponds to index. Returns null if index
658 is length or greater.
659 660 Params:
661 index = cache item index
662 663 Returns:
664 the corresponding cache item or null if index is length or greater.
665 666 ***************************************************************************/667 668 protectedCacheItem* getItem ( size_tindex )
669 {
670 return (index < this.length)? &this.items[index] : null;
671 }
672 673 /***************************************************************************
674 675 Gets an item from the cache or creates it if not already existing. If
676 the item was found in the cache, its access time is updated.
677 678 Params:
679 key = key to lookup
680 existed = true: the item already existed,
681 false: the item was created
682 683 Returns:
684 a pointer to the obtained or created item.
685 686 Out:
687 The returned pointer is never null.
688 689 ***************************************************************************/690 691 privateCacheItem* getOrAdd ( hash_tkey, outboolexisted, outtime_taccess_time )
692 out (item)
693 {
694 assert (item !isnull);
695 }
696 do697 {
698 CacheItem* item = this.get__(key, access_time);
699 700 existed = item !isnull;
701 702 returnexisted? item : this.add(key, access_time);
703 }
704 705 /***************************************************************************
706 707 Adds an item to the cache. If the cache is full, the oldest item will be
708 removed and replaced with the new item.
709 710 Params:
711 key = key of item
712 access_time = access time (also the create time)
713 714 Returns:
715 the added cache item.
716 717 Out:
718 The returned pointer is never null.
719 720 ***************************************************************************/721 722 protectedCacheItem* add ( hash_tkey, outtime_taccess_time )
723 out (cache_item)
724 {
725 assert (cache_item !isnull);
726 }
727 do728 {
729 // Add key->item mapping730 731 CacheItem* cache_item = &this.items[this.register(key, access_time)];
732 733 // Set the key in chosen element of items array.734 735 cache_item.key = key;
736 737 returncache_item;
738 }
739 740 /***************************************************************************
741 742 Makes the GC scan the cache items. Should be called by the subclass
743 constructor if it stores values that contain GC references.
744 This method should be called after the constructor of this class has
745 returned.
746 747 ***************************************************************************/748 749 staticif (!is_dynamic)
750 {
751 protectedvoidenableGcValueScanning ( )
752 {
753 verify(this.items !isnull,
754 "please call enableGcValueScanning() *after* the super
755 constructor");
756 757 GC.clrAttr(this.items.ptr, GC.BlkAttr.NO_SCAN);
758 }
759 }
760 761 debug (CacheTimes)
762 {
763 /**********************************************************************
764 765 String nul-termination buffer
766 767 ***********************************************************************/768 769 privatechar[] nt_buffer;
770 771 /**********************************************************************
772 773 Writes the access times and the number of records with that time to
774 a file, appending to that file.
775 776 ***********************************************************************/777 778 voiddumpTimes ( char[] filename, time_tnow )
779 {
780 FILE* f = fopen(this.nt_buffer.concat(filename, "\0").ptr, "a");
781 782 if (f)
783 {
784 scope (exit) fclose(f);
785 786 char[26] buf;
787 788 fprintf(f, "> %10u %s", now, ctime_r(&now, buf.ptr));
789 790 TimeToIndex.Mappingmapping = this.time_to_index.firstMapping;
791 792 if (mapping)
793 {
794 time_tt = mapping.key;
795 796 uintn = 0;
797 798 foreach (time_tu; this.time_to_index)
799 {
800 if (t == u)
801 {
802 n++;
803 }
804 else805 {
806 fprintf(f, "%10u %10u\n", t, n);
807 t = u;
808 n = 0;
809 }
810 }
811 }
812 }
813 else814 {
815 perror(this.nt_buffer.concat("unable to open \"", filename, "\"\0").ptr);
816 }
817 }
818 }
819 }
820 821 /*******************************************************************************
822 823 Typed cache class template. Stores items of a particular type.
824 825 Params:
826 T = type of item to store in cache
827 TrackCreateTimes = if true, each cache item is stored with its create
828 time, in addition to its last access time
829 830 *******************************************************************************/831 832 classCache ( T, boolTrackCreateTimes = false ) : Cache!(T.sizeof, TrackCreateTimes)
833 {
834 /***************************************************************************
835 836 Constructor.
837 838 Params:
839 max_items = maximum number of items in the cache, set once, cannot
840 be changed
841 842 ***************************************************************************/843 844 publicthis ( size_tmax_items )
845 {
846 super(max_items);
847 }
848 849 /***************************************************************************
850 851 Puts an item into the cache. If the cache is full, the oldest item is
852 replaced with the new item. (In the case where several items are equally
853 old, the choice of which one to be replaced is made arbitrarily.)
854 855 Params:
856 key = item key
857 value = item to store in cache
858 859 Returns:
860 true if a record was updated / overwritten, false if a new record
861 was added
862 863 ***************************************************************************/864 865 publicboolput ( hash_tkey, Tvalue )
866 {
867 boolexisted;
868 869 T* dst = this.getOrCreate(key, existed);
870 871 if (dst)
872 {
873 *dst = value;
874 }
875 876 returnexisted;
877 }
878 879 /***************************************************************************
880 881 Creates a cache item and sets the create time. If the cache is full, the
882 oldest item is replaced with the new item. (In the case where several
883 items are equally old, the choice of which one to be replaced is made
884 arbitrarily.)
885 886 Params:
887 key = item key
888 889 Returns:
890 true if a record was updated / overwritten, false if a new record
891 was added
892 893 ***************************************************************************/894 895 publicT* create ( hash_tkey )
896 out (val)
897 {
898 assert (val !isnull);
899 }
900 do901 {
902 returncast (T*) this.createRaw(key)[0 .. T.sizeof].ptr;
903 }
904 905 /***************************************************************************
906 907 Gets an item from the cache. A pointer to the item is returned, if
908 found. If the item exists in the cache, its update time is updated.
909 910 Note that, if the item already existed and you change the value pointed
911 to by the returned pointer, the create time will not be updated.
912 913 Params:
914 key = key to lookup
915 916 Returns:
917 pointer to item value, may be null if key not found
918 919 ***************************************************************************/920 921 publicT* get ( hash_tkey )
922 {
923 returncast (T*) this.getRaw(key);
924 }
925 926 927 /***************************************************************************
928 929 Gets an item from the cache or creates it if not already existing. If
930 the item exists in the cache, its update time is updated, otherwise its
931 create time is set.
932 933 Note that the create time is set only if an item is created, not if it
934 already existed and you change the value referenced by the returned
935 pointer.
936 937 Params:
938 key = key to lookup
939 existed = true: the item already existed,
940 false: the item was created
941 942 Returns:
943 pointer to item value
944 945 ***************************************************************************/946 947 publicT* getOrCreate ( hash_tkey, outboolexisted )
948 out (val)
949 {
950 assert (val !isnull);
951 }
952 do953 {
954 returncast (T*) this.getOrCreateRaw(key, existed)[0 .. T.sizeof].ptr;
955 }
956 }
957 958 /*******************************************************************************
959 960 Unit test
961 962 *******************************************************************************/963 964 version (unittest)
965 {
966 importcore.sys.posix.stdlib: srand48, mrand48, drand48;
967 importcore.sys.posix.unistd: getpid;
968 importcore.stdc.time: time;
969 importocean.io.Stdout;
970 importocean.core.Array: shuffle;
971 }
972 973 unittest974 {
975 srand48(time(null)+getpid());
976 977 staticulongulrand ( )
978 {
979 return (cast (ulong) mrand48() << 0x20) | cast (uint) mrand48();
980 }
981 982 time_ttime = 234567;
983 984 // ---------------------------------------------------------------------985 // Test of static sized cache986 987 version (all)
988 {{
989 staticimmutablen_records = 33,
990 capacity = 22,
991 n_overflow = 7;
992 993 staticassert (n_records >= capacity,
994 "Number of records smaller than capacity!");
995 996 structRecord997 {
998 hash_tkey; // random number999 size_tval; // counter1000 }
1001 1002 // Initialise the list of records.1003 1004 Record[n_records] records;
1005 1006 foreach (i, refrecord; records)
1007 {
1008 record = Record(ulrand(), i);
1009 }
1010 1011 // Populate the cache to the limit.1012 1013 time_tt = 0;
1014 1015 scopecache = newclassCache!(size_t)
1016 {
1017 this ( ) {super(capacity);}
1018 1019 overridetime_tnow ( ) {return ++t;}
1020 };
1021 1022 test!("==")(capacity, cache.max_length,
1023 "Max length of cache does not equal configured capacity!");
1024 1025 foreach (record; records[0 .. cache.max_length])
1026 {
1027 cache.put(record.key, record.val);
1028 }
1029 1030 // Shuffle records and count how many of the first n_overflow of the1031 // shuffled records are in the cache. If either all or none of these are1032 // in the cache, shuffle and try again.1033 1034 uintn_existing;
1035 1036 do1037 {
1038 n_existing = 0;
1039 foreach (i, record; records.shuffle(drand48)[0 .. n_overflow])
1040 {
1041 n_existing += cache.exists(record.key);
1042 }
1043 }
1044 while (!n_existing || n_existing == n_overflow);
1045 1046 test (n_existing > 0 && n_existing < n_overflow, "n_existing has unexpected value");
1047 1048 // Get the shuffled records from the cache and verify them. Record the1049 // keys of the first n_overflow existing records which will get the1050 // least (oldest) access time by cache.getItem() and therefore be the1051 // first records to be removed on a cache overflow.1052 1053 hash_t[n_overflow] oldest_keys;
1054 1055 {
1056 uinti = 0;
1057 1058 foreach (record; records)
1059 {
1060 autov = cache.get(record.key);
1061 1062 if (record.val < cache.max_length)
1063 {
1064 test!("!is") (v, null);
1065 test!("==") (*v, record.val);
1066 1067 if (i < n_overflow)
1068 {
1069 oldest_keys[i++] = record.key;
1070 }
1071 }
1072 else1073 {
1074 test!("is") (v, null);
1075 }
1076 }
1077 1078 test!("==") (i, n_overflow);
1079 }
1080 1081 test!("==") (t, cache.max_length * 2);
1082 1083 // Put the first n_overflow shuffled records so that the cache will1084 // overflow.1085 // Existing records should be updated to a new value. To enable1086 // verification of the update, change the values to 4711 + i.1087 1088 foreach (i, refrecord; records[0 .. n_overflow])
1089 {
1090 record.val = 4711 + i;
1091 1092 cache.put(record.key, record.val);
1093 }
1094 1095 test!("==") (t, cache.max_length * 2 + n_overflow);
1096 1097 // Verify the records.1098 1099 foreach (i, record; records[0 .. n_overflow])
1100 {
1101 autov = cache.get(record.key);
1102 1103 test!("!is") (v, null);
1104 test!("==") (*v, 4711 + i);
1105 }
1106 1107 test!("==") (t, cache.max_length * 2 + n_overflow * 2);
1108 1109 // oldest_keys[n_existing .. $] should have been removed from the1110 // cache due to cache overflow.1111 1112 foreach (key; oldest_keys[n_existing .. $])
1113 {
1114 autov = cache.get(key);
1115 1116 test!("is") (v, null);
1117 }
1118 1119 // cache.get should not have evaluated the lazy ++t.1120 1121 test!("==") (t, cache.max_length * 2 + n_overflow * 2);
1122 1123 // Verify that all other records still exist in the cache.1124 1125 {
1126 uintn = 0;
1127 1128 foreach (record; records[n_overflow .. $])
1129 {
1130 autov = cache.get(record.key);
1131 1132 if (v !isnull)
1133 {
1134 test!("==") (*v, record.val);
1135 1136 n++;
1137 }
1138 }
1139 1140 test!("==") (n, cache.max_length - n_overflow);
1141 }
1142 1143 test!("==") (t, cache.max_length * 3 + n_overflow);
1144 }}
1145 else1146 {
1147 structData1148 {
1149 intx;
1150 }
1151 1152 scopestatic_cache = newCache!(Data)(2);
1153 1154 with (static_cache)
1155 {
1156 test!("==")(length, 0);
1157 1158 {
1159 boolreplaced = put(1, time, Data(23));
1160 1161 test(!replaced);
1162 1163 test!("==")(length, 1);
1164 test(exists(1));
1165 1166 Data* item = get(1, time);
1167 test!("!is")(item, null);
1168 test!("==")(item.x, 23);
1169 }
1170 1171 {
1172 boolreplaced = put(2, time + 1, Data(24));
1173 1174 test(!replaced);
1175 1176 test!("==")(length, 2);
1177 test(exists(2));
1178 1179 Data* item = get(2, time + 1);
1180 test!("!is")(item, null);
1181 test!("==")(item.x, 24);
1182 }
1183 1184 {
1185 boolreplaced = put(2, time + 1, Data(25));
1186 1187 test(replaced);
1188 1189 test!("==")(length, 2);
1190 test(exists(2));
1191 1192 Data* item = get(2, time + 1);
1193 test!("!is")(item, null);
1194 test!("==")(item.x, 25);
1195 }
1196 1197 {
1198 boolreplaced = put(3, time + 2, Data(26));
1199 1200 test(!replaced);
1201 1202 test!("==")(length, 2);
1203 test(!exists(1));
1204 test(exists(2));
1205 test(exists(3));
1206 1207 Data* item = get(3, time + 2);
1208 test!("!is")(item);
1209 test!("==")(item.x, 26);
1210 }
1211 1212 {
1213 boolreplaced = put(4, time + 3, Data(27));
1214 1215 test(!replaced);
1216 1217 test!("==")(length, 2);
1218 test(!exists(1));
1219 test(!exists(2));
1220 test(exists(3));
1221 test(exists(4));
1222 1223 Data* item = get(4, time + 3);
1224 test!("!is")(item);
1225 test!("==")(item.x, 27);
1226 }
1227 1228 clear();
1229 test!("==")(length, 0);
1230 test(!exists(1));
1231 test!("is")(get(1, time), null);
1232 test(!exists(2));
1233 test!("is")(get(2, time), null);
1234 test(!exists(3));
1235 test!("is")(get(3, time), null);
1236 test(!exists(4));
1237 test!("is")(get(4, time), null);
1238 1239 {
1240 boolreplaced = put(1, time, Data(23));
1241 1242 test(!replaced);
1243 1244 test!("==")(length, 1);
1245 test(exists(1));
1246 1247 Data* item = get(1, time);
1248 test!("!is")(item);
1249 test!("==")(item.x, 23);
1250 }
1251 1252 {
1253 boolreplaced = put(2, time + 1, Data(24));
1254 1255 test(!replaced);
1256 1257 test!("==")(length, 2);
1258 test(exists(2));
1259 1260 Data* item = get(2, time + 1);
1261 test!("!is")(item);
1262 test!("==")(item.x, 24);
1263 }
1264 1265 remove(1);
1266 test!("==")(length, 1);
1267 test(!exists(1));
1268 test(exists(2));
1269 }
1270 }
1271 1272 // ---------------------------------------------------------------------1273 // Test of dynamic sized cache1274 1275 {
1276 ubyte[] data1 = cast(ubyte[])"hello world";
1277 ubyte[] data2 = cast(ubyte[])"goodbye world";
1278 ubyte[] data3 = cast(ubyte[])"hallo welt";
1279 1280 scopedynamic_cache = newclassCache!()
1281 {
1282 this ( ) {super(2);}
1283 1284 time_tnow_sec ( ) {return ++time;}
1285 };
1286 1287 test!("==")(dynamic_cache.length, 0);
1288 1289 version (all)
1290 {
1291 *dynamic_cache.createRaw(1) = data1;
1292 {
1293 autoval = dynamic_cache.getRaw(1);
1294 test!("!is")(val, null);
1295 test!("==")((*val)[], data1);
1296 }
1297 1298 *dynamic_cache.createRaw(2) = data2;
1299 {
1300 autoval = dynamic_cache.getRaw(1);
1301 test!("!is")(val, null);
1302 test!("==")((*val)[], data1);
1303 }
1304 {
1305 autoval = dynamic_cache.getRaw(2);
1306 test!("!is")(val, null);
1307 test!("==")((*val)[], data2);
1308 }
1309 1310 *dynamic_cache.createRaw(3) = data3;
1311 test!("is")(dynamic_cache.getRaw(1), null);
1312 {
1313 autoval = dynamic_cache.getRaw(2);
1314 test!("!is")(val, null);
1315 test!("==")((*val)[], data2);
1316 }
1317 {
1318 autoval = dynamic_cache.getRaw(3);
1319 test!("!is")(val, null);
1320 test!("==")((*val)[], data3);
1321 }
1322 1323 dynamic_cache.clear;
1324 test!("==")(dynamic_cache.length, 0);
1325 test!("is")(dynamic_cache.getRaw(1), null);
1326 test!("is")(dynamic_cache.getRaw(2), null);
1327 test!("is")(dynamic_cache.getRaw(3), null);
1328 1329 *dynamic_cache.createRaw(1) = data1;
1330 test!("==")(dynamic_cache.length, 1);
1331 {
1332 autoval = dynamic_cache.getRaw(1);
1333 test!("!is")(val, null);
1334 test!("==")((*val)[], data1);
1335 }
1336 1337 *dynamic_cache.createRaw(2) = data2;
1338 test!("==")(dynamic_cache.length, 2);
1339 {
1340 autoval = dynamic_cache.getRaw(2);
1341 test!("!is")(val, null);
1342 test!("==")((*val)[], data2);
1343 }
1344 1345 dynamic_cache.remove(1);
1346 test!("==")(dynamic_cache.length, 1);
1347 test!("is")(dynamic_cache.getRaw(1), null);
1348 {
1349 autoval = dynamic_cache.getRaw(2);
1350 test!("!is")(val, null);
1351 test!("==")((*val)[], data2);
1352 }
1353 }
1354 else1355 {
1356 dynamic_cache.putRaw(1, data1);
1357 test(dynamic_cache.exists(1));
1358 test!("==")((*dynamic_cache.getRaw(1))[], data1);
1359 1360 dynamic_cache.putRaw(2, data2);
1361 test(dynamic_cache.exists(1));
1362 test(dynamic_cache.exists(2));
1363 test!("==")((*dynamic_cache.getRaw(1))[], data1);
1364 test!("==")((*dynamic_cache.getRaw(2))[], data2);
1365 1366 dynamic_cache.putRaw(3, data3);
1367 test(!dynamic_cache.exists(1));
1368 test(dynamic_cache.exists(2));
1369 test(dynamic_cache.exists(3));
1370 test!("==")((*dynamic_cache.getRaw(2))[], data2);
1371 test!("==")((*dynamic_cache.getRaw(3))[], data3);
1372 1373 dynamic_cache.clear;
1374 test!("==")(dynamic_cache.length, 0);
1375 test(!dynamic_cache.exists(1));
1376 test(!dynamic_cache.exists(2));
1377 test(!dynamic_cache.exists(3));
1378 1379 dynamic_cache.putRaw(1, data1);
1380 test!("==")(dynamic_cache.length, 1);
1381 test(dynamic_cache.exists(1));
1382 test!("==")((*dynamic_cache.getRaw(1))[], data1);
1383 1384 dynamic_cache.putRaw(2, data2);
1385 test!("==")(dynamic_cache.length, 2);
1386 test(dynamic_cache.exists(2));
1387 test!("==")((*dynamic_cache.getRaw(2))[], data2);
1388 1389 dynamic_cache.remove(1);
1390 test!("==")(dynamic_cache.length, 1);
1391 test(!dynamic_cache.exists(1));
1392 test(dynamic_cache.exists(2));
1393 }
1394 }
1395 }
1396 1397 1398 1399 1400 /*******************************************************************************
1401 1402 Performance test
1403 1404 *******************************************************************************/1405 1406 debug ( OceanPerformanceTest )
1407 {
1408 importocean.core.Memory;
1409 1410 importocean.math.random.Random;
1411 1412 importocean.time.StopWatch;
1413 1414 importocean.io.Stdout : Stderr;
1415 1416 unittest1417 {
1418 GC.disable;
1419 1420 Stderr.formatln("Starting Cache performance test");
1421 1422 autorandom = newRandom;
1423 1424 staticimmutablecache_size = 100_000;
1425 1426 staticimmutablemax_item_size = 1024 * 4;
1427 1428 StopWatchsw;
1429 1430 autocache = newCache!()(cache_size);
1431 1432 ubyte[] value;
1433 value.length = max_item_size;
1434 1435 time_ttime = 1;
1436 1437 // Fill cache1438 Stderr.formatln("Filling cache:");
1439 sw.start;
1440 for ( uinti; i < cache_size; i++ )
1441 {
1442 cache.put(i, time, value);
1443 ubyted_time;
1444 random(d_time);
1445 time += d_time % 16;
1446 }
1447 Stderr.formatln("{} puts, {} puts/s", cache_size, cast(float)cache_size / (cast(float)sw.microsec / 1_000_000));
1448 1449 // Put values into full cache1450 staticimmutableputs = 1_000_000;
1451 Stderr.formatln("Writing to cache: ");
1452 sw.start;
1453 for ( uinti; i < puts; i++ )
1454 {
1455 cache.put(i % cache_size, time, value);
1456 ubyted_time;
1457 random(d_time);
1458 time += d_time % 16;
1459 }
1460 Stderr.formatln("{} puts, {} puts/s", puts, cast(float)puts / (cast(float)sw.microsec / 1_000_000));
1461 1462 // Get values from cache1463 staticimmutablegets = 1_000_000;
1464 Stderr.formatln("Reading from cache: {} gets, {} gets/s", gets, cast(float)gets / (cast(float)sw.microsec / 1_000_000));
1465 sw.start;
1466 for ( uinti; i < gets; i++ )
1467 {
1468 cache.get(i % cache_size, time);
1469 ubyted_time;
1470 random(d_time);
1471 time += d_time % 16;
1472 }
1473 Stderr.formatln("Writing to cache: {} gets, {} gets/s", gets, cast(float)gets / (cast(float)sw.microsec / 1_000_000));
1474 1475 Stderr.formatln("Cache performance test finished");
1476 }
1477 }
1478 1479 version (CacheTest) voidmain ( ) { }
1480 1481 1482 unittest1483 {
1484 classCacheImpl: Cache!()
1485 {
1486 privatebool* item_dropped;
1487 privatesize_t* index;
1488 1489 publicthis (size_tmax_items, bool* item_dropped)
1490 {
1491 super(max_items);
1492 this.item_dropped = item_dropped;
1493 }
1494 1495 protectedoverridevoidwhenCacheItemDropped ( size_tindex )
1496 {
1497 *item_dropped = true;
1498 }
1499 }
1500 1501 1502 // Test if the whenCacheItemDropped is being called1503 staticimmutablemax_items = 10;
1504 autoitem_dropped = false;
1505 size_tindex = 0;
1506 1507 autocache = newCacheImpl( max_items, &item_dropped );
1508 1509 for(inti = 0; i < max_items * 2; i++)
1510 {
1511 autodata = cache.createRaw(i);
1512 1513 if(i > max_items - 1)
1514 {
1515 // Test if it is being called1516 test(item_dropped);
1517 1518 // Test the next case1519 item_dropped = false;
1520 }
1521 else1522 {
1523 test(!item_dropped);
1524 }
1525 }
1526 }