Sign in to follow this  

Dynamic Array trouble

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

If you intended to correct an error in the post then please contact us.

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;

        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[i]._regbase) != NULL &&
                i < _HEAP_REGIONMAX; i++)
        {
            if (pUserData >= base && pUserData <
                    (void *)(((char *)base)+_heap_regions[i]._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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites

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

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this