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