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