Improve performance of mesecon.turnon and mesecon.turnoff (#556)

2 files changed, 93 insertions, 17 deletions

diff --git a/mesecons/fifo_queue.lua b/mesecons/fifo_queue.lua
new file mode 100644
index 0000000..a71c71b
--- /dev/null
+++ b/mesecons/fifo_queue.lua
@@ -0,0 +1,62 @@
+
+-- a simple first-in-first-out queue
+-- very similar to the one in https://github.com/minetest/minetest/pull/7683
+
+local fifo_queue = {}
+
+local metatable = {__index = fifo_queue}
+
+-- creates a new empty queue
+function fifo_queue.new()
+	local q = {n_in = 0, n_out = 0, i_out = 1, buf_in = {}, buf_out = {}}
+	setmetatable(q, metatable)
+	return q
+end
+
+-- adds an element to the queue
+function fifo_queue.add(self, v)
+	local n = self.n_in + 1
+	self.n_in = n
+	self.buf_in[n] = v
+end
+
+-- removes and returns the next element, or nil of empty
+function fifo_queue.take(self)
+	local i_out = self.i_out
+	if i_out <= self.n_out then
+		local v = self.buf_out[i_out]
+		self.i_out = i_out + 1
+		self.buf_out[i_out] = true
+		return v
+	end
+
+	-- buf_out is empty, try to swap
+	self.i_out = 1
+	self.n_out = 0
+	if self.n_in == 0 then
+		return nil -- empty
+	end
+
+	-- swap
+	self.n_out = self.n_in
+	self.n_in = 0
+	self.buf_out, self.buf_in = self.buf_in, self.buf_out
+
+	local v = self.buf_out[1]
+	self.i_out = 2
+	self.buf_out[1] = true
+	return v
+end
+
+-- returns whether the queue is empty
+function fifo_queue.is_empty(self)
+	return self.n_out == self.i_out + 1 and self.n_in == 0
+end
+
+-- returns stuff for iteration in a for loop, like pairs
+-- adding new elements while iterating is no problem
+function fifo_queue.iter(self)
+	return fifo_queue.take, self, nil
+end
+
+return fifo_queue
diff --git a/mesecons/internal.lua b/mesecons/internal.lua
index 044e3bf..93eccf9 100644
--- a/mesecons/internal.lua
+++ b/mesecons/internal.lua
@@ -11,7 +11,7 @@
 
 -- RECEPTORS
 -- mesecon.is_receptor(nodename)	--> Returns true if nodename is a receptor
--- mesecon.is_receptor_on(nodename	--> Returns true if nodename is an receptor with state = mesecon.state.on
+-- mesecon.is_receptor_on(nodename)	--> Returns true if nodename is an receptor with state = mesecon.state.on
 -- mesecon.is_receptor_off(nodename)	--> Returns true if nodename is an receptor with state = mesecon.state.off
 -- mesecon.receptor_get_rules(node)	--> Returns the rules of the receptor (mesecon.rules.default if none specified)
 
@@ -46,6 +46,8 @@
 -- mesecon.rotate_rules_down(rules)
 -- These functions return rules that have been rotated in the specific direction
 
+local fifo_queue = dofile(minetest.get_modpath("mesecons").."/fifo_queue.lua")
+
 -- General
 function mesecon.get_effector(nodename)
 	if  minetest.registered_nodes[nodename]
@@ -371,32 +373,39 @@ end
 -- Follow all all conductor paths replacing conductors that were already
 -- looked at, activating / changing all effectors along the way.
 function mesecon.turnon(pos, link)
-	local frontiers = {{pos = pos, link = link}}
+	local frontiers = fifo_queue.new()
+	frontiers:add({pos = pos, link = link})
+	local pos_can_be_skipped = {}
 
 	local depth = 1
-	while frontiers[1] do
-		local f = table.remove(frontiers, 1)
+	for f in frontiers:iter() do
 		local node = mesecon.get_node_force(f.pos)
 
 		if not node then
 			-- Area does not exist; do nothing
+			pos_can_be_skipped[minetest.hash_node_position(f.pos)] = true
 		elseif mesecon.is_conductor_off(node, f.link) then
 			local rules = mesecon.conductor_get_rules(node)
 
 			-- Call turnon on neighbors
 			for _, r in ipairs(mesecon.rule2meta(f.link, rules)) do
 				local np = vector.add(f.pos, r)
-				for _, l in ipairs(mesecon.rules_link_rule_all(f.pos, r)) do
-					table.insert(frontiers, {pos = np, link = l})
+				if not pos_can_be_skipped[minetest.hash_node_position(np)] then
+					for _, l in ipairs(mesecon.rules_link_rule_all(f.pos, r)) do
+						frontiers:add({pos = np, link = l})
+					end
 				end
 			end
 
 			mesecon.swap_node_force(f.pos, mesecon.get_conductor_on(node, f.link))
+			pos_can_be_skipped[minetest.hash_node_position(f.pos)] = true
 		elseif mesecon.is_effector(node.name) then
 			mesecon.changesignal(f.pos, node, f.link, mesecon.state.on, depth)
 			if mesecon.is_effector_off(node.name) then
 				mesecon.activate(f.pos, node, f.link, depth)
 			end
+		else
+			pos_can_be_skipped[minetest.hash_node_position(f.pos)] = true
 		end
 		depth = depth + 1
 	end
@@ -419,37 +428,40 @@ end
 --	depth = indicates order in which signals wire fired, higher is later
 -- }
 function mesecon.turnoff(pos, link)
-	local frontiers = {{pos = pos, link = link}}
+	local frontiers = fifo_queue.new()
+	frontiers:add({pos = pos, link = link})
 	local signals = {}
+	local pos_can_be_skipped = {}
 
 	local depth = 1
-	while frontiers[1] do
-		local f = table.remove(frontiers, 1)
+	for f in frontiers:iter() do
 		local node = mesecon.get_node_force(f.pos)
 
 		if not node then
 			-- Area does not exist; do nothing
+			pos_can_be_skipped[minetest.hash_node_position(f.pos)] = true
 		elseif mesecon.is_conductor_on(node, f.link) then
 			local rules = mesecon.conductor_get_rules(node)
 			for _, r in ipairs(mesecon.rule2meta(f.link, rules)) do
 				local np = vector.add(f.pos, r)
 
-				-- Check if an onstate receptor is connected. If that is the case,
-				-- abort this turnoff process by returning false. `receptor_off` will
-				-- discard all the changes that we made in the voxelmanip:
-				for _, l in ipairs(mesecon.rules_link_rule_all_inverted(f.pos, r)) do
+				if not pos_can_be_skipped[minetest.hash_node_position(np)] then
+					-- Check if an onstate receptor is connected. If that is the case,
+					-- abort this turnoff process by returning false. `receptor_off` will
+					-- discard all the changes that we made in the voxelmanip:
 					if mesecon.is_receptor_on(mesecon.get_node_force(np).name) then
 						return false
 					end
-				end
 
-				-- Call turnoff on neighbors
-				for _, l in ipairs(mesecon.rules_link_rule_all(f.pos, r)) do
-					table.insert(frontiers, {pos = np, link = l})
+					-- Call turnoff on neighbors
+					for _, l in ipairs(mesecon.rules_link_rule_all(f.pos, r)) do
+						frontiers:add({pos = np, link = l})
+					end
 				end
 			end
 
 			mesecon.swap_node_force(f.pos, mesecon.get_conductor_off(node, f.link))
+			pos_can_be_skipped[minetest.hash_node_position(f.pos)] = true
 		elseif mesecon.is_effector(node.name) then
 			table.insert(signals, {
 				pos = f.pos,
@@ -457,6 +469,8 @@ function mesecon.turnoff(pos, link)
 				link = f.link,
 				depth = depth
 			})
+		else
+			pos_can_be_skipped[minetest.hash_node_position(f.pos)] = true
 		end
 		depth = depth + 1
 	end