The Battle for Wesnoth  1.19.0-dev
map.cpp
Go to the documentation of this file.
1 /*
2  Copyright (C) 2010 - 2024
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 "display.hpp"
18 #include "log.hpp"
19 #include "units/unit.hpp"
20 
21 #include "units/map.hpp"
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;
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 
129 
130  self_check();
131 
132  return std::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.";
149  return std::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 << ")";
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  << ").";
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.";
178 
179  uinsert = umap_.emplace(p->underlying_id(), upod);
180 
181  int guard(0);
182  while(!uinsert.second && (++guard < 1e6)) {
183  p->mark_clone(false);
184  uinsert = umap_.emplace(p->underlying_id(), upod);
185  }
186 
187  if(!uinsert.second) {
188  throw game::error("One million collisions in unit_map");
189  }
190  }
191  }
192 
193  std::pair<lmap::iterator, bool> linsert = lmap_.emplace(loc, uinsert.first);
194 
195  // Fail if the location is occupied
196  if(!linsert.second) {
197  if(upod.ref_count == 0) {
198  // Undo a virgin insertion
199  umap_.erase(uinsert.first);
200  } else {
201  // undo a reinsertion
202  uinsert.first->second.unit.reset();
203  }
204 
205  DBG_NG << "Trying to add " << p->name() << " - " << p->id() << " at location (" << loc << "); Occupied by "
206  << (linsert.first->second->second).unit->name() << " - " << linsert.first->second->second.unit->id()
207  << "\n";
208 
209  return std::pair(make_unit_iterator(umap_.end()), false);
210  }
211 
212  self_check();
213  return std::pair(make_unit_iterator(uinsert.first), true);
214 }
215 
217 {
218  self_check();
219  p->set_location(l);
220  erase(l);
221  return insert(p);
222 }
223 
224 std::size_t unit_map::num_iters() const
225 {
226  /** Add up number of extant iterators */
227  std::size_t num_iters(0);
228  umap::const_iterator ui = umap_.begin();
229  umap::const_iterator uend = umap_.end();
230 
231  for(; ui != uend; ++ui) {
232  if(ui->second.ref_count < 0) {
233  // Somewhere, someone generated 2^31 iterators to this unit.
234  bool a_reference_counter_overflowed(false);
235  assert(a_reference_counter_overflowed);
236  }
237 
238  num_iters += ui->second.ref_count;
239  }
240 
241  return num_iters;
242 }
243 
244 void unit_map::clear(bool force)
245 {
246  assert(force || (num_iters() == 0));
247 
248  for(umap::iterator i = umap_.begin(); i != umap_.end(); ++i) {
249  if(is_valid(i)) {
250  DBG_NG << "Delete unit " << i->second.unit->underlying_id();
251  i->second.unit.reset();
252  }
253  }
254 
255  lmap_.clear();
256  umap_.clear();
257 }
258 
260 {
261  self_check();
262 
263  lmap::iterator i = lmap_.find(loc);
264  if(i == lmap_.end()) {
265  return unit_ptr();
266  }
267 
268  umap::iterator uit(i->second);
269 
270  unit_ptr u = uit->second.unit;
271  std::size_t uid(u->underlying_id());
272 
273  DBG_NG << "Extract unit " << uid << " - " << u->id() << " from location: (" << loc << ")";
274 
275  assert(uit->first == uit->second.unit->underlying_id());
276  if(uit->second.ref_count == 0) {
277  umap_.erase(uit);
278  } else {
279  // Soft extraction keeps the old lit item if any iterators reference it
280  uit->second.unit.reset();
281  }
282 
283  lmap_.erase(i);
284  self_check();
285 
286  return u;
287 }
288 
289 std::size_t unit_map::erase(const map_location& loc)
290 {
291  self_check();
292 
293  unit_ptr u = extract(loc);
294  if(!u) {
295  return 0;
296  }
297 
298  u.reset();
299  return 1;
300 }
301 
303 {
304  self_check();
305 
306  umap::iterator i(umap_.find(id));
307  if((i != umap_.end()) && !i->second.unit) {
308  i = umap_.end();
309  }
310 
311  return make_unit_iterator<umap::iterator>(i);
312 }
313 
315 {
316  self_check();
317  return make_unit_iterator<lmap::iterator>(lmap_.find(loc));
318 }
319 
321 {
322  unit_map::iterator i = begin(), i_end = end();
323  for(; i != i_end; ++i) {
324  if(i->side() == side && i->can_recruit()) {
325  return i;
326  }
327  }
328 
329  return i_end;
330 }
331 
333 {
334  unit_map::iterator i = begin(), i_end = end();
335  unit_map::iterator first_leader = end();
336 
337  for(; i != i_end; ++i) {
338  if(i->side() == side && i->can_recruit()) {
339  if((first_leader == end()) || (i->underlying_id() < first_leader->underlying_id())) {
340  first_leader = i;
341  }
342  }
343  }
344 
345  return first_leader;
346 }
347 
348 std::vector<unit_map::unit_iterator> unit_map::find_leaders(int side)
349 {
350  unit_map::unit_iterator i = begin(), i_end = end();
351 
352  std::vector<unit_map::unit_iterator> leaders;
353  for(; i != i_end; ++i) {
354  if(i->side() == side && i->can_recruit()) {
355  leaders.push_back(i);
356  }
357  }
358 
359  return leaders;
360 }
361 
362 std::vector<unit_map::const_unit_iterator> unit_map::find_leaders(int side) const
363 {
364  const std::vector<unit_map::unit_iterator>& leaders = const_cast<unit_map*>(this)->find_leaders(side);
365  std::vector<unit_map::const_unit_iterator> const_leaders(leaders.begin(), leaders.end());
366 
367  return const_leaders;
368 }
369 
371 {
372 #ifdef DEBUG_UNIT_MAP
373  bool good(true);
374 
375  umap::const_iterator uit(umap_.begin());
376  for(; uit != umap_.end(); ++uit) {
377  if(uit->second.ref_count < 0) {
378  good = false;
379  ERR_NG << "unit_map pod ref_count <0 is " << uit->second.ref_count;
380  }
381 
382  if(uit->second.unit) {
383  uit->second.unit->id(); // crash if bad pointer
384  }
385 
386  if(uit->first <= 0) {
387  good = false;
388  ERR_NG << "unit_map umap uid <=0 is " << uit->first;
389  }
390 
391  if(!uit->second.unit && uit->second.ref_count == 0) {
392  good = false;
393  ERR_NG << "unit_map umap unit==nullptr when refcount == 0";
394  }
395 
396  if(uit->second.unit && uit->second.unit->underlying_id() != uit->first) {
397  good = false;
398  ERR_NG << "unit_map umap uid(" << uit->first << ") != underlying_id()[" << uit->second.unit->underlying_id()
399  << "]";
400  }
401  }
402 
403  lmap::const_iterator locit(lmap_.begin());
404  for(; locit != lmap_.end(); ++locit) {
405  if(locit->second == umap_.end()) {
406  good = false;
407  ERR_NG << "unit_map lmap element == umap_.end() ";
408  }
409  if(locit->first != locit->second->second.unit->get_location()) {
410  good = false;
411  ERR_NG << "unit_map lmap location != unit->get_location() ";
412  }
413  }
414 
415  // assert(good);
416  return good;
417 #else
418  return true;
419 #endif
420 }
421 
422 bool unit_map::has_unit(const unit* const u) const
423 {
424  assert(u);
425 
426  for(const umap::value_type& item : umap_) {
427  if(item.second.unit.get() == u) {
428  return true;
429  }
430  }
431 
432  return false;
433 }
434 
435 bool unit_map::has_unit_at(const map_location& loc) const
436 {
437  return find(loc) != end();
438 }
439 
440 void swap(unit_map& lhs, unit_map& rhs)
441 {
442  lhs.swap(rhs);
443 }
bool invalidate(const map_location &loc)
Function to invalidate a specific tile for redrawing.
Definition: display.cpp:3137
static display * get_singleton()
Returns the display object if a display object exists.
Definition: display.hpp:95
Container associating units to locations.
Definition: map.hpp:98
umap::iterator begin_core() const
Definition: map.cpp:64
std::vector< unit_iterator > find_leaders(int side)
Definition: map.cpp:348
unit_iterator end()
Definition: map.hpp:428
umap umap_
underlying_id -> unit_pod.
Definition: map.hpp:589
bool has_unit_at(const map_location &loc) const
Tests whether a unit exists at the given location.
Definition: map.cpp:435
std::pair< unit_iterator, bool > umap_retval_pair_t
Definition: map.hpp:452
void swap(unit_map &o)
Definition: map.cpp:51
bool self_check() const
Checks invariants.
Definition: map.cpp:370
unit_map()
Definition: map.cpp:29
void clear(bool force=false)
Definition: map.cpp:244
unit_ptr extract(const map_location &loc)
Extracts a unit from the map.
Definition: map.cpp:259
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:216
unit_iterator find(std::size_t id)
Definition: map.cpp:302
unit_map & operator=(const unit_map &that)
Definition: map.cpp:44
unit_map::unit_iterator make_unit_iterator(const X &i)
Definition: map.hpp:566
unit_iterator begin()
Definition: map.hpp:418
std::size_t num_iters() const
Definition: map.cpp:224
unit_iterator find_first_leader(int side)
Definition: map.cpp:332
lmap lmap_
location -> umap::iterator.
Definition: map.hpp:594
bool has_unit(const unit *const u) const
Is the unit in the map?
Definition: map.cpp:422
std::size_t erase(const map_location &l)
Erases the unit at location l, if any.
Definition: map.cpp:289
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
unit_iterator find_leader(int side)
Definition: map.cpp:320
umap_retval_pair_t insert(unit_ptr p)
Inserts the unit pointed to by p into the map.
Definition: map.cpp:135
bool is_valid(const umap::const_iterator &i) const
Definition: map.hpp:545
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
~unit_map()
Definition: map.cpp:59
This class represents a single unit of a specific type.
Definition: unit.hpp:133
unit_ptr clone() const
Definition: unit.hpp:221
std::size_t i
Definition: function.cpp:968
const t_string & name() const
Gets this unit's translatable display name.
Definition: unit.hpp:403
Standard logging facilities (interface).
std::pair< std::string, unsigned > item
Definition: help_impl.hpp:412
std::string::const_iterator iterator
Definition: tokenizer.hpp:25
bool good
Definition: picture.cpp:195
std::shared_ptr< unit > unit_ptr
Definition: ptr.hpp:26
Base class for all the errors encountered by the engine.
Definition: exceptions.hpp:29
Encapsulates the map of the game.
Definition: location.hpp:38
bool valid() const
Definition: location.hpp:89
The pointer to the unit and a reference counter to record the number of extant iteratorspointing to t...
Definition: map.hpp:101
n_ref_counter::ref_counter< signed int > ref_count
Definition: map.hpp:109
unit_ptr unit
Definition: map.hpp:108
mock_party p
void swap(unit_map &lhs, unit_map &rhs)
Implement non-member swap function for std::swap (calls unit_map::swap).
Definition: map.cpp:440
static lg::log_domain log_engine("engine")
#define ERR_NG
Definition: map.cpp:24
#define DBG_NG
Definition: map.cpp:27