The Battle for Wesnoth  1.17.0-dev
map.hpp
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 #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;
147  typedef value_type& reference;
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 
162  iterator_base(iterator_type i, container_type* m)
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  {
193  return iterator_base<const_iter_types>(i_, tank_);
194  }
195 
196  private:
197  /** Constructs an iterator from the location map. */
198  iterator_base(lmap::iterator ui, container_type* m)
199  : i_(ui->second)
200  , tank_(m)
201  {
202  inc();
203  valid_exit();
204  }
205 
206  public:
207  pointer operator->() const
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  */
218  pointer get_shared_ptr() const
219  {
220  return operator->();
221  }
222 
223  reference operator*() const
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();
256  iterator_type begin(the_map().begin());
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 */
353  iterator_type i_;
354  /** the unit_map for i_ */
355  container_type* tank_;
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.
371  typedef unit_iterator iterator;
372  typedef const_unit_iterator const_iterator;
373 
374  unit_iterator find(std::size_t id);
375  unit_iterator find(const map_location& loc);
376 
377  const_unit_iterator find(const map_location& loc) const
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 
403  const_unit_iterator find_leader(int side) const
404  {
405  return const_cast<unit_map*>(this)->find_leader(side);
406  }
407 
408  unit_iterator find_first_leader(int side);
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 
419  unit_iterator begin()
420  {
421  return make_unit_iterator(begin_core());
422  }
423 
424  const_unit_iterator begin() const
425  {
427  }
428 
429  unit_iterator end()
430  {
431  return make_unit_iterator(umap_.end());
432  }
433 
434  const_unit_iterator end() const
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  */
595  lmap lmap_;
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 }
iterator_base(lmap::iterator ui, container_type *m)
Constructs an iterator from the location map.
Definition: map.hpp:198
iter_types::container_type container_type
Definition: map.hpp:148
unit_const_ptr find_unit_ptr(const T &val) const
Definition: map.hpp:395
void dec()
Decrement the reference counter Delete the umap entry if the unit is gone and the reference counter i...
Definition: map.hpp:334
std::vector< unit_iterator > find_leaders(int side)
Definition: map.cpp:356
unit_iterator end()
Definition: map.hpp:429
bool valid_ref_count() const
Definition: map.hpp:315
iterator_base< standard_iter_types > unit_iterator
Definition: map.hpp:367
This class represents a single unit of a specific type.
Definition: unit.hpp:121
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
iter_types::iterator_type iterator_type
Definition: map.hpp:149
unit_iterator begin()
Definition: map.hpp:419
std::map< std::size_t, unit_pod > umap
Definition: map.hpp:118
pointer operator->() const
Definition: map.hpp:207
std::size_t erase(const map_location &l)
Erases the unit at location l, if any.
Definition: map.cpp:297
unit_map::unit_iterator make_unit_iterator(const X &i)
Definition: map.hpp:567
unit_map const container_type
Definition: map.hpp:135
iterator_base< const_iter_types > const_unit_iterator
Definition: map.hpp:368
std::shared_ptr< unit > unit_ptr
Definition: ptr.hpp:26
const unit value_type
Definition: map.hpp:137
bool is_found(const lmap::const_iterator &i) const
Definition: map.hpp:561
unit_ptr find_unit_ptr(const T &val)
Definition: map.hpp:388
std::shared_ptr< const unit > unit_const_ptr
Definition: ptr.hpp:27
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
iterator_base(const iterator_base &that)
Definition: map.hpp:170
std::unordered_map< map_location, umap::iterator > lmap
Map of location to umap iterator.
Definition: map.hpp:121
bool valid_entry() const
Definition: map.hpp:303
const_unit_iterator const_iterator
Definition: map.hpp:372
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_for_dereference() const
Definition: map.hpp:298
iterator_base & operator=(const iterator_base &that)
Definition: map.hpp:178
iterator_base operator--(int)
Definition: map.hpp:267
void clear(bool force=false)
Definition: map.cpp:252
const_unit_iterator find(std::size_t id) const
Definition: map.hpp:382
unit_map::umap::iterator iterator_type
Definition: map.hpp:129
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
bool operator!=(const iterator_base &rhs) const
Definition: map.hpp:289
iterator_base(iterator_type i, container_type *m)
Definition: map.hpp:162
std::size_t count(const map_location &loc) const
Definition: map.hpp:414
std::size_t size() const
Definition: map.hpp:439
umap::iterator begin_core() const
Definition: map.cpp:65
Encapsulates the map of the game.
Definition: location.hpp:38
unit_map::umap & the_map() const
Definition: map.hpp:345
unit_iterator iterator
Definition: map.hpp:371
void swap(unit_map &o)
Definition: map.cpp:52
unit_ptr unit
Definition: map.hpp:109
reference operator*() const
Definition: map.hpp:223
unit_iterator find(std::size_t id)
Definition: map.cpp:310
pointer get_shared_ptr() const
This is exactly the same as operator-> but it&#39;s slightly more readable, and can replace &*iter syntax...
Definition: map.hpp:218
std::size_t i
Definition: function.cpp:967
unit_iterator find_first_leader(int side)
Definition: map.cpp:340
unit_map::umap::iterator iterator_type
Definition: map.hpp:136
mock_party p
std::size_t num_iters() const
Definition: map.cpp:232
iterator_base & operator--()
Definition: map.hpp:252
void inc()
Increment the reference counter.
Definition: map.hpp:321
bool operator==(const config &a, const config &b)
Definition: config.cpp:1475
bool empty() const
Definition: map.hpp:446
iterator_base & operator++()
Definition: map.hpp:230
bool operator==(const iterator_base &rhs) const
Definition: map.hpp:284
iterator_type i_
local iterator
Definition: map.hpp:353
const_unit_iterator begin() const
Definition: map.hpp:424
The pointer to the unit and a reference counter to record the number of extant iteratorspointing to t...
Definition: map.hpp:101
void valid_exit() const
Definition: map.hpp:308
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
std::forward_iterator_tag iterator_category
Definition: map.hpp:143
container_type * tank_
the unit_map for i_
Definition: map.hpp:355
unit_ptr extract(const map_location &loc)
Extracts a unit from the map.
Definition: map.cpp:267
n_ref_counter::ref_counter< signed int > ref_count
Definition: map.hpp:110
unit_map()
Definition: map.cpp:30
lmap lmap_
location -> umap::iterator.
Definition: map.hpp:595
unit_map::const_unit_iterator make_const_unit_iterator(const X &i) const
Definition: map.hpp:577
Container associating units to locations.
Definition: map.hpp:98
bool is_found(const umap::const_iterator &i) const
Definition: map.hpp:556
const_unit_iterator end() const
Definition: map.hpp:434
bool is_valid(const lmap::const_iterator &i) const
Definition: map.hpp:551
~unit_map()
Definition: map.cpp:60
umap umap_
underlying_id -> unit_pod.
Definition: map.hpp:590
std::shared_ptr< value_type > pointer
Definition: map.hpp:146
bool is_valid(const umap::const_iterator &i) const
Definition: map.hpp:546
iter_types::value_type value_type
Definition: map.hpp:145
iterator_base operator++(int)
Definition: map.hpp:245
bool valid() const
Definition: map.hpp:274
std::string::const_iterator iterator
Definition: tokenizer.hpp:25
const_unit_iterator find(const map_location &loc) const
Definition: map.hpp:377
bool has_unit(const unit *const u) const
Is the unit in the map?
Definition: map.cpp:430
const_unit_iterator find_leader(int side) const
Definition: map.hpp:403
value_type & reference
Definition: map.hpp:147