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