-- Structure --
-- Elements are stored in a linked list with max size.
-- If max size is reached, the last element will be removed.
-- Access (get/set) will move the element to the first position.
-- TTL will only expire an element, but will not remove it.
local initCache = function(in_max_size)
-- returns table { get, set, free, clean }
-- set(key[, value[, ttl]]) set/update a key to value -> returns value[, removed key, removed value]
-- - optional time to live
-- - no value will unset
-- get(key) -> returns value[, ttl] (nil -> if not exist or nil, value -> if expired)
-- free() -> number of slots available
-- clean() -> will run through the list and remove expired elements (expensive) -> returns available slots, available before
local n_size = tonumber(in_max_size)
local t_cache
local free = function()
return n_size
end
if not(n_size) or n_size <= 0 then
n_size = 0
local set = function(ix_key, ix_value, i_selfcall)
if ix_key == t_cache then
return i_selfcall, ix_value, i_selfcall
end
return ix_value, ix_key, ix_value
end
t_cache = {get = function() end, set = set, free = free, clean = function() return 0, 0 end}
return t_cache
end
local KEY, VAL, TTL, PRV, NXT = 1, 2, 3, 4, 5
local t_data = {}
local t_first = nil
local t_last = nil
local getTx = function()
-- returns number timestamp
local n_year, n_day, n_hour, n_minute, n_second = string.match(os.date("!%Y%j%H%M%S"),
"(%d%d%d%d)(%d%d%d)(%d%d)(%d%d)(%d%d)")
-- ttl < 1 year; the year is just prefix, cache will reset on Jan 01 00:00:00
return (n_year * 100000000) + ((((((n_day * 24) + n_hour) * 60) + n_minute) * 60) + n_second)
end
local popElement = function(it_value)
-- returns nil
local t_prev = it_value[PRV]
if t_prev then
t_prev[NXT] = it_value[NXT]
else
t_first = it_value[NXT]
end
if it_value[NXT] then
it_value[NXT][PRV] = it_value[PRV]
else
t_last = it_value[PRV]
end
it_value[PRV] = nil
it_value[NXT] = nil
end
local pushFirst = function(it_value)
-- returns nil
if t_first then
it_value[NXT] = t_first
t_first[PRV] = it_value
end
t_first = it_value
if not(t_last) then
t_last = it_value
end
end
local set = function(ix_key, ix_value, in_ttl, i_selfcall)
-- returns value
if ix_key == t_cache then
return t_cache.set(ix_value, in_ttl, i_selfcall)
end
if t_data[ix_key] then
popElement(t_data[ix_key])
n_size = n_size + 1
t_data[ix_key] = nil
end
if ix_value == nil then
return
end
-- initialize with 5 elements
t_data[ix_key] = {ix_key, ix_value, in_ttl and getTx() + in_ttl, false, false}
pushFirst(t_data[ix_key])
if n_size == 0 then
local t_value = t_last
t_data[t_last[KEY]] = nil
t_last = t_last[PRV]
t_last[NXT][PRV] = nil
t_last[NXT] = nil
return ix_value, t_value[KEY], t_value[VAL]
end
n_size = n_size - 1
return ix_value
end
local get = function(ix_key, i_selfcall)
-- returns value, ttl or nil, expired value
if ix_key == t_cache then
return t_cache.get(i_selfcall)
end
local t_value = t_data[ix_key]
if t_value then
local n_ttl
if t_value[TTL] then
n_ttl = t_value[TTL] - getTx()
if n_ttl <= 0 then
set(ix_key)
return nil, t_value[VAL]
end
end
popElement(t_value)
pushFirst(t_value)
return t_value[VAL], n_ttl
end
end
local clean = function()
local n_size_before = n_size
local t_element = t_first
while t_element do
local ix_key = t_element[TTL] and (t_element[TTL] - getTx()) <= 0 and t_element[KEY] or nil
t_element = t_element[NXT]
if ix_key then
set(ix_key)
end
end
return n_size, n_size_before
end
t_cache = {get = get, set = set, free = free, clean = clean}
return t_cache
end
--{TEST
local c = initCache()
assert(c.free() == 0)
assert(c.set(1, 1) == 1)
assert(c:set(1, 1) == 1)
local c = initCache(-1)
assert(c.free() == 0)
local c = initCache(0)
local n_value, n_lkey, n_lvalue = c.set(1,1)
assert(n_value == 1)
assert(n_lkey == 1)
assert(n_lvalue == 1)
assert(c.get(1) == nil)
local c = initCache(1)
local n_value, n_lkey, n_lvalue = c.set(1,1)
assert(n_value == 1)
assert(n_lkey == nil)
assert(n_lvalue == nil)
assert(c.get(1) == 1)
c.set(2,2)
assert(c.get(1) == nil)
assert(c.get(2) == 2)
local c = initCache(3)
c.set(1,1)
assert(c.get(1) == 1)
c.set(2,2)
assert(c.get(2) == 2)
c.set(3,3)
assert(c.get(3) == 3)
-- self access
local c = initCache(3)
c:set(1,1)
assert(c:get(1) == 1)
c:set(2,2)
assert(c:get(2) == 2)
c:set(3,3)
assert(c:get(3) == 3)
-- access -> first position
assert(c.get(1) == 1)
-- last (2) will be dropped
local n_value, n_lkey, n_lvalue = c.set(4,4)
assert(n_value == 4)
assert(n_lkey == 2)
assert(n_lvalue == 2)
assert(c.get(4) == 4)
assert(c.get(1) == 1)
assert(c.get(2) == nil)
-- check ttl
c.set(1,1,2)
c.set(2,2)
c.set(3,3,1)
local _, t = c.get(1)
assert(t == 2 or t == 1)
local _, t = c.get(2)
assert(t == nil)
assert(c.get(1) == 1)
if not(_BUILD_VERBOSE == false) then
print("sleep 2 to test ttl")
os.execute("sleep 2")
local v, ev = c.get(1)
assert(v == nil)
assert(ev == 1)
assert(c.free() == 1)
assert(c.clean() == 2) -- (2, 1)
else
assert(c.free() == 0)
assert(c.clean() == 0) -- (0, 0)
end