The Battle for Wesnoth  1.15.3+dev
map.hpp
Go to the documentation of this file.
1 /*
2  Copyright (C) 2006 - 2009 by Rusty Russell <rusty@rustcorp.com.au>
3  Copyright (C) 2010 - 2018 by Guillaume Melquiond <guillaume.melquiond@gmail.com>
4  Part of the Battle for Wesnoth Project https://www.wesnoth.org/
5 
6  This program is free software; you can redistribute it and/or modify
7  it under the terms of the GNU General Public License as published by
8  the Free Software Foundation; either version 2 of the License, or
9  (at your option) any later version.
10  This program is distributed in the hope that it will be useful,
11  but WITHOUT ANY WARRANTY.
12 
13  See the COPYING file for more details.
14 */
15 
16 /** @file */
17 
18 #pragma once
19 
20 #include "map/location.hpp"
21 #include "units/ptr.hpp"
23 
24 #include <cassert>
25 #include <list>
26 #include <map>
27 #include <unordered_map>
28 
29 //#define DEBUG_UNIT_MAP
30 
31 /**
32  * Container associating units to locations.
33  *
34  * The indirection location -> underlying_id -> unit ensures that iterators stay valid even if WML
35  * modifies or moves units on the fly. They even stay valid if a unit is erased from the map and
36  * another unit with the same underlying id is inserted in the map. In other words, it is a doubly
37  * indexed ordered map with persistent iterators (that never invalidate).
38  *
39  * @note The unit_map is implemented as 2 maps: an unordered map that stores iterators from the
40  * ordered map of reference-counted pointers to units.
41  *
42  * The unordered map provides O(1) find times. The ordered map ensures ordering of units by
43  * underlying_id. The reference counting is what guarantees the persistent iterators. Storing an
44  * iterator only prevents that dead unit's id-map entry from being recovered.
45  *
46  * @note Preferred usages for tight loops follows:
47  *
48  * Use the std::pair<iterator, bool> format which checks the preconditions and returns false
49  * (second) to indicate failure and no change to the unit_map. True indicates success along with the
50  * new iterator (first).
51  *
52  * Storing the result iterator prevents the old iterator from entering the fallback recovery code.
53  * This is faster than the old methodology of find to check if empty, insert, and then find to check
54  * for success. It is the same method as std::map uses, the C++ way.
55  *
56  * ================================================================================================
57  *
58  * unit_iterator i; //results are stored here
59  *
60  * ADD:
61  * std::pair<unit_iterator, bool> try_add(units->add(loc, unit));
62  * if(try_add.second) { i = try_add.first; }
63  *
64  * MOVE:
65  * std::pair<unit_iterator, bool> try_add(units->move(src, dst));
66  * if(try_add.second) { i = try_add.first; }
67  *
68  * INSERT:
69  * std::pair<unit_iterator, bool> try_add(units->insert(unitp));
70  * if(try_add.second) { i = try_add.first; }
71  *
72  * REPLACE (preferred over erase and then add)
73  * std::pair<unit_iterator, bool> try_add(units->move(loc, unit));
74  * if(try_add.second){ i = try_add.first; }
75  *
76  * ================================================================================================
77  *
78  *
79  * @note The previous implementation was 2 binary tree based maps: a location map pointing to another.
80  * Lookups were O(2*log(N)) and O(log(N)). Order was implicit in the id map chosen as the base.
81  * Persistence was provided by reference counting all iterators collectively and only recovering space
82  * when there were no iterators outstanding. Even 1 iterator being stored caused a leak, because all
83  * space for dead units was not recovered.
84  *
85  * @note Units are owned by the container.
86  *
87  * @note The indirection does not involve map lookups whenever an iterator is dereferenced, it just
88  * causes a pointer indirection. The downside is that incrementing iterators is not O(1).
89  *
90  * @note The code does not involve any magic, so units moved while being iterated upon may be skipped
91  * or visited twice.
92  *
93  * @note Iterators prevent ghost units from being collected, so they should never be stored in data
94  * structures, as it will cause slowdowns!
95  *
96  * @note By popular demand iterators are effectively permanent. They are handles and not iterators.
97  * Any access might cause a full lookup. Keeping iterators around holds onto memory.
98  */
99 class unit_map
100 {
101  /// The pointer to the unit and a reference counter to record the number of extant iterators
102  /// pointing to this unit.
103  struct unit_pod
104  {
106  : unit()
107  , ref_count()
108  {
109  }
110 
113  };
114 
115  /*
116  * Map of underlying_id to unit and a reference counter. Dead units have a unit pointer equal to nullptr.
117  * The map entry is removed iff the reference counter equals zero and there are no more
118  * iterators pointing to this unit.
119  */
120  typedef std::map<std::size_t, unit_pod> umap;
121 
122  /** Map of location to umap iterator. */
123  typedef std::unordered_map<map_location, umap::iterator> lmap;
124 
125 public:
126  // ~~~ Begin iterator code ~~~
127 
129  {
132  typedef unit value_type;
133  };
134 
136  {
137  typedef unit_map const container_type;
139  typedef const unit value_type;
140  };
141 
142  template<typename iter_types>
144  {
145  typedef std::forward_iterator_tag iterator_category;
146  typedef int difference_type;
147  typedef typename iter_types::value_type value_type;
148  typedef boost::intrusive_ptr<value_type> pointer;
149  typedef value_type& reference;
150  typedef typename iter_types::container_type container_type;
151  typedef typename iter_types::iterator_type iterator_type;
152 
154  {
155  dec();
156  }
157 
159  : i_()
160  , tank_(nullptr)
161  {
162  }
163 
164  iterator_base(iterator_type i, container_type* m)
165  : i_(i)
166  , tank_(m)
167  {
168  inc();
169  valid_exit();
170  }
171 
173  : i_(that.i_)
174  , tank_(that.tank_)
175  {
176  inc();
177  valid_exit();
178  }
179 
181  {
182  if(*this != that) {
183  dec();
184  tank_ = that.tank_;
185  i_ = that.i_;
186  inc();
187  valid_exit();
188  }
189 
190  return *this;
191  }
192 
194  {
195  return iterator_base<const_iter_types>(i_, tank_);
196  }
197 
198  private:
199  /** Constructs an iterator from the location map. */
200  iterator_base(lmap::iterator ui, container_type* m)
201  : i_(ui->second)
202  , tank_(m)
203  {
204  inc();
205  valid_exit();
206  }
207 
208  public:
209  pointer operator->() const
210  {
211  assert(valid());
212  tank_->self_check();
213  return i_->second.unit;
214  }
215 
216  /**
217  * This is exactly the same as operator-> but it's slightly more readable, and can replace
218  * &*iter syntax easily.
219  */
220  pointer get_shared_ptr() const
221  {
222  return operator->();
223  }
224 
225  reference operator*() const
226  {
227  tank_->self_check();
228  assert(valid());
229  return *i_->second.unit;
230  }
231 
233  {
234  assert(valid_entry());
235  tank_->self_check();
236  iterator_type new_i(i_);
237  do {
238  ++new_i;
239  } while((new_i != the_map().end()) && (!new_i->second.unit));
240  dec();
241  i_ = new_i;
242  inc();
243  valid_exit();
244  return *this;
245  }
246 
248  {
249  iterator_base temp(*this);
250  operator++();
251  return temp;
252  }
253 
255  {
256  assert(tank_ && i_ != the_map().begin());
257  tank_->self_check();
258  iterator_type begin(the_map().begin());
259  dec();
260  do {
261  --i_;
262  } while(i_ != begin && (!i_->second.unit));
263  inc();
264 
265  valid_exit();
266  return *this;
267  }
268 
270  {
271  iterator_base temp(*this);
272  operator--();
273  return temp;
274  }
275 
276  bool valid() const
277  {
278  return (valid_for_dereference() && i_->second.unit);
279  }
280 
281  explicit operator bool() const
282  {
283  return valid();
284  }
285 
286  bool operator==(const iterator_base& rhs) const
287  {
288  return (tank_ == rhs.tank_) && (i_ == rhs.i_);
289  }
290 
291  bool operator!=(const iterator_base& rhs) const
292  {
293  return !operator==(rhs);
294  }
295 
296  template<typename Y>
297  friend struct iterator_base;
298 
299  private:
301  {
302  return (tank_ != nullptr) && (i_ != the_map().end());
303  }
304 
305  bool valid_entry() const
306  {
307  return ((tank_ != nullptr) && (i_ != the_map().end()));
308  }
309 
310  void valid_exit() const
311  {
312  if((tank_ != nullptr) && i_ != the_map().end()) {
313  assert(i_->second.ref_count > 0);
314  }
315  }
316 
317  bool valid_ref_count() const
318  {
319  return (tank_ != nullptr) && (i_ != the_map().end());
320  }
321 
322  /** Increment the reference counter. */
323  void inc()
324  {
325  if(valid_ref_count()) {
326  ++(i_->second.ref_count);
327  }
328  }
329 
330  /**
331  * Decrement the reference counter
332  * Delete the umap entry if the unit is gone and the reference counter is zero.
333  *
334  * @note this deletion will advance i_ to the next umap entry.
335  */
336  void dec()
337  {
338  if(valid_ref_count()) {
339  assert(i_->second.ref_count != 0);
340  if((--(i_->second.ref_count) == 0) && (!i_->second.unit)) {
341  iterator_type old = i_++;
342  tank_->umap_.erase(old);
343  }
344  }
345  }
346 
348  {
349  return tank_->umap_;
350  }
351 
352  friend class unit_map;
353 
354  iterator_type i_; /// local iterator
355  container_type* tank_; /// 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.
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() ? 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() ? res.get_shared_ptr() : unit_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:200
iter_types::container_type container_type
Definition: map.hpp:150
boost::intrusive_ptr< const unit > unit_const_ptr
Definition: ptr.hpp:30
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:336
std::vector< unit_iterator > find_leaders(int side)
Definition: map.cpp:357
unit_iterator end()
Definition: map.hpp:429
bool valid_ref_count() const
Definition: map.hpp:317
iterator_base< standard_iter_types > unit_iterator
Definition: map.hpp:367
This class represents a single unit of a specific type.
Definition: unit.hpp:129
unit_map & operator=(const unit_map &that)
Definition: map.cpp:46
boost::intrusive_ptr< value_type > pointer
Definition: map.hpp:148
umap_retval_pair_t insert(unit_ptr p)
Inserts the unit pointed to by p into the map.
Definition: map.cpp:135
unit_iterator find_leader(int side)
Definition: map.cpp:329
iter_types::iterator_type iterator_type
Definition: map.hpp:151
unit_iterator begin()
Definition: map.hpp:419
std::map< std::size_t, unit_pod > umap
Definition: map.hpp:120
pointer operator->() const
Definition: map.hpp:209
std::size_t erase(const map_location &l)
Erases the unit at location l, if any.
Definition: map.cpp:298
unit_map::unit_iterator make_unit_iterator(const X &i)
Definition: map.hpp:567
unit_map const container_type
Definition: map.hpp:137
iterator_base< const_iter_types > const_unit_iterator
Definition: map.hpp:368
const unit value_type
Definition: map.hpp:139
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
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:225
iterator_base(const iterator_base &that)
Definition: map.hpp:172
std::unordered_map< map_location, umap::iterator > lmap
Map of location to umap iterator.
Definition: map.hpp:123
bool valid_entry() const
Definition: map.hpp:305
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:78
bool valid_for_dereference() const
Definition: map.hpp:300
iterator_base & operator=(const iterator_base &that)
Definition: map.hpp:180
iterator_base operator--(int)
Definition: map.hpp:269
void clear(bool force=false)
Definition: map.cpp:253
const_unit_iterator find(std::size_t id) const
Definition: map.hpp:382
unit_map::umap::iterator iterator_type
Definition: map.hpp:131
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:94
bool operator!=(const iterator_base &rhs) const
Definition: map.hpp:291
iterator_base(iterator_type i, container_type *m)
Definition: map.hpp:164
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:66
Encapsulates the map of the game.
Definition: location.hpp:42
unit_map::umap & the_map() const
Definition: map.hpp:347
unit_iterator iterator
Definition: map.hpp:371
void swap(unit_map &o)
Definition: map.cpp:53
unit_ptr unit
Definition: map.hpp:111
reference operator*() const
Definition: map.hpp:225
unit_iterator find(std::size_t id)
Definition: map.cpp:311
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:220
std::size_t i
Definition: function.cpp:933
unit_iterator find_first_leader(int side)
Definition: map.cpp:341
unit_map::umap::iterator iterator_type
Definition: map.hpp:138
mock_party p
std::size_t num_iters() const
Definition: map.cpp:233
iterator_base & operator--()
Definition: map.hpp:254
void inc()
Increment the reference counter.
Definition: map.hpp:323
bool operator==(const config &a, const config &b)
Definition: config.cpp:1418
bool empty() const
Definition: map.hpp:446
iterator_base & operator++()
Definition: map.hpp:232
bool operator==(const iterator_base &rhs) const
Definition: map.hpp:286
iterator_type i_
Definition: map.hpp:354
const_unit_iterator begin() const
Definition: map.hpp:424
The pointer to the unit and a reference counter to record the number of extant iterators pointing to ...
Definition: map.hpp:103
boost::intrusive_ptr< unit > unit_ptr
Definition: ptr.hpp:29
void valid_exit() const
Definition: map.hpp:310
bool has_unit_at(const map_location &loc) const
Tests whether a unit exists at the given location.
Definition: map.cpp:444
bool self_check() const
Checks invariants.
Definition: map.cpp:379
std::forward_iterator_tag iterator_category
Definition: map.hpp:145
container_type * tank_
local iterator
Definition: map.hpp:355
unit_ptr extract(const map_location &loc)
Extracts a unit from the map.
Definition: map.cpp:268
n_ref_counter::ref_counter< signed int > ref_count
Definition: map.hpp:112
unit_map()
Definition: map.cpp:31
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:99
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:61
umap umap_
underlying_id -> unit_pod.
Definition: map.hpp:590
bool is_valid(const umap::const_iterator &i) const
Definition: map.hpp:546
iter_types::value_type value_type
Definition: map.hpp:147
iterator_base operator++(int)
Definition: map.hpp:247
bool valid() const
Definition: map.hpp:276
std::string::const_iterator iterator
Definition: tokenizer.hpp:24
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:431
const_unit_iterator find_leader(int side) const
Definition: map.hpp:403
value_type & reference
Definition: map.hpp:149