util/cache.lua

   1 local cache_methods = {};
   2 local cache_mt = { __index = cache_methods };
   3
   4 local function new(size)
   5         assert(size > 0, "cache size must be greater than zero");
   6         local data = {};
   7         return setmetatable({ data = data, count = 0, size = size, head = nil, tail = nil }, cache_mt);
   8 end
   9
  10 local function _remove(list, m)
  11         if m.prev then
  12                 m.prev.next = m.next;
  13         end
  14         if m.next then
  15                 m.next.prev = m.prev;
  16         end
  17         if list.tail == m then
  18                 list.tail = m.prev;
  19         end
  20         if list.head == m then
  21                 list.head = m.next;
  22         end
  23         list.count = list.count - 1;
  24 end
  25
  26 local function _insert(list, m)
  27         if list.head then
  28                 list.head.prev = m;
  29         end
  30         m.prev, m.next = nil, list.head;
  31         list.head = m;
  32         if not list.tail then
  33                 list.tail = m;
  34         end
  35         list.count = list.count + 1;
  36 end
  37
  38 function cache_methods:set(k, v)
  39         local m = self.data[k];
  40         if m then
  41                 -- Key already exists
  42                 if v ~= nil then
  43                         -- Bump to head of list
  44                         _remove(self, m);
  45                         _insert(self, m);
  46                         m.value = v;
  47                 else
  48                         -- Remove from list
  49                         _remove(self, m);
  50                         self.data[k] = nil;
  51                 end
  52                 return;
  53         end
  54         -- New key
  55         if v == nil then
  56                 return;
  57         end
  58         -- Check whether we need to remove oldest k/v
  59         if self.count == self.size then
  60                 self.data[self.tail.key] = nil;
  61                 _remove(self, self.tail);
  62         end
  63
  64         m = { key = k, value = v, prev = nil, next = nil };
  65         self.data[k] = m;
  66         _insert(self, m);
  67 end
  68
  69 function cache_methods:get(k)
  70         local m = self.data[k];
  71         if m then
  72                 return m.value;
  73         end
  74         return nil;
  75 end
  76
  77 function cache_methods:items()
  78         local m = self.head;
  79         return function ()
  80                 if not m then
  81                         return;
  82                 end
  83                 local k, v = m.key, m.value;
  84                 m = m.next;
  85                 return k, v;
  86         end
  87 end
  88
  89 return {
  90         new = new;
  91 }