1 module tagion.utils.LRU;
2 
3 // EvictCallback is used to get a callback when a cache entry is evicted
4 
5 //import std.stdio;
6 import std.algorithm : map;
7 import std.conv;
8 import std.format;
9 import std.traits;
10 import tagion.utils.DList;
11 import tagion.utils.Result;
12 
13 @safe:
14 // LRU implements a non-thread safe fixed size LRU cache
15 class LRU(K, V) {
16     enum does_not_have_immutable_members = __traits(compiles, { V v; void f(ref V _v) {
17             _v = v;} });
18 
19             @safe @nogc struct Entry {
20                 K key;
21                 V value;
22                 this(K key, ref V value) pure nothrow {
23                     this.key = key;
24                     this.value = value;
25                 }
26             }
27 
28             alias EvictList = DList!(Entry*);
29             alias Element = EvictList.Element;
30             private EvictList evictList;
31             private Element*[K] items;
32             alias void delegate(scope const(K), Element*) @safe nothrow EvictCallback;
33             immutable uint size;
34             private EvictCallback onEvict;
35 
36             // NewLRU constructs an LRU of the given size
37             // size zero means unlimited
38             this(EvictCallback onEvict = null, immutable uint size = 0) pure nothrow {
39                 this.size = size;
40                 //evictList =  EvictList;
41                 this.onEvict = onEvict;
42             }
43 
44             // purge is used to completely clear the cache
45             void purge() {
46                 foreach (ref k, ref e; items) {
47                     if (onEvict !is null) {
48                         onEvict(k, e);
49                     }
50                 }
51                 items = null;
52                 evictList = EvictList.init;
53             }
54 
55             // add adds a value to the cache.  Returns true if an eviction occurred.
56             bool add(const(K) key, ref V value) {
57                 // Check for existing item
58                 auto ent = key in items;
59                 if (ent !is null) {
60                     auto element = *ent;
61                     evictList.moveToFront(element);
62                     //            onEvict(element, CallbackType.MOVEFRONT);
63                     return false;
64                 }
65 
66                 // Add new item
67                 auto entry = new Entry(key, value);
68                 auto element = evictList.unshift(entry);
69                 items[key] = element;
70 
71                 bool evict = (size != 0) && (evictList.length > size);
72                 // Verify size not exceeded
73                 if (evict) {
74                     // Remove the oldest element
75                     removeOldest;
76                 }
77                 return evict;
78             }
79 
80             // updates the value if exists or inserts if flag pecified
81             bool update(const(K) key, ref V value, bool upsert = false){
82                 auto ent = key in items;
83                 if (ent !is null) {
84                     auto element = *ent;
85                     element.entry.value = value;
86                     evictList.moveToFront(element);
87                     return true;
88                 }
89                 return upsert ? add(key,value) : false;
90             }
91 
92             // Get looks up a key's value from the cache.
93             static if (does_not_have_immutable_members) {
94                 bool get(scope const(K) key, ref V value) nothrow {
95                     auto ent = key in items;
96                     if (ent !is null) {
97                         auto element = *ent;
98                         evictList.moveToFront(element);
99                         value = element.entry.value;
100                         return true;
101                     }
102                     return false;
103                 }
104             }
105 
106             V opIndex(scope const(K) key) {
107                 static if (does_not_have_immutable_members) {
108                     V value;
109                     const found = get(key, value);
110                     static if (hasMember!(V, "undefined")) {
111                         if (!found) {
112                             return V.undefined;
113                         }
114                     } else {
115                         if(!found) {
116                             return V.init;
117                         }    
118                     }
119                     return value;
120                 }
121                 else {
122                     auto ent = key in items;
123                     if (ent !is null) {
124                         auto element = *ent;
125                         evictList.moveToFront(element);
126                         return element.entry.value;
127                     }
128                     static if (hasMember!(V, "undefined")) {
129                         return V.undefined;
130                     } else {
131                         return V.init;
132                     }                        
133 
134                 }
135             }
136 
137             void opIndexAssign(ref V value, const(K) key) {
138                 add(key, value);
139             }
140 
141             // Check if a key is in the cache, without updating the recent-ness
142             // or deleting it for being stale.
143             @nogc
144             bool contains(scope const(K) key) const pure nothrow {
145                 return (key in items) !is null;
146             }
147 
148             // Returns the key value (or undefined if not found) without updating
149             // the "recently used"-ness of the key.
150             static if (does_not_have_immutable_members) {
151                 @nogc
152                 bool peek(const(K) key, ref V value) pure nothrow {
153                     auto ent = key in items;
154                     if (ent !is null) {
155                         value = (*ent).entry.value;
156                         return true;
157                     }
158                     return false;
159                 }
160             }
161 
162             V peek(const(K) key) {
163                 static if (does_not_have_immutable_members) {
164                     V value;
165                     peek(key, value);
166                     return value;
167                 }
168                 else {
169                     auto ent = key in items;
170                     if (ent !is null) {
171                         return (*ent).entry.value;
172                     }
173                     static if (hasMember!(V, "undefined")) {
174                         return V.undefined;
175                     } else {
176                         return V.init;
177                     }                        
178                 }
179             }
180 
181             // Remove removes the provided key from the cache, returning if the
182             // key was contained.
183             
184             bool remove(scope const(K) key) nothrow {
185                 auto ent = key in items;
186                 if (ent !is null) {
187                     auto element = *ent;
188                     if (onEvict !is null) {
189                         onEvict(key, element);
190                     }
191                     evictList.remove(element);
192                     items.remove(key);
193                     return true;
194                 }
195                 return false;
196             }
197 
198             @nogc
199             void setEvict(EvictCallback evict) nothrow {
200                 onEvict = evict;
201             }
202 
203             // RemoveOldest removes the oldest item from the cache.
204             const(Result!(Entry*)) removeOldest() nothrow {
205                 const e = evictList.pop;
206                 if (!e.error) {
207                     auto element = items[e.value.key];
208                     items.remove(e.value.key);
209                     if (onEvict !is null) {
210                         onEvict(e.value.key, element);
211                     }
212                 }
213                 return e;
214             }
215 
216             // GetOldest returns the oldest entry
217             @nogc
218             const(Entry)* getOldest() const pure nothrow {
219                 auto last = evictList.last;
220                 if (last) {
221                     return evictList.last.entry;
222                 }
223                 else {
224                     return null;
225                 }
226             }
227 
228             /// keys returns a slice of the keys in the cache, from oldest to newest.
229             @nogc
230             auto keys() pure nothrow {
231                 return evictList.revert.map!(a => a.key);
232             }
233 
234             // length returns the number of items in the cache.
235             @nogc
236             uint length() pure const nothrow {
237                 return evictList.length;
238             }
239 
240             @nogc EvictList.Range!false opSlice() nothrow {
241                 return evictList[];
242             }
243 
244             invariant {
245                 assert(items.length == evictList.length);
246             }
247 }
248 
249     unittest {
250         alias LRU!(int, int) TestLRU;
251         uint evictCounter;
252 
253         void onEvicted(scope const(int) i, TestLRU.Element* e) @safe {
254             assert(e.entry.key == e.entry.value);
255             evictCounter++;
256         }
257 
258         enum amount = 8;
259         auto l = new TestLRU(&onEvicted, amount);
260         foreach (i; 0 .. amount) {
261             l.add(i, i);
262         }
263     }
264 
265     unittest {
266         alias LRU!(int, int) TestLRU;
267         uint evictCounter;
268 
269         void onEvicted(scope const(int) i, TestLRU.Element* e) @safe {
270             assert(e.entry.key == e.entry.value);
271             evictCounter++;
272         }
273 
274         enum amount = 8;
275         auto l = new TestLRU(&onEvicted, amount);
276         foreach (i; 0 .. amount * 2) {
277             l.add(i, i);
278             if (i < amount) {
279                 assert(i + 1 == l.length);
280             }
281             else {
282                 assert(amount == l.length);
283             }
284         }
285         assert(l.length == amount);
286         assert(evictCounter == amount);
287         int v;
288         bool ok;
289         import std.range : enumerate;
290 
291         foreach (i, k; l.keys.enumerate) {
292             ok = l.get(k, v);
293             assert(ok);
294             assert(k == v);
295             assert(v == i + amount);
296         }
297         foreach (j; 0 .. amount) {
298             ok = l.get(j, v);
299             assert(!ok, "should be evicted");
300         }
301 
302         foreach (j; amount .. amount * 2) {
303             ok = l.get(j, v);
304             assert(ok, "should not be evicted");
305         }
306         enum amount2 = (amount + amount / 2);
307         foreach (j; amount .. amount2) {
308             ok = l.remove(j);
309             assert(ok, "should contain j");
310             ok = l.remove(j);
311             assert(!ok, "should not be contained");
312             ok = l.get(j, v);
313             assert(!ok, "should be deleted");
314         }
315 
316         l.get(amount2, v); // expect amount2 to be last key in l.Keys()
317 
318         foreach (i, k; l.keys.enumerate) {
319             enum amount_i = amount / 2 - 1;
320             bool not_good = ((i < amount_i) && (k != i + amount2 + 1)) || ((i == amount_i) && (
321                     k != amount2));
322             assert(!not_good, "out of order key: " ~ to!string(k));
323         }
324 
325         l.purge();
326         assert(l.length == 0);
327 
328         ok = l.get(200, v);
329         assert(!ok, "should contain nothing");
330     }
331 
332     unittest { // getOldest removeOldest
333         alias LRU!(int, int) TestLRU;
334         uint evictCounter;
335         void onEvicted(scope const(int) i, TestLRU.Element* e) @safe {
336             assert(e.entry.key == e.entry.value);
337             evictCounter++;
338         }
339 
340         enum amount = 8;
341         auto l = new TestLRU(&onEvicted, amount);
342         bool ok;
343         foreach (i; 0 .. amount * 2) {
344             l.add(i, i);
345         }
346         auto e = l.getOldest();
347         assert(e !is null, "missing");
348         assert(e.value == amount, "bad value " ~ to!string(e.key));
349         e = l.removeOldest.value;
350         assert(e !is null, "missing");
351         assert(e.value == amount, "bad value " ~ to!string(e.key));
352         e = l.removeOldest.value;
353         assert(e !is null, "missing");
354         assert(e.value == amount + 1, "bad value " ~ to!string(e.value));
355     }
356 
357     // Test that Add returns true/false if an eviction occurred
358     unittest { // add
359         alias LRU!(int, int) TestLRU;
360         uint evictCounter;
361         void onEvicted(scope const(int) i, TestLRU.Element* e) @safe {
362             assert(e.entry.key == e.entry.value);
363             evictCounter++;
364         }
365 
366         bool ok;
367         auto l = new TestLRU(&onEvicted, 1);
368         // evictCounter := 0
369         // onEvicted := func(k interface{}, v interface{}) {
370         // 	evictCounter += 1
371         // }
372 
373         // l := NewLRU(1, onEvicted)
374         int x = 1;
375         ok = l.add(1, x);
376         assert(!ok);
377         assert(evictCounter == 0, "should not have an eviction");
378         x++;
379         ok = l.add(2, x);
380         assert(ok);
381         assert(evictCounter == 1, "should have an eviction");
382     }
383 
384     // Test that Contains doesn't update recent-ness
385     //func TestLRU_Contains(t *testing.T) {
386     unittest {
387         alias LRU!(int, int) TestLRU;
388         void onEvicted(scope const(int) i, TestLRU.Element* e) @safe {
389             assert(e.entry.key == e.entry.value);
390         }
391 
392         auto l = new TestLRU(&onEvicted, 2);
393         // l := NewLRU(2, nil)
394 
395         int x = 1;
396 
397         l.add(1, x);
398         x++;
399         l.add(2, x);
400         x++;
401         assert(l.contains(1), "1 should be contained");
402         l.add(3, x);
403         assert(!l.contains(1), "Contains should not have updated recent-ness of 1");
404 
405     }
406 
407     // Test that Peek doesn't update recent-ness
408     //func TestLRU_Peek(t *testing.T) {
409     unittest {
410         alias LRU!(int, int) TestLRU;
411         void onEvicted(scope const(int) i, TestLRU.Element* e) @safe {
412             assert(e.entry.key == e.entry.value);
413         }
414 
415         auto l = new TestLRU(&onEvicted, 2);
416         //	l := NewLRU(2, nil)
417         int x = 1;
418 
419         l.add(1, x);
420         x++;
421         l.add(2, x);
422         x++;
423         int v;
424         bool ok;
425         ok = l.peek(1, v);
426         assert(ok);
427         assert(v == 1, "1 should be set to 1 not " ~ to!string(v));
428         l.add(3, x);
429         assert(!l.contains(1), "should not have updated recent-ness of 1");
430     }
431 
432     unittest { // Test undefined
433         @safe struct E {
434             string x;
435             static E undefined() {
436                 return E("Not found");
437             }
438         }
439 
440         alias TestLRU = LRU!(int, E);
441         uint count;
442 
443         void onEvicted(scope const(int) i, TestLRU.Element* e) @safe {
444             count++;
445         }
446 
447         auto l = new TestLRU(&onEvicted);
448 
449         enum N = 4;
450         foreach (int i; 0 .. N) {
451             auto e = E(i.to!string);
452             l[i] = e;
453         }
454 
455         assert(l[N] == E.undefined);
456         assert(l[N - 1] != E.undefined);
457         assert(l.length == N);
458         assert(l.remove(2));
459         assert(count == 1);
460         assert(l.length == N - 1);
461         assert(l[2] == E.undefined);
462     }
463 
464     /// Test with a key which is not an atomic value
465     unittest {
466         import std.string : representation;
467 
468         alias Key = immutable(ubyte[]);
469         static struct E {
470             string x;
471             static E undefined() {
472                 return E("Not found");
473             }
474 
475         }
476 
477         alias TestLRU = LRU!(Key, E);
478         uint count;
479 
480         void onEvicted(scope const(Key) key, TestLRU.Element* e) @safe {
481             count++;
482         }
483 
484         auto l = new TestLRU(&onEvicted);
485 
486         Key make_key(size_t num) {
487             return format("data %d", num).representation;
488         }
489 
490         enum N = 4;
491         foreach (i; 0 .. N) {
492             auto key = make_key(i);
493             auto e = E(i.to!string);
494             l[key] = e;
495         }
496 
497         assert(l[make_key(N)] == E.undefined);
498         assert(l[make_key(N - 1)] != E.undefined);
499         assert(l.length == N);
500         assert(l.remove(make_key(2)));
501         assert(count == 1);
502         assert(l.length == N - 1);
503         assert(l[make_key(2)] == E.undefined);
504 //        alias TestSyncLRU = SyncLRU!(Key, E);
505     }
506 
507     /// update/upsert test
508     unittest{
509         alias LRU!(int, int) TestLRU;
510         uint evictCounter;
511         void onEvicted(scope const(int) i, TestLRU.Element* e) @safe {
512             assert(e.entry.key == e.entry.value || e.entry.value == e.entry.key * 7);
513             evictCounter++;
514         }
515         bool ok;
516         auto l = new TestLRU(&onEvicted, 2);
517         int x = 1;
518         ok = l.add(1, x);
519         assert(!ok);
520         assert(evictCounter == 0, "should not have an eviction");
521         x++;
522         ok = l.add(2, x);
523         assert(!ok);
524         assert(evictCounter == 0, "should still not have an eviction");
525         ok = l.get(2,x);
526         assert(ok);
527         assert(x == 2, "check inserted");
528         x = 14;
529         ok = l.update(2,x);
530         assert(ok);
531         ok = l.get(2, x);
532         assert(ok);
533         assert(x == 14, "check updates");
534         x = 3;
535         ok = l.update(3,x,true);
536         assert(ok);
537         assert(evictCounter == 1, "should have an eviction");
538         ok = l.get(3, x);
539         assert(ok);
540         assert(x == 3, "check upsert");
541     }
542 
543 /*
544     synchronized
545     class SyncLRU(K, V) {
546         alias LRU_t = LRU!(K, V);
547         protected LRU!(K, V) _lru;
548 
549         void opIndexAssign(ref V value, const(K) key) @trusted {
550             pragma(msg, "LRU ", typeof(_lru));
551             pragma(msg, "LRU_t ", LRU_t);
552             auto tmp_lru = cast(LRU_t) _lru;
553             tmp_lru.add(key, value);
554         }
555     }
556 */
557 
558