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:table()
 120         if not self.proxy_table then
 121                 self.proxy_table = setmetatable({}, {
 122                         __index = function (t, k)
 123                                 return self:get(k);
 124                         end;
 125                         __newindex = function (t, k, v)
 126                                 if not self:set(k, v) then
 127                                         error("failed to insert key into cache - full");
 128                                 end
 129                         end;
 130                         __pairs = function (t)
 131                                 return self:items();
 132                         end;
 133                         __len = function (t)
 134                                 return self:count();
 135                         end;
 136                 });
 137         end
 138         return self.proxy_table;
 139 end
 140
 141 local function new(size, on_evict)
 142         size = assert(tonumber(size), "cache size must be a number");
 143         size = math.floor(size);
 144         assert(size > 0, "cache size must be greater than zero");
 145         local data = {};
 146         return setmetatable({ _data = data, _count = 0, size = size, _head = nil, _tail = nil, _on_evict = on_evict }, cache_mt);
 147 end
 148
 149 return {
 150         new = new;
 151 }