Tree with multiple nodes + memory leak

[codey666]

I am trying to implement a search algorithm,it needs a tree with four(NOTE n=4) nodes.Is the struct declaration correct for array of structure pointers??You see the main idea is start with the 'cur' node.Then take a new 'temp' node. Copy the contents of 'cur->state' into 'temp->state' then perform the 'res' operation.The result of which is stored in the 'cur->action[i]' node for every 'n' iteration.I am getting a memory leak ,I can only do one iteration.The program terminates at the 'temp' declaration during the second iteration.Please help me am I missing something??I have allocated and freed 'temp' then why the memory leak??Please ignore the other parts.

void srch(void *states,int nstates,int *actions,const int n,void (*res)(void *,int),unsigned long int (*heuc)(void *),bool (*gl)(void *))
 {
    typedef  struct tree
      {
             void *state;
              tree *action[4];
      };
      tree *cur=new tree;

      for(int i=0;i<n;i++)
      {
         cur->action[i]=NULL;     

      }

      while(!(*gl)(cur->state))
     {
         int ph=0,max=0;

         for(int i=0;i<n;i++)
         {

           tree *temp=new tree;
           memcpy( temp->state,cur->state,sizeof(cur->state)*nstates);

           for(int k=0;k<n;k++)
             temp->action[k]=NULL;

           (*res)(temp->state,actions[i]);
           cur->action[i]=temp;
            memcpy(cur->action[i],temp,sizeof(tree*));
            delete[] temp;
         }

        cur= cur->action[max];                    
     }          
      delete[] cur;

 }      

[Ancient Dragon]

line 35: where is the array of curr->action ever set to anything other than NULL?

Where is the value of max set (line 35) ?

line 37: wrong delete. Since curr is not an array (see line 8) then that should be just delete curr; But that's not possible either because you changed the memory location to which curr originally pointer (line 35). You need another temporary pointer to hold the original address of curr that was set on line 8 so that it can be deleted on line 35.

If the action array is ever allocated new memory then you need to delete those too.

[mike_2000_17]

The memory leak is the least of your worries. This function is riddled with undefined behavior, memory leaks, heap corruption, memory corruption, and general mayhem. I'm surprised that it makes it as far as completing one iteration.

1) When you allocate a single object with the new, you need to delete it with delete, not with delete[]. This is because when you use delete[] (which is for deleting an array of objects) it will attempt to find the size (number of objects), which is not present when you allocated a single object, and therefore, it is generally going to read some undefined value for the size, and attempt to free that number of objects, which is going to cause a heap corruption, see here.

2) The use of the typedef in this local structure declaration:

typedef  struct tree
  {
         void *state;
          tree *action[4];
  };

is very antiquated C syntax. The correct way to do it in C++ (and in modern C) is as follows:

  struct tree
  {
      void *state;
      tree *action[4];
  };

3) You never initialize the state pointers within your tree nodes. When you create your new tree nodes, you (correctly) initialize all the action pointers to NULL, but you never initialize the state pointer to point to anywhere. This means that the state pointers point to some arbitrary (undefined) location in memory, and then, you perform memcpy operations on that. This is a memory corruption problem, see here. Consider this line:

memcpy( temp->state,cur->state,sizeof(cur->state)*nstates);

where you are taking memory which is nstates times the size of a pointer (why?), and copying it from some undefined memory location cur->state to some other undefined memory location temp->state. You are literally copying junk memory from arbitrary locations to arbitrary locations. There is no way that you could implement code that would do a better job at corrupting your program's memory.

4) You have weird stuff like this:

memcpy(cur->action[i],temp,sizeof(tree*));

which is incomprehensible, the size of a tree-pointer would have nothing to do with size of the memory that temp or cur->action[i] point to, and they happen to point to the same location, since you assign one to the other just one line above that, making this whole memcpy statement useless.

5) After you've assigned the temp pointer to the cur->action[i] pointer, you then delete the memory that that pointer points to, effectively making cur->action[i] a pointer to unallocated memory. This will, again, lead to either memory corruption (on the next access to that memory) or heap corruption (when you try to free that memory again).

And finally, I cannot comment on the logic of your code because (1) there are too many serious problems with it, making it incomprehensible, and (2) I have absolutely no idea what the functions like res or gl are supposed to do, nor to I have any idea what the overall function is supposed to accomplish. You need to provide better explanations, and you need to use longer and more meaningful names for your variables (as the saying goes for programming "typing is cheap, reading is expensive", in other words, invest in the typing of long meaningful names, it pays off by making things a lot clearer).

And another final note, I don't know who taught you to write code in this manner (using void* everywhere, and function pointers), but this is bad even by antiquated C coding standards. Whoever taught you this must be very old. And also, this is not standard C++ code (standard functions like memcpy reside in the std namespace, and need to be called with std::memcpy, not to mention that memcpy is not safe to use to copy C++ objects in general, you need to use std::copy instead, see here).

[codey666]

Thank you mike for ur amazing reply,yes I am a newbie. First of all what I am trying to implement is a heuristic depth first search for a sliding block puzzle problem.U see I am trying to implement the algorithm to be more generic.That is the exact reason why I am using void *state.In the current program it is an 4 by 4 matrix.I will post the whole code.I have seen implementation of functions using 'void *' in a libray implementation for linear algebra functions.I dint learn by the book I looked at code to teach myself.

#include <iostream>
#include <conio.h>
#define TRUE 1
#define FALSE 0
using namespace std;

void wrapper(void *ptr,int p[][4])
{
     int iptr[16];
     memcpy(iptr,ptr,16*sizeof(int));

     for(int i=0;i<4;i++)
     for(int j=0;j<4;j++)
     p[i][j]=iptr[4*i+j];



}
void wrapper2(void *ptr,int p[][4])
{
     int iptr[16];
     for(int i=0;i<4;i++)
     for(int j=0;j<4;j++)
     iptr[4*i+j]=p[i][j];
     memcpy(ptr,iptr,16*sizeof(int));

 }
bool goal(void *ptr)
{     int p[4][4];
      wrapper(ptr,p);
      bool g=TRUE;
     for(int i=0;i<4;i++)
     for(int j=0;j<4;j++)
     if(p[i][j]!=(4*i+j))
     g=FALSE;
     return(g);
}

void circ(int p[][4],int zx,int zy,int x,int y)
{


         if(!((zx+y)<0 || (zx+y)>3 || (zy+x)<0 || (zy+x)>3))
         {
           p[zx][zy]=p[zx+y][zy+x];
           p[zx+y][zy+x]=0;
         }
}
void result(void *ptr,int move)
{
     int p[4][4];
     wrapper(ptr,p);
     int zx=0,zy=0;
     for(int i=0;i<4;i++)
     for(int j=0;j<4;j++)
     if(p[i][j]==0)
     {
                   zx=i;zy=j;
     }
     switch(move)
     {
      case 1:circ(p,zx,zy,0,1);break;
      case 2:circ(p,zx,zy,0,-1);break;
      case 3:circ(p,zx,zy,1,0);break;
      case 4:circ(p,zx,zy,-1,0);break;
      default:cout<<"\n||Don't fuck with me!!!||\n";

      }          
     wrapper2(ptr,p);
 }
 void print(void *ptr)
 {
      int p[4][4];
      wrapper(ptr,p);
      cout<<"\n----------------------------------------------------------------------\n";
      for(int i=0;i<4;i++)
      {
      for(int j=0;j<4;j++)
       {
              cout<<"\t"<<p[i][j];
       }
              cout<<"\n";
       }
       cout<<"\n----------------------------------------------------------------------\n";
       wrapper2(ptr,p);
 }

 unsigned long int her(void *ptr)
 {
     int p[4][4];
     wrapper(ptr,p);     

     unsigned long int sum=0;
     for(int i=0;i<4;i++)
     for(int j=0;j<4;j++)

 sum+=abs(4*i+j-p[i][j]);

 return(sum);
}






 void srch(void *states,int nstates,int *actions,const int n,void (*res)(void *,int),unsigned long int (*heuc)(void *),bool (*gl)(void *))
 { 
    struct tree
      {
             void *state;
              tree *action[4];
      };

     tree *cur=new tree;

      cur->state=states;

      for(int i=0;i<n;i++)
      {
         cur->action[i]=NULL;     

      }

      while(!(*gl)(cur->state))
      {
         int ph=0,max=0;
         tree *temp;

         for(int i=0;i<n;i++)
         {

           cout<<"i="<<i; 
           temp=new tree;


        if(temp==NULL)
 {
 cout<<"NO MEM";
 }
           cout<<"Ä";           
          for(int k=0;k<n;k++)
          temp->action[k]=NULL;
          temp->state=new int;
    memcpy( temp->state,cur->state,sizeof(cur->state)*nstates);



      print(cur->state);
          (*res)(temp->state,actions[i]);
       cout<<"a="<<actions[i];    

          if( ph<(*heuc)(temp->state))
          {
             ph=(*heuc)(temp->state);
             max=i;
          }
             cout<<"\nC"<<max;


        cur->action[i]=temp;

        print((cur->action[i])->state); 

      delete temp;



         }

        cur= cur->action[max];                    
        cout<<"pppppppppppppppppppppp";        

          }          
      delete[] cur;

 }      

int main()
{
    int p[]={1,2,3,4,15,14,13,12,0,8,9,10,7,5,11,6},pp[4][4];


    int a[]={1,2,3,4};
    cout<<"Is it a goal="<<goal(p);


    srch(p,16,a,4,result,her,goal);
    cout<<her(p);
    print(p);
    cout<<"Is it a goal="<<goal(p);
    getch();
    return 0;
}

Please let me explain the supposed logic of the program.
1.The cur->state holds the pointer to the chunk of 4 by 4 integers used in sliding block puzzle which I here implement as a int[16] array.
2.There are 4 actions that can be done and the result of that action each results in new state.Hence cur->state has four tree* action[4] nodes each corresponding to the result of four actions.
3.Atleast one of the result action state is closer to the goal that the others.Its closeness to the goal is measured by the heuristic function that returns an integer.
4.So the node with the highest value of heuristic function is made as the current node.
5.So hopefully by repeatedly depth first searching the goal with the highest heuristics in every iteration we hope to reach the goal.

What I have implemented here according to me??
Since the function search is supposed to be generic I have taken measures to avoid any trace of my current problem( the sliding block puzzle) from entering the function.In an attempt I think I have screwed up the memory.
Let me explain the parameters
1.void *states - pass the first pointer location of the state.Here first location is first pointer of int[16] array.
2. int nstates - The size of the state array here 16.
3. int *actions- The array of actions that can be performed.
4. const int n - The number of actions possible here n=4.
5. void (*res)(void *,int)- This is a 'result fuction'.Result of an action on a state. This was supposed to be as 'result(state,action)'.So I have supposedely generalised by using void * for state and int for action and the result would be reflected in the change that was made to the void * state.
5. unsigned long int (*heuc)(void *) - This is the 'heuristic function' and
supposed to be like heuristic(state).Returns a uint number based on closeness to the goal.
6. bool (*gl)(void *) - Is supposed to be 'isgoal(state)'.Returns TRUE if its the goal state else 0.

So as u can see I have first constructed the tree with four node and a state.
I first tried to do tree action[n] but I couldn't.
1.First intialise the cur->state to intial configurations and cur->action[] to NULL.
2.Then while(its not a goal)
Repeat
1.Set a temp->node initialise temp->node to NULL.But I dont know how to initialise temp->state.Please help.
2.Perform 'result(cur->state,action)' store the resulting state in 'temp->state' and find the heurisitic variable and make max= largest action in the iteration till now.
3.Then put cur->action[i]=temp.Then delete temp.
Since (cur->action[i])->state shows up the correct state I thought there is no problem with initialisation of temp->state.
4.After the iterations are over max contains the state/node with the largest heuristic so now we set cur->state=cur->action[max].
5.Do this till we hit the goal state.

What corrections have I tried???
1.First of all,I switched to delete from delete[]
2.Secondly I removed the typedef.
3.Now regarding initialising temp->state.U see if I try to initialise temp->state=cur->state. Then do the memcpy it points to the cur->state by reference and on every iteration cur->state will point to the same location
on every iteration resulting in overwriting of the previous states.I tried temp->state = new int and temp->state=new int* but both gave the same results.
4.I have removed the redundant line
4.Yes exactly what I thought,I assign cur->actions[i]=temp then I delete temp.I thought maybe it releases temp from pointing to that memory.How am I to free temp then for the next iteration??Also even after removing delete temp it gives the same result.
Basically I am not from CS background.I am the kind of person who would learn by trying on their own.I am trying to get into 'Programming in AI and Robotics'.So I just read the theory behind search such as A-star etc....I resist any attempt to look into actual C++ implementation and test what I have learnt by programming them myself and get into mess trying to implement them as you can see above.Please help me.I am terribly in need of help.Hoping to hear advise from experts like you!!!