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/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;
98 
99  // Find the unit at the src location
100  lmap::iterator i = lmap_.find(src);
101  if(i == lmap_.end()) {
102  return std::pair(make_unit_iterator(i), false);
103  }
104 
105  umap::iterator uit(i->second);
106 
107  if(src == dst) {
108  return std::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::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::pair(make_unit_iterator(uit), false);
128  }
129 
131 
132  self_check();
133 
134  return std::pair(make_unit_iterator(uit), true);
135 }
136 
138 {
139  // 1. Construct a unit_pod.
140  // 2. Try insertion into the umap.
141  // 3. Try insertion in the lmap and remove the umap entry on failure.
142 
143  self_check();
144  assert(p);
145 
146  std::size_t unit_id = p->underlying_id();
147  const map_location& loc = p->get_location();
148 
149  if(!loc.valid()) {
150  ERR_NG << "Trying to add " << p->name() << " - " << p->id() << " at an invalid location; Discarding.";
151  return std::pair(make_unit_iterator(umap_.end()), false);
152  }
153 
154  unit_pod upod;
155  upod.unit = p;
156 
157  DBG_NG << "Adding unit " << p->underlying_id() << " - " << p->id() << " to location: (" << loc << ")";
158 
159  std::pair<umap::iterator, bool> uinsert = umap_.emplace(unit_id, upod);
160 
161  if(!uinsert.second) {
162  // If the pod is empty reinsert the unit in the same list element.
163  if(!uinsert.first->second.unit) {
164  unit_pod& opod = uinsert.first->second;
165  opod.unit = p;
166 
167  assert(opod.ref_count != 0);
168  } else {
169  unit_ptr q = uinsert.first->second.unit;
170  ERR_NG << "Trying to add " << p->name()
171  << " - " << p->id() << " - " << p->underlying_id()
172  << " (" << loc << ") over " << q->name()
173  << " - " << q->id() << " - " << q->underlying_id()
174  << " (" << q->get_location()
175  << ").";
176 
177  p->mark_clone(false);
178  ERR_NG << "The new unit was assigned underlying_id=" << p->underlying_id()
179  << " to prevent duplicate id conflicts.";
180 
181  uinsert = umap_.emplace(p->underlying_id(), upod);
182 
183  int guard(0);
184  while(!uinsert.second && (++guard < 1e6)) {
185  p->mark_clone(false);
186  uinsert = umap_.emplace(p->underlying_id(), upod);
187  }
188 
189  if(!uinsert.second) {
190  throw game::error("One million collisions in unit_map");
191  }
192  }
193  }
194 
195  std::pair<lmap::iterator, bool> linsert = lmap_.emplace(loc, uinsert.first);
196 
197  // Fail if the location is occupied
198  if(!linsert.second) {
199  if(upod.ref_count == 0) {
200  // Undo a virgin insertion
201  umap_.erase(uinsert.first);
202  } else {
203  // undo a reinsertion
204  uinsert.first->second.unit.reset();
205  }
206 
207  DBG_NG << "Trying to add " << p->name() << " - " << p->id() << " at location (" << loc << "); Occupied by "
208  << (linsert.first->second->second).unit->name() << " - " << linsert.first->second->second.unit->id()
209  << "\n";
210 
211  return std::pair(make_unit_iterator(umap_.end()), false);
212  }
213 
214  self_check();
215  return std::pair(make_unit_iterator(uinsert.first), true);
216 }
217 
219 {
220  self_check();
221  p->set_location(l);
222  erase(l);
223  return insert(p);
224 }
225 
226 std::size_t unit_map::num_iters() const
227 {
228  /** Add up number of extant iterators */
229  std::size_t num_iters(0);
230  umap::const_iterator ui = umap_.begin();
231  umap::const_iterator uend = umap_.end();
232 
233  for(; ui != uend; ++ui) {
234  if(ui->second.ref_count < 0) {
235  // Somewhere, someone generated 2^31 iterators to this unit.
236  bool a_reference_counter_overflowed(false);
237  assert(a_reference_counter_overflowed);
238  }
239 
240  num_iters += ui->second.ref_count;
241  }
242 
243  return num_iters;
244 }
245 
246 void unit_map::clear(bool force)
247 {
248  assert(force || (num_iters() == 0));
249 
250  for(umap::iterator i = umap_.begin(); i != umap_.end(); ++i) {
251  if(is_valid(i)) {
252  DBG_NG << "Delete unit " << i->second.unit->underlying_id();
253  i->second.unit.reset();
254  }
255  }
256 
257  lmap_.clear();
258  umap_.clear();
259 }
260 
262 {
263  self_check();
264 
265  lmap::iterator i = lmap_.find(loc);
266  if(i == lmap_.end()) {
267  return unit_ptr();
268  }
269 
270  umap::iterator uit(i->second);
271 
272  unit_ptr u = uit->second.unit;
273  std::size_t uid(u->underlying_id());
274 
275  DBG_NG << "Extract unit " << uid << " - " << u->id() << " from location: (" << loc << ")";
276 
277  assert(uit->first == uit->second.unit->underlying_id());
278  if(uit->second.ref_count == 0) {
279  umap_.erase(uit);
280  } else {
281  // Soft extraction keeps the old lit item if any iterators reference it
282  uit->second.unit.reset();
283  }
284 
285  lmap_.erase(i);
286  self_check();
287 
288  return u;
289 }
290 
291 std::size_t unit_map::erase(const map_location& loc)
292 {
293  self_check();
294 
295  unit_ptr u = extract(loc);
296  if(!u) {
297  return 0;
298  }
299 
300  u.reset();
301  return 1;
302 }
303 
305 {
306  self_check();
307 
308  umap::iterator i(umap_.find(id));
309  if((i != umap_.end()) && !i->second.unit) {
310  i = umap_.end();
311  }
312 
313  return make_unit_iterator<umap::iterator>(i);
314 }
315 
317 {
318  self_check();
319  return make_unit_iterator<lmap::iterator>(lmap_.find(loc));
320 }
321 
323 {
324  unit_map::iterator i = begin(), i_end = end();
325  for(; i != i_end; ++i) {
326  if(i->side() == side && i->can_recruit()) {
327  return i;
328  }
329  }
330 
331  return i_end;
332 }
333 
335 {
336  unit_map::iterator i = begin(), i_end = end();
337  unit_map::iterator first_leader = end();
338 
339  for(; i != i_end; ++i) {
340  if(i->side() == side && i->can_recruit()) {
341  if((first_leader == end()) || (i->underlying_id() < first_leader->underlying_id())) {
342  first_leader = i;
343  }
344  }
345  }
346 
347  return first_leader;
348 }
349 
350 std::vector<unit_map::unit_iterator> unit_map::find_leaders(int side)
351 {
352  unit_map::unit_iterator i = begin(), i_end = end();
353 
354  std::vector<unit_map::unit_iterator> leaders;
355  for(; i != i_end; ++i) {
356  if(i->side() == side && i->can_recruit()) {
357  leaders.push_back(i);
358  }
359  }
360 
361  return leaders;
362 }
363 
364 std::vector<unit_map::const_unit_iterator> unit_map::find_leaders(int side) const
365 {
366  const std::vector<unit_map::unit_iterator>& leaders = const_cast<unit_map*>(this)->find_leaders(side);
367  std::vector<unit_map::const_unit_iterator> const_leaders(leaders.begin(), leaders.end());
368 
369  return const_leaders;
370 }
371 
373 {
374 #ifdef DEBUG_UNIT_MAP
375  bool good(true);
376 
377  umap::const_iterator uit(umap_.begin());
378  for(; uit != umap_.end(); ++uit) {
379  if(uit->second.ref_count < 0) {
380  good = false;
381  ERR_NG << "unit_map pod ref_count <0 is " << uit->second.ref_count;
382  }
383 
384  if(uit->second.unit) {
385  uit->second.unit->id(); // crash if bad pointer
386  }
387 
388  if(uit->first <= 0) {
389  good = false;
390  ERR_NG << "unit_map umap uid <=0 is " << uit->first;
391  }
392 
393  if(!uit->second.unit && uit->second.ref_count == 0) {
394  good = false;
395  ERR_NG << "unit_map umap unit==nullptr when refcount == 0";
396  }
397 
398  if(uit->second.unit && uit->second.unit->underlying_id() != uit->first) {
399  good = false;
400  ERR_NG << "unit_map umap uid(" << uit->first << ") != underlying_id()[" << uit->second.unit->underlying_id()
401  << "]";
402  }
403  }
404 
405  lmap::const_iterator locit(lmap_.begin());
406  for(; locit != lmap_.end(); ++locit) {
407  if(locit->second == umap_.end()) {
408  good = false;
409  ERR_NG << "unit_map lmap element == umap_.end() ";
410  }
411  if(locit->first != locit->second->second.unit->get_location()) {
412  good = false;
413  ERR_NG << "unit_map lmap location != unit->get_location() ";
414  }
415  }
416 
417  // assert(good);
418  return good;
419 #else
420  return true;
421 #endif
422 }
423 
424 bool unit_map::has_unit(const unit* const u) const
425 {
426  assert(u);
427 
428  for(const umap::value_type& item : umap_) {
429  if(item.second.unit.get() == u) {
430  return true;
431  }
432  }
433 
434  return false;
435 }
436 
437 bool unit_map::has_unit_at(const map_location& loc) const
438 {
439  return find(loc) != end();
440 }
441 
442 void swap(unit_map& lhs, unit_map& rhs)
443 {
444  lhs.swap(rhs);
445 }
bool invalidate(const map_location &loc)
Function to invalidate a specific tile for redrawing.
Definition: display.cpp:3143
static display * get_singleton()
Returns the display object if a display object exists.
Definition: display.hpp:100
Container associating units to locations.
Definition: map.hpp:99
umap::iterator begin_core() const
Definition: map.cpp:66
std::vector< unit_iterator > find_leaders(int side)
Definition: map.cpp:350
unit_iterator end()
Definition: map.hpp:429
umap umap_
underlying_id -> unit_pod.
Definition: map.hpp:590
bool has_unit_at(const map_location &loc) const
Tests whether a unit exists at the given location.
Definition: map.cpp:437
std::pair< unit_iterator, bool > umap_retval_pair_t
Definition: map.hpp:453
void swap(unit_map &o)
Definition: map.cpp:53
bool self_check() const
Checks invariants.
Definition: map.cpp:372
unit_map()
Definition: map.cpp:31
void clear(bool force=false)
Definition: map.cpp:246
unit_ptr extract(const map_location &loc)
Extracts a unit from the map.
Definition: map.cpp:261
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:218
unit_iterator find(std::size_t id)
Definition: map.cpp:304
unit_map & operator=(const unit_map &that)
Definition: map.cpp:46
unit_map::unit_iterator make_unit_iterator(const X &i)
Definition: map.hpp:567
unit_iterator begin()
Definition: map.hpp:419
std::size_t num_iters() const
Definition: map.cpp:226
unit_iterator find_first_leader(int side)
Definition: map.cpp:334
lmap lmap_
location -> umap::iterator.
Definition: map.hpp:595
bool has_unit(const unit *const u) const
Is the unit in the map?
Definition: map.cpp:424
std::size_t erase(const map_location &l)
Erases the unit at location l, if any.
Definition: map.cpp:291
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
unit_iterator find_leader(int side)
Definition: map.cpp:322
umap_retval_pair_t insert(unit_ptr p)
Inserts the unit pointed to by p into the map.
Definition: map.cpp:137
bool is_valid(const umap::const_iterator &i) const
Definition: map.hpp:546
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
~unit_map()
Definition: map.cpp:61
This class represents a single unit of a specific type.
Definition: unit.hpp:135
unit_ptr clone() const
Definition: unit.hpp:223
std::size_t i
Definition: function.cpp:968
const t_string & name() const
Gets this unit's translatable display name.
Definition: unit.hpp:405
Standard logging facilities (interface).
std::pair< std::string, unsigned > item
Definition: help_impl.hpp:414
std::string::const_iterator iterator
Definition: tokenizer.hpp:25
bool good
Definition: picture.cpp:200
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:102
n_ref_counter::ref_counter< signed int > ref_count
Definition: map.hpp:110
unit_ptr unit
Definition: map.hpp:109
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:442
static lg::log_domain log_engine("engine")
#define ERR_NG
Definition: map.cpp:26
#define DBG_NG
Definition: map.cpp:29