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 = self._on_evict;
  57                 if on_evict then
  58                         on_evict(tail.key, tail.value);
  59                 end
  60                 _remove(self, tail);
  61                 self._data[tail.key] = nil;
  62         end
  63
  64         m = { key = k, value = v, prev = nil, next = nil };
  65         self._data[k] = m;
  66         _insert(self, m);
  67         return true;
  68 end
  69
  70 function cache_methods:get(k)
  71         local m = self._data[k];
  72         if m then
  73                 return m.value;
  74         end
  75         return nil;
  76 end
  77
  78 function cache_methods:items()
  79         local m = self._head;
  80         return function ()
  81                 if not m then
  82                         return;
  83                 end
  84                 local k, v = m.key, m.value;
  85                 m = m.next;
  86                 return k, v;
  87         end
  88 end
  89
  90 function cache_methods:count()
  91         return self._count;
  92 end
  93
  94 local function new(size, on_evict)
  95         size = assert(tonumber(size), "cache size must be a number");
  96         size = math.floor(size);
  97         assert(size > 0, "cache size must be greater than zero");
  98         local data = {};
  99         return setmetatable({ _data = data, _count = 0, size = size, _head = nil, _tail = nil, _on_evict = on_evict }, cache_mt);
 100 end
 101
 102 return {
 103         new = new;
 104 }