aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorMatthew Wild <mwild1@gmail.com>2015-11-24 10:44:41 +0000
committerMatthew Wild <mwild1@gmail.com>2015-11-24 10:44:41 +0000
commit89bc6c6ad740c0c309fd9679eca8c4c8006177d8 (patch)
tree7107cb1aebaee8f0c83b0218075e8b97b624d7fd
parentc3b43754d587da5a1f8c474990ebcb3642deadab (diff)
downloadprosody-89bc6c6ad740c0c309fd9679eca8c4c8006177d8.tar.gz
prosody-89bc6c6ad740c0c309fd9679eca8c4c8006177d8.zip
util.cache: Ordered key->value data structure, with size limit (same as pubsub)
-rw-r--r--util/cache.lua91
1 files changed, 91 insertions, 0 deletions
diff --git a/util/cache.lua b/util/cache.lua
new file mode 100644
index 00000000..9453697c
--- /dev/null
+++ b/util/cache.lua
@@ -0,0 +1,91 @@
+local cache_methods = {};
+local cache_mt = { __index = cache_methods };
+
+local function new(size)
+ assert(size > 0, "cache size must be greater than zero");
+ local data = {};
+ return setmetatable({ data = data, count = 0, size = size, head = nil, tail = nil }, cache_mt);
+end
+
+local function _remove(list, m)
+ if m.prev then
+ m.prev.next = m.next;
+ end
+ if m.next then
+ m.next.prev = m.prev;
+ end
+ if list.tail == m then
+ list.tail = m.prev;
+ end
+ if list.head == m then
+ list.head = m.next;
+ end
+ list.count = list.count - 1;
+end
+
+local function _insert(list, m)
+ if list.head then
+ list.head.prev = m;
+ end
+ m.prev, m.next = nil, list.head;
+ list.head = m;
+ if not list.tail then
+ list.tail = m;
+ end
+ list.count = list.count + 1;
+end
+
+function cache_methods:set(k, v)
+ local m = self.data[k];
+ if m then
+ -- Key already exists
+ if v ~= nil then
+ -- Bump to head of list
+ _remove(self, m);
+ _insert(self, m);
+ m.value = v;
+ else
+ -- Remove from list
+ _remove(self, m);
+ self.data[k] = nil;
+ end
+ return;
+ end
+ -- New key
+ if v == nil then
+ return;
+ end
+ -- Check whether we need to remove oldest k/v
+ if self.count == self.size then
+ self.data[self.tail.key] = nil;
+ _remove(self, self.tail);
+ end
+
+ m = { key = k, value = v, prev = nil, next = nil };
+ self.data[k] = m;
+ _insert(self, m);
+end
+
+function cache_methods:get(k)
+ local m = self.data[k];
+ if m then
+ return m.value;
+ end
+ return nil;
+end
+
+function cache_methods:items()
+ local m = self.head;
+ return function ()
+ if not m then
+ return;
+ end
+ local k, v = m.key, m.value;
+ m = m.next;
+ return k, v;
+ end
+end
+
+return {
+ new = new;
+}