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