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

G

gold

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?
 
B

Boris Glawe

gold said:
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
 
J

John Cochran

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.

I agree that the OP's question is senseless. But your answer also leaves
a lot to be desired. C does not mandate the use of a stack for call
processing. In fact, not all computers have a stack (take at look at the
IBM 360/370/390 architecture). For those computers that don't have a stack,
the proper call/return nesting can be done by using a linked list of
blocks of memory where each block contains the linkage information to
handle the return as well as storage for local variables.
 
C

Chris Dollin

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

As well say "the opposite of a heap is a queue", or "the opposite
of sunlight is an open door".
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.

Well, um, no.

(a) C makes no mention of a "stack", nor indeed of a "heap". There is
no requirement that a C implementation uses either, although a stack
is a natural match to the function-call requirements it *does* impose.

(b) In no C implementation that I've ever heard of does a function call
put any instructions on a stack.

(c) In many C implementations - including ones I've used - arguments
to the function are passed *in registers*, where convenient, and
further, the called function may consume *no* stack, where possible,
eg in the case of simple leaf functions.
This stack is then
processed from the top to the bottom by the CPU.

Well, no, again. Even when arguments are passed on a stack (usually
"the" stack, ie, the same one is used for all function calls), there's
no necessity for that stack to be processed from top to bottom. (If
that makes it not a "proper" or "pure" stack, so be it.)
There's one exception: the call of malloc (C) or new (C++). malloc and new
reserve memory on the heap

If by "heap" we mean "that area of memory managed by malloc", yes.
 
D

Dave Vandervies

John Cochran said:
C does not mandate the use of a stack for call
processing.

Perhaps not in so many words, but it does require something that looks,
feels, and smells like a stack.
In fact, not all computers have a stack (take at look at the
IBM 360/370/390 architecture). For those computers that don't have a stack,
the proper call/return nesting can be done by using a linked list of
blocks of memory where each block contains the linkage information to
handle the return as well as storage for local variables.

....and, once you've started pushing a link onto the list when you enter
a function and popping a link off of the list when you leave a function,
this starts looking suspiciously like a linked-list implementation of
a stack.


dave
 
E

Eric Sosman

John said:
I agree that the OP's question is senseless. But your answer also leaves
a lot to be desired. C does not mandate the use of a stack for call
processing. In fact, not all computers have a stack (take at look at the
IBM 360/370/390 architecture). For those computers that don't have a stack,
the proper call/return nesting can be done by using a linked list of
blocks of memory where each block contains the linkage information to
handle the return as well as storage for local variables.

<topicality level="marginal">

Um, er, why doesn't the linked list you describe
qualify as a "stack?" You can push things onto it and
pop them off again in LIFO order -- that's a "stack" as
far as I can see, even if it doesn't happen to use
sequential allocation.

</topicality>
 
M

Michael Wojcik

Um, er, why doesn't the linked list you describe
qualify as a "stack?" You can push things onto it and
pop them off again in LIFO order -- that's a "stack" as
far as I can see, even if it doesn't happen to use
sequential allocation.

Sure, if you define "stack" as any data structure accessed in LIFO
order, then it's a stack. Many people, however, define "stack" as a
contiguous area with LIFO access in various contexts, and claiming
that C uses a stack is one of those. John's comment is perfectly
reasonable in that context.

A C implementation could use activation records and provide an
extension whereby they could be used in non-LIFO order (by adding
continuations to the language, for example). A program that did not
use that extension, and was entirely a conforming C program, would
still be using a C implementation that did not have a stack, even
though it happened to be using a data structure in a stack-like
manner.
 
D

Default User

Chris said:
Boris Glawe wrote:

If by "heap" we mean "that area of memory managed by malloc", yes.

I kind of like the C++ terminology "free store" they use when refering
to this storage. It gives you a specific term for it, without being too
detailed.




Brian Rodenborn
 
K

Keith Thompson

Perhaps not in so many words, but it does require something that looks,
feels, and smells like a stack.

We're using two different meanings of the word "stack".

A hardware stack is a contiguous chunk of memory with a pointer to the
"top" of it; typically the top-of-stack pointer is a hardware
register, and the CPU provides instructions to manipulate it.

The term "stack" is also used to refer to an abstract data structure
that allows items to be stored and retrieved in a last-in first-out
manner. It may also allow access to items below the top of the stack.

C's function-call semantics require some kind of stack data structure.
(If C didn't allow recursive calls, it could probably be implemented
without a stack.) The abstract stack may or may be implemented as a
hardware stack.

Perhaps understanding this distinction can avoid yet another "yes it
does"/"no it doesn't" argument that's really about the definition of a
word.
 
C

CBFalconer

Boris said:
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.

Your answer is meaningless in C. There is no stack defined. Some
implementations may use a stack for various purposes, including
allocation of automatic storage.

All there is are certain characteristics of the various forms of
storage, as defined in the C standard. You can count on nothing
more.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,482
Members
44,900
Latest member
Nell636132

Latest Threads

Top