Skip to content

Commit 559dd99

Browse files
Ekdohibsparamat
Ekdohibs
authored and
paramat
committedJun 11, 2016
Make node timers more efficient
·
5.11.00.4.15
1 parent 27aff22 commit 559dd99

File tree

8 files changed

+125
-77
lines changed

8 files changed

+125
-77
lines changed
 

‎src/content_nodemeta.cpp

+1-1
Original file line numberDiff line numberDiff line change
@@ -186,7 +186,7 @@ void content_nodemeta_deserialize_legacy(std::istream &is,
186186
meta->set(p, data);
187187

188188
if(need_timer)
189-
timers->set(p, NodeTimer(1., 0.));
189+
timers->set(NodeTimer(1., 0., p));
190190
}
191191
}
192192

‎src/environment.cpp

+17-15
Original file line numberDiff line numberDiff line change
@@ -1030,17 +1030,17 @@ void ServerEnvironment::activateBlock(MapBlock *block, u32 additional_dtime)
10301030
m_lbm_mgr.applyLBMs(this, block, stamp);
10311031

10321032
// Run node timers
1033-
std::map<v3s16, NodeTimer> elapsed_timers =
1033+
std::vector<NodeTimer> elapsed_timers =
10341034
block->m_node_timers.step((float)dtime_s);
1035-
if(!elapsed_timers.empty()){
1035+
if (!elapsed_timers.empty()) {
10361036
MapNode n;
1037-
for(std::map<v3s16, NodeTimer>::iterator
1037+
for (std::vector<NodeTimer>::iterator
10381038
i = elapsed_timers.begin();
10391039
i != elapsed_timers.end(); ++i){
1040-
n = block->getNodeNoEx(i->first);
1041-
v3s16 p = i->first + block->getPosRelative();
1042-
if(m_script->node_on_timer(p,n,i->second.elapsed))
1043-
block->setNodeTimer(i->first,NodeTimer(i->second.timeout,0));
1040+
n = block->getNodeNoEx(i->position);
1041+
v3s16 p = i->position + block->getPosRelative();
1042+
if (m_script->node_on_timer(p, n, i->elapsed))
1043+
block->setNodeTimer(NodeTimer(i->timeout, 0, i->position));
10441044
}
10451045
}
10461046

@@ -1434,17 +1434,19 @@ void ServerEnvironment::step(float dtime)
14341434
MOD_REASON_BLOCK_EXPIRED);
14351435

14361436
// Run node timers
1437-
std::map<v3s16, NodeTimer> elapsed_timers =
1437+
std::vector<NodeTimer> elapsed_timers =
14381438
block->m_node_timers.step((float)dtime);
1439-
if(!elapsed_timers.empty()){
1439+
if (!elapsed_timers.empty()) {
14401440
MapNode n;
1441-
for(std::map<v3s16, NodeTimer>::iterator
1441+
for (std::vector<NodeTimer>::iterator
14421442
i = elapsed_timers.begin();
1443-
i != elapsed_timers.end(); ++i){
1444-
n = block->getNodeNoEx(i->first);
1445-
p = i->first + block->getPosRelative();
1446-
if(m_script->node_on_timer(p,n,i->second.elapsed))
1447-
block->setNodeTimer(i->first,NodeTimer(i->second.timeout,0));
1443+
i != elapsed_timers.end(); ++i) {
1444+
n = block->getNodeNoEx(i->position);
1445+
p = i->position + block->getPosRelative();
1446+
if (m_script->node_on_timer(p, n, i->elapsed)) {
1447+
block->setNodeTimer(NodeTimer(
1448+
i->timeout, 0, i->position));
1449+
}
14481450
}
14491451
}
14501452
}

‎src/map.cpp

+6-3
Original file line numberDiff line numberDiff line change
@@ -2087,11 +2087,13 @@ NodeTimer Map::getNodeTimer(v3s16 p)
20872087
return NodeTimer();
20882088
}
20892089
NodeTimer t = block->m_node_timers.get(p_rel);
2090-
return t;
2090+
NodeTimer nt(t.timeout, t.elapsed, p);
2091+
return nt;
20912092
}
20922093

2093-
void Map::setNodeTimer(v3s16 p, NodeTimer t)
2094+
void Map::setNodeTimer(const NodeTimer &t)
20942095
{
2096+
v3s16 p = t.position;
20952097
v3s16 blockpos = getNodeBlockPos(p);
20962098
v3s16 p_rel = p - blockpos*MAP_BLOCKSIZE;
20972099
MapBlock *block = getBlockNoCreateNoEx(blockpos);
@@ -2105,7 +2107,8 @@ void Map::setNodeTimer(v3s16 p, NodeTimer t)
21052107
<<std::endl;
21062108
return;
21072109
}
2108-
block->m_node_timers.set(p_rel, t);
2110+
NodeTimer nt(t.timeout, t.elapsed, p_rel);
2111+
block->m_node_timers.set(nt);
21092112
}
21102113

21112114
void Map::removeNodeTimer(v3s16 p)

‎src/map.h

+1-1
Original file line numberDiff line numberDiff line change
@@ -327,7 +327,7 @@ class Map /*: public NodeContainer*/
327327
*/
328328

329329
NodeTimer getNodeTimer(v3s16 p);
330-
void setNodeTimer(v3s16 p, NodeTimer t);
330+
void setNodeTimer(const NodeTimer &t);
331331
void removeNodeTimer(v3s16 p);
332332

333333
/*

‎src/mapblock.h

+2-2
Original file line numberDiff line numberDiff line change
@@ -488,9 +488,9 @@ class MapBlock /*: public NodeContainer*/
488488
m_node_timers.remove(p);
489489
}
490490

491-
inline void setNodeTimer(v3s16 p, NodeTimer t)
491+
inline void setNodeTimer(const NodeTimer &t)
492492
{
493-
m_node_timers.set(p,t);
493+
m_node_timers.set(t);
494494
}
495495

496496
inline void clearNodeTimers()

‎src/nodetimer.cpp

+35-37
Original file line numberDiff line numberDiff line change
@@ -47,53 +47,54 @@ void NodeTimerList::serialize(std::ostream &os, u8 map_format_version) const
4747
{
4848
if (map_format_version == 24) {
4949
// Version 0 is a placeholder for "nothing to see here; go away."
50-
if (m_data.empty()) {
50+
if (m_timers.empty()) {
5151
writeU8(os, 0); // version
5252
return;
5353
}
5454
writeU8(os, 1); // version
55-
writeU16(os, m_data.size());
55+
writeU16(os, m_timers.size());
5656
}
5757

5858
if (map_format_version >= 25) {
5959
writeU8(os, 2 + 4 + 4); // length of the data for a single timer
60-
writeU16(os, m_data.size());
60+
writeU16(os, m_timers.size());
6161
}
6262

63-
for (std::map<v3s16, NodeTimer>::const_iterator
64-
i = m_data.begin();
65-
i != m_data.end(); ++i) {
66-
v3s16 p = i->first;
63+
for (std::multimap<double, NodeTimer>::const_iterator
64+
i = m_timers.begin();
65+
i != m_timers.end(); ++i) {
6766
NodeTimer t = i->second;
67+
NodeTimer nt = NodeTimer(t.timeout,
68+
t.timeout - (f32)(i->first - m_time), t.position);
69+
v3s16 p = t.position;
6870

6971
u16 p16 = p.Z * MAP_BLOCKSIZE * MAP_BLOCKSIZE + p.Y * MAP_BLOCKSIZE + p.X;
7072
writeU16(os, p16);
71-
t.serialize(os);
73+
nt.serialize(os);
7274
}
7375
}
7476

7577
void NodeTimerList::deSerialize(std::istream &is, u8 map_format_version)
7678
{
77-
m_data.clear();
79+
clear();
7880

79-
if(map_format_version == 24){
81+
if (map_format_version == 24) {
8082
u8 timer_version = readU8(is);
8183
if(timer_version == 0)
8284
return;
8385
if(timer_version != 1)
8486
throw SerializationError("unsupported NodeTimerList version");
8587
}
8688

87-
if(map_format_version >= 25){
89+
if (map_format_version >= 25) {
8890
u8 timer_data_len = readU8(is);
8991
if(timer_data_len != 2+4+4)
9092
throw SerializationError("unsupported NodeTimer data length");
9193
}
9294

9395
u16 count = readU16(is);
9496

95-
for(u16 i=0; i<count; i++)
96-
{
97+
for (u16 i = 0; i < count; i++) {
9798
u16 p16 = readU16(is);
9899

99100
v3s16 p;
@@ -103,52 +104,49 @@ void NodeTimerList::deSerialize(std::istream &is, u8 map_format_version)
103104
p16 &= MAP_BLOCKSIZE - 1;
104105
p.X = p16;
105106

106-
NodeTimer t;
107+
NodeTimer t(p);
107108
t.deSerialize(is);
108109

109-
if(t.timeout <= 0)
110-
{
110+
if (t.timeout <= 0) {
111111
warningstream<<"NodeTimerList::deSerialize(): "
112112
<<"invalid data at position"
113113
<<"("<<p.X<<","<<p.Y<<","<<p.Z<<"): Ignoring."
114114
<<std::endl;
115115
continue;
116116
}
117117

118-
if(m_data.find(p) != m_data.end())
119-
{
118+
if (m_iterators.find(p) != m_iterators.end()) {
120119
warningstream<<"NodeTimerList::deSerialize(): "
121120
<<"already set data at position"
122121
<<"("<<p.X<<","<<p.Y<<","<<p.Z<<"): Ignoring."
123122
<<std::endl;
124123
continue;
125124
}
126125

127-
m_data.insert(std::make_pair(p, t));
126+
insert(t);
128127
}
129128
}
130129

131-
std::map<v3s16, NodeTimer> NodeTimerList::step(float dtime)
130+
std::vector<NodeTimer> NodeTimerList::step(float dtime)
132131
{
133-
std::map<v3s16, NodeTimer> elapsed_timers;
134-
// Increment timers
135-
for(std::map<v3s16, NodeTimer>::iterator
136-
i = m_data.begin();
137-
i != m_data.end(); ++i){
138-
v3s16 p = i->first;
132+
std::vector<NodeTimer> elapsed_timers;
133+
m_time += dtime;
134+
if (m_next_trigger_time == -1. || m_time < m_next_trigger_time) {
135+
return elapsed_timers;
136+
}
137+
std::multimap<double, NodeTimer>::iterator i = m_timers.begin();
138+
// Process timers
139+
for (; i != m_timers.end() && i->first <= m_time; ++i) {
139140
NodeTimer t = i->second;
140-
t.elapsed += dtime;
141-
if(t.elapsed >= t.timeout)
142-
elapsed_timers.insert(std::make_pair(p, t));
143-
else
144-
i->second = t;
141+
t.elapsed = t.timeout + (f32)(m_time - i->first);
142+
elapsed_timers.push_back(t);
143+
m_iterators.erase(t.position);
145144
}
146145
// Delete elapsed timers
147-
for(std::map<v3s16, NodeTimer>::const_iterator
148-
i = elapsed_timers.begin();
149-
i != elapsed_timers.end(); ++i){
150-
v3s16 p = i->first;
151-
m_data.erase(p);
152-
}
146+
m_timers.erase(m_timers.begin(), i);
147+
if (m_timers.empty())
148+
m_next_trigger_time = -1.;
149+
else
150+
m_next_trigger_time = m_timers.begin()->first;
153151
return elapsed_timers;
154152
}

‎src/nodetimer.h

+61-16
Original file line numberDiff line numberDiff line change
@@ -23,6 +23,7 @@ with this program; if not, write to the Free Software Foundation, Inc.,
2323
#include "irr_v3d.h"
2424
#include <iostream>
2525
#include <map>
26+
#include <vector>
2627

2728
/*
2829
NodeTimer provides per-node timed callback functionality.
@@ -36,15 +37,18 @@ class NodeTimer
3637
{
3738
public:
3839
NodeTimer(): timeout(0.), elapsed(0.) {}
39-
NodeTimer(f32 timeout_, f32 elapsed_):
40-
timeout(timeout_), elapsed(elapsed_) {}
40+
NodeTimer(const v3s16 &position_):
41+
timeout(0.), elapsed(0.), position(position_) {}
42+
NodeTimer(f32 timeout_, f32 elapsed_, v3s16 position_):
43+
timeout(timeout_), elapsed(elapsed_), position(position_) {}
4144
~NodeTimer() {}
4245

4346
void serialize(std::ostream &os) const;
4447
void deSerialize(std::istream &is);
4548

4649
f32 timeout;
4750
f32 elapsed;
51+
v3s16 position;
4852
};
4953

5054
/*
@@ -54,37 +58,78 @@ class NodeTimer
5458
class NodeTimerList
5559
{
5660
public:
57-
NodeTimerList() {}
61+
NodeTimerList(): m_next_trigger_time(-1.), m_time(0.) {}
5862
~NodeTimerList() {}
5963

6064
void serialize(std::ostream &os, u8 map_format_version) const;
6165
void deSerialize(std::istream &is, u8 map_format_version);
6266

6367
// Get timer
64-
NodeTimer get(v3s16 p){
65-
std::map<v3s16, NodeTimer>::iterator n = m_data.find(p);
66-
if(n == m_data.end())
68+
NodeTimer get(const v3s16 &p) {
69+
std::map<v3s16, std::multimap<double, NodeTimer>::iterator>::iterator n =
70+
m_iterators.find(p);
71+
if (n == m_iterators.end())
6772
return NodeTimer();
68-
return n->second;
73+
NodeTimer t = n->second->second;
74+
t.elapsed = t.timeout - (n->second->first - m_time);
75+
return t;
6976
}
7077
// Deletes timer
71-
void remove(v3s16 p){
72-
m_data.erase(p);
78+
void remove(v3s16 p) {
79+
std::map<v3s16, std::multimap<double, NodeTimer>::iterator>::iterator n =
80+
m_iterators.find(p);
81+
if(n != m_iterators.end()) {
82+
double removed_time = n->second->first;
83+
m_timers.erase(n->second);
84+
m_iterators.erase(n);
85+
// Yes, this is float equality, but it is not a problem
86+
// since we only test equality of floats as an ordered type
87+
// and thus we never lose precision
88+
if (removed_time == m_next_trigger_time) {
89+
if (m_timers.empty())
90+
m_next_trigger_time = -1.;
91+
else
92+
m_next_trigger_time = m_timers.begin()->first;
93+
}
94+
}
95+
}
96+
// Undefined behaviour if there already is a timer
97+
void insert(NodeTimer timer) {
98+
v3s16 p = timer.position;
99+
double trigger_time = m_time + (double)(timer.timeout - timer.elapsed);
100+
std::multimap<double, NodeTimer>::iterator it =
101+
m_timers.insert(std::pair<double, NodeTimer>(
102+
trigger_time, timer
103+
));
104+
m_iterators.insert(
105+
std::pair<v3s16, std::multimap<double, NodeTimer>::iterator>(p, it));
106+
if (m_next_trigger_time == -1. || trigger_time < m_next_trigger_time)
107+
m_next_trigger_time = trigger_time;
73108
}
74109
// Deletes old timer and sets a new one
75-
void set(v3s16 p, NodeTimer t){
76-
m_data[p] = t;
110+
inline void set(const NodeTimer &timer) {
111+
remove(timer.position);
112+
insert(timer);
77113
}
78114
// Deletes all timers
79-
void clear(){
80-
m_data.clear();
115+
void clear() {
116+
m_timers.clear();
117+
m_iterators.clear();
118+
m_next_trigger_time = -1.;
119+
}
120+
121+
inline double getNextTriggerTime() {
122+
return m_next_trigger_time;
81123
}
82124

83-
// A step in time. Returns map of elapsed timers.
84-
std::map<v3s16, NodeTimer> step(float dtime);
125+
// Move forward in time, returns elapsed timers
126+
std::vector<NodeTimer> step(float dtime);
85127

86128
private:
87-
std::map<v3s16, NodeTimer> m_data;
129+
std::multimap<double, NodeTimer> m_timers;
130+
std::map<v3s16, std::multimap<double, NodeTimer>::iterator> m_iterators;
131+
double m_next_trigger_time;
132+
double m_time;
88133
};
89134

90135
#endif

‎src/script/lua_api/l_nodetimer.cpp

+2-2
Original file line numberDiff line numberDiff line change
@@ -45,7 +45,7 @@ int NodeTimerRef::l_set(lua_State *L)
4545
if(env == NULL) return 0;
4646
f32 t = luaL_checknumber(L,2);
4747
f32 e = luaL_checknumber(L,3);
48-
env->getMap().setNodeTimer(o->m_p,NodeTimer(t,e));
48+
env->getMap().setNodeTimer(NodeTimer(t, e, o->m_p));
4949
return 0;
5050
}
5151

@@ -56,7 +56,7 @@ int NodeTimerRef::l_start(lua_State *L)
5656
ServerEnvironment *env = o->m_env;
5757
if(env == NULL) return 0;
5858
f32 t = luaL_checknumber(L,2);
59-
env->getMap().setNodeTimer(o->m_p,NodeTimer(t,0));
59+
env->getMap().setNodeTimer(NodeTimer(t, 0, o->m_p));
6060
return 0;
6161
}
6262

0 commit comments

Comments
 (0)
Please sign in to comment.