Author: boucman
Date: Tue Aug 2 09:31:39 2011
New Revision: 50546
URL: http://svn.gna.org/viewcvs/wesnoth?rev=50546&view=rev
Log:
apply patch #2819 : Change unit_map to a faster implementation by thonsew
Modified:
trunk/RELEASE_NOTES
trunk/src/map_location.hpp
trunk/src/unit_map.cpp
trunk/src/unit_map.hpp
Modified: trunk/RELEASE_NOTES
URL:
http://svn.gna.org/viewcvs/wesnoth/trunk/RELEASE_NOTES?rev=50546&r1=50545&r2=50546&view=diff
==============================================================================
--- trunk/RELEASE_NOTES (original)
+++ trunk/RELEASE_NOTES Tue Aug 2 09:31:39 2011
@@ -14,8 +14,8 @@
CHANGES
=======
-[section="title"]
-text
+[section="Dependencies"]
+Wesnoth now requires boost 1.36 to have unordered map
[/section]
Modified: trunk/src/map_location.hpp
URL:
http://svn.gna.org/viewcvs/wesnoth/trunk/src/map_location.hpp?rev=50546&r1=50545&r2=50546&view=diff
==============================================================================
--- trunk/src/map_location.hpp (original)
+++ trunk/src/map_location.hpp Tue Aug 2 09:31:39 2011
@@ -24,6 +24,7 @@
#include <string>
#include <vector>
#include <set>
+#include <boost/unordered_map.hpp>
#define MAX_MAP_AREA 65536
@@ -98,6 +99,8 @@
static DIRECTION get_opposite_dir(DIRECTION d);
static const map_location null_location;
+
+ friend std::size_t hash_value(map_location const &a);
};
/** Function which tells if two locations are adjacent. */
@@ -138,4 +141,10 @@
/** Dumps a vector of positions on a stream, for debug purposes. */
std::ostream &operator<<(std::ostream &s, std::vector<map_location> const &v);
+/** Inlined bodies **/
+inline std::size_t hash_value(map_location const & a){
+ boost::hash<size_t> h;
+ return h( (a.x << 16) ^ a.y );
+}
+
#endif
Modified: trunk/src/unit_map.cpp
URL:
http://svn.gna.org/viewcvs/wesnoth/trunk/src/unit_map.cpp?rev=50546&r1=50545&r2=50546&view=diff
==============================================================================
--- trunk/src/unit_map.cpp (original)
+++ trunk/src/unit_map.cpp Tue Aug 2 09:31:39 2011
@@ -21,6 +21,7 @@
#include "log.hpp"
#include <functional>
+#include "unit_map.hpp"
static lg::log_domain log_engine("engine");
#define ERR_NG LOG_STREAM(err, log_engine)
@@ -54,28 +55,8 @@
std::swap(num_invalid_, o.num_invalid_);
}
-unit_map::~unit_map()
-{
+unit_map::~unit_map() {
clear();
-}
-
-unit_map::unit_iterator unit_map::find(const map_location &loc) {
- lmap::const_iterator i = lmap_.find(loc);
- if (i == lmap_.end()) {
- return unit_iterator(map_.end(), this);
- }
-
- umap::iterator iter = map_.find(i->second);
-
- assert(is_valid(iter));
- return unit_iterator(iter, this);
-}
-
-unit_map::unit_iterator unit_map::find(size_t id)
-{
- umap::iterator iter = map_.find(id);
- if (!is_valid(iter)) iter = map_.end();
- return unit_iterator(iter, this);
}
unit_map::unit_iterator unit_map::begin() {
@@ -151,8 +132,9 @@
DBG_NG << "Adding unit " << p->underlying_id() << " - " << p->id()
<< " to location: (" << loc << ")\n";
- std::pair<lmap::iterator,bool> res = lmap_.insert(std::make_pair(loc,
unit_id));
+ std::pair<lmap::iterator,bool> res = lmap_.insert(std::make_pair(loc,
biter.first));
assert(res.second);
+
}
void unit_map::replace(const map_location &l, const unit &u)
@@ -184,17 +166,17 @@
unit *unit_map::extract(const map_location &loc)
{
lmap::iterator i = lmap_.find(loc);
- if (i == lmap_.end())
- return NULL;
-
- umap::iterator iter = map_.find(i->second);
+ if (i == lmap_.end()) {
+ return NULL; }
+
+ umap::iterator iter = i->second;
unit *res = iter->second;
DBG_NG << "Extract unit " << res->underlying_id() << " - " << res->id()
<< " from location: (" << loc << ")\n";
iter->second = NULL;
++num_invalid_;
- lmap_.erase(i);
+ lmap_.erase_return_void(i);
return res;
}
Modified: trunk/src/unit_map.hpp
URL:
http://svn.gna.org/viewcvs/wesnoth/trunk/src/unit_map.hpp?rev=50546&r1=50545&r2=50546&view=diff
==============================================================================
--- trunk/src/unit_map.hpp (original)
+++ trunk/src/unit_map.hpp Tue Aug 2 09:31:39 2011
@@ -23,6 +23,7 @@
#include <cassert>
#include <map>
+#include <boost/unordered_map.hpp>
class unit;
@@ -41,11 +42,10 @@
* @note Iterators prevent ghost units from being collected. So they should
* never be stored into data structures, as it will cause slowdowns!
*/
-class unit_map
-{
+class unit_map {
public:
- typedef std::map<size_t, unit *> umap;
- typedef std::map<map_location, size_t> lmap;
+ typedef boost::unordered_map<size_t, unit *> umap;
+ typedef boost::unordered_map<map_location, umap::iterator> lmap;
unit_map() : map_(), lmap_(), num_iters_(0), num_invalid_(0) { };
unit_map(const unit_map &that);
@@ -129,8 +129,9 @@
iterator_base& operator--()
{
assert(map_ && i_ != map_->map_.begin());
- do --i_;
- while (i_ != map_->map_.begin() && !i_->second);
+ iterator_type next(map_->map_.begin()), oldi(i_);
+ do { i_ = ++next;
+ }while(next != oldi );
return *this;
}
@@ -183,8 +184,20 @@
typedef unit_iterator iterator;
typedef const_unit_iterator const_iterator;
- unit_iterator find(const map_location& loc) ;
- unit_iterator find(size_t id);
+ unit_iterator find(size_t id) {
+ umap::iterator iter = map_.find(id);
+ if (!is_valid(iter)) iter = map_.end();
+ return unit_iterator(iter, this);
+ }
+
+ unit_iterator find(const map_location &loc) {
+ lmap::const_iterator i = lmap_.find(loc);
+ if (i == lmap_.end()) {
+ return unit_iterator(map_.end(), this);
+ }
+ assert(is_valid(i->second));
+ return unit_iterator(i->second, this);
+ }
const_unit_iterator find(const map_location &loc) const
{ return const_cast<unit_map *>(this)->find(loc); }
@@ -199,7 +212,7 @@
std::vector<unit_iterator> find_leaders(int side);
std::vector<const_unit_iterator> find_leaders(int side) const;
- size_t count(const map_location& loc) const { return lmap_.count(loc); }
+ size_t count(const map_location& loc) const { return
static_cast<size_t>(lmap_.count(loc)); }
unit_iterator begin();
const_unit_iterator begin() const;
@@ -291,4 +304,6 @@
assert(0);
}
+
+
#endif // UNIT_MAP_H_INCLUDED
_______________________________________________
Wesnoth-commits mailing list
[email protected]
https://mail.gna.org/listinfo/wesnoth-commits
