ocean.util.container.cache.model.ICache source code

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 }