-- Copyright (C) Yichun Zhang (agentzh) local ffi = require "ffi" local ffi_new = ffi.new local ffi_sizeof = ffi.sizeof local ffi_cast = ffi.cast local ffi_fill = ffi.fill local ngx_now = ngx.now local uintptr_t = ffi.typeof("uintptr_t") local setmetatable = setmetatable local tonumber = tonumber local type = type local new_tab do local ok ok, new_tab = pcall(require, "table.new") if not ok then new_tab = function(narr, nrec) return {} end end end if string.find(jit.version, " 2.0", 1, true) then ngx.log(ngx.ALERT, "use of lua-resty-lrucache with LuaJIT 2.0 is ", "not recommended; use LuaJIT 2.1+ instead") end local ok, tb_clear = pcall(require, "table.clear") if not ok then local pairs = pairs tb_clear = function (tab) for k, _ in pairs(tab) do tab[k] = nil end end end -- queue data types -- -- this queue is a double-ended queue and the first node -- is reserved for the queue itself. -- the implementation is mostly borrowed from nginx's ngx_queue_t data -- structure. ffi.cdef[[ typedef struct lrucache_queue_s lrucache_queue_t; struct lrucache_queue_s { double expire; /* in seconds */ lrucache_queue_t *prev; lrucache_queue_t *next; uint32_t user_flags; }; ]] local queue_arr_type = ffi.typeof("lrucache_queue_t[?]") local queue_type = ffi.typeof("lrucache_queue_t") local NULL = ffi.null -- queue utility functions local function queue_insert_tail(h, x) local last = h[0].prev x.prev = last last.next = x x.next = h h[0].prev = x end local function queue_init(size) if not size then size = 0 end local q = ffi_new(queue_arr_type, size + 1) ffi_fill(q, ffi_sizeof(queue_type, size + 1), 0) if size == 0 then q[0].prev = q q[0].next = q else local prev = q[0] for i = 1, size do local e = q + i e.user_flags = 0 prev.next = e e.prev = prev prev = e end local last = q[size] last.next = q q[0].prev = last end return q end local function queue_is_empty(q) -- print("q: ", tostring(q), "q.prev: ", tostring(q), ": ", q == q.prev) return q == q[0].prev end local function queue_remove(x) local prev = x.prev local next = x.next next.prev = prev prev.next = next -- for debugging purpose only: x.prev = NULL x.next = NULL end local function queue_insert_head(h, x) x.next = h[0].next x.next.prev = x x.prev = h h[0].next = x end local function queue_last(h) return h[0].prev end local function queue_head(h) return h[0].next end -- true module stuffs local _M = { _VERSION = '0.14' } local mt = { __index = _M } local function ptr2num(ptr) local v = tonumber(ffi_cast(uintptr_t, ptr)) return v end function _M.new(size) if size < 1 then return nil, "size too small" end local self = { hasht = {}, free_queue = queue_init(size), cache_queue = queue_init(), key2node = {}, node2key = {}, num_items = 0, max_items = size, } setmetatable(self, mt) return self end function _M.count(self) return self.num_items end function _M.capacity(self) return self.max_items end function _M.get(self, key) local hasht = self.hasht local val = hasht[key] if val == nil then return nil end local node = self.key2node[key] -- print(key, ": moving node ", tostring(node), " to cache queue head") local cache_queue = self.cache_queue queue_remove(node) queue_insert_head(cache_queue, node) if node.expire >= 0 and node.expire < ngx_now() then -- print("expired: ", node.expire, " > ", ngx_now()) return nil, val, node.user_flags end return val, nil, node.user_flags end function _M.delete(self, key) self.hasht[key] = nil local key2node = self.key2node local node = key2node[key] if not node then return false end key2node[key] = nil self.node2key[ptr2num(node)] = nil queue_remove(node) queue_insert_tail(self.free_queue, node) self.num_items = self.num_items - 1 return true end function _M.set(self, key, value, ttl, flags) local hasht = self.hasht hasht[key] = value local key2node = self.key2node local node = key2node[key] if not node then local free_queue = self.free_queue local node2key = self.node2key if queue_is_empty(free_queue) then -- evict the least recently used key -- assert(not queue_is_empty(self.cache_queue)) node = queue_last(self.cache_queue) local oldkey = node2key[ptr2num(node)] -- print(key, ": evicting oldkey: ", oldkey, ", oldnode: ", -- tostring(node)) if oldkey then hasht[oldkey] = nil key2node[oldkey] = nil end else -- take a free queue node node = queue_head(free_queue) -- only add count if we are not evicting self.num_items = self.num_items + 1 -- print(key, ": get a new free node: ", tostring(node)) end node2key[ptr2num(node)] = key key2node[key] = node end queue_remove(node) queue_insert_head(self.cache_queue, node) if ttl then node.expire = ngx_now() + ttl else node.expire = -1 end if type(flags) == "number" and flags >= 0 then node.user_flags = flags else node.user_flags = 0 end end function _M.get_keys(self, max_count, res) if not max_count or max_count == 0 then max_count = self.num_items end if not res then res = new_tab(max_count + 1, 0) -- + 1 for trailing hole end local cache_queue = self.cache_queue local node2key = self.node2key local i = 0 local node = queue_head(cache_queue) while node ~= cache_queue do if i >= max_count then break end i = i + 1 res[i] = node2key[ptr2num(node)] node = node.next end res[i + 1] = nil return res end function _M.flush_all(self) tb_clear(self.hasht) tb_clear(self.node2key) tb_clear(self.key2node) self.num_items = 0 local cache_queue = self.cache_queue local free_queue = self.free_queue -- splice the cache_queue into free_queue if not queue_is_empty(cache_queue) then local free_head = free_queue[0] local free_last = free_head.prev local cache_head = cache_queue[0] local cache_first = cache_head.next local cache_last = cache_head.prev free_last.next = cache_first cache_first.prev = free_last cache_last.next = free_head free_head.prev = cache_last cache_head.next = cache_queue cache_head.prev = cache_queue end end return _M