1 module tagion.utils.LRUT;
2 
3 import core.atomic;
4 import std.algorithm : map;
5 import std.conv;
6 import std.format;
7 import std.traits;
8 import std.datetime.systime;
9 import tagion.utils.DList;
10 import tagion.utils.Result;
11 
12 import tagion.utils.LRU;
13 
14 @safe:
15 
16 double timestamp() nothrow
17 {
18     auto ts = Clock.currTime().toTimeSpec();
19     return ts.tv_sec + ts.tv_nsec/1e9;
20 }
21 
22 // LRUT is a thread-safe timed successor of tagion.utils.LRU
23 
24 synchronized 
25 class LRUT(K,V) {
26     
27     enum does_not_have_immutable_members = __traits(compiles, { V v; void f(ref V _v) { _v = v;} });
28 
29 
30     alias LRU_t=LRU!(K, V);
31     
32     alias Entry = LRU_t.Entry;
33     alias EvictList = LRU_t.EvictList;
34     alias Element = LRU_t.Element;
35     alias EvictCallback = LRU_t.EvictCallback;
36 
37     
38     protected LRU!(K, V) _lru;
39     private immutable double maxage;
40     private double[K] ctime;
41 
42     this(EvictCallback onEvict = null, immutable uint size = 0, immutable double maxage = 0) nothrow {
43         _lru = new LRU_t(null,size);
44         auto tmp_lru=(() @trusted => cast(LRU_t)_lru)();
45         tmp_lru.setEvict(cast(EvictCallback)onEvict);
46         this.maxage = maxage;
47     }    
48 
49     double upTime( K key ) nothrow {
50         auto t = key in ctime;
51         return (t !is null) ? timestamp() - *t : -1;
52     }
53     
54     bool expired( K key ) nothrow {
55         return (this.maxage > 0) && (upTime(key) > this.maxage);
56     }
57     
58     // -- LRU members wrapped
59 
60     // purge is used to completely clear the cache
61     void purge() {
62         auto tmp_lru=(() @trusted => cast(LRU_t)_lru)();
63         tmp_lru.purge();
64         ctime = null;
65     }
66 
67 
68     // add adds a value to the cache.  Returns true if an eviction occurred.
69     bool add( K key, ref V value, bool update = false) {
70         auto tmp_lru=(() @trusted => cast(LRU_t)_lru)();
71         if(tmp_lru.contains(key) && update){
72             tmp_lru.update(key,value);
73             ctime[key] = timestamp;
74             return false;
75         }
76         ctime[key] = timestamp;
77         return tmp_lru.add(key,value);
78     }
79     
80     // Get looks up a key's value from the cache.
81     static if (does_not_have_immutable_members) {
82         bool get( K key, ref V value) {
83             auto tmp_lru=(() @trusted => cast(LRU_t)_lru)();
84             if(expired(key)){
85                 tmp_lru.remove(key);
86                 return false;
87             }    
88             return tmp_lru.get(key, value);
89         }
90     }
91 
92     V opIndex( K key) {
93         auto tmp_lru=(() @trusted => cast(LRU_t)_lru)();
94         if(expired(key)){
95             tmp_lru.remove(key);
96             static if (hasMember!(V, "undefined")) {
97                 return V.undefined;
98             } else {
99                 return V.init;
100             }                        
101         }
102         return tmp_lru.opIndex(key);
103     }
104 
105     void opIndexAssign(ref V value, const(K) key) {
106         auto tmp_lru=(() @trusted => cast(LRU_t)_lru)();
107         tmp_lru.add(key, value);
108     }
109 
110     // Check if a key is in the cache, without updating the recent-ness or deleting it for being stale.
111     bool contains( K key ) nothrow {
112         auto tmp_lru=(() @trusted => cast(LRU_t)_lru)();
113         if(expired(key)){
114             tmp_lru.remove(key);
115             return false;
116         }            
117         return tmp_lru.contains(key);
118     }
119 
120     // Returns the key value (or undefined if not found) without updating
121     // the "recently used"-ness of the key.
122     static if (does_not_have_immutable_members) {
123         bool peek( K key, ref V value) nothrow {
124             auto tmp_lru=(() @trusted => cast(LRU_t)_lru)();
125             if(expired(key)){
126                 tmp_lru.remove(key);
127                 return false;
128             }
129             return tmp_lru.peek(key, value);
130         }
131     }
132 
133     V peek( K key ) {
134         auto tmp_lru=(() @trusted => cast(LRU_t)_lru)();
135         if(expired(key)){
136             tmp_lru.remove(key);
137             static if (hasMember!(V, "undefined")) {
138                 return V.undefined;
139             }else{
140                 return V.init;
141             }    
142         }
143         return tmp_lru.peek(key);
144     }
145 
146     // Remove removes the provided key from the cache, returning if the key was contained.
147     bool remove(scope const(K) key) {
148         auto tmp_lru=(() @trusted => cast(LRU_t)_lru)();
149         bool b = tmp_lru.remove(key);
150         if(b)
151             ctime.remove(key);
152         return b;
153     }
154 
155     @nogc
156     void setEvict(EvictCallback evict) nothrow {
157         auto tmp_lru=(() @trusted => cast(LRU_t)_lru)();
158         tmp_lru.setEvict(evict);
159     }
160 
161     // RemoveOldest removes the oldest item from the cache.
162     const(Result!(Entry*)) removeOldest() nothrow {
163         auto tmp_lru=(() @trusted => cast(LRU_t)_lru)();
164         auto e = tmp_lru.removeOldest();
165         if (!e.error)
166             ctime.remove(e.value.key);
167         return e;            
168     }
169 
170     // GetOldest returns the oldest entry
171     @nogc
172     const(Entry)* getOldest() const pure nothrow {
173         auto tmp_lru=(() @trusted => cast(LRU_t)_lru)();
174         return tmp_lru.getOldest();
175     }
176 
177 
178     /// keys returns a slice of the keys in the cache, from oldest to newest.
179     @nogc
180     auto keys() pure nothrow {
181         auto tmp_lru=(() @trusted => cast(LRU_t)_lru)();
182         return tmp_lru.keys();
183     }
184 
185     // length returns the number of items in the cache.
186     @nogc
187     uint length() pure const nothrow {
188         auto tmp_lru=(() @trusted => cast(LRU_t)_lru)();
189         return tmp_lru.length();
190     }
191 
192     @nogc EvictList.Range!false opSlice() nothrow {
193         auto tmp_lru=(() @trusted => cast(LRU_t)_lru)();
194         return tmp_lru.opSlice();
195     }
196 
197 } // class LRUT
198 
199 
200 unittest {
201 
202     import core.thread;
203 
204     alias LRUT!(int, int) TestLRU;
205     shared uint evictCounter;
206     
207     
208     void onEvicted(scope const(int) i, TestLRU.Element* e) @safe {
209         assert(e.entry.key == e.entry.value);
210         core.atomic.atomicOp!"+="(evictCounter, 1);
211         //evictCounter++;
212     }
213 
214     enum amount = 8;
215     double ttl = 0.5; // max age in seconds
216 
217     auto l = new shared(TestLRU)(&onEvicted, amount, ttl);
218 
219 
220     foreach (i; 0 .. amount) {
221         l.add(i, i);
222     }
223     
224     (() @trusted => Thread.sleep(500.msecs))();
225 
226     int x  = 999;
227     l.add(999,x);
228 
229     assert(l.expired(1));
230     assert(!l.expired(999));
231     
232     bool ok;
233     int v;
234 
235     ok = l.get(1,v);
236     assert(!ok);
237 
238     ok = l.get(999,v);
239     assert(ok);
240     assert(v == 999);
241 
242 }
243 
244