[Wesnoth-cvs-commits] wesnoth/src astarnode.cpp astarnode.hpp pathfin...

[Guillaume Melquiond]

CVSROOT:        /cvsroot/wesnoth
Module name:    wesnoth
Branch:         
Changes by:     Guillaume Melquiond <address@hidden>    05/06/05 10:56:41

Modified files:
        src            : astarnode.cpp astarnode.hpp pathfind.cpp 

Log message:
        Review of the A* allocation code. A lot of noise due to switching to 
Wesnoth coding style: underscore after the private members. The memory leaks on 
destruction are now plugged, and the node pool is now private to the node 
world; the pathfinder doesn't know about it anymore. The parano assertions are 
no longer needed. All these changes are only interface changes, the 
implementation is not changed: this is still the same page-based allocation 
strategy.

CVSWeb URLs:
http://savannah.gnu.org/cgi-bin/viewcvs/wesnoth/wesnoth/src/astarnode.cpp.diff?tr1=1.3&tr2=1.4&r1=text&r2=text
http://savannah.gnu.org/cgi-bin/viewcvs/wesnoth/wesnoth/src/astarnode.hpp.diff?tr1=1.4&tr2=1.5&r1=text&r2=text
http://savannah.gnu.org/cgi-bin/viewcvs/wesnoth/wesnoth/src/pathfind.cpp.diff?tr1=1.70&tr2=1.71&r1=text&r2=text

Patches:
Index: wesnoth/src/astarnode.cpp
diff -u wesnoth/src/astarnode.cpp:1.3 wesnoth/src/astarnode.cpp:1.4
--- wesnoth/src/astarnode.cpp:1.3       Sat Jun  4 19:16:05 2005
+++ wesnoth/src/astarnode.cpp   Sun Jun  5 10:56:41 2005
@@ -1,6 +1,7 @@
-/* $Id: astarnode.cpp,v 1.3 2005/06/04 19:16:05 ott Exp $ */
+/* $Id: astarnode.cpp,v 1.4 2005/06/05 10:56:41 silene Exp $ */
 /*
 Copyright (C) 2003 by David White <address@hidden>
+Copyright (C) 2005 by Guillaume Melquiond <address@hidden>
 Part of the Battle for Wesnoth Project http://www.wesnoth.org/
 
 This program is free software; you can redistribute it and/or modify
@@ -15,11 +16,8 @@
 #include "astarnode.hpp"
 #include "wassert.hpp"
 
-poss_a_star_node* SingletonPOSS_AStarNode = NULL;
-
-void a_star_node::initNode(const gamemap::location& pos, const 
gamemap::location& dst,
-                                                                               
                        double cost, a_star_node* parent,
-                                                                               
                        const std::set<gamemap::location>* teleports)
+void a_star_node::initNode(gamemap::location const &pos, gamemap::location 
const &dst,
+                           double cost, a_star_node *parent, 
std::set<gamemap::location> const *teleports)
 {
        isInCloseList = false;
        loc = pos;
@@ -46,128 +44,116 @@
        }
 }
 
-poss_a_star_node::poss_a_star_node(void) :
-capacity(0), curIndex(0)
+class a_star_world::poss_a_star_node
 {
-       nbElemByPage = size_t((4096 - 24) / sizeof(a_star_node));
-       wassert(nbElemByPage > 0);
-       addPage();
-       SingletonPOSS_AStarNode = this;
+private:
+       typedef std::vector<a_star_node*> vect_page_a_star_node;
+       vect_page_a_star_node vectPageAStarNode_;
+       size_t nbElemByPage_;
+       size_t capacity_;
+       size_t curIndex_;
+       void addPage();
+
+public:
+       poss_a_star_node();
+       ~poss_a_star_node();
+       a_star_node *getAStarNode();
+       void clear();
+};
+
+void a_star_world::poss_a_star_node::addPage()
+{
+       vectPageAStarNode_.push_back(new a_star_node[nbElemByPage_]);
+       capacity_ += nbElemByPage_;
 }
 
-void poss_a_star_node::addPage(void)
+a_star_world::poss_a_star_node::poss_a_star_node()
+       : capacity_(0), curIndex_(0)
 {
-       a_star_node* locPageAStarNode;
-
-       locPageAStarNode = new a_star_node[nbElemByPage];
-       vectPageAStarNode.push_back(locPageAStarNode);
-       capacity += nbElemByPage;
+       nbElemByPage_ = size_t((4096 - 24) / sizeof(a_star_node));
+       wassert(nbElemByPage_ > 0);
+       addPage();
 }
 
-a_star_node* poss_a_star_node::getAStarNode(void)
+a_star_world::poss_a_star_node::~poss_a_star_node()
 {
-       //----------------- PRE_CONDITIONS ------------------
-       wassert(capacity > 0);
-       wassert(curIndex <= capacity);
-       //---------------------------------------------------
-       a_star_node* locPageAStarNode;
-
-       if (curIndex == capacity)
-               addPage();
-
-       const size_t locIndexPage = curIndex / nbElemByPage;
-       const size_t locIndexInsidePage = curIndex % nbElemByPage;
-       ++curIndex;
-
-       assertParanoAstar(locIndexPage < vectPageAStarNode.size());
-       locPageAStarNode = vectPageAStarNode[locIndexPage];
-       assertParanoAstar(locIndexInsidePage < nbElemByPage);
-       return (&(locPageAStarNode[locIndexInsidePage]));
-}
-
-void poss_a_star_node::reduce(void)
-{
-       if (capacity > nbElemByPage)
-       {
-               for (vect_page_a_star_node::iterator iter = 
vectPageAStarNode.begin() + 1; iter != vectPageAStarNode.end(); ++iter)
-                       delete[] (*iter);
-               vectPageAStarNode.resize(1);
-               capacity = nbElemByPage;
-       }
-       curIndex = 0;
-       //----------------- POST_CONDITIONS -----------------
-       wassert(capacity == nbElemByPage);
-       wassert(vectPageAStarNode.size() == 1);
-       //---------------------------------------------------
+       for(vect_page_a_star_node::iterator iter = vectPageAStarNode_.begin(),
+                                           iend = vectPageAStarNode_.end();
+           iter != iend; ++iter)
+               delete[] *iter;
 }
 
-void a_star_world::resize_IFN(const size_t parWidth, const size_t parHeight)
+a_star_node *a_star_world::poss_a_star_node::getAStarNode()
 {
        //----------------- PRE_CONDITIONS ------------------
-       wassert(_nbNode == 0);
+       wassert(capacity_ > 0);
+       wassert(curIndex_ <= capacity_);
        //---------------------------------------------------
-       _width = parWidth;
-       if (_vectAStarNode.size() != parWidth * parHeight)
-       {
-               _vectAStarNode.reserve(parWidth * parHeight);
-               _vectAStarNode.resize(parWidth * parHeight);
-       }
+       if (curIndex_ == capacity_)
+               addPage();
+       size_t i = curIndex_++;
+       return &vectPageAStarNode_[i / nbElemByPage_][i % nbElemByPage_];
 }
 
-void a_star_world::clear(void)
+void a_star_world::poss_a_star_node::clear()
 {
-       if (_nbNode > 0)
-       {
-               a_star_node* locNode = NULL;
-               std::fill(_vectAStarNode.begin(), _vectAStarNode.end(), 
locNode);
-               _nbNode = 0;
+       if (capacity_ > nbElemByPage_) {
+               for(vect_page_a_star_node::iterator iter = 
vectPageAStarNode_.begin() + 1,
+                                                   iend = 
vectPageAStarNode_.end();
+                   iter != iend; ++iter)
+                       delete[] *iter;
+               vectPageAStarNode_.resize(1);
+               capacity_ = nbElemByPage_;
        }
+       curIndex_ = 0;
+       //----------------- POST_CONDITIONS -----------------
+       wassert(capacity_ == nbElemByPage_);
+       wassert(vectPageAStarNode_.size() == 1);
+       //---------------------------------------------------
 }
 
-bool a_star_world::empty(void)
+a_star_world::a_star_world()
+       : pool_(new poss_a_star_node), width_(0), nbNode_(0)
 {
-       return (_nbNode == 0);
 }
 
-bool a_star_world::reallyEmpty(void)
+a_star_world::~a_star_world()
 {
-       for (vect_a_star_node::iterator iter = _vectAStarNode.begin(); iter != 
_vectAStarNode.end(); ++iter)
-       {
-               if (*iter != NULL)
-                       return (false);
-       }
-       return (true);
+       delete pool_;
 }
 
-void a_star_world::erase(gamemap::location const &loc)
+void a_star_world::resize_IFN(size_t parWidth, size_t parHeight)
 {
        //----------------- PRE_CONDITIONS ------------------
-       wassert(loc.valid());
-       wassert(loc.x + (loc.y * _width) < _vectAStarNode.size());
+       wassert(nbNode_ == 0);
        //---------------------------------------------------
-       _vectAStarNode[loc.x + (loc.y * _width)] = NULL;
+       width_ = parWidth;
+       size_t sz = parWidth * parHeight;
+       if (vectAStarNode_.size() == sz)
+               return;
+       vectAStarNode_.reserve(sz);
+       vectAStarNode_.resize(sz);
+}
+
+void a_star_world::clear(void)
+{
+       a_star_node *locNode = NULL;
+       std::fill(vectAStarNode_.begin(), vectAStarNode_.end(), locNode);
+       nbNode_ = 0;
+       pool_->clear();
 }
 
-a_star_node* a_star_world::getNodeFromLocation(gamemap::location const &loc, 
bool& isCreated)
+a_star_node *a_star_world::getNodeFromLocation(gamemap::location const &loc, 
bool &isCreated)
 {
        //----------------- PRE_CONDITIONS ------------------
        wassert(loc.valid());
+       wassert(loc.x + loc.y * width_ < vectAStarNode_.size());
        //---------------------------------------------------
-       a_star_node*            node;
-       size_t                          index;
 
-       index = size_t(loc.x + (loc.y * _width));
-       assertParanoAstar(index < _vectAStarNode.size());
-       node = _vectAStarNode[index];
-       if (node == NULL)
-       {
-               isCreated = true;
-               wassert(SingletonPOSS_AStarNode != NULL);
-               node = SingletonPOSS_AStarNode->getAStarNode();
-               _vectAStarNode[index] = node;
-               ++_nbNode;
+       a_star_node *&node = vectAStarNode_[loc.x + loc.y * width_];
+       if ((isCreated = (node == NULL))) {
+               node = pool_->getAStarNode();
+               ++nbNode_;
        }
-       else
-               isCreated = false;
-       return (node);
+       return node;
 }
Index: wesnoth/src/astarnode.hpp
diff -u wesnoth/src/astarnode.hpp:1.4 wesnoth/src/astarnode.hpp:1.5
--- wesnoth/src/astarnode.hpp:1.4       Sun Jun  5 09:23:32 2005
+++ wesnoth/src/astarnode.hpp   Sun Jun  5 10:56:41 2005
@@ -1,6 +1,7 @@
-/* $Id: astarnode.hpp,v 1.4 2005/06/05 09:23:32 silene Exp $ */
+/* $Id: astarnode.hpp,v 1.5 2005/06/05 10:56:41 silene Exp $ */
 /*
 Copyright (C) 2003 by David White <address@hidden>
+Copyright (C) 2005 by Guillaume Melquiond <address@hidden>
 Part of the Battle for Wesnoth Project http://www.wesnoth.org/
 
 This program is free software; you can redistribute it and/or modify
@@ -19,12 +20,6 @@
 #include <set>
 #include <vector>
 
-#ifdef _PARANO_ASTAR_
-# define assertParanoAstar(param) assert(param)
-#else
-# define assertParanoAstar(param) {}
-#endif
-
 struct a_star_node
 {
 public:
@@ -42,41 +37,20 @@
        }
 };
 
-class poss_a_star_node
-{
-private:
-       typedef std::vector<a_star_node*> vect_page_a_star_node;
-
-       vect_page_a_star_node vectPageAStarNode;
-       size_t nbElemByPage;
-       size_t capacity;
-       size_t curIndex;
-
-public:
-       poss_a_star_node(void);
-       void addPage(void);
-       a_star_node* getAStarNode(void);
-       void reduce(void);
-};
-
 class a_star_world
 {
-protected:
+       class poss_a_star_node;
+       poss_a_star_node *pool_;
        typedef std::vector<a_star_node*> vect_a_star_node;
-
-       vect_a_star_node _vectAStarNode;
-       size_t _width;
+       vect_a_star_node vectAStarNode_;
+       size_t width_, nbNode_;
 
 public:
-       size_t _nbNode;
-
-       void resize_IFN(const size_t parWidth, const size_t parHeight);
-       void clear(void);
-       void erase(gamemap::location const &loc);
+       void resize_IFN(size_t parWidth, size_t parHeight);
+       void clear();
        a_star_node* getNodeFromLocation(gamemap::location const &loc, bool& 
isCreated);
-       bool empty(void);
-       bool reallyEmpty(void);
-       a_star_world(void) : _width(0), _nbNode(0) {};
+       a_star_world();
+       ~a_star_world();
 };
 
 #endif
Index: wesnoth/src/pathfind.cpp
diff -u wesnoth/src/pathfind.cpp:1.70 wesnoth/src/pathfind.cpp:1.71
--- wesnoth/src/pathfind.cpp:1.70       Sun Jun  5 09:32:26 2005
+++ wesnoth/src/pathfind.cpp    Sun Jun  5 10:56:41 2005
@@ -1,6 +1,7 @@
-/* $Id: pathfind.cpp,v 1.70 2005/06/05 09:32:26 silene Exp $ */
+/* $Id: pathfind.cpp,v 1.71 2005/06/05 10:56:41 silene Exp $ */
 /*
 Copyright (C) 2003 by David White <address@hidden>
+Copyright (C) 2005 by Guillaume Melquiond <address@hidden>
 Part of the Battle for Wesnoth Project http://www.wesnoth.org/
 
 This program is free software; you can redistribute it and/or modify
@@ -46,7 +47,6 @@
        bool locIsCreated;
 
        aStarGameWorld.resize_IFN(parWidth, parHeight);
-       wassert(aStarGameWorld.empty());
        a_star_node *locStartNode = aStarGameWorld.getNodeFromLocation(src, 
locIsCreated);
        wassert(locIsCreated);
        locStartNode->initNode(src, dst, 0.0, NULL, teleports);
@@ -152,7 +152,6 @@
        wassert(stop_at <= costCalculator->getNoPathValue());
        //---------------------------------------------------
        static a_star_world aStarGameWorld;
-       static poss_a_star_node POSS_AStarNode;
 
        vector_a_star_node openList;
        vector_location vectLocation;
@@ -213,7 +212,6 @@
 
 label_AStarSearch_end:
        openList.clear();
-       POSS_AStarNode.reduce();
        aStarGameWorld.clear();
        return locRoute;
 }