The Battle for Wesnoth  1.17.21+dev
map.hpp
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 #pragma once
18 
19 #include "map/location.hpp"
20 #include "units/ptr.hpp"
22 
23 #include <cassert>
24 #include <list>
25 #include <map>
26 #include <unordered_map>
27 
28 //#define DEBUG_UNIT_MAP
29 
30 /**
31  * Container associating units to locations.
32  *
33  * The indirection location -> underlying_id -> unit ensures that iterators stay valid even if WML
34  * modifies or moves units on the fly. They even stay valid if a unit is erased from the map and
35  * another unit with the same underlying id is inserted in the map. In other words, it is a doubly
36  * indexed ordered map with persistent iterators (that never invalidate).
37  *
38  * @note The unit_map is implemented as 2 maps: an unordered map that stores iterators from the
39  * ordered map of reference-counted pointers to units.
40  *
41  * The unordered map provides O(1) find times. The ordered map ensures ordering of units by
42  * underlying_id. The reference counting is what guarantees the persistent iterators. Storing an
43  * iterator only prevents that dead unit's id-map entry from being recovered.
44  *
45  * @note Preferred usages for tight loops follows:
46  *
47  * Use the std::pair<iterator, bool> format which checks the preconditions and returns false
48  * (second) to indicate failure and no change to the unit_map. True indicates success along with the
49  * new iterator (first).
50  *
51  * Storing the result iterator prevents the old iterator from entering the fallback recovery code.
52  * This is faster than the old methodology of find to check if empty, insert, and then find to check
53  * for success. It is the same method as std::map uses, the C++ way.
54  *
55  * ================================================================================================
56  *
57  * unit_iterator i; //results are stored here
58  *
59  * ADD:
60  * std::pair<unit_iterator, bool> try_add(units->add(loc, unit));
61  * if(try_add.second) { i = try_add.first; }
62  *
63  * MOVE:
64  * std::pair<unit_iterator, bool> try_add(units->move(src, dst));
65  * if(try_add.second) { i = try_add.first; }
66  *
67  * INSERT:
68  * std::pair<unit_iterator, bool> try_add(units->insert(unitp));
69  * if(try_add.second) { i = try_add.first; }
70  *
71  * REPLACE (preferred over erase and then add)
72  * std::pair<unit_iterator, bool> try_add(units->move(loc, unit));
73  * if(try_add.second){ i = try_add.first; }
74  *
75  * ================================================================================================
76  *
77  *
78  * @note The previous implementation was 2 binary tree based maps: a location map pointing to another.
79  * Lookups were O(2*log(N)) and O(log(N)). Order was implicit in the id map chosen as the base.
80  * Persistence was provided by reference counting all iterators collectively and only recovering space
81  * when there were no iterators outstanding. Even 1 iterator being stored caused a leak, because all
82  * space for dead units was not recovered.
83  *
84  * @note Units are owned by the container.
85  *
86  * @note The indirection does not involve map lookups whenever an iterator is dereferenced, it just
87  * causes a pointer indirection. The downside is that incrementing iterators is not O(1).
88  *
89  * @note The code does not involve any magic, so units moved while being iterated upon may be skipped
90  * or visited twice.
91  *
92  * @note Iterators prevent ghost units from being collected, so they should never be stored in data
93  * structures, as it will cause slowdowns!
94  *
95  * @note By popular demand iterators are effectively permanent. They are handles and not iterators.
96  * Any access might cause a full lookup. Keeping iterators around holds onto memory.
97  */
98 class unit_map
99 {
100  /** The pointer to the unit and a reference counter to record the number of extant iteratorspointing to this unit. */
101  struct unit_pod
102  {
104  : unit()
105  , ref_count()
106  {
107  }
108 
111  };
112 
113  /*
114  * Map of underlying_id to unit and a reference counter. Dead units have a unit pointer equal to nullptr.
115  * The map entry is removed iff the reference counter equals zero and there are no more
116  * iterators pointing to this unit.
117  */
118  typedef std::map<std::size_t, unit_pod> umap;
119 
120  /** Map of location to umap iterator. */
121  typedef std::unordered_map<map_location, umap::iterator> lmap;
122 
123 public:
124  // ~~~ Begin iterator code ~~~
125 
127  {
130  typedef unit value_type;
131  };
132 
134  {
135  typedef unit_map const container_type;
137  typedef const unit value_type;
138  };
139 
140  template<typename iter_types>
142  {
143  typedef std::forward_iterator_tag iterator_category;
144  typedef int difference_type;
145  typedef typename iter_types::value_type value_type;
146  typedef std::shared_ptr<value_type> pointer;
148  typedef typename iter_types::container_type container_type;
149  typedef typename iter_types::iterator_type iterator_type;
150 
152  {
153  dec();
154  }
155 
157  : i_()
158  , tank_(nullptr)
159  {
160  }
161 
163  : i_(i)
164  , tank_(m)
165  {
166  inc();
167  valid_exit();
168  }
169 
171  : i_(that.i_)
172  , tank_(that.tank_)
173  {
174  inc();
175  valid_exit();
176  }
177 
179  {
180  if(*this != that) {
181  dec();
182  tank_ = that.tank_;
183  i_ = that.i_;
184  inc();
185  valid_exit();
186  }
187 
188  return *this;
189  }
190 
192  {
194  }
195 
196  private:
197  /** Constructs an iterator from the location map. */
199  : i_(ui->second)
200  , tank_(m)
201  {
202  inc();
203  valid_exit();
204  }
205 
206  public:
208  {
209  assert(valid());
210  tank_->self_check();
211  return i_->second.unit;
212  }
213 
214  /**
215  * This is exactly the same as operator-> but it's slightly more readable, and can replace
216  * &*iter syntax easily.
217  */
219  {
220  return operator->();
221  }
222 
224  {
225  tank_->self_check();
226  assert(valid());
227  return *i_->second.unit;
228  }
229 
231  {
232  assert(valid_entry());
233  tank_->self_check();
234  iterator_type new_i(i_);
235  do {
236  ++new_i;
237  } while((new_i != the_map().end()) && (!new_i->second.unit));
238  dec();
239  i_ = new_i;
240  inc();
241  valid_exit();
242  return *this;
243  }
244 
246  {
247  iterator_base temp(*this);
248  operator++();
249  return temp;
250  }
251 
253  {
254  assert(tank_ && i_ != the_map().begin());
255  tank_->self_check();
257  dec();
258  do {
259  --i_;
260  } while(i_ != begin && (!i_->second.unit));
261  inc();
262 
263  valid_exit();
264  return *this;
265  }
266 
268  {
269  iterator_base temp(*this);
270  operator--();
271  return temp;
272  }
273 
274  bool valid() const
275  {
276  return (valid_for_dereference() && i_->second.unit);
277  }
278 
279  explicit operator bool() const
280  {
281  return valid();
282  }
283 
284  bool operator==(const iterator_base& rhs) const
285  {
286  return (tank_ == rhs.tank_) && (i_ == rhs.i_);
287  }
288 
289  bool operator!=(const iterator_base& rhs) const
290  {
291  return !operator==(rhs);
292  }
293 
294  template<typename Y>
295  friend struct iterator_base;
296 
297  private:
299  {
300  return (tank_ != nullptr) && (i_ != the_map().end());
301  }
302 
303  bool valid_entry() const
304  {
305  return ((tank_ != nullptr) && (i_ != the_map().end()));
306  }
307 
308  void valid_exit() const
309  {
310  if((tank_ != nullptr) && i_ != the_map().end()) {
311  assert(i_->second.ref_count > 0);
312  }
313  }
314 
315  bool valid_ref_count() const
316  {
317  return (tank_ != nullptr) && (i_ != the_map().end());
318  }
319 
320  /** Increment the reference counter. */
321  void inc()
322  {
323  if(valid_ref_count()) {
324  ++(i_->second.ref_count);
325  }
326  }
327 
328  /**
329  * Decrement the reference counter
330  * Delete the umap entry if the unit is gone and the reference counter is zero.
331  *
332  * @note this deletion will advance i_ to the next umap entry.
333  */
334  void dec()
335  {
336  if(valid_ref_count()) {
337  assert(i_->second.ref_count != 0);
338  if((--(i_->second.ref_count) == 0) && (!i_->second.unit)) {
339  iterator_type old = i_++;
340  tank_->umap_.erase(old);
341  }
342  }
343  }
344 
346  {
347  return tank_->umap_;
348  }
349 
350  friend class unit_map;
351 
352  /** local iterator */
354  /** the unit_map for i_ */
356  };
357 
358  // ~~~ End iterator code ~~~
359 
360  unit_map();
361  unit_map(const unit_map& that);
362  unit_map& operator=(const unit_map& that);
363 
364  ~unit_map();
365  void swap(unit_map& o);
366 
369 
370  // Provided as a convenience, since unit_map used to be an std::map.
373 
374  unit_iterator find(std::size_t id);
375  unit_iterator find(const map_location& loc);
376 
378  {
379  return const_cast<unit_map*>(this)->find(loc);
380  }
381 
382  const_unit_iterator find(std::size_t id) const
383  {
384  return const_cast<unit_map*>(this)->find(id);
385  }
386 
387  template<typename T>
388  unit_ptr find_unit_ptr(const T& val)
389  {
390  auto res = find(val);
391  return res != end() ? unit_ptr(res.get_shared_ptr()) : unit_ptr();
392  }
393 
394  template<typename T>
395  unit_const_ptr find_unit_ptr(const T& val) const
396  {
397  auto res = find(val);
398  return res != end() ? unit_const_ptr(res.get_shared_ptr()) : unit_const_ptr();
399  }
400 
401  unit_iterator find_leader(int side);
402 
404  {
405  return const_cast<unit_map*>(this)->find_leader(side);
406  }
407 
409 
410  std::vector<unit_iterator> find_leaders(int side);
411 
412  std::vector<const_unit_iterator> find_leaders(int side) const;
413 
414  std::size_t count(const map_location& loc) const
415  {
416  return lmap_.count(loc);
417  }
418 
420  {
421  return make_unit_iterator(begin_core());
422  }
423 
425  {
427  }
428 
430  {
431  return make_unit_iterator(umap_.end());
432  }
433 
435  {
436  return make_const_unit_iterator(umap_.end());
437  }
438 
439  std::size_t size() const
440  {
441  return lmap_.size();
442  }
443 
444  std::size_t num_iters() const;
445 
446  bool empty() const
447  {
448  return lmap_.empty();
449  }
450 
451  void clear(bool force = false);
452 
453  using umap_retval_pair_t = std::pair<unit_iterator, bool>;
454 
455  /**
456  * Adds a copy of unit @a u at location @a l of the map.
457  *
458  * @returns A pair consisting of an iterator pointing to the new unit (or the unit
459  * already occupying that location) and a bool indicating success.
460  *
461  * @note It is 3 times as fast to attempt to insert a unit at @a l and check for
462  * success than it is to verify that the location is empty, insert the unit,
463  * and then check the location for the unit.
464  */
465  umap_retval_pair_t add(const map_location& l, const unit& u);
466 
467  /**
468  * Inserts the unit pointed to by @a p into the map.
469  *
470  * If insertion into either the unit or location map fails, all operations are reverted.
471  *
472  * The one oddity is that to facilitate non-invalidating iterators, the list sometimes has
473  * nullptr pointers which should be used when they correspond to uids previously used.
474  *
475  * @returns A pair consisting of an iterator pointing to the new unit (or the unit
476  * already occupying that location) and a bool indicating success.
477  *
478  * @note It is 3 times as fast to attempt to insert a unit at @a l and check for
479  * success than it is to verify that the location is empty, insert the unit,
480  * and then check the location for the unit.
481  *
482  * @note If the unit::underlying_id is already in use, a new one will be generated.
483  * @note The map takes ownership of the pointed object only if the operation succeeds.
484  */
486 
487  /**
488  * Moves a unit from location @a src to location @a dst.
489  *
490  * @returns A pair consisting of an iterator pointing to the new unit (or the unit
491  * already occupying that location) and a bool indicating success.
492  *
493  * @note It is 3 times as fast to attempt to insert a unit at @a l and check for
494  * success than it is to verify that the location is empty, insert the unit,
495  * and then check the location for the unit.
496  */
497  umap_retval_pair_t move(const map_location& src, const map_location& dst);
498 
499  /**
500  * Works like unit_map::add; but @a l is emptied first, if needed.
501  *
502  * @returns A pair consisting of an iterator pointing to the new unit (or the unit
503  * already occupying that location) and a bool indicating success.
504  */
506 
507  /**
508  * Erases the unit at location @a l, if any.
509  * @returns the number of erased units (0 or 1).
510  */
511  std::size_t erase(const map_location& l);
512 
513  /**
514  * Erases a unit given by a pointer or an iterator.
515  * @pre The unit is on the map.
516  */
517  template<typename T>
518  std::size_t erase(const T& iter);
519 
520  /**
521  * Extracts a unit from the map.
522  * The unit is no longer owned by the map. It can be reinserted later, if needed.
523  */
524  unit_ptr extract(const map_location& loc);
525 
526  /** Checks invariants. For debugging purposes only. Doesn't do anything in non-debug mode. */
527  bool self_check() const;
528 
529  /**
530  * Is the unit in the map?
531  *
532  * @pre @p u != @c nullptr
533  *
534  * @param u Pointer to the unit to find.
535  *
536  * @returns True if found, false otherwise.
537  */
538  bool has_unit(const unit* const u) const;
539 
540  /** Tests whether a unit exists at the given location. */
541  bool has_unit_at(const map_location& loc) const;
542 
543 private:
544  umap::iterator begin_core() const;
545 
546  bool is_valid(const umap::const_iterator& i) const
547  {
548  return is_found(i) && (i->second.unit != nullptr);
549  }
550 
551  bool is_valid(const lmap::const_iterator& i) const
552  {
553  return is_found(i) && (i->second->second.unit != nullptr);
554  }
555 
556  bool is_found(const umap::const_iterator& i) const
557  {
558  return i != umap_.end();
559  }
560 
561  bool is_found(const lmap::const_iterator& i) const
562  {
563  return i != lmap_.end();
564  }
565 
566  template<typename X>
568  {
569  if(!is_found(i)) {
570  return unit_iterator(umap_.end(), this);
571  }
572 
573  return unit_iterator(i, this);
574  }
575 
576  template<typename X>
578  {
579  if(!is_found(i)) {
580  return const_unit_iterator(umap_.end(), this);
581  }
582 
583  return const_unit_iterator(i, this);
584  }
585 
586  /**
587  * underlying_id -> unit_pod.
588  * This requires that underlying_id be unique (which is enforced in unit_map::insert).
589  */
590  mutable umap umap_;
591 
592  /**
593  * location -> umap::iterator.
594  */
596 };
597 
598 /** Implement non-member swap function for std::swap (calls @ref unit_map::swap). */
599 void swap(unit_map& lhs, unit_map& rhs);
600 
601 template<typename T>
602 std::size_t unit_map::erase(const T& iter)
603 {
604  assert(iter.valid());
605 
606  return erase(iter->get_location());
607 }
Container associating units to locations.
Definition: map.hpp:99
unit_const_ptr find_unit_ptr(const T &val) const
Definition: map.hpp:395
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
bool empty() const
Definition: map.hpp:446
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
const_unit_iterator end() const
Definition: map.hpp:434
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
iterator_base< const_iter_types > const_unit_iterator
Definition: map.hpp:368
const_unit_iterator find(std::size_t id) const
Definition: map.hpp:382
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
unit_iterator iterator
Definition: map.hpp:371
std::size_t count(const map_location &loc) const
Definition: map.hpp:414
const_unit_iterator const_iterator
Definition: map.hpp:372
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
iterator_base< standard_iter_types > unit_iterator
Definition: map.hpp:367
unit_ptr find_unit_ptr(const T &val)
Definition: map.hpp:388
const_unit_iterator begin() const
Definition: map.hpp:424
const_unit_iterator find(const map_location &loc) const
Definition: map.hpp:377
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 is_found(const lmap::const_iterator &i) const
Definition: map.hpp:561
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
std::size_t size() const
Definition: map.hpp:439
unit_iterator find_leader(int side)
Definition: map.cpp:319
std::unordered_map< map_location, umap::iterator > lmap
Map of location to umap iterator.
Definition: map.hpp:121
umap_retval_pair_t insert(unit_ptr p)
Inserts the unit pointed to by p into the map.
Definition: map.cpp:134
const_unit_iterator find_leader(int side) const
Definition: map.hpp:403
bool is_valid(const lmap::const_iterator &i) const
Definition: map.hpp:551
bool is_found(const umap::const_iterator &i) const
Definition: map.hpp:556
bool is_valid(const umap::const_iterator &i) const
Definition: map.hpp:546
std::map< std::size_t, unit_pod > umap
Definition: map.hpp:118
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
unit_map::const_unit_iterator make_const_unit_iterator(const X &i) const
Definition: map.hpp:577
This class represents a single unit of a specific type.
Definition: unit.hpp:134
std::size_t i
Definition: function.cpp:968
std::string::const_iterator iterator
Definition: tokenizer.hpp:25
std::shared_ptr< const unit > unit_const_ptr
Definition: ptr.hpp:27
std::shared_ptr< unit > unit_ptr
Definition: ptr.hpp:26
Encapsulates the map of the game.
Definition: location.hpp:38
unit_map const container_type
Definition: map.hpp:135
unit_map::umap::iterator iterator_type
Definition: map.hpp:136
const unit value_type
Definition: map.hpp:137
std::forward_iterator_tag iterator_category
Definition: map.hpp:143
iterator_base & operator++()
Definition: map.hpp:230
bool valid() const
Definition: map.hpp:274
iter_types::value_type value_type
Definition: map.hpp:145
iterator_base & operator--()
Definition: map.hpp:252
iterator_base(lmap::iterator ui, container_type *m)
Constructs an iterator from the location map.
Definition: map.hpp:198
iterator_base & operator=(const iterator_base &that)
Definition: map.hpp:178
iterator_base operator--(int)
Definition: map.hpp:267
iterator_base(const iterator_base &that)
Definition: map.hpp:170
unit_map::umap & the_map() const
Definition: map.hpp:345
bool valid_for_dereference() const
Definition: map.hpp:298
std::shared_ptr< value_type > pointer
Definition: map.hpp:146
reference operator*() const
Definition: map.hpp:223
bool operator==(const iterator_base &rhs) const
Definition: map.hpp:284
iterator_base(iterator_type i, container_type *m)
Definition: map.hpp:162
iter_types::container_type container_type
Definition: map.hpp:148
pointer operator->() const
Definition: map.hpp:207
bool operator!=(const iterator_base &rhs) const
Definition: map.hpp:289
iter_types::iterator_type iterator_type
Definition: map.hpp:149
bool valid_entry() const
Definition: map.hpp:303
iterator_base operator++(int)
Definition: map.hpp:245
iterator_type i_
local iterator
Definition: map.hpp:353
void valid_exit() const
Definition: map.hpp:308
void dec()
Decrement the reference counter Delete the umap entry if the unit is gone and the reference counter i...
Definition: map.hpp:334
value_type & reference
Definition: map.hpp:147
container_type * tank_
the unit_map for i_
Definition: map.hpp:355
pointer get_shared_ptr() const
This is exactly the same as operator-> but it's slightly more readable, and can replace &*iter syntax...
Definition: map.hpp:218
void inc()
Increment the reference counter.
Definition: map.hpp:321
bool valid_ref_count() const
Definition: map.hpp:315
unit_map::umap::iterator iterator_type
Definition: map.hpp:129
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