The Battle for Wesnoth  1.15.2+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  unit_iterator find_leader(int side);
388 
389  const_unit_iterator find_leader(int side) const
390  {
391  return const_cast<unit_map*>(this)->find_leader(side);
392  }
393 
394  unit_iterator find_first_leader(int side);
395 
396  std::vector<unit_iterator> find_leaders(int side);
397 
398  std::vector<const_unit_iterator> find_leaders(int side) const;
399 
400  std::size_t count(const map_location& loc) const
401  {
402  return lmap_.count(loc);
403  }
404 
405  unit_iterator begin()
406  {
407  return make_unit_iterator(begin_core());
408  }
409 
410  const_unit_iterator begin() const
411  {
413  }
414 
415  unit_iterator end()
416  {
417  return make_unit_iterator(umap_.end());
418  }
419 
420  const_unit_iterator end() const
421  {
422  return make_const_unit_iterator(umap_.end());
423  }
424 
425  std::size_t size() const
426  {
427  return lmap_.size();
428  }
429 
430  std::size_t num_iters() const;
431 
432  bool empty() const
433  {
434  return lmap_.empty();
435  }
436 
437  void clear(bool force = false);
438 
439  using umap_retval_pair_t = std::pair<unit_iterator, bool>;
440 
441  /**
442  * Adds a copy of unit @a u at location @a l of the map.
443  *
444  * @returns A pair consisting of an iterator pointing to the new unit (or the unit
445  * already occupying that location) and a bool indicating success.
446  *
447  * @note It is 3 times as fast to attempt to insert a unit at @a l and check for
448  * success than it is to verify that the location is empty, insert the unit,
449  * and then check the location for the unit.
450  */
451  umap_retval_pair_t add(const map_location& l, const unit& u);
452 
453  /**
454  * Inserts the unit pointed to by @a p into the map.
455  *
456  * If insertion into either the unit or location map fails, all operations are reverted.
457  *
458  * The one oddity is that to facilitate non-invalidating iterators, the list sometimes has
459  * nullptr pointers which should be used when they correspond to uids previously used.
460  *
461  * @returns A pair consisting of an iterator pointing to the new unit (or the unit
462  * already occupying that location) and a bool indicating success.
463  *
464  * @note It is 3 times as fast to attempt to insert a unit at @a l and check for
465  * success than it is to verify that the location is empty, insert the unit,
466  * and then check the location for the unit.
467  *
468  * @note If the unit::underlying_id is already in use, a new one will be generated.
469  * @note The map takes ownership of the pointed object only if the operation succeeds.
470  */
472 
473  /**
474  * Moves a unit from location @a src to location @a dst.
475  *
476  * @returns A pair consisting of an iterator pointing to the new unit (or the unit
477  * already occupying that location) and a bool indicating success.
478  *
479  * @note It is 3 times as fast to attempt to insert a unit at @a l and check for
480  * success than it is to verify that the location is empty, insert the unit,
481  * and then check the location for the unit.
482  */
483  umap_retval_pair_t move(const map_location& src, const map_location& dst);
484 
485  /**
486  * Works like unit_map::add; but @a l is emptied first, if needed.
487  *
488  * @returns A pair consisting of an iterator pointing to the new unit (or the unit
489  * already occupying that location) and a bool indicating success.
490  */
492 
493  /**
494  * Erases the unit at location @a l, if any.
495  * @returns the number of erased units (0 or 1).
496  */
497  std::size_t erase(const map_location& l);
498 
499  /**
500  * Erases a unit given by a pointer or an iterator.
501  * @pre The unit is on the map.
502  */
503  template<typename T>
504  std::size_t erase(const T& iter);
505 
506  /**
507  * Extracts a unit from the map.
508  * The unit is no longer owned by the map. It can be reinserted later, if needed.
509  */
510  unit_ptr extract(const map_location& loc);
511 
512  /** Checks invariants. For debugging purposes only. Doesn't do anything in non-debug mode. */
513  bool self_check() const;
514 
515  /**
516  * Is the unit in the map?
517  *
518  * @pre @p u != @c nullptr
519  *
520  * @param u Pointer to the unit to find.
521  *
522  * @returns True if found, false otherwise.
523  */
524  bool has_unit(const unit* const u) const;
525 
526  /** Tests whether a unit exists at the given location. */
527  bool has_unit_at(const map_location& loc) const;
528 
529 private:
530  umap::iterator begin_core() const;
531 
532  bool is_valid(const umap::const_iterator& i) const
533  {
534  return is_found(i) && (i->second.unit != nullptr);
535  }
536 
537  bool is_valid(const lmap::const_iterator& i) const
538  {
539  return is_found(i) && (i->second->second.unit != nullptr);
540  }
541 
542  bool is_found(const umap::const_iterator& i) const
543  {
544  return i != umap_.end();
545  }
546 
547  bool is_found(const lmap::const_iterator& i) const
548  {
549  return i != lmap_.end();
550  }
551 
552  template<typename X>
554  {
555  if(!is_found(i)) {
556  return unit_iterator(umap_.end(), this);
557  }
558 
559  return unit_iterator(i, this);
560  }
561 
562  template<typename X>
564  {
565  if(!is_found(i)) {
566  return const_unit_iterator(umap_.end(), this);
567  }
568 
569  return const_unit_iterator(i, this);
570  }
571 
572  /**
573  * underlying_id -> unit_pod.
574  * This requires that underlying_id be unique (which is enforced in unit_map::insert).
575  */
576  mutable umap umap_;
577 
578  /**
579  * location -> umap::iterator.
580  */
581  lmap lmap_;
582 };
583 
584 /** Implement non-member swap function for std::swap (calls @ref unit_map::swap). */
585 void swap(unit_map& lhs, unit_map& rhs);
586 
587 template<typename T>
588 std::size_t unit_map::erase(const T& iter)
589 {
590  assert(iter.valid());
591 
592  return erase(iter->get_location());
593 }
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
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:415
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:99
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:405
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:553
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:547
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:439
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:400
std::size_t size() const
Definition: map.hpp:425
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:1405
bool empty() const
Definition: map.hpp:432
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:410
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:581
unit_map::const_unit_iterator make_const_unit_iterator(const X &i) const
Definition: map.hpp:563
Container associating units to locations.
Definition: map.hpp:99
bool is_found(const umap::const_iterator &i) const
Definition: map.hpp:542
const_unit_iterator end() const
Definition: map.hpp:420
bool is_valid(const lmap::const_iterator &i) const
Definition: map.hpp:537
~unit_map()
Definition: map.cpp:61
umap umap_
underlying_id -> unit_pod.
Definition: map.hpp:576
bool is_valid(const umap::const_iterator &i) const
Definition: map.hpp:532
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:389
value_type & reference
Definition: map.hpp:149