1 /******************************************************************************* 2 3 (L)east (R)ecently (U)sed Cache class, Caches data items according to their 4 access time and discards item that were least recently accessed. 5 6 Cache of raw data (ubyte[] / void[]) items of either fixed or variable 7 length. The cache is initialised with a fixed capacity (the number of items 8 that can be stored). When the cache reaches its full capacity, any newly 9 added items will replace older items in the cache. The cache keeps track of 10 the last time each item was written or read, and will replace the oldest 11 items first. 12 13 The basic Cache template is used to store raw data. A second template exists 14 which takes a type as its parameter. This implements a thin wrapper around 15 the basic Cache, allowing the transparent storage of (no-op) serialized 16 values of the specified type. 17 18 19 Note that with variable value length anything stored in the cache is 20 invisible to the garbage collector because the internal value data type of 21 the cache is ubyte[]. So if you store references (objects, pointers, slices 22 to dynamic arrays) in the cache with variable value length, make sure your 23 application keeps a reference to it. Otherwise the object referenced to may 24 be garbage collected and attempting to use it after getting it from the 25 cache will make your program go to HELL. 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.getOrCreate() return a reference to a record in the cache. 38 Cache.getAndRefresh() return a reference to a record in the cache or 39 returns null otherwise. 40 For fixed length values the record value reference is a slice to the record 41 value. 42 43 N.B. only get methods with `refresh` in their name update the recency of 44 an item. If you use a plain `get()` this won't happen and the item may get 45 evicted sooner than you might think. 46 47 Usage example: 48 49 --- 50 51 import ocean.util.container.LRUCache; 52 53 // Create a fixed-size cache which can store 2 items, each of length 3. 54 auto cache = new LRUCache!(char[3])(2); 55 56 // Add an item using getOrCreate(). getOrCreate() returns a pointer to 57 // void[] array with length 3 which references the value in the cache. 58 59 hash_t key = 0x12345678; 60 61 char[3] val = "abc"; 62 63 *cache.getOrCreate(key) = val[]; 64 65 // Obtain an item using getAndRefresh(). If found, getAndRefresh() 66 // returns a pointer to a value slice just like getOrCreate() or null 67 // if not found. 68 69 char[] val_got = cache.getAndRefresh(key); 70 71 if (val_got !is null) 72 { 73 // val_got contains the value that corresponds to key. 74 // The value in the cache can be modified in-place by setting array 75 // elements or copying to the whole array: 76 77 (cast(char[])val_got)[2] = '!'; // Set the third value byte to '!'. 78 79 (cast(char[])val_got)[] = "def"; // Set the value to "def". 80 } 81 else 82 { 83 // not found 84 } 85 86 --- 87 88 For variable length arrays it is a pointer to the Cache.Value struct which 89 encapsulates the value, which is void[], providing access to the value via 90 operator overloading: 91 92 - opAssign sets the value array instance to an input array slice 93 (overwriting the previous array instance), 94 - opSliceAssign treats the value array as an allocated buffer and copies 95 the content of the an input array slice into the value array, 96 - opSlice returns the value array. 97 98 opSliceAssign reuses an existing buffer and is therefore memory-friendly as 99 long as opAssign is not used with the same value instance. 100 101 Rule of thumb: For each cache instance with variable value size use either 102 opAssign or opSliceAssign with the values, never both. 103 104 Usage Example 1: Store string slices in a cache using Value.opAssign. 105 106 --- 107 108 auto cache = new LRUCache!(char[])(100); 109 110 char[] str1 = "Hello World", 111 str2 = "Eggs and Spam"; 112 113 { 114 auto val = cache.getRefreshOrCreate(4711); 115 116 // Store a slice to str1 in the array using (*val).opAssign. 117 118 *val = str1; 119 } 120 121 { 122 auto val = cache.getAndRefresh(4711); 123 124 // (*val)[] ((*val).opSlice) now returns a slice to str1. 125 126 // Replace this value with a slice to str2 using (*val).opAssign. 127 128 *val = str2; 129 } 130 131 --- 132 133 Usage Example 2: Store copies of strings in a cache using 134 Value.opSliceAssign. 135 136 --- 137 138 auto cache = new LRUCache!(char[])(100); 139 140 char[] str1 = "Hello World", 141 str2 = "Eggs and Spam"; 142 143 { 144 auto val = cache.getRefreshOrCreate(4711); 145 146 // Allocate a value array buffer with str1.length and copy the 147 // content of str1 into that value buffer. 148 149 (*val)[] = str1; 150 } 151 152 { 153 auto val = cache.getAndRefresh(4711); 154 155 // (*val)[] ((*val).opSlice) now returns the value array buffer 156 // which contains a copy of the content of str1. 157 158 // Use (*val)[] = str2 ((*val).opSliceAssign(x)) to resize the value 159 // array buffer to str2.length and copy the content of str2 into it. 160 161 (*val)[] = str2; 162 } 163 164 --- 165 166 For special situations it is possible to obtain a pointer to the value 167 array. One such situation is when the value array needs to be modified by 168 an external function which doesn't know about the cache. 169 170 --- 171 172 void setValue ( ref void[] value ) 173 { 174 value = "Hello World!"; 175 } 176 177 auto cache = new LRUCache!(char[])(100); 178 179 auto val = cache.getRefreshOrCreate(4711); 180 181 void[]* val_array = cast (void[]*) (*val); 182 183 setValue(*val_array); 184 185 --- 186 187 Link with: 188 -Llibebtree.a 189 190 TODO: 191 Extend the cache by making values visible to the GC by default and 192 provide GC hiding as an option. 193 194 Copyright: 195 Copyright (c) 2009-2016 dunnhumby Germany GmbH. 196 All rights reserved. 197 198 License: 199 Boost Software License Version 1.0. See LICENSE_BOOST.txt for details. 200 Alternatively, this file may be distributed under the terms of the Tango 201 3-Clause BSD License (see LICENSE_BSD.txt for details). 202 203 *******************************************************************************/ 204 205 module ocean.util.container.cache.LRUCache; 206 207 208 import ocean.util.container.cache.PriorityCache; 209 import core.stdc.time: time_t, time; 210 211 import core.memory; 212 import ocean.meta.traits.Basic /* : isArrayType, ArrayKind */; 213 214 /******************************************************************************* 215 216 Creates an extra create_time field depending on the template parameter. 217 218 Params: 219 T = the type of value to store 220 TrackCreateTimes = flags whether a create_time field should be created 221 222 *******************************************************************************/ 223 224 private struct ValueT(T, bool TrackCreateTimes) 225 { 226 T value; 227 static if (TrackCreateTimes) 228 { 229 time_t create_time; 230 } 231 } 232 233 /******************************************************************************* 234 235 Data cache class template. Stores items of raw data, either of fixed or 236 dynamic size. 237 238 Params: 239 T = type of item to store in cache 240 TrackCreateTimes = if true, each cache item is stored with its create 241 time, in addition to its last access time 242 243 *******************************************************************************/ 244 245 class LRUCache(T, bool TrackCreateTimes = false) : PriorityCache!(ValueT!(T, TrackCreateTimes)) 246 { 247 /*************************************************************************** 248 249 An alias for the type stored in PriorityCache. 250 251 The stored type is a wrapper around T which might (or might not) add 252 extra fields in addition to T be stored (depending on the 253 TrackCreateTimes template parameters). 254 255 ***************************************************************************/ 256 257 protected alias ValueT!(T, TrackCreateTimes) Value; 258 259 /*************************************************************************** 260 261 Constructor. 262 263 Params: 264 max_items = maximum number of items in the cache, set once, cannot 265 be changed 266 267 ***************************************************************************/ 268 269 public this ( size_t max_items ) 270 { 271 super(max_items); 272 } 273 274 /*************************************************************************** 275 276 Puts an item into the cache. If the cache is full, the oldest item is 277 replaced with the new item. (In the case where several items are equally 278 old, the choice of which one to be replaced is made arbitrarily.) 279 280 Params: 281 key = item key 282 value = item to store in cache 283 284 Returns: 285 true if a record was updated / overwritten, false if a new record 286 was added 287 288 ***************************************************************************/ 289 290 public bool put ( hash_t key, T value ) 291 { 292 bool existed; 293 294 T* dst = this.getRefreshOrCreate(key, existed); 295 296 if (dst) 297 { 298 // This check is not needed in D2 299 static if ( isArrayType!(T) == ArrayKind.Static ) 300 { 301 // TODO: Add support in PriorityCache.opApply for arrays 302 (*dst)[] = value[]; 303 } 304 else 305 { 306 (*dst) = value; 307 } 308 } 309 310 return existed; 311 } 312 313 /*************************************************************************** 314 315 Gets an item from the cache or creates it if not already existing. If 316 the item exists in the cache, its update time is updated, otherwise its 317 create time is set. 318 319 Note that the create time is set only if an item is created, not if it 320 already existed and you change the value referenced by the returned 321 pointer. 322 323 Params: 324 key = key to lookup or create 325 326 Returns: 327 The returned reference is never null. 328 329 ***************************************************************************/ 330 331 public T* getRefreshOrCreate ( hash_t key ) 332 out (val) 333 { 334 assert (val !is null); 335 } 336 do 337 { 338 bool existed_ignore; 339 340 return this.getRefreshOrCreate(key, existed_ignore); 341 } 342 343 /*************************************************************************** 344 345 Gets an item from the cache or creates it if not already existing. If 346 the item was found in the cache, its access time is updated, otherwise 347 its create time is set. 348 349 Note that the create time is set only if an item is created, not if it 350 already existed and you change the value referenced by the returned 351 reference. 352 353 Params: 354 key = key to lookup 355 existed = true: the item already existed, 356 false: the item was created 357 358 Returns: 359 a reference to the value of the obtained or created item. If an item 360 was created, the returned reference may refer to the value of a 361 previously removed element. 362 363 Out: 364 The returned reference is never null. 365 366 ***************************************************************************/ 367 368 public T* getRefreshOrCreate ( hash_t key, out bool existed ) 369 out (val) 370 { 371 assert (val !is null); 372 } 373 do 374 { 375 time_t access_time; 376 377 return this.getRefreshOrCreate(key, access_time, existed); 378 } 379 380 /*************************************************************************** 381 382 Gets an item from the cache or creates it if not already existing. If 383 the item was found in the cache, its access time is updated, otherwise 384 its create time is set. 385 386 Note that the create time is set only if an item is created, not if it 387 already existed and you change the value referenced by the returned 388 reference. 389 390 Params: 391 key = key to lookup 392 access_time = access time of the element 393 existed = true: the item already existed, 394 false: the item was created 395 396 Returns: 397 a reference to the value of the obtained or created item. If an item 398 was created, the returned reference may refer to the value of a 399 previously removed element. 400 401 Out: 402 The returned reference is never null. 403 404 ***************************************************************************/ 405 406 public T* getRefreshOrCreate ( hash_t key, out time_t access_time, out bool existed ) 407 out (val) 408 { 409 assert (val !is null); 410 } 411 do 412 { 413 if ( Value* val = this.getRefreshOrCreateRaw(key, access_time, existed) ) 414 { 415 return &val.value; 416 } 417 else 418 { 419 return null; 420 } 421 } 422 423 /*************************************************************************** 424 425 Gets an item from the cache or creates it if not already existing. If 426 the item was found in the cache, its access time is updated, otherwise 427 its create time is set. 428 429 Note that the create time is set only if an item is created, not if it 430 already existed and you change the value referenced by the returned 431 reference. 432 433 Params: 434 key = key to lookup 435 access_time = access time of the element 436 existed = true: the item already existed, 437 false: the item was created 438 439 Returns: 440 a reference to the value of the obtained or created item. If an item 441 was created, the returned reference may refer to the value of a 442 previously removed element. 443 444 Out: 445 The returned reference is never null. 446 447 ***************************************************************************/ 448 449 protected Value* getRefreshOrCreateRaw ( hash_t key, out time_t access_time, out bool existed ) 450 out (val) 451 { 452 assert (val !is null); 453 } 454 do 455 { 456 access_time = this.now(); 457 458 Value* value = this.getUpdateOrCreate(key, access_time, existed); 459 static if ( TrackCreateTimes ) 460 { 461 if (!existed) 462 { 463 value.create_time = access_time; 464 } 465 } 466 467 return value; 468 } 469 470 /*************************************************************************** 471 472 Gets an item from the cache. A pointer to the item is returned, if 473 found. If the item exists in the cache, its update time is updated. 474 475 Note that, if the item already existed and you change the value pointed 476 to by the returned pointer, the create time will not be updated. 477 478 Params: 479 key = key to lookup 480 481 Returns: 482 pointer to item value, may be null if key not found 483 484 ***************************************************************************/ 485 486 public T* getAndRefresh ( hash_t key ) 487 { 488 time_t access_time; 489 return this.getAndRefresh(key, access_time); 490 } 491 492 /*************************************************************************** 493 494 Gets an item from the cache. A pointer to the item is returned, if 495 found. If the item exists in the cache, its update time is updated. 496 497 Note that, if the item already existed and you change the value pointed 498 to by the returned pointer, the create time will not be updated. 499 500 Params: 501 key = key to lookup 502 access_time = access time of the element 503 504 Returns: 505 pointer to item value, may be null if key not found 506 507 ***************************************************************************/ 508 509 public T* getAndRefresh (hash_t key, out time_t access_time) 510 { 511 if ( Value* val = this.getAndRefreshRaw(key, access_time) ) 512 { 513 return &val.value; 514 } 515 else 516 { 517 return null; 518 } 519 } 520 521 /*************************************************************************** 522 523 Gets an item from the cache. A pointer to the item is returned, if 524 found. If the item exists in the cache, its update time is updated. 525 526 Note that, if the item already existed and you change the value pointed 527 to by the returned pointer, the create time will not be updated. 528 529 Params: 530 key = key to lookup 531 access_time = access time of the element 532 533 Returns: 534 pointer to item value, may be null if key not found 535 536 ***************************************************************************/ 537 538 protected Value* getAndRefreshRaw(hash_t key, out time_t access_time) 539 { 540 return this.updatePriority(key, access_time = this.now()); 541 } 542 543 /*************************************************************************** 544 545 Obtains the current time. By default this is the wall clock time in 546 seconds. 547 This time value is used to find the least recently updated cache item 548 and stored as create time. A subclass may override this method to use a 549 different time unit or clock. 550 551 552 Returns: 553 the current time in seconds. 554 555 ***************************************************************************/ 556 557 protected time_t now ( ) 558 { 559 return .time(null); 560 } 561 }