util/cache.lua

   1
   2 local function _remove(list, m)
   3         if m.prev then
   4                 m.prev.next = m.next;
   5         end
   6         if m.next then
   7                 m.next.prev = m.prev;
   8         end
   9         if list._tail == m then
  10                 list._tail = m.prev;
  11         end
  12         if list._head == m then
  13                 list._head = m.next;
  14         end
  15         list._count = list._count - 1;
  16 end
  17
  18 local function _insert(list, m)
  19         if list._head then
  20                 list._head.prev = m;
  21         end
  22         m.prev, m.next = nil, list._head;
  23         list._head = m;
  24         if not list._tail then
  25                 list._tail = m;
  26         end
  27         list._count = list._count + 1;
  28 end
  29
  30 local cache_methods = {};
  31 local cache_mt = { __index = cache_methods };
  32
  33 function cache_methods:set(k, v)
  34         local m = self._data[k];
  35         if m then
  36                 -- Key already exists
  37                 if v ~= nil then
  38                         -- Bump to head of list
  39                         _remove(self, m);
  40                         _insert(self, m);
  41                         m.value = v;
  42                 else
  43                         -- Remove from list
  44                         _remove(self, m);
  45                         self._data[k] = nil;
  46                 end
  47                 return true;
  48         end
  49         -- New key
  50         if v == nil then
  51                 return true;
  52         end
  53         -- Check whether we need to remove oldest k/v
  54         if self._count == self.size then
  55                 local tail = self._tail;
  56                 local on_evict, evicted_key, evicted_value = self._on_evict, tail.key, tail.value;
  57                 if on_evict ~= nil and (on_evict == false or on_evict(evicted_key, evicted_value) == false) then
  58                         -- Cache is full, and we're not allowed to evict
  59                         return false;
  60                 end
  61                 _remove(self, tail);
  62                 self._data[evicted_key] = nil;
  63         end
  64
  65         m = { key = k, value = v, prev = nil, next = nil };
  66         self._data[k] = m;
  67         _insert(self, m);
  68         return true;
  69 end
  70
  71 function cache_methods:get(k)
  72         local m = self._data[k];
  73         if m then
  74                 return m.value;
  75         end
  76         return nil;
  77 end
  78
  79 function cache_methods:items()
  80         local m = self._head;
  81         return function ()
  82                 if not m then
  83                         return;
  84                 end
  85                 local k, v = m.key, m.value;
  86                 m = m.next;
  87                 return k, v;
  88         end
  89 end
  90
  91 function cache_methods:values()
  92         local m = self._head;
  93         return function ()
  94                 if not m then
  95                         return;
  96                 end
  97                 local v = m.value;
  98                 m = m.next;
  99                 return v;
 100         end
 101 end
 102
 103 function cache_methods:count()
 104         return self._count;
 105 end
 106
 107 function cache_methods:head()
 108         local head = self._head;
 109         if not head then return nil, nil; end
 110         return head.key, head.value;
 111 end
 112
 113 function cache_methods:tail()
 114         local tail = self._tail;
 115         if not tail then return nil, nil; end
 116         return tail.key, tail.value;
 117 end
 118
 119 function cache_methods:resize(new_size)
 120         new_size = assert(tonumber(new_size), "cache size must be a number");
 121         new_size = math.floor(new_size);
 122         assert(new_size > 0, "cache size must be greater than zero");
 123         local on_evict = self._on_evict;
 124         while self._count > new_size do
 125                 local tail = self._tail;
 126                 local evicted_key, evicted_value = tail.key, tail.value;
 127                 if on_evict ~= nil and (on_evict == false or on_evict(evicted_key, evicted_value) == false) then
 128                         -- Cache is full, and we're not allowed to evict
 129                         return false;
 130                 end
 131                 _remove(self, tail);
 132                 self._data[evicted_key] = nil;
 133         end
 134         self.size = new_size;
 135         return true;
 136 end
 137
 138 function cache_methods:table()
 139         --luacheck: ignore 212/t
 140         if not self.proxy_table then
 141                 self.proxy_table = setmetatable({}, {
 142                         __index = function (t, k)
 143                                 return self:get(k);
 144                         end;
 145                         __newindex = function (t, k, v)
 146                                 if not self:set(k, v) then
 147                                         error("failed to insert key into cache - full");
 148                                 end
 149                         end;
 150                         __pairs = function (t)
 151                                 return self:items();
 152                         end;
 153                         __len = function (t)
 154                                 return self:count();
 155                         end;
 156                 });
 157         end
 158         return self.proxy_table;
 159 end
 160
 161 function cache_methods:clear()
 162         self._data = {};
 163         self._count = 0;
 164         self._head = nil;
 165         self._tail = nil;
 166 end
 167
 168 local function new(size, on_evict)
 169         size = assert(tonumber(size), "cache size must be a number");
 170         size = math.floor(size);
 171         assert(size > 0, "cache size must be greater than zero");
 172         local data = {};
 173         return setmetatable({ _data = data, _count = 0, size = size, _head = nil, _tail = nil, _on_evict = on_evict }, cache_mt);
 174 end
 175
 176 return {
 177         new = new;
 178 }