Re: Linked List & Dynamic Memory Allocation

Well, you have a memory leak. That is, once you have allocated the memory, it is no
longer available for use except for the purpose it was allocated for. If you neglect to
call free, that storage will not be available any longer. There won;t be an immediate
disaster, but eventually your program will call malloc and will get NULL returned, because
there's no more memory available. Now, if you are actually *using* all that memory,
you've gone one problem, because it means your program needs more memory than is
available. But if you didn't need that memory any longer, but simply forgot to delete it,
then your program is considered erroneous.

You must call free() for every pointer you got via malloc().

Consider the following

for(int i = 0; i < 1000000; i++)
{ /* create a picture */
Picture * p = malloc(100000);
...fill in p->bitmap;
p->next = PictureList;
PictureList->next = p;
} /* create a picture */

Suppose you needed a million pictures. You'll probably run out of space. So you would
actually have to write
Picture * p = malloc(100000);
if(p == NULL)
{ /* out of picture space */
... report that you only had enough room for
... i pictures, and can't fill in any more
break;
} * out of picture space */
.. fill in p->bitmap;

This is a legitimate case where you may need more memory than actually is available.

However, this is a bug:

for(int i = 0; i < 100000; i++)
{
Thing * = (Thing *)malloc(sizeof(Thing));
... deal with error
... deal with Thing
ThingLIst->next = Thing;
}

Now, having created 100,000 Things, you do whatever you want to do with the list, then
come back and do

void ProcessThings()
{
Thing * ThingList;
ThingList->next = NULL;

for(...)
... the loop above...

...process all the things
return;
}

Now note what happened. The only reference to those 100,000 Thing objects is in that
local variable. You return from the function. All 100,000 Things remain allocated, and
there's no way to find out where they are! That storage is now lost forever (or for as
long as the program runs, until it exits).

So the correct approach is then to do

while(ThingList->next != NULL)
{ /* free them up */
Thing * nextthing = ThingList->next->next;
free(ThingList->next);
ThingList->next = nextthing;
} /* free them up */
return;

So you have to iterate down the list and free up each value. Now, note that you could NOT
write this as

while(ThingList->next != NULL)
{ /* buggy */
free(ThingList->next);
ThingList->next = ThingList->next->next;
} /* buggy */

Why? Because as soon as you do the free(), the storage occupied is now available for
allocation. So an attempt to use the pointer in the next statement is using storage that
has already been freed! (In the debug build, the debug runtime actually overwrites the
contents of the storage block on free(), thus destroying the pointer. In a multithreaded
app, just as you return from free, another thread might come in, do a malloc(), and
reallocate that storage for its own purposes, so by the time you get arround to using the
pointer you freed, the storage it points to has already been modified for another purpose
and is not available).

There are three serious errors you can make using dynamic allocation:
Failing to free storage you no longer need (storage leak)
Using a pointer to storage you have already freed (dangling pointer)
Freeing the same storage twice (double free)
The debug runtime looks for all three of these errors and reports them via assertion
failures in the library. The storage leak will be reported when the program exits.

Note that if you have something like

struct Thing {
Thing * next;
LPCTSTR name;
};

and you've done
Thing * p = (Thing *)malloc(sizeof(Thing));
p->name = (LPCTSTR)malloc(_tcslen(InputString) + 1);
_tcscpy(p->name, InputString);
... add Thing to list of Things

then
Thing * p = ...get a thing somehow
free(p);
will free the Thing, but *not* the string pointed to by p->name! So the way to free an
object is to do
free(p->name);
free(p);

Now this can be handled in C++ by destructors:

struct Thing {
Thing() { name = NULL; }
~Thing() { delete [] name; }
void AddName(LPCTSTR n) { delete [] name;
name = new TCHAR[_tcslen(n) + 1];
_tcscpy(name, n);
}
};


So you can write
Thing * p = new Thing;
... use it
p->AddName(InputName);
delete p;

and when you call delete, the storage you explicitly allocated will be freed when ~Thing
is called (note that you have to use new/delete on Things, rather than malloc/free)

Now note that objects like CString handle the implicit deallocation automatically, so if
you do
struct Thing {
Thing() {}
CString name;
void AddName(LPCTSTR n) { name = n; }
};

then when you do
Thing * t = new Thing;
t->AddName(InputString);
...
delete t;

The delete will call destructors on all the objects (but not pointers-to-objects) in the
class/struct, so the space pointed to by the CString is freed when ~CString is called. And
that's the whole point of C++ as far as storage management: you don't need to worry about
deallocating things that you set up to be automatically deallocated.

joe

On Tue, 28 Aug 2007 06:44:53 -0700, one-trick-pony <worldofpain.aamir@xxxxxxxxx> wrote:

Greetings,

I have everything working now. Thanks for your tips, suggestions and
guidance. I have better understanding of how programs relate to stack
and heap. I have created a singly linked list with dynamic memory
allocation enabled. Next task is doubly linked list but I've got a
good handle on that. One last question with this topic is, what
happens when memory allocated with malloc is not freed with free? I
am not seeing an immediate disaster when I deliberately leave out call
to free. And with every new record/item for which memory is allocated
do I need to call free( ) for every single memory allocation call or
just once? Thanks.
Joseph M. Newcomer [MVP]
email: newcomer@xxxxxxxxxxxx
Web: http://www.flounder.com
MVP Tips: http://www.flounder.com/mvp_tips.htm
.

Relevant Pages

  • Re: trying to make my "fillvalues" function work...
    ... void checkPtr_error(const char *location, const void *pointer) ... fprintf(stderr, "Memory allocation failure (%s). ...
    (comp.lang.c)
  • Re: Policy on rebooting?
    ... >> appropriate sizes of the pools statically was impossible. ... The problem is not the use of dynamic memory, ... so that the allocation can be ... If you can guarantee that only one pointer to a particular block is ...
    (comp.arch.embedded)
  • Re: various objects in my VB6 project - Calling IUnknown
    ... memory allocation and deallocation is half ... Doing something like this with a pointer would be a permanent leak in C++. ... Visual C++ has heap checking built ...
    (microsoft.public.vb.general.discussion)
  • Re: memory
    ... statement caused a corruption of the free memory pool or allocated ... allocation routines so I could have access to the free memory pool and ... removing your internal copy of the pointer as you do. ... Dig the even newer still, yet more improved, sig! ...
    (comp.lang.c)
  • Re: Vector and derived classes objects
    ... >> wont be called for the objects the pointer points to, hence I dont see ... > storage for that vector is grown. ... > succeed without throwing to tell you that you've run out of memory. ...
    (comp.lang.cpp)
Loading