Re: What Kind of DataStructures C using? ( Heap or Tree ??)

From: Boris Glawe (boris_at_boris-glawe.de)
Date: 10/08/04 

Date: Fri, 08 Oct 2004 13:25:32 +0200

gold wrote:
> Hello all,
>
> I want know abt wht kind of datastructures using both C & C++ internally.
> Some were said heap, others said tree
>
> anyone can explain brief?
>
>

Your question is senseless. The "opposite" of a heap is a stack.

if you call a function in a C program (you call at least the main function) all
instructions and data is put on a stack. This stack is then processed from the
top to the bottom by the CPU. After having processed all instructions of the
function, the stack is deleted again.

There's one exception: the call of malloc (C) or new (C++). malloc and new
reserve memory on the heap (which is a different memory area then the stack) and
return a pointer to this memory area.

now watch this example:

void func(){

        char *ptr = (char*)malloc(sizeof(char));

}

I told you, that all data and instructions are put on the stack. The pointer
*ptr is such data, thus it's put on the stack, but the data the pointer is
pointing to, is on the heap (because it's reserved by malloc).
As soon as the function returns, the stack will be deleted - including the
pointer, but the memory on the heap will still be there. With the deletion of
the pointer you've lost the information where this data is stored. This is
called a memory leak.

There are two things, you have to do:

1. delete the reserved memory:

void func(){

        char *ptr = (char*)malloc(sizeof(char));

        //... do something

        free (ptr);
}

2. if you still need the data structure, which is on the heap, after the
function has returned, return the pointer to this datastructure:
char* func(){

        char *ptr = (char*)malloc(sizeof(char));

        //... do something

        return ptr:
}
Don't forget to delete the data, as soon as don't need it any more outside the
function.

The advantage of programming with malloc and new is that you have your data
structues on the heap and you're just passing around pointers. This is great for
performance. It's also an advantage for semantic reasons, because a pointer
represents an object.

The disadvantage is the risk for memory leaks, if you forget the delelte the
reserved memory before the last pointer to this memory is deleted.

greets Boris

Relevant Pages

  • Re: run-time vs compile-time
    ... > offset related to some location (like stack base) somewhere. ... > offset from heap to pi. ... When you allocate an int on the heap, it is allocated at address 1. ... application has a given amount of memory it can use as it wishes. ...
    (alt.comp.lang.learn.c-cpp)
  • Re: run-time vs compile-time
    ... > offset related to some location (like stack base) somewhere. ... > offset from heap to pi. ... When you allocate an int on the heap, it is allocated at address 1. ... application has a given amount of memory it can use as it wishes. ...
    (comp.lang.cpp)
  • Re: Error Raising and Memory in VB (general question)
    ... > object is terminated go out of scope, and the memory is also released. ... But why are you saying it uses stack? ... I think we are dealing with heap memory here. ... "COM's IMalloc allocator: ...
    (microsoft.public.vb.general.discussion)
  • Re: ptrs validity
    ... I have a pointer that points to an unknown heap memory block, ... hardware checked segment for each allocation. ...
    (comp.lang.c)
  • Re: Stack, Heap, Mfc
    ... >> is put on the heap. ... >> decendant does this not mean that all memory will be on the heap because ... > stack or the heap. ... You first try to limit the recursion to an acceptable ...
    (microsoft.public.vc.mfc)