Make node timers more efficient

8 files changed, 125 insertions, 77 deletions

diff --git a/src/content_nodemeta.cpp b/src/content_nodemeta.cpp
index 7f4264d8e..79a32b6bf 100644
--- a/src/content_nodemeta.cpp
+++ b/src/content_nodemeta.cpp
@@ -186,7 +186,7 @@ void content_nodemeta_deserialize_legacy(std::istream &is,
 		meta->set(p, data);
 
 		if(need_timer)
-			timers->set(p, NodeTimer(1., 0.));
+			timers->set(NodeTimer(1., 0., p));
 	}
 }
 
diff --git a/src/environment.cpp b/src/environment.cpp
index 413bc7ff1..eea264699 100644
--- a/src/environment.cpp
+++ b/src/environment.cpp
@@ -1030,17 +1030,17 @@ void ServerEnvironment::activateBlock(MapBlock *block, u32 additional_dtime)
 	m_lbm_mgr.applyLBMs(this, block, stamp);
 
 	// Run node timers
-	std::map<v3s16, NodeTimer> elapsed_timers =
+	std::vector<NodeTimer> elapsed_timers =
 		block->m_node_timers.step((float)dtime_s);
-	if(!elapsed_timers.empty()){
+	if (!elapsed_timers.empty()) {
 		MapNode n;
-		for(std::map<v3s16, NodeTimer>::iterator
+		for (std::vector<NodeTimer>::iterator
 				i = elapsed_timers.begin();
 				i != elapsed_timers.end(); ++i){
-			n = block->getNodeNoEx(i->first);
-			v3s16 p = i->first + block->getPosRelative();
-			if(m_script->node_on_timer(p,n,i->second.elapsed))
-				block->setNodeTimer(i->first,NodeTimer(i->second.timeout,0));
+			n = block->getNodeNoEx(i->position);
+			v3s16 p = i->position + block->getPosRelative();
+			if (m_script->node_on_timer(p, n, i->elapsed))
+				block->setNodeTimer(NodeTimer(i->timeout, 0, i->position));
 		}
 	}
 
@@ -1434,17 +1434,19 @@ void ServerEnvironment::step(float dtime)
 					MOD_REASON_BLOCK_EXPIRED);
 
 			// Run node timers
-			std::map<v3s16, NodeTimer> elapsed_timers =
+			std::vector<NodeTimer> elapsed_timers =
 				block->m_node_timers.step((float)dtime);
-			if(!elapsed_timers.empty()){
+			if (!elapsed_timers.empty()) {
 				MapNode n;
-				for(std::map<v3s16, NodeTimer>::iterator
+				for (std::vector<NodeTimer>::iterator
 						i = elapsed_timers.begin();
-						i != elapsed_timers.end(); ++i){
-					n = block->getNodeNoEx(i->first);
-					p = i->first + block->getPosRelative();
-					if(m_script->node_on_timer(p,n,i->second.elapsed))
-						block->setNodeTimer(i->first,NodeTimer(i->second.timeout,0));
+						i != elapsed_timers.end(); ++i) {
+					n = block->getNodeNoEx(i->position);
+					p = i->position + block->getPosRelative();
+					if (m_script->node_on_timer(p, n, i->elapsed)) {
+						block->setNodeTimer(NodeTimer(
+							i->timeout, 0, i->position));
+					}
 				}
 			}
 		}
diff --git a/src/map.cpp b/src/map.cpp
index 03daf4fa8..a1f2086ce 100644
--- a/src/map.cpp
+++ b/src/map.cpp
@@ -2087,11 +2087,13 @@ NodeTimer Map::getNodeTimer(v3s16 p)
 		return NodeTimer();
 	}
 	NodeTimer t = block->m_node_timers.get(p_rel);
-	return t;
+	NodeTimer nt(t.timeout, t.elapsed, p);
+	return nt;
 }
 
-void Map::setNodeTimer(v3s16 p, NodeTimer t)
+void Map::setNodeTimer(const NodeTimer &t)
 {
+	v3s16 p = t.position;
 	v3s16 blockpos = getNodeBlockPos(p);
 	v3s16 p_rel = p - blockpos*MAP_BLOCKSIZE;
 	MapBlock *block = getBlockNoCreateNoEx(blockpos);
@@ -2105,7 +2107,8 @@ void Map::setNodeTimer(v3s16 p, NodeTimer t)
 				<<std::endl;
 		return;
 	}
-	block->m_node_timers.set(p_rel, t);
+	NodeTimer nt(t.timeout, t.elapsed, p_rel);
+	block->m_node_timers.set(nt);
 }
 
 void Map::removeNodeTimer(v3s16 p)
diff --git a/src/map.h b/src/map.h
index 78614d228..23da56471 100644
--- a/src/map.h
+++ b/src/map.h
@@ -327,7 +327,7 @@ public:
 	*/
 
 	NodeTimer getNodeTimer(v3s16 p);
-	void setNodeTimer(v3s16 p, NodeTimer t);
+	void setNodeTimer(const NodeTimer &t);
 	void removeNodeTimer(v3s16 p);
 
 	/*
diff --git a/src/mapblock.h b/src/mapblock.h
index 73c17ee60..5adfcf3fb 100644
--- a/src/mapblock.h
+++ b/src/mapblock.h
@@ -488,9 +488,9 @@ public:
 		m_node_timers.remove(p);
 	}
 
-	inline void setNodeTimer(v3s16 p, NodeTimer t)
+	inline void setNodeTimer(const NodeTimer &t)
 	{
-		m_node_timers.set(p,t);
+		m_node_timers.set(t);
 	}
 
 	inline void clearNodeTimers()
diff --git a/src/nodetimer.cpp b/src/nodetimer.cpp
index 350940546..003d08782 100644
--- a/src/nodetimer.cpp
+++ b/src/nodetimer.cpp
@@ -47,36 +47,38 @@ void NodeTimerList::serialize(std::ostream &os, u8 map_format_version) const
 {
 	if (map_format_version == 24) {
 		// Version 0 is a placeholder for "nothing to see here; go away."
-		if (m_data.empty()) {
+		if (m_timers.empty()) {
 			writeU8(os, 0); // version
 			return;
 		}
 		writeU8(os, 1); // version
-		writeU16(os, m_data.size());
+		writeU16(os, m_timers.size());
 	}
 
 	if (map_format_version >= 25) {
 		writeU8(os, 2 + 4 + 4); // length of the data for a single timer
-		writeU16(os, m_data.size());
+		writeU16(os, m_timers.size());
 	}
 
-	for (std::map<v3s16, NodeTimer>::const_iterator
-			i = m_data.begin();
-			i != m_data.end(); ++i) {
-		v3s16 p = i->first;
+	for (std::multimap<double, NodeTimer>::const_iterator
+			i = m_timers.begin();
+			i != m_timers.end(); ++i) {
 		NodeTimer t = i->second;
+		NodeTimer nt = NodeTimer(t.timeout,
+			t.timeout - (f32)(i->first - m_time), t.position);
+		v3s16 p = t.position;
 
 		u16 p16 = p.Z * MAP_BLOCKSIZE * MAP_BLOCKSIZE + p.Y * MAP_BLOCKSIZE + p.X;
 		writeU16(os, p16);
-		t.serialize(os);
+		nt.serialize(os);
 	}
 }
 
 void NodeTimerList::deSerialize(std::istream &is, u8 map_format_version)
 {
-	m_data.clear();
+	clear();
 
-	if(map_format_version == 24){
+	if (map_format_version == 24) {
 		u8 timer_version = readU8(is);
 		if(timer_version == 0)
 			return;
@@ -84,7 +86,7 @@ void NodeTimerList::deSerialize(std::istream &is, u8 map_format_version)
 			throw SerializationError("unsupported NodeTimerList version");
 	}
 
-	if(map_format_version >= 25){
+	if (map_format_version >= 25) {
 		u8 timer_data_len = readU8(is);
 		if(timer_data_len != 2+4+4)
 			throw SerializationError("unsupported NodeTimer data length");
@@ -92,8 +94,7 @@ void NodeTimerList::deSerialize(std::istream &is, u8 map_format_version)
 
 	u16 count = readU16(is);
 
-	for(u16 i=0; i<count; i++)
-	{
+	for (u16 i = 0; i < count; i++) {
 		u16 p16 = readU16(is);
 
 		v3s16 p;
@@ -103,11 +104,10 @@ void NodeTimerList::deSerialize(std::istream &is, u8 map_format_version)
 		p16 &= MAP_BLOCKSIZE - 1;
 		p.X = p16;
 
-		NodeTimer t;
+		NodeTimer t(p);
 		t.deSerialize(is);
 
-		if(t.timeout <= 0)
-		{
+		if (t.timeout <= 0) {
 			warningstream<<"NodeTimerList::deSerialize(): "
 					<<"invalid data at position"
 					<<"("<<p.X<<","<<p.Y<<","<<p.Z<<"): Ignoring."
@@ -115,8 +115,7 @@ void NodeTimerList::deSerialize(std::istream &is, u8 map_format_version)
 			continue;
 		}
 
-		if(m_data.find(p) != m_data.end())
-		{
+		if (m_iterators.find(p) != m_iterators.end()) {
 			warningstream<<"NodeTimerList::deSerialize(): "
 					<<"already set data at position"
 					<<"("<<p.X<<","<<p.Y<<","<<p.Z<<"): Ignoring."
@@ -124,31 +123,30 @@ void NodeTimerList::deSerialize(std::istream &is, u8 map_format_version)
 			continue;
 		}
 
-		m_data.insert(std::make_pair(p, t));
+		insert(t);
 	}
 }
 
-std::map<v3s16, NodeTimer> NodeTimerList::step(float dtime)
+std::vector<NodeTimer> NodeTimerList::step(float dtime)
 {
-	std::map<v3s16, NodeTimer> elapsed_timers;
-	// Increment timers
-	for(std::map<v3s16, NodeTimer>::iterator
-			i = m_data.begin();
-			i != m_data.end(); ++i){
-		v3s16 p = i->first;
+	std::vector<NodeTimer> elapsed_timers;
+	m_time += dtime;
+	if (m_next_trigger_time == -1. || m_time < m_next_trigger_time) {
+		return elapsed_timers;
+	}
+	std::multimap<double, NodeTimer>::iterator i = m_timers.begin();
+	// Process timers
+	for (; i != m_timers.end() && i->first <= m_time; ++i) {
 		NodeTimer t = i->second;
-		t.elapsed += dtime;
-		if(t.elapsed >= t.timeout)
-			elapsed_timers.insert(std::make_pair(p, t));
-		else
-			i->second = t;
+		t.elapsed = t.timeout + (f32)(m_time - i->first);
+		elapsed_timers.push_back(t);
+		m_iterators.erase(t.position);
 	}
 	// Delete elapsed timers
-	for(std::map<v3s16, NodeTimer>::const_iterator
-			i = elapsed_timers.begin();
-			i != elapsed_timers.end(); ++i){
-		v3s16 p = i->first;
-		m_data.erase(p);
-	}
+	m_timers.erase(m_timers.begin(), i);
+	if (m_timers.empty())
+		m_next_trigger_time = -1.;
+	else
+		m_next_trigger_time = m_timers.begin()->first;
 	return elapsed_timers;
 }
diff --git a/src/nodetimer.h b/src/nodetimer.h
index 9fb56edec..0fd43b2a8 100644
--- a/src/nodetimer.h
+++ b/src/nodetimer.h
@@ -23,6 +23,7 @@ with this program; if not, write to the Free Software Foundation, Inc.,
 #include "irr_v3d.h"
 #include <iostream>
 #include <map>
+#include <vector>
 
 /*
 	NodeTimer provides per-node timed callback functionality.
@@ -36,8 +37,10 @@ class NodeTimer
 {
 public:
 	NodeTimer(): timeout(0.), elapsed(0.) {}
-	NodeTimer(f32 timeout_, f32 elapsed_):
-		timeout(timeout_), elapsed(elapsed_) {}
+	NodeTimer(const v3s16 &position_):
+		timeout(0.), elapsed(0.), position(position_) {}
+	NodeTimer(f32 timeout_, f32 elapsed_, v3s16 position_):
+		timeout(timeout_), elapsed(elapsed_), position(position_) {}
 	~NodeTimer() {}
 	
 	void serialize(std::ostream &os) const;
@@ -45,6 +48,7 @@ public:
 	
 	f32 timeout;
 	f32 elapsed;
+	v3s16 position;
 };
 
 /*
@@ -54,37 +58,78 @@ public:
 class NodeTimerList
 {
 public:
-	NodeTimerList() {}
+	NodeTimerList(): m_next_trigger_time(-1.), m_time(0.) {}
 	~NodeTimerList() {}
 	
 	void serialize(std::ostream &os, u8 map_format_version) const;
 	void deSerialize(std::istream &is, u8 map_format_version);
 	
 	// Get timer
-	NodeTimer get(v3s16 p){
-		std::map<v3s16, NodeTimer>::iterator n = m_data.find(p);
-		if(n == m_data.end())
+	NodeTimer get(const v3s16 &p) {
+		std::map<v3s16, std::multimap<double, NodeTimer>::iterator>::iterator n =
+			m_iterators.find(p);
+		if (n == m_iterators.end())
 			return NodeTimer();
-		return n->second;
+		NodeTimer t = n->second->second;
+		t.elapsed = t.timeout - (n->second->first - m_time);
+		return t;
 	}
 	// Deletes timer
-	void remove(v3s16 p){
-		m_data.erase(p);
+	void remove(v3s16 p) {
+		std::map<v3s16, std::multimap<double, NodeTimer>::iterator>::iterator n =
+			m_iterators.find(p);
+		if(n != m_iterators.end()) {
+			double removed_time = n->second->first;
+			m_timers.erase(n->second);
+			m_iterators.erase(n);
+			// Yes, this is float equality, but it is not a problem
+			// since we only test equality of floats as an ordered type
+			// and thus we never lose precision
+			if (removed_time == m_next_trigger_time) {
+				if (m_timers.empty())
+					m_next_trigger_time = -1.;
+				else
+					m_next_trigger_time = m_timers.begin()->first;
+			}
+		}
+	}
+	// Undefined behaviour if there already is a timer
+	void insert(NodeTimer timer) {
+		v3s16 p = timer.position;
+		double trigger_time = m_time + (double)(timer.timeout - timer.elapsed);
+		std::multimap<double, NodeTimer>::iterator it =
+			m_timers.insert(std::pair<double, NodeTimer>(
+				trigger_time, timer
+			));
+		m_iterators.insert(
+			std::pair<v3s16, std::multimap<double, NodeTimer>::iterator>(p, it));
+		if (m_next_trigger_time == -1. || trigger_time < m_next_trigger_time)
+			m_next_trigger_time = trigger_time;
 	}
 	// Deletes old timer and sets a new one
-	void set(v3s16 p, NodeTimer t){
-		m_data[p] = t;
+	inline void set(const NodeTimer &timer) {
+		remove(timer.position);
+		insert(timer);
 	}
 	// Deletes all timers
-	void clear(){
-		m_data.clear();
+	void clear() {
+		m_timers.clear();
+		m_iterators.clear();
+		m_next_trigger_time = -1.;
+	}
+
+	inline double getNextTriggerTime() {
+		return m_next_trigger_time;
 	}
 
-	// A step in time. Returns map of elapsed timers.
-	std::map<v3s16, NodeTimer> step(float dtime);
+	// Move forward in time, returns elapsed timers
+	std::vector<NodeTimer> step(float dtime);
 
 private:
-	std::map<v3s16, NodeTimer> m_data;
+	std::multimap<double, NodeTimer> m_timers;
+	std::map<v3s16, std::multimap<double, NodeTimer>::iterator> m_iterators;
+	double m_next_trigger_time;
+	double m_time;
 };
 
 #endif
diff --git a/src/script/lua_api/l_nodetimer.cpp b/src/script/lua_api/l_nodetimer.cpp
index 601113516..3242d6ea5 100644
--- a/src/script/lua_api/l_nodetimer.cpp
+++ b/src/script/lua_api/l_nodetimer.cpp
@@ -45,7 +45,7 @@ int NodeTimerRef::l_set(lua_State *L)
 	if(env == NULL) return 0;
 	f32 t = luaL_checknumber(L,2);
 	f32 e = luaL_checknumber(L,3);
-	env->getMap().setNodeTimer(o->m_p,NodeTimer(t,e));
+	env->getMap().setNodeTimer(NodeTimer(t, e, o->m_p));
 	return 0;
 }
 
@@ -56,7 +56,7 @@ int NodeTimerRef::l_start(lua_State *L)
 	ServerEnvironment *env = o->m_env;
 	if(env == NULL) return 0;
 	f32 t = luaL_checknumber(L,2);
-	env->getMap().setNodeTimer(o->m_p,NodeTimer(t,0));
+	env->getMap().setNodeTimer(NodeTimer(t, 0, o->m_p));
 	return 0;
 }