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