Block type is valid(pHead->nBlockUse)

witam,
mam problem z troche rozległym kodem, ale zdaje mi się, że wiem gdzie leży błąd tylko nie wiem jak go rozwiązać :
mam funkcję która wykonuje algorytm a* - w miejscu zaznaczonym komentarzem wystepuje właśnie Block Type Is Valid :

 std::list<MapSearchNode> findPath(MapSearchNode a, MapSearchNode goalNode)
{
	MapSearchNode final;
	bool goalFound = false;

	std::list<MapSearchNode> closedList;
	std::list<MapSearchNode> openList;

	std::list<MapSearchNode *> listToDelete;

	std::list<MapSearchNode>::iterator openListIterator;
	std::list<MapSearchNode>::iterator openListIteratorToErase;

	a.g = 0;
	a.h = a.GoalDistanceEstimate(goalNode);

	openList.push_back(a);

	MapSearchNode B;

	while(!openList.empty())
	{
		//find node with minimum f value on the openList
		/*MapSearchNode*/ B = *openList.begin(); // B as best node

		if( (int) openList.size() == 1 )	
			openListIteratorToErase = openList.begin();
		else
		{
			for(openListIterator = openList.begin()  ;  ;  )
			{
				if(openListIterator->g + openListIterator->h < B.g + B.h) 
				{
					B = *openListIterator;
					openListIteratorToErase = openListIterator;
				}

				if(openListIterator == --openList.end() )
					break;

				if(openListIterator->x != (--openList.end())->x  &&  openListIterator->y != (--openList.end())->y )
					openListIterator++;
			}
		}

		//remove B from openList and add it to closedList
		if(B.IsContainedIn(openList))
			openList.erase(openListIteratorToErase);
		closedList.push_back(B);

		float tentGscore = 99999;
			for(int i = 0; i < 8 ; ++i)// CHECK EACH NEIGHBOUR OF B - NODE WITH LOWEST F VALUE FROM OPENLIST-------------
			{
					MapSearchNode *thisNeighbour = new MapSearchNode;
					*thisNeighbour = GiveNeighbour(B, i);

					listToDelete.push_back(thisNeighbour);

/* ----->>> !!  */        if(  (thisNeighbour->IsContainedIn(closedList)) || (GetMap(*thisNeighbour) == 9 /*not traversible*/))
				{
					//delete thisNeighbour;
					continue;
				}
				tentGscore = B.g + ( i%2 ? 1.0 : 1.4 );

				if(	!(thisNeighbour->IsContainedIn(openList)) ) 
				{
					thisNeighbour->g = tentGscore;
					thisNeighbour->h = thisNeighbour->GoalDistanceEstimate(goalNode);

					thisNeighbour->parent = &B;

					openList.push_back( *thisNeighbour ); // add it to openList
				}
				else 
				{																		
					for(std::list<MapSearchNode>::iterator iter = openList.begin(); iter != openList.end(); iter++)
					{
						if(iter->x == thisNeighbour->x && iter->y == thisNeighbour->y )
						{
							openList.erase(iter);
							break;
						}
					}
					thisNeighbour->g = tentGscore;
					thisNeighbour->h = thisNeighbour->GoalDistanceEstimate(goalNode);

					thisNeighbour->parent = &B;
					openList.push_back( *thisNeighbour ); // add it to openList
				}

				if(thisNeighbour->IsGoal(goalNode))
				{
					goalFound = true;

					thisNeighbour->parent = &B;

					final = *thisNeighbour;
					break;
				}
			}
			if(goalFound)
				break;
	}

	// construct the route from back to front 
	std::list<MapSearchNode> toReturn;
	MapSearchNode temp;
	while( final.parent != NULL)
	{
		toReturn.push_front(final);

		temp = final;
		final = *final.parent;
		delete &temp;
	}
	for(std::list<MapSearchNode *>::iterator delIter = listToDelete.begin() ; delIter != listToDelete.end(); delIter++)
	{
		delete &delIter;
	}

	return toReturn;
}

funkcja is contained in wygląda natomiast tak:

bool MapSearchNode::IsContainedIn( std::list<MapSearchNode> listToLookIn)
{
	if(listToLookIn.empty())
		return false;
	else if(( listToLookIn.size() == 1 ) && (listToLookIn.begin()->x == this->x) && (listToLookIn.begin()->y == this->y))
		return true;
	for(std::list<MapSearchNode>::iterator myIterator = listToLookIn.begin(); myIterator != listToLookIn.end(); myIterator++)
	{
		if( (this->x == myIterator->x) && (this->y == myIterator->y) )
			return true;
	}

	return false;
} 

przy debugowaniu okzauje się że program przechodzi przez funkcję isContainedIn dochodzi do return false i potem wystepuje błąd.
jakieś wskazówki ?

MapSearchNode temp;
while( final.parent != NULL)
{
        ...
        delete &temp; //<--- wtf?!
}

for(std::list<MapSearchNode*>::iterator delIter; ...)
{
        delete &delIter; //<--- wtf?!
}

Jeśli klasa MapSearchNode ma jakieś pola, które są wskaźnikami (lub istnieje ryzyko pośredniego kopiowania wskaźników), powinna mieć odpowiednio zdefiniowany operator przypisania i konstruktor kopiujący.

dzięki za odpowiedź i sorry, że tak długo mi zajęło odpisanie.
Po pierwsze czy mógłbyś trochę wytłumaczyć pośrednie kopiowanie wskaźników bo nie za bardzo potrafię znaleźć coś o tym w sieci.
Po drugie trochę mi się pomyliło z tym zwalnianiem pamięci :

delete &temp; 

ale to nie zmienia faktu, że dostaję dalej ten sam błąd po wyjściu z funkcji isContainedIn()
a klasa MapSearchNode wygląda tak :

class MapSearchNode
{
	public:
	  unsigned int x;  // the (x,y) positions of the node
	  unsigned int y;
	  unsigned int cost;

	  float g;  // cost to curent node
	  float h;  // heuristic to the goal
	  // f = g + h

	  MapSearchNode *parent;

	  MapSearchNode() { parentx = parenty = -1; x = y = 0; g = h = 999999 ; parent = NULL; cost = 1; }
	  MapSearchNode( unsigned int px, unsigned int py );
	  ~MapSearchNode() { delete parent;}

	  float GoalDistanceEstimate( MapSearchNode &nodeGoal );
	  bool IsGoal( MapSearchNode &nodeGoal );
	  float GetCost( MapSearchNode &successor );
	  bool IsSameState( MapSearchNode &rhs );

	  bool IsContainedIn( std::list<MapSearchNode> listToLookIn);

	  std::list<MapSearchNode> findPath(MapSearchNode a, MapSearchNode goalNode);

	  void SetG(float g);
	  void SetH(float h);
	  void SetParent(MapSearchNode * parent);

	  void PrintNodeInfo();
}; 

czy mógłbyś trochę wytłumaczyć pośrednie kopiowanie wskaźników

Chodziło mi o to, czy nie ma tam np. jakiegoś kontenera, który przetrzymuje wskaźniki.

a klasa MapSearchNode wygląda tak :

No, moje podejrzenia były uzasadnione:

class MapSearchNode
{
	...

	MapSearchNode *parent; //<--- !!!

	...
	
	~MapSearchNode() 
	{ 
		delete parent; //<--- !!!
	}
};




std::list<MapSearchNode> closedList;

...

MapSearchNode B;

...
 
B = *openList.begin(); //<--- kopiujesz

...

 closedList.push_back(B); //<--- kopiujesz

 ...
 
 thisNeighbour->IsContainedIn(closedList)) //<--- przekazujesz przez wartość, kopiujesz

... w efekcie zostanie kilkukrotnie usunięty obiekt wskazywany przez parent, o ile coś tam do niego zostało przypisane.

no rozumiem, ale za bardzo nie potrafię za bardzo wymyślić jakiegoś rozwiązania . Jedyne co przychodzi mi na myśl to zawsze przekazywać przez wskaźniki albo referencje a jaki może być inny ? (i podejrzewam, że lepszy )

Pytanie, czy MapSearchNode powinien być odpowiedzialny za usunięcie parenta? Według mnie nie, ale to Twój^(?) kod, powinieneś wiedzieć lepiej. Jeśli chodzi o wskaźniki i referencje, to tak, użyj ich. Zrób jeszcze coś takiego:

class MapSearchNode
{
private:
	MapSearchNode(const MapSearchNode&);
	MapSearchNode& operator=(const MapSearchNode&);
	
	...

to uchroni Cię przed przekazywaniem przez wartość.

ok, więc zdecydowałem, że chyba lepiej będzie jak zrobię to trochę inaczej, bo gdy każdy MapSearchNode będzie miał parenta, to powstaje wtedy o wiele więcej instancji MapSearchNode niż de facto potrzebuję.
Zdecydowałem zrobić swego rodzaju mapę z MapSearchNode'ami i każda instancja MapSearchNode będzie miała wskaźnik, który wskazuje na 'miejsce' na mapie.

tylko teraz jak zabrać się za zwalnianie pamięci jeżeli kilka MapSearchNode'ów może mieć tego samaego rodzica ?

btw:
czy tak mogą wyglądać operatory przypisania i kopiujący zakładając, że pamięć zwolnię na sam koniec funkcji znajdującej drogę więc tutaj nie muszę się o to martwić :

MapSearchNode::MapSearchNode(const MapSearchNode& that)
{
	this->g = that.g;
	this->h = that.h;
	this->cost = that.cost;
	this->x = that.x;
	this->y = that.y;
	this->parent = new MapSearchNode( GetNode(that.parent) );

	return *this;
}

MapSearchNode& MapSearchNode::operator=(const MapSearchNode& that)
{
	if(this != &other)
	{
		this->g = that.g;
		this->h = that.h;
		this->cost = that.cost;
		this->x = that.x;
		this->y = that.y;

		this->parent = new MapSearchNode( GetNode(that.parent) );
		delete that.parent;
	}
	return *this;
}

 MapSearchNode * GetNode(MapSearchNode * node)
{
	return &nodeMap[(node->y*MAP_WIDTH)+node->x];
}

tylko teraz jak zabrać się za zwalnianie pamięci jeżeli kilka MapSearchNode'ów może mieć tego samaego rodzica ?

Opcje są dwie:
*nie zwalniać - usuwanie odbywa się w sposób jawny z zewnątrz.
*użyć inteligentnego wskaźnika, który zlicza referencje (boost::shared_ptr lub jakaś własna implementacja - na dobrą sprawę MapSearchNode może mieć metody AddRef i Release).

czy tak mogą wyglądać operatory przypisania i kopiujący (...)

Nie wiem, dlaczego ta linia tak wygląda:

this->parent = new MapSearchNode( GetNode(that.parent) ); // masz tu błąd. GetNode zwraca wskaźnik. 

a nie chociażby tak:

this->parent = new MapSearchNode(*that.parent);

Choć nie wydaje mi się, żeby oba rozwiązania były dobre. Zrób tak, jak napisałem wcześniej.

MapSearchNode& MapSearchNode::operator=(const MapSearchNode& that)
{
	...
	delete that.parent; //<--- WTF?!
	...
}

MapSearchNode& MapSearchNode::operator=(const MapSearchNode& that)
{
	...
	delete that.parent; //<--- WTF?!
	...
}

to akurat było wykomentowane nie wiem dlaczego w takiej formie to tutaj wysłałem. ( to jeszcze było z innej wersji bo cały czas zmieniam jakby podejście do parent'a

mam teraz jeden jedyny problem ze zwolnieniem pamięci, a mianowicie :
zmieniłem większość kodu tak aby nie było tam żadnych wskaźników ( MapSearchNode zamiast wskaźnika ma zmienne parent'a jako int'y ) ale jeden jedyny problem leży tutaj

	std::list<MapSearchNode> toReturn;
	MapSearchNode * temp = new MapSearchNode;
	temp = GetNode( & goalNode );

	while( (temp->x != a.x) || (temp->y != a.y) )
	{
		toReturn.push_front( *temp);
		temp = GetNode( temp->parentx, temp->parenty );

	}

	delete temp; //   <<--------- !!
	return toReturn; 

jeżeli zostawię to tak jak jest to dostaję błąd jak na samym początku " Block type is valid .... " a jak wykomentuję delete temp; to wtedy wsyzskto działa ale jakby nie patrzeć zostaje nieporządek w pamięci.
czy coś robię źle ? otrzymuję już wszystkie wartości tka jak chciałem.

MapSearchNode * temp = new MapSearchNode;
temp = GetNode( & goalNode ); //<--- !!!

...

delete temp; 

To przypisanie powoduje wyciek (patrz linia wyżej), to po pierwsze. Po drugie, z tego co widzę, GeNode zwraca wskaźnik na element tablicy nodeMap, zatem nie możesz zwolnić pamięci spod tego wskaźnika w ten sposób.

0x666 napisał(a)

MapSearchNode * temp = new MapSearchNode;
temp = GetNode( & goalNode ); //<--- !!!

...

delete temp; 

To przypisanie powoduje wyciek (patrz linia wyżej), to po pierwsze.

mógłbyś wytłumaczyć dlaczego to przypisanie powoduje wyciek ?

0x666 napisał(a)

Po drugie, z tego co widzę, GeNode zwraca wskaźnik na element tablicy nodeMap, zatem nie możesz zwolnić pamięci spod tego wskaźnika w ten sposób.

nie za bardzo to rozumiem - mogłbym pomyśleć, żeby w ogóle nie zwalniać temp'a ale to nie jest raczej najlepszy pomysł.

MapSearchNode * temp = new MapSearchNode; // tworzysz na stercie nowy obiekt, jego adres przypisujesz 'temp'
temp = GetNode( & goalNode ); //przypisujesz inny wskaźnik, zwrócony przez 'GetNode', gubiąc ten wcześniejszy. I ta zguba to Twój wyciek.
 

mogłbym pomyśleć, żeby w ogóle nie zwalniać temp'a (...)

No, mógłbyś ;)

A tak:

MapSearchNode* temp = GetNode( &goalNode );

while( (temp->x != a.x) || (temp->y != a.y) )
{
	toReturn.push_front(*temp);
	temp = GetNode( temp->parentx, temp->parenty );
}

return toReturn; 

nie wystarczy?

ok wystarczy jak najbardziej ;) dzięki