ocean.util.container.cache.ExpiringLRUCache source code

1 /*******************************************************************************
2 
3     Expiring (L)east (R)ecently (U)sed Cache.
4 
5     Extends the Cache by providing a settable lifetime and automatically
6     removing  elements where the difference between the current time and the
7     createtime is greater than that lifetime value.
8 
9     Copyright:
10         Copyright (c) 2009-2016 dunnhumby Germany GmbH.
11         All rights reserved.
12 
13     License:
14         Boost Software License Version 1.0. See LICENSE_BOOST.txt for details.
15         Alternatively, this file may be distributed under the terms of the Tango
16         3-Clause BSD License (see LICENSE_BSD.txt for details).
17 
18 *******************************************************************************/
19 
20 module ocean.util.container.cache.ExpiringLRUCache;
21 
22 
23 import ocean.meta.types.Qualifiers;
24 
25 import ocean.util.container.cache.model.IExpiringCacheInfo;
26 
27 import ocean.util.container.cache.LRUCache;
28 
29 import core.stdc.time: time_t;
30 
31 version (unittest) import ocean.core.Test;
32 
33 /*******************************************************************************
34 
35     Data cache class template with element life time limitation. Stores items of
36     raw data, either of fixed or dynamic size. When the life time of an item,
37     which is the difference between its creation time and the current wall clock
38     time, has expired, it is removed automatically on the next
39     getAndRefreshValue()/exists() access.
40 
41     Params:
42         T = the type of data that will be stored
43 
44 *******************************************************************************/
45 
46 class ExpiringLRUCache(T = void[]) : LRUCache!(T, true), IExpiringCacheInfo
47 {
48     import ocean.core.Verify;
49 
50     /***************************************************************************
51 
52         Life time for all items in seconds; may be changed at any time.
53         This value must be at least 1.
54 
55     ***************************************************************************/
56 
57     public time_t lifetime;
58 
59     /***************************************************************************
60 
61         Counts the number of lookups where an existing element was expired.
62 
63     ***************************************************************************/
64 
65     protected uint n_expired = 0;
66 
67     /***************************************************************************
68 
69         Constructor.
70 
71         Params:
72             max_items = maximum number of items in the cache, set once, cannot
73                         be changed
74             lifetime  = life time for all items in seconds; may be changed at
75                         any time. This value must be at least 1.
76 
77     ***************************************************************************/
78 
79     public this ( size_t max_items, time_t lifetime )
80     {
81         verify (lifetime > 0,
82                 "cache element lifetime is expected to be at least 1");
83 
84         super(max_items);
85 
86         this.lifetime = lifetime;
87     }
88 
89     /***************************************************************************
90 
91         Gets an item from the cache. If the item was found in the cache, its
92         access time is updated. If the item life time has expired, it is
93         automatically removed.
94 
95         Note that, if you change the value referenced by the returned reference,
96         the create time will not be updated.
97 
98         Params:
99             key = key to lookup
100 
101         Returns:
102             a reference to the item value or null if no such item was found or
103             it has expired so it was removed.
104 
105     ***************************************************************************/
106 
107     public override T* getAndRefresh ( hash_t key )
108     {
109         bool existed;
110 
111         return this.getAndRefresh(key, existed);
112     }
113 
114     /// ditto
115     public alias LRUCache!(T, true).getAndRefresh getAndRefresh;
116 
117     /***************************************************************************
118 
119         Gets an item from the cache. If the item was found in the cache, its
120         access time is updated. If the item life time has expired, it is
121         automatically removed.
122 
123         Note that, if you change the value referenced by the returned reference,
124         the create time will not be updated.
125 
126         Params:
127             key     = key to lookup
128             expired = true:  the item was found but expired so it was removed,
129                       false: the item was not found
130 
131         Returns:
132             a reference to the item value or null if no such item was found or
133             it has expired so it was removed.
134 
135         Out:
136             - If expired, the returned reference is null.
137 
138     ***************************************************************************/
139 
140     public T* getAndRefresh ( hash_t key, out bool expired )
141     out (val)
142     {
143         if (expired) assert (val is null);
144     }
145     do
146     {
147         bool existed;
148 
149         T* val = this.getExpiringOrCreate(key, existed);
150 
151         expired = !val && existed;
152 
153         return val;
154     }
155 
156     /***************************************************************************
157 
158         Gets an item from the cache or creates it if not already existing. If
159         the item was found in the cache, its access time is updated, otherwise
160         its create time is set. If the item was found but was expired, the
161         effect is the same as if the item was not found.
162 
163         Note that the create time is set only if an item is created, not if it
164         already existed and you change the value referenced by the returned
165         reference.
166 
167         Params:
168             key     = key to lookup
169             existed = true:  the item already existed,
170                       false: the item was created either because it did not
171                              exist or was expired
172 
173         Returns:
174             a reference to the value of the obtained or created item. If an old
175             item was replaced, this reference refers to the old value.
176 
177         Out:
178             See super class.
179 
180     ***************************************************************************/
181 
182     public override T* getRefreshOrCreate ( hash_t key, out bool existed )
183     {
184         return this.getExpiringOrCreate(key, existed, true);
185     }
186 
187     /***************************************************************************
188 
189         Imports the super class overloaded methods which were hidden by the
190         getOrCreate() override implementation.
191 
192     ***************************************************************************/
193 
194     alias LRUCache!(T, true).getRefreshOrCreate getRefreshOrCreate;
195 
196     /***************************************************************************
197 
198         Checks whether an item exists in the cache and updates its access time.
199         If the life time of the item has expired, it is removed.
200 
201         Params:
202             key     = key to lookup
203             expired = true: an item was found but removed because it was expired
204 
205         Returns:
206             true if item exists in cache and its life time is not yet expired.
207 
208         Out:
209             If expired is false, the return value is false.
210 
211     ***************************************************************************/
212 
213     public bool exists ( hash_t key, out bool expired )
214     out (does_exist)
215     {
216         if (expired) assert (!does_exist);
217     }
218     do
219     {
220         return this.getAndRefresh(key, expired) !is null;
221     }
222 
223     /***************************************************************************
224 
225         Checks whether an item exists in the cache and updates its access time.
226         If the life time of the item has expired, it is removed.
227 
228         Params:
229             key = key to lookup
230 
231         Returns:
232             true if item exists in cache and its life time is not yet expired.
233 
234     ***************************************************************************/
235 
236     override public bool exists ( hash_t key )
237     {
238         bool expired;
239 
240         return this.exists(key, expired);
241     }
242 
243     /***************************************************************************
244 
245         Returns:
246             the number of cache lookups  since instantiation or the last call of
247             resetStats() where the element could be found but was expired.
248 
249     ***************************************************************************/
250 
251     public uint num_expired ( )
252     {
253         return this.n_expired;
254     }
255 
256     /***************************************************************************
257 
258         Resets the statistics counter values.
259 
260     ***************************************************************************/
261 
262     public override void resetStats ( )
263     {
264         super.resetStats();
265         this.n_expired = 0;
266     }
267 
268     /***************************************************************************
269 
270         Gets an item from the cache or optionally creates it if not already
271         existing. If the item was found in the cache, its access time is
272         updated, otherwise its create time is set. If the item was found but was
273         expired, the effect is the same as if the item was not found.
274 
275         Note that the create time is set only if an item is created, not if it
276         already existed and you change the value referenced by the returned
277         reference.
278 
279         Params:
280             key     = key to lookup
281             existed = true:  the item already existed,
282                       false: the item did not exist or was expired
283             create  = true: create the item if it doesn't exist or is expired
284 
285         Returns:
286             a reference to the value of the obtained or created item. If an old
287             item was replaced, this reference refers to the old value.
288 
289         Out:
290             - If create is true, the returned reference is not null.
291             - If create and existed are false, the returned reference is null.
292 
293     ***************************************************************************/
294 
295     private T* getExpiringOrCreate ( hash_t key, out bool existed,
296                                      bool create = false )
297     out (val)
298     {
299         if (create)
300         {
301             assert (val !is null);
302         }
303         else if (!existed)
304         {
305             assert (val is null);
306         }
307     }
308     do
309     {
310         verify (this.lifetime > 0,
311                 "cache element lifetime is expected to be at least 1");
312 
313         Value* item;
314 
315         time_t new_access_time;
316         if (create)
317         {
318             item = this.getRefreshOrCreateRaw(key, new_access_time, existed);
319         }
320         else
321         {
322             item = this.getAndRefreshRaw(key, new_access_time);
323             existed = item !is null;
324         }
325 
326         if (item)
327         {
328             // If we reached that point, then it must be an old item which
329             // existed before. We should check if it has expired
330             if (new_access_time >= item.create_time &&
331                 this.lifetime <= (new_access_time - item.create_time))
332             {
333                 existed = false;
334                 this.remove(key);
335                 item = null;
336 
337                 this.n_expired++;
338                 // TODO: increase these ones
339                 // this.n_misses++;
340             }
341 
342             return &item.value;
343         }
344         else
345         {
346             // The misses was already increased, no need to do it again
347             return null;
348         }
349     }
350 }
351 
352 /******************************************************************************/
353 
354 import core.sys.posix.stdlib: srand48, mrand48, drand48;
355 import core.stdc.time: time;
356 
357 
358 extern (C) int getpid();
359 
360 
361 unittest
362 {
363     srand48(time(null)+getpid());
364 
365     static ulong ulrand ( )
366     {
367         return (cast (ulong) mrand48() << 0x20) | cast (uint) mrand48();
368     }
369 
370     time_t time = 234567;
371 
372     // ---------------------------------------------------------------------
373     // Test of expiring cache
374 
375     {
376         mstring data1 = "hello world".dup,
377                 data2 = "goodbye world".dup,
378                 data3 = "hallo welt".dup;
379 
380         time_t t = 0;
381 
382         scope expiring_cache = new class ExpiringLRUCache!()
383         {
384             this ( ) {super(4, 10);}
385 
386             override time_t now ( ) {return ++t;}
387         };
388 
389         with (expiring_cache)
390         {
391             test(length == 0);
392 
393             *getRefreshOrCreate(1) = data1;
394             test(length == 1);
395             test(exists(1));
396             {
397                 auto data = getAndRefresh(1);
398                 test(data !is null);
399                 test((*data)[] == data1);
400             }
401 
402             test(t <= 5);
403             t = 5;
404 
405             *getRefreshOrCreate(2) = data2;
406             test(length == 2);
407             test(exists(2));
408             {
409                 auto data = getAndRefresh(2);
410                 test(data !is null);
411                 test((*data)[] == data2);
412             }
413 
414             test(t <= 10);
415             t = 10;
416 
417             test(!exists(1));
418 
419             test(t <= 17);
420             t = 17;
421             {
422                 auto data = getAndRefresh(2);
423                 test(data is null);
424             }
425         }
426     }
427 
428 }
429 
430 unittest
431 {
432     // check cache with const elements
433     scope expiring_cache = new ExpiringLRUCache!(cstring)(1, 1);
434     *expiring_cache.getRefreshOrCreate(1) = "abc"[];
435 }