Deallocating memory from the first element of a link list

[Una]

Hello all,

Suppose that I have a hash table of pointers node * hash_table[100], and some elements in the hash table as in the following example:

hash_table[0] : 1 -> 4 -> 5
hash_table[1] -> NULL
hash_table[2]: -> 5
...

If I would like to delete the first element (node 1) from hash_table[0], it is done as following
hash_table[0] = hash_table[0]->next;

My question is how to we free memory previously taken by hash_table[0], and do we need to free it at all. This question might be stupid, but I m getting 'St9bad_alloc', and trying to determine its cause.

Thanx, Una

[Galik]

Something like this:

node* gone = hash_table[0];
hash_table[0] = hash_table[0]->next;
delete gone;

You need to make sure you initialise your array to zero before you use it;

for(int i = 0; i < 100; ++i)
{
	hash_table[i] = 0;
}

And you want to make sure you initialise all your node pointer members to zero:

class node
{
private:
	node* next;

public:
	node() : next(0) {}
};

[Una]

Thanx for your reply. I already did the sam thing, but I m still getting 'St9bad_alloc' :(

[Galik]

Can you post a little more of the code and the exact error message and what line it occurs on?

[Galik]

Actually your error looks like an allocation error, like you would expect of you didn't have enough memory to allocate for a new object.

Are you putting your hash_table on the stack rather than the heap?

You could try this:

struct node
{
	node* next;
	node() : next(0) {}
};

node** hash_table;

int main()
{
	hash_table = new node*[100];

	for(int i = 0; i < 100; ++i)
	{
		hash_table[i] = 0;
	}

	// ...

	node* gone = hash_table[0];
	hash_table[0] = hash_table[0]->next;
	delete gone;

	// ...


	return 0;
}

[Una]

Thanx once again for your prompt reply. As I m not I very good programmer, I dont know how to use the debugger to find out what is the cause of the error. That is why I dont know exactly which line is causing the following error

terminate called after throwing an instance of 'St9bad_alloc'
what(): std::bad_alloc
Aborted

As I have around 800 lines of codes, it is difficult to post all the code on this forum.

Una

[Una]

Actually, I declared the hash_table in the following way:

  struct gain_node
     {
        gain_node() : vertex(), previous(0), next(0) {}
        int vertex;
        gain_node *previous;
        gain_node *next;
     };
      gain_node * hash_table[15][2000];   

Might that be the reason why there is not enough memory to allocate?

Thanx, Una

[Galik]

It depends whether your definition appears within a function or in global space.

If your above declaration/definition appears within a function then it will be occupying a lot of memory on the stack. But it should be fine if its a global declaration/definition.

Can you try to narrow down where in the program the error is being thrown by putting in print statements to see how far the processing gets?

Also you can try to catch the exception as a way to narrow down what is causing it.

Like this:

try
{
	// .. call some functions
	// .. do some calculations
}
catch(std::exception& e)
{
	std::cout << e.what() << " at line " << __LINE__ << " in file " __FILE__ << std::endl;
}

You can try adding the try/catch block around parts of the code. Particularly parts that allocate memory by calling "new" as in:

hash_table[x][y] = new gain_node;

[Una]

Thanx a lot. You are a life saver :)

[Galik]

Oh, one other thought. Are you passing your array as a parameter to a function?

If you do, you need to pass it by reference or pointer, otherwise it will be very expensive on stack memory.

// If you have anything like this:

void func(gain_node* hash_table[15][2000])
{

}

// You might want to replace it with this:

void func(gain_node* (&hash_table)[15][2000])
{

}

// Or this

void func(gain_node*** hash_table)
{
	hash_table[2][4] = new gain_node;
}

[Una]

No. I defined the array as global variable to avoid passing it as parameter all the time.

[Galik]

Then maybe isolate the parts of the program where you allocate memory and present some of the surrounding code so that we can see what might be the trouble?

[chrisname]

Globals are evil.

[Una]

I really appreciate your help. It would be a lot easier if i knew how to use the debugging tool:(

[Galik]

I don't know what system you are running but there is a graphical dubugger called "ddd" that is reasonably easy to use:

http://www.gnu.org/software/ddd/

After you install it you runn it by typing:

> ddd progname

And it should let you just step through the program line by line.

But even so, putting print statements in the program should help you to narrow it down.

[Una]

I will try it. Thanx

[Una]

After inluding the try-catch statements as suggested by Galik, I found out the part causing std::bad_alloc is my delete function, which deletes a node from the 2D hash_table of pointers. Since the function is of reasonable size, I post it here for someone to take a look:)

 void delete_from_move_gain(int gain, int clust, int part)  //We would like to delete a node with value = clust
  {
     gain_node *temp = new gain_node;
     temp = gain_from_move[part][1000+gain]; //gain_from_move is the 2D_hash_table. 
                                                                        //The indexes to the hash_table are given as parameters.
     bool found = false; 
   
     while(!found and temp!=NULL)
     {
         if(temp->vertex==clust)
         {
            if(gain_from_move[part][1000 + gain]->vertex==clust and gain_from_move[part][1000 + gain]->next==NULL)
            {
               gain_from_move[part][1000 + gain] = NULL;
               delete temp;
            }else if(gain_from_move[part][1000 + gain]->vertex==clust and gain_from_move[part][1000 + gain]->next!=NULL)
            {
                gain_node * del = new gain_node;
                del = gain_from_move[part][1000 + gain];
                gain_from_move[part][1000 + gain] = gain_from_move[part][1000 + gain]->next;
                
                delete del;
             
            }else if(temp->next==NULL)
            {
                temp->previous->next = NULL;
                delete temp;
                
            }else if(temp->next!=NULL and temp->previous!=NULL)
            {
               temp->previous->next = temp->next;
               temp->next->previous = temp->previous; 
               delete temp;
            } 
            else cout<<"WEIRD CASE UNHANDLED"<<endl;
            found=true; break;
         } 
          temp=temp->next;
     } if(!found)     
        cout<<"This is not good"<<endl;   
  }

I think that the problem with this function is that it does not deallocate memory correctly. Many thanx in advance for any possible suggestions.

Una :)

[Galik]

Line 3 & 18 are both causing memory to leak.

You shouldn't create a new gain_node every time you create a pointer, because you don't use it, you assign a different gain_node to the pointer straight away.

So where you have:

gain_node *temp = new gain_node;
temp = gain_from_move[part][1000+gain];

You allocate some memory to temp and then immediately
overwrite it with a new value.

So you should really do this:

gain_node *temp = 0; // do not allocate anything here.
temp = gain_from_move[part][1000+gain];

You have this problem at lines 3 & 18 as far as I can see.

This could be causing the problem if it only happens after the
program has been running for a while. It will slowly eat memory
until there is no more left.

Try changing that and see if it fixes things.

[Una]

Galik, you are a genious. I can never tank you enough. I finally got rid of the allocation error. :D

100000 X Thanx, Una