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