1 /*******************************************************************************
2 3 Cache with an element expiration facility.
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 The cache can be configured to apply different lifetimes to empty and
10 non-empty values (where a cached record with array length 0 is considered
11 "empty"). See constructor arguments.
12 13 Copyright:
14 Copyright (c) 2009-2016 dunnhumby Germany GmbH.
15 All rights reserved.
16 17 License:
18 Boost Software License Version 1.0. See LICENSE_BOOST.txt for details.
19 Alternatively, this file may be distributed under the terms of the Tango
20 3-Clause BSD License (see LICENSE_BSD.txt for details).
21 22 *******************************************************************************/23 24 moduleocean.util.container.cache.ExpiringCache;
25 26 importocean.meta.types.Qualifiers;
27 28 importocean.util.container.cache.model.IExpiringCacheInfo;
29 30 importocean.util.container.cache.Cache;
31 32 importcore.stdc.time: time_t;
33 34 version (unittest)
35 {
36 importocean.core.Test;
37 }
38 39 40 /*******************************************************************************
41 42 Data cache class template with element life time limitation. Stores items of
43 raw data, either of fixed or dynamic size. When the life time of an item,
44 which is the difference between its creation time and the current wall clock
45 time, has expired, it is removed automatically on the next getRaw()/exists()
46 access.
47 48 Params:
49 ValueSize = size of a data item. If 0 is specified (the default), the
50 items stored in the cache are of variable (dynamic) size
51 52 *******************************************************************************/53 54 classExpiringCache ( size_tValueSize = 0 ) : Cache!(ValueSize, true),
55 IExpiringCacheInfo56 {
57 importocean.core.Verify;
58 59 /***************************************************************************
60 61 Life time for non-empty items in seconds; may be changed at any time.
62 This value must be at least 1.
63 64 ***************************************************************************/65 66 publictime_tlifetime;
67 68 /***************************************************************************
69 70 Life time for empty items in seconds; may be changed at any time.
71 This value must be at least 1. Can be same as `lifetime`.
72 73 ExpiringCache considers a cached record with array length 0 as being
74 "empty".
75 76 ***************************************************************************/77 78 publictime_tempty_lifetime;
79 80 /***************************************************************************
81 82 Counts the number of lookups where an existing element was expired.
83 84 ***************************************************************************/85 86 protecteduintn_expired = 0;
87 88 /***************************************************************************
89 90 Constructor.
91 92 Params:
93 max_items = maximum number of items in the cache, set once, cannot
94 be changed
95 lifetime = lifetime for non-empty items in seconds; may be changed
96 at any time. This value must be at least 1.
97 empty_lifetime = lifetime for empty items in seconds. If set to 0
98 (default), will be same as regular `lifetime`
99 100 ***************************************************************************/101 102 publicthis ( size_tmax_items, time_tlifetime, time_tempty_lifetime = 0 )
103 {
104 verify (lifetime > 0,
105 "cache element lifetime is expected to be at least 1");
106 107 super(max_items);
108 109 this.lifetime = lifetime;
110 this.empty_lifetime = empty_lifetime ? empty_lifetime : lifetime;
111 }
112 113 /***************************************************************************
114 115 Gets an item from the cache. If the item was found in the cache, its
116 access time is updated. If the item life time has expired, it is
117 automatically removed.
118 119 Note that, if you change the value referenced by the returned reference,
120 the create time will not be updated.
121 122 Params:
123 key = key to lookup
124 125 Returns:
126 a reference to the item value or null if no such item was found or
127 it has expired so it was removed.
128 129 Out:
130 See super class.
131 132 ***************************************************************************/133 134 publicoverrideValueRefgetRaw ( hash_tkey )
135 {
136 boolexisted;
137 138 returnthis.getExpiringOrCreate(key, existed);
139 }
140 141 /***************************************************************************
142 143 Gets an item from the cache. If the item was found in the cache, its
144 access time is updated. If the item life time has expired, it is
145 automatically removed.
146 147 Note that, if you change the value referenced by the returned reference,
148 the create time will not be updated.
149 150 Params:
151 key = key to lookup
152 expired = true: the item was found but expired so it was removed,
153 false: the item was not found
154 155 Returns:
156 a reference to the item value or null if no such item was found or
157 it has expired so it was removed.
158 159 Out:
160 - If expired, the returned reference is null.
161 - See super class.
162 163 ***************************************************************************/164 165 publicValueRefgetRaw ( hash_tkey, outboolexpired )
166 out (val)
167 {
168 if (expired) assert (valisnull);
169 }
170 do171 {
172 boolexisted;
173 174 ValueRefval = this.getExpiringOrCreate(key, existed);
175 176 expired = !val && existed;
177 178 returnval;
179 }
180 181 /***************************************************************************
182 183 Gets an item from the cache or creates it if not already existing. If
184 the item was found in the cache, its access time is updated, otherwise
185 its create time is set. If the item was found but was expired, the
186 effect is the same as if the item was not found.
187 188 Note that the create time is set only if an item is created, not if it
189 already existed and you change the value referenced by the returned
190 reference.
191 192 Params:
193 key = key to lookup
194 existed = true: the item already existed,
195 false: the item was created either because it did not
196 exist or was expired
197 198 Returns:
199 a reference to the value of the obtained or created item. If an old
200 item was replaced, this reference refers to the old value.
201 202 Out:
203 See super class.
204 205 ***************************************************************************/206 207 publicoverrideValueRefgetOrCreateRaw ( hash_tkey, outboolexisted )
208 {
209 returnthis.getExpiringOrCreate(key, existed, true);
210 }
211 212 /***************************************************************************
213 214 Checks whether an item exists in the cache and updates its access time.
215 If the life time of the item has expired, it is removed.
216 217 Params:
218 key = key to lookup
219 expired = true: an item was found but removed because it was expired
220 221 Returns:
222 true if item exists in cache and its life time is not yet expired.
223 224 Out:
225 If expired is false, the return value is false.
226 227 ***************************************************************************/228 229 publicboolexists ( hash_tkey, outboolexpired )
230 out (does_exist)
231 {
232 if (expired) assert (!does_exist);
233 }
234 do235 {
236 returnthis.getRaw(key, expired) !isnull;
237 }
238 239 /***************************************************************************
240 241 Checks whether an item exists in the cache and updates its access time.
242 If the life time of the item has expired, it is removed.
243 244 Params:
245 key = key to lookup
246 247 Returns:
248 true if item exists in cache and its life time is not yet expired.
249 250 ***************************************************************************/251 252 publicoverrideboolexists ( hash_tkey )
253 {
254 boolexpired;
255 256 returnthis.exists(key, expired);
257 }
258 259 /***************************************************************************
260 261 Returns:
262 the number of cache lookups since instantiation or the last call of
263 resetStats() where the element could be found but was expired.
264 265 ***************************************************************************/266 267 publicuintnum_expired ( )
268 {
269 returnthis.n_expired;
270 }
271 272 /***************************************************************************
273 274 Resets the statistics counter values.
275 276 ***************************************************************************/277 278 publicoverridevoidresetStats ( )
279 {
280 super.resetStats();
281 this.n_expired = 0;
282 }
283 284 /***************************************************************************
285 286 Gets an item from the cache or optionally creates it if not already
287 existing. If the item was found in the cache, its access time is
288 updated, otherwise its create time is set. If the item was found but was
289 expired, the effect is the same as if the item was not found.
290 291 Note that the create time is set only if an item is created, not if it
292 already existed and you change the value referenced by the returned
293 reference.
294 295 Params:
296 key = key to lookup
297 existed = true: the item already existed,
298 false: the item did not exist or was expired
299 create = true: create the item if it doesn't exist or is expired
300 301 Returns:
302 a reference to the value of the obtained or created item. If an old
303 item was replaced, this reference refers to the old value.
304 305 Out:
306 - If create is true, the returned reference is not null.
307 - If create and existed are false, the returned reference is null.
308 309 ***************************************************************************/310 311 privateValueRefgetExpiringOrCreate ( hash_tkey, outboolexisted,
312 boolcreate = false )
313 out (val)
314 {
315 if (create)
316 {
317 assert (val !isnull);
318 }
319 elseif (!existed)
320 {
321 assert (valisnull);
322 }
323 }
324 do325 {
326 TimeToIndex.Node** node = keyinthis;
327 328 // opIn_r may return null but never a pointer to null.329 330 CacheItem* cache_item = null;
331 332 existed = node !isnull;
333 334 if (existed)
335 {
336 time_taccess_time;
337 338 cache_item = this.access(**node, access_time);
339 // XXX: This was previously an assert() but it was changed to340 // verify() due to a compiler bug when using -release -inline -O.341 // In that case the null check is removed by -release and it seems342 // that due to compiler optimizations and inlining, the compiler343 // ends up thinking that cache_item is null when used afterwards344 // (in the following if statement for example). By using verify()345 // instead of assert() we make sure the compiler can see there is a346 // null check even when -release is used.347 verify(cache_item !isnull,
348 "cache item existed, so it shouldn't be null");
349 boolempty = cache_item.value_ref.length == 0;
350 351 time_tused_lifetime = empty ? this.empty_lifetime : this.lifetime;
352 verify (used_lifetime > 0,
353 "cache element lifetime is expected to be at least 1");
354 355 if (access_time >= cache_item.create_time)
356 {
357 /*
358 * We silently tolerate the case the element was created after
359 * its last access because with the system time as external
360 * data source this is theoretically possible and at least no
361 * program bug.
362 */363 364 existed = (access_time - cache_item.create_time) < used_lifetime;
365 }
366 367 if (!existed)
368 {
369 if (create)
370 {
371 cache_item.create_time = access_time;
372 }
373 else374 {
375 this.remove_(key, **node);
376 cache_item = null;
377 }
378 379 this.n_expired++;
380 this.n_misses++;
381 }
382 }
383 elseif (create)
384 {
385 time_taccess_time;
386 387 cache_item = this.add(key, access_time);
388 389 cache_item.create_time = access_time;
390 }
391 392 returncache_item? cache_item.value_ref : null;
393 }
394 }
395 396 /******************************************************************************/397 398 importcore.sys.posix.stdlib: srand48, mrand48, drand48;
399 importcore.stdc.time: time;
400 401 extern (C) intgetpid();
402 403 404 unittest405 {
406 srand48(time(null)+getpid());
407 408 staticulongulrand ( )
409 {
410 return (cast (ulong) mrand48() << 0x20) | cast (uint) mrand48();
411 }
412 413 time_ttime = 234567;
414 415 // ---------------------------------------------------------------------416 // Test of expiring cache417 418 {
419 mstringdata1 = "hello world".dup,
420 data2 = "goodbye world".dup,
421 data3 = "hallo welt".dup;
422 423 time_tt = 0;
424 425 scopeexpiring_cache = newclassExpiringCache!()
426 {
427 this ( ) {super(4, 10, 5);}
428 429 overridetime_tnow ( ) {return ++t;}
430 };
431 432 with (expiring_cache)
433 {
434 test!("==")(length, 0);
435 436 *createRaw(1) = data1;
437 test!("==")(length, 1);
438 test(exists(1));
439 {
440 Value* data = getRaw(1);
441 test!("!is")(data, null);
442 test!("==")((*data)[], data1);
443 }
444 445 test!("<=")(t, 5);
446 t = 5;
447 448 *createRaw(2) = data2;
449 test!("==")(length, 2);
450 test(exists(2));
451 {
452 Value* data = getRaw(2);
453 test!("!is")(data, null);
454 test!("==")((*data)[], data2);
455 }
456 457 test!("<=")(t, 10);
458 t = 10;
459 460 test(!exists(1));
461 462 test!("<=")(t, 17);
463 t = 17;
464 465 {
466 Value* data = getRaw(2);
467 test!("is")(data, null);
468 }
469 }
470 471 // Test clear().472 with (expiring_cache)
473 {
474 t = 5;
475 476 test!("==")(length, 0);
477 478 *createRaw(1) = data1;
479 test!("==")(length, 1);
480 test(exists(1));
481 482 *createRaw(2) = data2;
483 test!("==")(length, 2);
484 test(exists(2));
485 486 clear();
487 test!("==")(length, 0);
488 test(!exists(1));
489 test(!exists(2));
490 }
491 492 // Test empty records493 with (expiring_cache)
494 {
495 t = 0;
496 test!("==")(length, 0);
497 498 *createRaw(1) = data1;
499 test!("==")(length, 1);
500 test(exists(1));
501 502 *getRaw(1) = null;
503 test!("==")(length, 1);
504 test(exists(1));
505 506 t = 6; // less than 10, more than 5507 {
508 Value* data = getRaw(1);
509 test!("is")(data, null);
510 }
511 }
512 }
513 514 }