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