1 /******************************************************************************* 2 3 Cache base class, implements the cache logic that is not related to values. 4 5 Copyright: 6 Copyright (c) 2009-2016 dunnhumby Germany GmbH. 7 All rights reserved. 8 9 License: 10 Boost Software License Version 1.0. See LICENSE_BOOST.txt for details. 11 Alternatively, this file may be distributed under the terms of the Tango 12 3-Clause BSD License (see LICENSE_BSD.txt for details). 13 14 *******************************************************************************/ 15 16 module ocean.util.container.cache.model.ICache; 17 18 19 import ocean.meta.types.Qualifiers; 20 21 import ocean.util.container.cache.model.ICacheInfo; 22 23 import ocean.util.container.cache.model.containers.TimeToIndex; 24 import ocean.util.container.cache.model.containers.KeyToNode; 25 26 import core.stdc.time: time_t, time; 27 28 /******************************************************************************/ 29 30 abstract class ICache : ICacheInfo 31 { 32 import ocean.core.Verify; 33 34 /*************************************************************************** 35 36 Alias required by the subclasses. 37 38 ***************************************************************************/ 39 40 protected alias .TimeToIndex TimeToIndex; 41 42 /*************************************************************************** 43 44 Insert position into array of items. 45 46 ***************************************************************************/ 47 48 private size_t insert; 49 50 51 /*************************************************************************** 52 53 Mapping from access time to the index of an item in the items array. The 54 map is implemented with an EBTree, so that it is sorted in order of 55 access times. 56 57 The time-to-index mapping records are stored in time_to_index as 58 so-called EBTree "nodes" of type TimeToIndex.Node. Each node contains a 59 so-called "key" of type TimeToIndex.Key which consists of two uint 60 values, "lo" and "hi". 61 The sort order is ascending by "hi"; records with the same "hi" value 62 are sorted by "lo". Therefore, since the time-to-index mapping records 63 should be sorted by access time, time and cache index are stored as 64 65 TimeToIndex.Key.hi = access time, 66 TimeToIndex.Key.lo = cache index. 67 68 ***************************************************************************/ 69 70 protected TimeToIndex time_to_index; 71 72 73 /*************************************************************************** 74 75 Mapping from key to TimeToIndex.Mapping struct (which contains a mapping 76 from an access time to the index of an elements in this.items). 77 78 ***************************************************************************/ 79 80 protected KeyToNode key_to_node; 81 82 83 /*************************************************************************** 84 85 Maximum number of items in the cache. 86 87 ***************************************************************************/ 88 89 private size_t max_items; 90 91 /*************************************************************************** 92 93 Counters for the cache lookups and misses. 94 95 ***************************************************************************/ 96 97 protected uint n_lookups = 0, 98 n_misses = 0; 99 100 /*************************************************************************** 101 102 Constructor. 103 104 Params: 105 max_items = maximum number of items in the cache, set once, cannot 106 be changed 107 108 ***************************************************************************/ 109 110 protected this ( size_t max_items ) 111 { 112 this.insert = 0; 113 114 this.max_items = max_items; 115 this.time_to_index = new TimeToIndex(max_items); 116 this.key_to_node = new KeyToNode(max_items); 117 } 118 119 /*************************************************************************** 120 121 Removes all items from the cache. 122 123 ***************************************************************************/ 124 125 public void clear ( ) 126 { 127 this.time_to_index.clear(); 128 this.key_to_node.clear(); 129 this.insert = 0; 130 } 131 132 /*************************************************************************** 133 134 Returns: 135 the number of items currently in the cache. 136 137 ***************************************************************************/ 138 139 public size_t length ( ) 140 { 141 return this.insert; 142 } 143 144 /*************************************************************************** 145 146 Returns: 147 the maximum number of items the cache can have. 148 149 ***************************************************************************/ 150 151 public size_t max_length ( ) 152 { 153 return this.max_items; 154 } 155 156 /*************************************************************************** 157 158 Returns: 159 the number of cache lookups since instantiation or the last call of 160 resetStats(). 161 162 ***************************************************************************/ 163 164 public uint num_lookups ( ) 165 { 166 return this.n_lookups; 167 } 168 169 /*************************************************************************** 170 171 Returns: 172 the number of cache lookups since instantiation or the last call of 173 resetStats(). 174 175 ***************************************************************************/ 176 177 public uint num_misses ( ) 178 { 179 return this.n_misses; 180 } 181 182 /*************************************************************************** 183 184 Resets the statistics counter values. 185 186 ***************************************************************************/ 187 188 public void resetStats ( ) 189 { 190 this.n_lookups = this.n_misses = 0; 191 } 192 193 /*************************************************************************** 194 195 Checks whether an item exists in the cache. 196 197 Params: 198 key = key to lookup 199 200 Returns: 201 true if item exists in cache 202 203 ***************************************************************************/ 204 205 public bool exists ( hash_t key ) 206 { 207 return (key in this) !is null; 208 } 209 210 /*************************************************************************** 211 212 Removes an item from the cache. 213 214 Params: 215 key = key of item to remove 216 217 Returns: 218 returns true if removed, false if not in cache 219 220 ***************************************************************************/ 221 222 public bool remove ( hash_t key ) 223 { 224 TimeToIndex.Node** node = key in this; 225 226 if (node) 227 { 228 this.remove_(key, **node); 229 return true; 230 } 231 else 232 { 233 return false; 234 } 235 } 236 237 /*************************************************************************** 238 239 Checks whether an item exists in the cache and returns the last time it 240 was accessed. 241 242 Params: 243 key = key to lookup 244 245 Returns: 246 item's last access time, or 0 if the item doesn't exist 247 248 ***************************************************************************/ 249 250 public time_t accessTime ( hash_t key ) 251 { 252 TimeToIndex.Node** node = key in this; 253 254 return node? (*node).key.hi : 0; 255 } 256 257 /*************************************************************************** 258 259 Obtains the index of the cache item that corresponds to node and updates 260 the access time. 261 If realtime is enabled, access_time is expected to be equal to or 262 greater than the time stored in node. If disabled and the access time is 263 less, the node will not be updated and a value of at least length 264 returned. 265 266 267 Params: 268 node = time-to-index tree node 269 access_time = access time 270 271 Returns: 272 the index of the corresponding cache item or a value of at least 273 length if realtime is disabled and the access time is less than the 274 access time in the node. 275 276 Out: 277 If realtime is enabled, the returned index is less than length. 278 279 ***************************************************************************/ 280 281 protected size_t accessIndex ( ref TimeToIndex.Node node, out time_t access_time ) 282 out (index) 283 { 284 assert (index < this.insert, "cache index out of bounds"); 285 } 286 do 287 { 288 TimeToIndex.Key key = node.key; 289 290 access_time = key.hi = this.now; 291 292 this.time_to_index.update(node, key); 293 294 return key.lo; 295 } 296 297 /*************************************************************************** 298 299 Obtains the current time. By default this is the wall clock time in 300 seconds. 301 This time value is used to find the least recently updated cache item 302 and stored as create time. A subclass may override this method to use a 303 different time unit or clock. 304 305 306 Returns: 307 the current time in seconds. 308 309 ***************************************************************************/ 310 311 protected time_t now ( ) 312 { 313 return .time(null); 314 } 315 316 /*************************************************************************** 317 318 Obtains the index of the cache item that corresponds to key and updates 319 the access time. 320 If realtime is enabled and key could be found, access_time is expected 321 to be at least the time value stored in node. If disabled and 322 access_time is less, the result is the same as if key could not be 323 found. 324 325 326 Params: 327 key = time-to-index tree key 328 access_time = access time 329 330 Returns: 331 the index of the corresponding cache item or a value of at least 332 this.length if key could not be found. 333 334 ***************************************************************************/ 335 336 protected size_t get_ ( hash_t key, out time_t access_time ) 337 { 338 TimeToIndex.Node** node = key in this; 339 340 return node? this.accessIndex(**node, access_time) : size_t.max; 341 } 342 343 /*************************************************************************** 344 345 Obtains the time-to-index node for key. 346 347 Params: 348 key = key to lookup 349 350 Returns: 351 pointer to the time-to-index node for key or null if not found. 352 353 Out: 354 If found, it is safe to dereference the pointer to which the 355 returned pointer points (*node is not null). 356 357 ***************************************************************************/ 358 359 protected TimeToIndex.Node** opIn_r ( hash_t key ) 360 out (node) 361 { 362 if (node) assert (*node !is null, "null pointer value was stored in key_to_node"); 363 } 364 do 365 { 366 TimeToIndex.Node** node = key in this.key_to_node; 367 368 this.n_lookups++; 369 this.n_misses += (node is null); 370 371 return node; 372 } 373 374 375 /*************************************************************************** 376 377 Support for the 'in' operator 378 379 Aliased to opIn_r, for backwards compatibility 380 381 ***************************************************************************/ 382 383 protected alias opBinaryRight ( istring op : "in" ) = opIn_r; 384 385 386 /*************************************************************************** 387 388 Registers a new cache element and obtains the cache item index for it. 389 If the cache is full, the oldest cache element is replaced. 390 If realtime is enabled, time is expected to be at least the time value 391 of the most recent cache element. 392 If realtime is disabled and time is less than the time value of the most 393 recent cache element, nothing is done and a value of at least length is 394 returned. 395 396 Params: 397 key = cache element key 398 access_time = cache element creation time 399 400 Returns: 401 the index of the cache item that corresponds to the newly registered 402 cache element or a value of at least length if realtime is disabled 403 and time is less than the time value of the most recent cache 404 element. 405 406 In: 407 If realtime is enabled, time must bebe at least the time value of 408 the most recent cache element. 409 410 Out: 411 If realtime is enabled, the returned index is below length. 412 413 ***************************************************************************/ 414 415 protected size_t register ( hash_t key, out time_t access_time ) 416 out (index) 417 { 418 assert (index < this.max_length); 419 } 420 do 421 { 422 size_t index; 423 424 access_time = this.now; 425 426 if ( this.insert < this.max_length ) 427 { 428 index = this.insert++; 429 } 430 else 431 { 432 // Find the item with lowest (ie oldest) update time. 433 TimeToIndex.Node* oldest_time_node = this.time_to_index.first; 434 435 verify (oldest_time_node !is null); 436 437 // Get the item index and check if the time of the last access is 438 // less than the current time. If not, notify the subclass because 439 // we are about to replace the oldest record with an even older one. 440 441 with (oldest_time_node.key) 442 { 443 index = lo; 444 445 if (access_time < hi) 446 { 447 this.whenEarlierThanOldestItem(access_time, hi); 448 } 449 } 450 451 // Call the notifier method before actual removal 452 this.whenCacheItemDropped(index); 453 454 // Remove old item in tree map 455 this.time_to_index.remove(*oldest_time_node); 456 457 this.key_to_node.remove(this.keyByIndex(index)); 458 } 459 460 461 *this.key_to_node.put(key) = this.time_to_index.add(TimeToIndex.Key(index, access_time)); 462 463 464 return index; 465 } 466 467 /*************************************************************************** 468 469 Called when the time value returned by now() is less than the time of 470 last access of the oldest record in the cache; may be overridden by a 471 subclass to be notified if this happens. 472 With the system time as external data source this can theoretically 473 happen and is at least not a program bug so in this class assert() would 474 be inappropriate. 475 476 Params: 477 now = time value reported by now() 478 oldest = last access time of the oldest record in the cache 479 480 ***************************************************************************/ 481 482 protected void whenEarlierThanOldestItem ( time_t now, time_t oldest ) { } 483 484 /*************************************************************************** 485 486 Called when the oldest item is replaced in cache with a new one 487 because cache is full. 488 When the cache gets full, the oldest item will be replaced with the 489 new value. Before that happens, this method will be called, having 490 the item index passed as a argument. 491 492 Params: 493 index = index of the cache item that will be dropped. 494 495 ***************************************************************************/ 496 497 protected void whenCacheItemDropped ( size_t index ) { } 498 499 /*************************************************************************** 500 501 Obtains the key of the cache item corresponding to index. 502 503 Params: 504 index = cache item index, guaranteed to be below length 505 506 Returns: 507 cache item key 508 509 ***************************************************************************/ 510 511 abstract protected hash_t keyByIndex ( size_t index ); 512 513 /*************************************************************************** 514 515 Removes the cache item that corresponds to dst_key and dst_node. 516 517 Params: 518 dst_key = key of item to remove 519 dst_node = time-to-index tree node to remove 520 521 ***************************************************************************/ 522 523 protected void remove_ ( hash_t dst_key, ref TimeToIndex.Node dst_node ) 524 { 525 /* 526 * Remove item in items list by copying the last item to the item to 527 * remove and decrementing the insert index which reflects the 528 * actual number of items. 529 */ 530 531 size_t index = dst_node.key.lo; 532 533 // Remove the tree map entry of the removed cache item. 534 this.time_to_index.remove(dst_node); 535 536 // Remove key -> item mapping 537 this.key_to_node.remove(dst_key); 538 539 if ( index != this.insert - 1) 540 { 541 hash_t src_key = this.replaceRemovedItem(index, this.insert - 1); 542 543 /* 544 * Obtain the time-to-mapping entry for the copied cache item. 545 * Update it to the new index and update the key-to-mapping 546 * entry to the updated time-to-mapping entry. 547 */ 548 549 TimeToIndex.Node** src_node_in_map = src_key in this.key_to_node; 550 551 verify (src_node_in_map !is null, "Null src_node_in_map found"); 552 553 TimeToIndex.Node* src_node = *src_node_in_map; 554 555 verify (src_node !is null, "Null src_node found"); 556 557 TimeToIndex.Key src_node_key = src_node.key; 558 559 src_node_key.lo = index; 560 561 *src_node_in_map = this.time_to_index.update(*src_node, src_node_key); 562 } 563 564 this.insert--; 565 } 566 567 /*************************************************************************** 568 569 Called when a cache element is removed, replaces the cache items at 570 index "replaced"" with the one at index "replace". 571 572 The "replace" and "replaced" indices are guaranteed to be different and 573 valid cache item indices, i.e. less than this.length. 574 575 When this method has returned, the cache item at index "replace" won't 576 be used until a new cache element is added; a subclass is free to do 577 with it as it pleases but should be aware that it will be reused later 578 on. 579 580 Params: 581 replaced = index of the cache item that is to be replaced 582 replace = index of the cache item that will replace the replaced 583 item 584 585 Returns: 586 the key of the cache item that was at index "replace"" before and is 587 at index "replaced" now. 588 589 ***************************************************************************/ 590 591 protected hash_t replaceRemovedItem ( size_t replaced, size_t replace ); 592 }