Refactor actionqueue.lua (#501)

Reduce actionqueue complexity, thus faster execution
Improve code style
Add documentation/explanations

1 files 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)