The Battle for Wesnoth  1.15.9+dev
map.cpp
Go to the documentation of this file.
1 /*
2  Copyright (C) 2006 - 2009 by Rusty Russell <rusty@rustcorp.com.au>
3  Copyright (C) 2010 - 2018 by Guillaume Melquiond <guillaume.melquiond@gmail.com>
4  Part of the Battle for Wesnoth Project https://www.wesnoth.org/
5 
6  This program is free software; you can redistribute it and/or modify
7  it under the terms of the GNU General Public License as published by
8  the Free Software Foundation; either version 2 of the License, or
9  (at your option) any later version.
10  This program is distributed in the hope that it will be useful,
11  but WITHOUT ANY WARRANTY.
12 
13  See the COPYING file for more details.
14 */
15 
16 #include "log.hpp"
17 #include "units/id.hpp"
18 #include "units/unit.hpp"
19 
20 #include "units/map.hpp"
21 #include <functional>
22 
23 static lg::log_domain log_engine("engine");
24 #define ERR_NG LOG_STREAM(err, log_engine)
25 #define WRN_NG LOG_STREAM(warn, log_engine)
26 #define LOG_NG LOG_STREAM(info, log_engine)
27 #define DBG_NG LOG_STREAM(debug, log_engine)
28 
30  : umap_()
31  , lmap_()
32 {
33 }
34 
36  : umap_()
37  , lmap_()
38 {
39  for(const auto& u : that) {
40  add(u.get_location(), u);
41  }
42 }
43 
45 {
46  unit_map temp(that);
47  swap(temp);
48  return *this;
49 }
50 
52 {
53  assert(num_iters() == 0 && o.num_iters() == 0);
54 
55  std::swap(umap_, o.umap_);
56  std::swap(lmap_, o.lmap_);
57 }
58 
60 {
61  clear(true);
62 }
63 
65 {
66  self_check();
67 
68  umap::iterator i = umap_.begin();
69  while(i != umap_.end() && (!i->second.unit)) {
70  ++i;
71  }
72 
73  return i;
74 }
75 
77 {
78  self_check();
79 
80  // TODO: should this take a shared pointer to a unit rather than make a copy?
81  unit_ptr p = u.clone();
82  p->set_location(l);
83 
85  if(res.second == false) {
86  p.reset();
87  }
88 
89  return res;
90 }
91 
93 {
94  self_check();
95  DBG_NG << "Unit map: Moving unit from " << src << " to " << dst << "\n";
96 
97  // Find the unit at the src location
98  lmap::iterator i = lmap_.find(src);
99  if(i == lmap_.end()) {
100  return std::pair(make_unit_iterator(i), false);
101  }
102 
103  umap::iterator uit(i->second);
104 
105  if(src == dst) {
106  return std::pair(make_unit_iterator(uit), true);
107  }
108 
109  // Fail if there is no unit to move.
110  unit_ptr p = uit->second.unit;
111  if(!p) {
112  return std::pair(make_unit_iterator(uit), false);
113  }
114 
115  p->set_location(dst);
116 
117  lmap_.erase(i);
118 
119  std::pair<lmap::iterator, bool> res = lmap_.emplace(dst, uit);
120 
121  // Fail and don't move if the destination is already occupied.
122  if(res.second == false) {
123  p->set_location(src);
124  lmap_.emplace(src, uit);
125  return std::pair(make_unit_iterator(uit), false);
126  }
127 
128  self_check();
129 
130  return std::pair(make_unit_iterator(uit), true);
131 }
132 
134 {
135  // 1. Construct a unit_pod.
136  // 2. Try insertion into the umap.
137  // 3. Try insertion in the lmap and remove the umap entry on failure.
138 
139  self_check();
140  assert(p);
141 
142  std::size_t unit_id = p->underlying_id();
143  const map_location& loc = p->get_location();
144 
145  if(!loc.valid()) {
146  ERR_NG << "Trying to add " << p->name() << " - " << p->id() << " at an invalid location; Discarding.\n";
147  return std::pair(make_unit_iterator(umap_.end()), false);
148  }
149 
150  unit_pod upod;
151  upod.unit = p;
152 
153  DBG_NG << "Adding unit " << p->underlying_id() << " - " << p->id() << " to location: (" << loc << ")\n";
154 
155  std::pair<umap::iterator, bool> uinsert = umap_.emplace(unit_id, upod);
156 
157  if(!uinsert.second) {
158  // If the pod is empty reinsert the unit in the same list element.
159  if(!uinsert.first->second.unit) {
160  unit_pod& opod = uinsert.first->second;
161  opod.unit = p;
162 
163  assert(opod.ref_count != 0);
164  } else {
165  unit_ptr q = uinsert.first->second.unit;
166  ERR_NG << "Trying to add " << p->name()
167  << " - " << p->id() << " - " << p->underlying_id()
168  << " (" << loc << ") over " << q->name()
169  << " - " << q->id() << " - " << q->underlying_id()
170  << " (" << q->get_location()
171  << ").\n";
172 
173  p->mark_clone(false);
174  ERR_NG << "The new unit was assigned underlying_id=" << p->underlying_id()
175  << " to prevent duplicate id conflicts.\n";
176 
177  uinsert = umap_.emplace(p->underlying_id(), upod);
178 
179  int guard(0);
180  while(!uinsert.second && (++guard < 1e6)) {
181  if(guard % 10 == 9) {
182  ERR_NG << "\n\nPlease Report this error to https://gna.org/bugs/index.php?18591 "
183  "\nIn addition to the standard details of operating system and wesnoth version "
184  "and how it happened, please answer the following questions "
185  "\n 1. Were you playing multi-player?"
186  "\n 2. Did you start/restart/reload the game/scenario?"
187  "\nThank you for your help in fixing this bug.\n";
188  }
189 
190  p->mark_clone(false);
191  uinsert = umap_.emplace(p->underlying_id(), upod);
192  }
193 
194  if(!uinsert.second) {
195  throw game::error("One million collisions in unit_map");
196  }
197  }
198  }
199 
200  std::pair<lmap::iterator, bool> linsert = lmap_.emplace(loc, uinsert.first);
201 
202  // Fail if the location is occupied
203  if(!linsert.second) {
204  if(upod.ref_count == 0) {
205  // Undo a virgin insertion
206  umap_.erase(uinsert.first);
207  } else {
208  // undo a reinsertion
209  uinsert.first->second.unit.reset();
210  }
211 
212  DBG_NG << "Trying to add " << p->name() << " - " << p->id() << " at location (" << loc << "); Occupied by "
213  << (linsert.first->second->second).unit->name() << " - " << linsert.first->second->second.unit->id()
214  << "\n";
215 
216  return std::pair(make_unit_iterator(umap_.end()), false);
217  }
218 
219  self_check();
220  return std::pair(make_unit_iterator(uinsert.first), true);
221 }
222 
224 {
225  self_check();
226  p->set_location(l);
227  erase(l);
228  return insert(p);
229 }
230 
231 std::size_t unit_map::num_iters() const
232 {
233  /** Add up number of extant iterators */
234  std::size_t num_iters(0);
235  umap::const_iterator ui = umap_.begin();
236  umap::const_iterator uend = umap_.end();
237 
238  for(; ui != uend; ++ui) {
239  if(ui->second.ref_count < 0) {
240  // Somewhere, someone generated 2^31 iterators to this unit.
241  bool a_reference_counter_overflowed(false);
242  assert(a_reference_counter_overflowed);
243  }
244 
245  num_iters += ui->second.ref_count;
246  }
247 
248  return num_iters;
249 }
250 
251 void unit_map::clear(bool force)
252 {
253  assert(force || (num_iters() == 0));
254 
255  for(umap::iterator i = umap_.begin(); i != umap_.end(); ++i) {
256  if(is_valid(i)) {
257  DBG_NG << "Delete unit " << i->second.unit->underlying_id() << "\n";
258  i->second.unit.reset();
259  }
260  }
261 
262  lmap_.clear();
263  umap_.clear();
264 }
265 
267 {
268  self_check();
269 
270  lmap::iterator i = lmap_.find(loc);
271  if(i == lmap_.end()) {
272  return unit_ptr();
273  }
274 
275  umap::iterator uit(i->second);
276 
277  unit_ptr u = uit->second.unit;
278  std::size_t uid(u->underlying_id());
279 
280  DBG_NG << "Extract unit " << uid << " - " << u->id() << " from location: (" << loc << ")\n";
281 
282  assert(uit->first == uit->second.unit->underlying_id());
283  if(uit->second.ref_count == 0) {
284  umap_.erase(uit);
285  } else {
286  // Soft extraction keeps the old lit item if any iterators reference it
287  uit->second.unit.reset();
288  }
289 
290  lmap_.erase(i);
291  self_check();
292 
293  return u;
294 }
295 
296 std::size_t unit_map::erase(const map_location& loc)
297 {
298  self_check();
299 
300  unit_ptr u = extract(loc);
301  if(!u) {
302  return 0;
303  }
304 
305  u.reset();
306  return 1;
307 }
308 
310 {
311  self_check();
312 
313  umap::iterator i(umap_.find(id));
314  if((i != umap_.end()) && !i->second.unit) {
315  i = umap_.end();
316  }
317 
318  return make_unit_iterator<umap::iterator>(i);
319 }
320 
322 {
323  self_check();
324  return make_unit_iterator<lmap::iterator>(lmap_.find(loc));
325 }
326 
328 {
329  unit_map::iterator i = begin(), i_end = end();
330  for(; i != i_end; ++i) {
331  if(i->side() == side && i->can_recruit()) {
332  return i;
333  }
334  }
335 
336  return i_end;
337 }
338 
340 {
341  unit_map::iterator i = begin(), i_end = end();
342  unit_map::iterator first_leader = end();
343 
344  for(; i != i_end; ++i) {
345  if(i->side() == side && i->can_recruit()) {
346  if((first_leader == end()) || (i->underlying_id() < first_leader->underlying_id())) {
347  first_leader = i;
348  }
349  }
350  }
351 
352  return first_leader;
353 }
354 
355 std::vector<unit_map::unit_iterator> unit_map::find_leaders(int side)
356 {
357  unit_map::unit_iterator i = begin(), i_end = end();
358 
359  std::vector<unit_map::unit_iterator> leaders;
360  for(; i != i_end; ++i) {
361  if(i->side() == side && i->can_recruit()) {
362  leaders.push_back(i);
363  }
364  }
365 
366  return leaders;
367 }
368 
369 std::vector<unit_map::const_unit_iterator> unit_map::find_leaders(int side) const
370 {
371  const std::vector<unit_map::unit_iterator>& leaders = const_cast<unit_map*>(this)->find_leaders(side);
372  std::vector<unit_map::const_unit_iterator> const_leaders(leaders.begin(), leaders.end());
373 
374  return const_leaders;
375 }
376 
378 {
379 #ifdef DEBUG_UNIT_MAP
380  bool good(true);
381 
382  umap::const_iterator uit(umap_.begin());
383  for(; uit != umap_.end(); ++uit) {
384  if(uit->second.ref_count < 0) {
385  good = false;
386  ERR_NG << "unit_map pod ref_count <0 is " << uit->second.ref_count << std::endl;
387  }
388 
389  if(uit->second.unit) {
390  uit->second.unit->id(); // crash if bad pointer
391  }
392 
393  if(uit->first <= 0) {
394  good = false;
395  ERR_NG << "unit_map umap uid <=0 is " << uit->first << std::endl;
396  }
397 
398  if(!uit->second.unit && uit->second.ref_count == 0) {
399  good = false;
400  ERR_NG << "unit_map umap unit==nullptr when refcount == 0" << std::endl;
401  }
402 
403  if(uit->second.unit && uit->second.unit->underlying_id() != uit->first) {
404  good = false;
405  ERR_NG << "unit_map umap uid(" << uit->first << ") != underlying_id()[" << uit->second.unit->underlying_id()
406  << "]" << std::endl;
407  }
408  }
409 
410  lmap::const_iterator locit(lmap_.begin());
411  for(; locit != lmap_.end(); ++locit) {
412  if(locit->second == umap_.end()) {
413  good = false;
414  ERR_NG << "unit_map lmap element == umap_.end() " << std::endl;
415  }
416  if(locit->first != locit->second->second.unit->get_location()) {
417  good = false;
418  ERR_NG << "unit_map lmap location != unit->get_location() " << std::endl;
419  }
420  }
421 
422  // assert(good);
423  return good;
424 #else
425  return true;
426 #endif
427 }
428 
429 bool unit_map::has_unit(const unit* const u) const
430 {
431  assert(u);
432 
433  for(const umap::value_type& item : umap_) {
434  if(item.second.unit.get() == u) {
435  return true;
436  }
437  }
438 
439  return false;
440 }
441 
442 bool unit_map::has_unit_at(const map_location& loc) const
443 {
444  return find(loc) != end();
445 }
446 
447 void swap(unit_map& lhs, unit_map& rhs)
448 {
449  lhs.swap(rhs);
450 }
std::vector< unit_iterator > find_leaders(int side)
Definition: map.cpp:355
unit_iterator end()
Definition: map.hpp:428
This class represents a single unit of a specific type.
Definition: unit.hpp:120
#define ERR_NG
Definition: map.cpp:24
unit_map & operator=(const unit_map &that)
Definition: map.cpp:44
umap_retval_pair_t insert(unit_ptr p)
Inserts the unit pointed to by p into the map.
Definition: map.cpp:133
unit_iterator find_leader(int side)
Definition: map.cpp:327
static l_noret error(LoadState *S, const char *why)
Definition: lundump.cpp:39
unit_ptr clone() const
Definition: unit.hpp:209
unit_iterator begin()
Definition: map.hpp:418
std::size_t erase(const map_location &l)
Erases the unit at location l, if any.
Definition: map.cpp:296
#define DBG_NG
Definition: map.cpp:27
unit_map::unit_iterator make_unit_iterator(const X &i)
Definition: map.hpp:566
std::shared_ptr< unit > unit_ptr
Definition: ptr.hpp:25
umap_retval_pair_t replace(const map_location &l, unit_ptr p)
Works like unit_map::add; but l is emptied first, if needed.
Definition: map.cpp:223
void swap(unit_map &lhs, unit_map &rhs)
Implement non-member swap function for std::swap (calls unit_map::swap).
Definition: map.cpp:447
umap_retval_pair_t add(const map_location &l, const unit &u)
Adds a copy of unit u at location l of the map.
Definition: map.cpp:76
bool valid() const
Definition: location.hpp:88
void clear(bool force=false)
Definition: map.cpp:251
const t_string & name() const
Gets this unit&#39;s translatable display name.
Definition: unit.hpp:393
std::pair< unit_iterator, bool > umap_retval_pair_t
Definition: map.hpp:452
umap_retval_pair_t move(const map_location &src, const map_location &dst)
Moves a unit from location src to location dst.
Definition: map.cpp:92
umap::iterator begin_core() const
Definition: map.cpp:64
Encapsulates the map of the game.
Definition: location.hpp:37
void swap(unit_map &o)
Definition: map.cpp:51
unit_ptr unit
Definition: map.hpp:108
unit_iterator find(std::size_t id)
Definition: map.cpp:309
std::size_t i
Definition: function.cpp:933
unit_iterator find_first_leader(int side)
Definition: map.cpp:339
mock_party p
std::size_t num_iters() const
Definition: map.cpp:231
The pointer to the unit and a reference counter to record the number of extant iteratorspointing to t...
Definition: map.hpp:100
bool has_unit_at(const map_location &loc) const
Tests whether a unit exists at the given location.
Definition: map.cpp:442
bool self_check() const
Checks invariants.
Definition: map.cpp:377
unit_ptr extract(const map_location &loc)
Extracts a unit from the map.
Definition: map.cpp:266
Standard logging facilities (interface).
n_ref_counter::ref_counter< signed int > ref_count
Definition: map.hpp:109
unit_map()
Definition: map.cpp:29
static lg::log_domain log_engine("engine")
lmap lmap_
location -> umap::iterator.
Definition: map.hpp:594
Container associating units to locations.
Definition: map.hpp:97
~unit_map()
Definition: map.cpp:59
umap umap_
underlying_id -> unit_pod.
Definition: map.hpp:589
bool is_valid(const umap::const_iterator &i) const
Definition: map.hpp:545
std::string::const_iterator iterator
Definition: tokenizer.hpp:24
std::pair< std::string, unsigned > item
Definition: help_impl.hpp:407
bool has_unit(const unit *const u) const
Is the unit in the map?
Definition: map.cpp:429