# Dynamic Array trouble

This topic is 5032 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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;

return FALSE;

#ifdef WINHEAP

#ifndef _WIN64
if ( __active_heap == __V6_HEAP )
{
{
}
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?

##### Share on other sites
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 :)

##### Share on other sites
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.

##### Share on other sites
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).

##### Share on other sites
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?

##### Share on other sites
Thank you for mentioning Count Valid! I forgot to have the SwitchChild function set CountValid to false. Thank you!

##### Share on other sites
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.

1. 1
2. 2
3. 3
4. 4
Rutin
18
5. 5

• 12
• 12
• 9
• 12
• 37
• ### Forum Statistics

• Total Topics
631421
• Total Posts
2999997
×