Dynamic Array trouble

Started by
5 comments, last by iMalc 19 years, 7 months ago
Yes, I'm using a Dynamic Array, not STL. I thought that in this case the memory allocation and de-allocation is simple. It should be, but something is wrong and I don't know what. Here is the offending function:

void GPPopulation::CrossOver(GPTreeData &CrossOver1, GPTreeData &CrossOver2)
{
	GPNode* Tree[2]={CrossOver1.Tree,CrossOver2.Tree};
	if(Tree[0]==NULL || Tree[1]==NULL)
	{
		Mutate(CrossOver1);
		Mutate(CrossOver2);
		return;
	}

	unsigned Choice[2];

	{
		unsigned NumNodes[2];
		unsigned DataTypes[2];
		DataType* DataTypeArray[2];
		for(unsigned J=0; J<2; J++)
		{
			unsigned Temp=0;
			NumNodes[J]=Tree[J]->Count();
			DataTypeArray[J]=new DataType[NumNodes[J]];
			DataTypes[J]=Tree[J]->NodeDataTypes(DataTypeArray[J],Temp);
		}
		unsigned AllDataTypes=DataTypes[0]&DataTypes[1];

		Choice[0]=GetChoice(DataTypeArray[0], NumNodes[0], AllDataTypes);
		Choice[1]=GetChoice(DataTypeArray[1], NumNodes[1], DataTypeArray[0][Choice[0]]);
		for(unsigned K=0; K<2; K++)
			delete [] DataTypeArray[K];//<-------Here is the offending statement
	}

	GPNode* Nodes[2];
	GPNode* Parents[2];
	for(unsigned J=0; J<2; J++)
	{
		Nodes[J]=Tree[J]->Find(Choice[J]);
		Parents[J]=Nodes[J]->GetParent();
	}
	for(unsigned K=0; K<2; K++)
		Parents[K]->SwitchChild(Nodes[K],Nodes[(K+1)%2]);
}


As you can see, I clearly have used the delete operator for every new operator, and I clearly have used the new operator for every delete operator. But the debugger acts like I am trying to delete data that has already been deleted. And, yes, this I am trying out Genetic Programming, but my problem isn't AI related. Here are the functions that use DataTypeArray in them:

unsigned GPNode::NodeDataTypes(DataType* &DataTypeArray, unsigned &Index)
{
	unsigned Types=DataTypeArray[Index]=ReturnType;
	Index++;
	for(unsigned K=0; K<NumChildren; K++)
		Types|=Children[K]->NodeDataTypes(DataTypeArray,Index);
	return Types;
}



unsigned GPPopulation::GetChoice(DataType* DataTypeArray, unsigned ArrayLength, unsigned AcceptableDataTypes)
{
	unsigned NumAcceptable=0;
	for(unsigned J=0; J<ArrayLength; J++)
		if(DataTypeArray[J]&AcceptableDataTypes)
			NumAcceptable++;
	unsigned Choice=rand()%NumAcceptable;

	bool Found=false;
	unsigned Index=0;
	for(unsigned K=0; !Found; K++)
	{
		if(DataTypeArray[K]&AcceptableDataTypes)
		{
			if(Choice==Index)
			{
				Choice=K;
				Found=true;
			}
			Index++;
		}
	}
	return Choice;
}


Now, the weird thing is that I never get an error the first time around. But if any of the inputs into the cross-over function have been inputs into the function before, there will be an error (I think that's what's causing it anyway, but I'm not entirely sure). O.K. Here is some data on the error I get: Here is the Call Stack up to CrossOver() ntdll.dll!77f75554() ntdll.dll!77f9c106() ntdll.dll!77f82566() ntdll.dll!77f9c4fd() ntdll.dll!77f8beac() kernel32.dll!77e733fb() kernel32.dll!77e6c936() Genetic Programming.exe!_CrtIsValidHeapPointer(const void * pUserData=0x016320c0) Line 1807 C Genetic Programming.exe!_free_dbg(void * pUserData=0x016320c0, int nBlockUse=1) Line 1132 + 0x9 C Genetic Programming.exe!operator delete(void * pUserData=0x016320c0) Line 54 + 0x10 C++ Genetic Programming.exe!operator delete[](void * p=0x016320c0) Line 21 + 0x9 C++ Genetic Programming.exe!GPPopulation::CrossOver(GPPopulation::GPTreeData & CrossOver1={...}, GPPopulation::GPTreeData & CrossOver2={...}) Line 185 + 0x23 C++ The error brings the debugger to dbgheap.c:

_CRTIMP int __cdecl _CrtIsValidHeapPointer(
        const void * pUserData
        )
{
#ifndef WINHEAP
        int i;
        void * base;
#endif  /* WINHEAP */

        if (!pUserData)
            return FALSE;

        if (!_CrtIsValidPointer(pHdr(pUserData), sizeof(_CrtMemBlockHeader), FALSE))
            return FALSE;

#ifdef WINHEAP

#ifndef _WIN64
        if ( __active_heap == __V6_HEAP )
        {
            PHEADER     pHeader;
            if (pHeader = __sbh_find_block(pHdr(pUserData)))
            {
                return __sbh_verify_block(pHeader, pHdr(pUserData));
            }
            else if ( (_osver & 0x8000) != 0 )
                return TRUE;
            else
                return HeapValidate( _crtheap, 0, pHdr(pUserData) );
        }
#ifdef CRTDLL
        else if ( __active_heap == __V5_HEAP )
        {
            __old_sbh_region_t * preg;
            __old_sbh_page_t *   ppage;
            __old_page_map_t *   pmap;
            if ( (pmap = __old_sbh_find_block( pHdr(pUserData), &preg, &ppage )) !=
                 NULL )
            {
                if ( *pmap )
                    return TRUE;
                else
                    return FALSE;
            }
            else if ( (_osver & 0x8000) != 0 )
                return TRUE;
            else
                return HeapValidate( _crtheap, 0, pHdr(pUserData) );
        }
#endif  /* CRTDLL */
        else    //  __active_heap == _SYSTEM_HEAP
#endif  /* _WIN64 */
        {
            return HeapValidate( _crtheap, 0, pHdr(pUserData) );
        }

#else  /* WINHEAP */

        /*
         * Go through the heap regions and see if the pointer lies within one
         * of the regions of the local heap.
         *
         * Pointers from non-local heaps cannot be handled. For example, a
         * non-local pointer may come from a DLL that has the CRT linked-in.
         *
         */

        for (i = 0; (base = _heap_regions._regbase) != NULL &&
                i < _HEAP_REGIONMAX; i++)
        {
            if (pUserData >= base && pUserData <
                    (void *)(((char *)base)+_heap_regions._currsize))
                return TRUE;
        }

        return FALSE;

#endif  /* WINHEAP */
}


It points to the closing bracket at the end. Here is the Debug Output: HEAP[Genetic Programming.exe]: Heap block at 01632098 modified at 01635488 past requested size of 33e8 Unhandled exception at 0x77f75554 in Genetic Programming.exe: User breakpoint. That should be enough information, don't you think?
I am the master of ideas.....If only I could write them down...
Advertisement
Odds are you've got an array bounds overrun somewhere.

When you allocate your arrays in sequence, they often end up being adjacent in memory. Each array has a header which contains the number of array elements that were allocated, and possibly other things. This header is located right before the pointer that is returned by array-new.
      |HEADER|    USABLE BLOCK      |HEADER|    USABLE BLOCK      |              ^              pointer


If you do write past the end of one such array, you may trash the header of the array that is right behind it, which causes the program to blow up when you try to delete the damaged array (see _CrtIsValidHeapPointer).

      |HEADER|xxxxxxxxxxxxxxxxxxxxxx|xxxxER|    USABLE BLOCK      |


Note - the presence of that header is one of the differences between scalar-new and array-new. It is, of course, totally implementation-defined :)
"Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it." — Brian W. Kernighan
But that doesn't explain why I never get the error the first time through, but always get it the second. I'm also pretty sure that I don't go out of the bounds of the array. Here is my count function:
unsigned GPNode::Count(){	if(CountValid)		return ChildCount;	ChildCount=1;							// Set ChildCount to 1 to Count this Node	for(unsigned K=0; K<NumChildren; K++)	// For Each Child		ChildCount+=Children[K]->Count();	// Count Their Nodes	CountValid=true;	return ChildCount;}

If you can see a problem with it, please tell me.

Here is the Reproduce Function that calls CrossOver:
void GPPopulation::Reproduce(){	if(NumSorted<NumTrees)		SortTrees();	for(unsigned J=NumTrees-1; J>=Rate.ToCopy; J--)						//	The Copying and Elimination Loop	{																	// Eliminate the Worst Trees, by Shifting The Trees up by the Copying Amount		if(J<NumTrees-Rate.ToCopy)										// If The Current Tree has been shifted,			Trees[J].Tree=NULL;											// Set it to NULL so that it doesn't delete		Trees[J]=Trees[J-Rate.ToCopy];									// Shift the Trees	}																	// Finished Shifting	const unsigned NonMutat=Rate.ToCopy+Rate.ToCross;					// The Amount that is Reproduced not by Mutation	for(unsigned K=NumTrees-1; K>=NonMutat; K--)						//	The Mutation Loop	{																	// This Loop Replaces the Worst Trees that are left by the Mutated Trees		delete Trees[K].Tree;											// Delete The Old Tree		unsigned Random=rand()%(NumTrees-1);							// Choose a Random Number		if(Random>=K)													// If the Random Number is More Than or Equal To this,			Random++;													// Increment the Random Number		Trees[K].Tree=new GPNode(NULL,Trees[Random].Tree);				// The Random Numbe is the Index of the Tree that will be Mutated,		Mutate(Trees[K]);												// And Mutate That Tree	}																	// Finished Mutating	for(unsigned L=0; L<(Rate.ToCross/2); L++)							//	The Cross Over Loop		CrossOver(Trees[L+Rate.ToCopy],Trees[NonMutat-(L+1)]);			// Cross Over The Trees that Are to be Crossed Over	ResetFitness();	NumSorted=Rate.ToCopy;	GenerationNum++;}

The first time I call this function, everything goes fine. The second time I call it, it gives me the error. L is always a low number - somewhere below 5. When I fisrt wrote this function I had the loop that calls CrossOver like this:
for(unsigned L=Rate.ToCopy; L<Rate.ToCopy+(Rate.ToCross/2); L++)	CrossOver(Trees[L],Trees[NonMutat-(L+1)]);
Rate.ToCopy is 10
Rate.ToCross is 80
Rate.ToMutat is 10
When L reached 45, I would get an error, every time.
I am the master of ideas.....If only I could write them down...
You have an array of arrays DataTypeArray[K][Nk]. I believe you have an overrun on Nk for some k.

That kind of thing is just about the only thing I know of that will lead to an error in _CrtIsValidHeapPointer: in between the times when you created and destroyed the arrays, you have overwritten the memory management structures (or you have made your pointers point to some invalid memory location).

"Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it." — Brian W. Kernighan
In the nodedatatypes function you may end up overwriting memory. I dont know the rest of your source code but I checked the "Count" function and seems it does an additional check for CountValid something NodeDataTypes doesnt. So is it possible the NumChildren variable to force enough reentries to overwrite non-allocated memory?
Thank you for mentioning Count Valid! I forgot to have the SwitchChild function set CountValid to false. Thank you!
I am the master of ideas.....If only I could write them down...
assert(); is your friend!!!
Use of asserts picks up a lot of silly mistakes. Regardless of whether you've found the problem yet you should still make good use of asserts, and they may show up an error for you next time.

nice to see someone correctly using delete[] when appropriate for a change.
"In order to understand recursion, you must first understand recursion."
My website dedicated to sorting algorithms

This topic is closed to new replies.

Advertisement