From 68c17299907d850a2565ed7c162be142cc817473 Mon Sep 17 00:00:00 2001 From: DS Date: Mon, 6 Jan 2020 21:59:02 +0100 Subject: Refactor actionqueue.lua (#501) Reduce actionqueue complexity, thus faster execution Improve code style Add documentation/explanations --- mesecons/actionqueue.lua | 170 +++++++++++++++++++++++++++++------------------ 1 file changed, 107 insertions(+), 63 deletions(-) diff --git a/mesecons/actionqueue.lua b/mesecons/actionqueue.lua index f3479ce..5508095 100644 --- a/mesecons/actionqueue.lua +++ b/mesecons/actionqueue.lua @@ -1,96 +1,140 @@ -mesecon.queue.actions={} -- contains all ActionQueue actions +--[[ +Mesecons uses something it calls an ActionQueue. -function mesecon.queue:add_function(name, func) - mesecon.queue.funcs[name] = func +The ActionQueue holds functions and actions. +Functions are added on load time with a specified name. +Actions are preserved over server restarts. + +Each action consists of a position, the name of an added function to be called, +the params that should be used in this function call (additionally to the pos), +the time after which it should be executed, an optional overwritecheck and a +priority. + +If time = 0, the action will be executed in the next globalstep, otherwise the +earliest globalstep when it will be executed is the after next globalstep. + +It is guaranteed, that for two actions ac1, ac2 where ac1 ~= ac2, +ac1.time == ac2.time, ac1.priority == ac2.priority and ac1 was added earlier +than ac2, ac1 will be executed before ac2 (but in the same globalstep). + +Note: Do not pass references in params, as they can not be preserved. + +Also note: Some of the guarantees here might be dropped at some time. +]] + + +-- localize for speed +local queue = mesecon.queue + +queue.actions = {} -- contains all ActionQueue actions + +function queue:add_function(name, func) + queue.funcs[name] = func end -- If add_action with twice the same overwritecheck and same position are called, the first one is overwritten -- use overwritecheck nil to never overwrite, but just add the event to the queue -- priority specifies the order actions are executed within one globalstep, highest first -- should be between 0 and 1 -function mesecon.queue:add_action(pos, func, params, time, overwritecheck, priority) +function queue:add_action(pos, func, params, time, overwritecheck, priority) -- Create Action Table: time = time or 0 -- time <= 0 --> execute, time > 0 --> wait time until execution priority = priority or 1 - local action = { pos=mesecon.tablecopy(pos), - func=func, - params=mesecon.tablecopy(params or {}), - time=time, - owcheck=(overwritecheck and mesecon.tablecopy(overwritecheck)) or nil, - priority=priority} - - local toremove = nil - -- Otherwise, add the action to the queue - if overwritecheck then -- check if old action has to be overwritten / removed: - for i, ac in ipairs(mesecon.queue.actions) do - if(vector.equals(pos, ac.pos) - and mesecon.cmpAny(overwritecheck, ac.owcheck)) then - toremove = i + local action = { + pos = mesecon.tablecopy(pos), + func = func, + params = mesecon.tablecopy(params or {}), + time = time, + owcheck = (overwritecheck and mesecon.tablecopy(overwritecheck)) or nil, + priority = priority + } + + -- check if old action has to be overwritten / removed: + if overwritecheck then + for i, ac in ipairs(queue.actions) do + if vector.equals(pos, ac.pos) + and mesecon.cmpAny(overwritecheck, ac.owcheck) then + -- remove the old action + table.remove(queue.actions, i) break end end end - if (toremove ~= nil) then - table.remove(mesecon.queue.actions, toremove) - end - - table.insert(mesecon.queue.actions, action) + table.insert(queue.actions, action) end -- execute the stored functions on a globalstep -- if however, the pos of a function is not loaded (get_node_or_nil == nil), do NOT execute the function --- this makes sure that resuming mesecons circuits when restarting minetest works fine +-- this makes sure that resuming mesecons circuits when restarting minetest works fine (hm, where do we do this?) -- However, even that does not work in some cases, that's why we delay the time the globalsteps --- start to be execute by 5 seconds -local get_highest_priority = function (actions) - local highestp = -1 - local highesti - for i, ac in ipairs(actions) do - if ac.priority > highestp then - highestp = ac.priority - highesti = i - end - end +-- start to be execute by 4 seconds - return highesti -end +local function globalstep_func(dtime) + local actions = queue.actions + -- split into two categories: + -- actions_now: actions to execute now + -- queue.actions: actions to execute later + local actions_now = {} + queue.actions = {} -local m_time = 0 -local resumetime = mesecon.setting("resumetime", 4) -minetest.register_globalstep(function (dtime) - m_time = m_time + dtime - -- don't even try if server has not been running for XY seconds; resumetime = time to wait - -- after starting the server before processing the ActionQueue, don't set this too low - if (m_time < resumetime) then return end - local actions = mesecon.tablecopy(mesecon.queue.actions) - local actions_now={} - - mesecon.queue.actions = {} - - -- sort actions into two categories: - -- those toexecute now (actions_now) and those to execute later (mesecon.queue.actions) - for i, ac in ipairs(actions) do + for _, ac in ipairs(actions) do if ac.time > 0 then - ac.time = ac.time - dtime -- executed later - table.insert(mesecon.queue.actions, ac) + -- action ac is to be executed later + -- ~> insert into queue.actions + ac.time = ac.time - dtime + table.insert(queue.actions, ac) else + -- action ac is to be executed now + -- ~> insert into actions_now table.insert(actions_now, ac) end end - while(#actions_now > 0) do -- execute highest priorities first, until all are executed - local hp = get_highest_priority(actions_now) - mesecon.queue:execute(actions_now[hp]) - table.remove(actions_now, hp) + -- stable-sort the executed actions after their priority + -- some constructions might depend on the execution order, hence we first + -- execute the actions that had a lower index in actions_now + local old_action_order = {} + for i, ac in ipairs(actions_now) do + old_action_order[ac] = i end -end) + table.sort(actions_now, function(ac1, ac2) + if ac1.priority ~= ac2.priority then + return ac1.priority > ac2.priority + else + return old_action_order[ac1] < old_action_order[ac2] + end + end) + + -- execute highest priorities first, until all are executed + for _, ac in ipairs(actions_now) do + queue:execute(ac) + end +end + +-- delay the time the globalsteps start to be execute by 4 seconds +do + local m_time = 0 + local resumetime = mesecon.setting("resumetime", 4) + local globalstep_func_index = #minetest.registered_globalsteps + 1 + + minetest.register_globalstep(function(dtime) + m_time = m_time + dtime + -- don't even try if server has not been running for XY seconds; resumetime = time to wait + -- after starting the server before processing the ActionQueue, don't set this too low + if m_time < resumetime then + return + end + -- replace this globalstep function + minetest.registered_globalsteps[globalstep_func_index] = globalstep_func + end) +end -function mesecon.queue:execute(action) +function queue:execute(action) -- ignore if action queue function name doesn't exist, -- (e.g. in case the action queue savegame was written by an old mesecons version) - if mesecon.queue.funcs[action.func] then - mesecon.queue.funcs[action.func](action.pos, unpack(action.params)) + if queue.funcs[action.func] then + queue.funcs[action.func](action.pos, unpack(action.params)) end end @@ -98,8 +142,8 @@ end -- Store and read the ActionQueue to / from a file -- so that upcoming actions are remembered when the game -- is restarted -mesecon.queue.actions = mesecon.file2table("mesecon_actionqueue") +queue.actions = mesecon.file2table("mesecon_actionqueue") minetest.register_on_shutdown(function() - mesecon.table2file("mesecon_actionqueue", mesecon.queue.actions) + mesecon.table2file("mesecon_actionqueue", queue.actions) end) -- cgit v1.2.3