By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
449,018 Members | 884 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 449,018 IT Pros & Developers. It's quick & easy.

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

P: n/a
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?
Nov 14 '05 #1
Share this Question
Share on Google+
9 Replies


P: n/a
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
Nov 14 '05 #2

P: n/a
In article <ck**********@newsreader2.netcologne.de>,
Boris Glawe <bo***@boris-glawe.de> wrote:
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.


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.
Nov 14 '05 #3

P: n/a
Boris Glawe wrote:
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.


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.

--
Chris "electric hedgehog" Dollin
C FAQs at: http://www.faqs.org/faqs/by-newsgrou...mp.lang.c.html
C welcome: http://www.angelfire.com/ms3/bchambl...me_to_clc.html
Nov 14 '05 #4

P: n/a
John Cochran wrote:
In article <ck**********@newsreader2.netcologne.de>,
Boris Glawe <bo***@boris-glawe.de> wrote:
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.

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>

--
Er*********@sun.com

Nov 14 '05 #5

P: n/a
In article <ck**********@smof.fiawol.org>,
John Cochran <jd*@smof.fiawol.org> wrote:
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

--
Dave Vandervies dj******@csclub.uwaterloo.ca
Acme Klein Bottles are made on a planet rich in silicon dioxide -- we never
clearcut rainforests, stripmine Kentucky towns, or smash oil tankers into
arctic shores. -http://www.kleinbottle.com/why_acme.htm
Nov 14 '05 #6

P: n/a

In article <ck**********@news1brm.Central.Sun.COM>, Eric Sosman <er*********@sun.com> writes:
John Cochran wrote:
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.


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.

--
Michael Wojcik mi************@microfocus.com

Recently, they appeared at the reopening of the Brookdale Library,
luring passersby with the opportunity to be anonymously silly.
Nov 14 '05 #7

P: n/a
Chris Dollin wrote:
Boris Glawe wrote:

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.


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
Nov 14 '05 #8

P: n/a
dj******@csclub.uwaterloo.ca (Dave Vandervies) writes:
In article <ck**********@smof.fiawol.org>,
John Cochran <jd*@smof.fiawol.org> wrote:
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.


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.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
Nov 14 '05 #9

P: n/a
Boris Glawe wrote:
gold wrote:

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.


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.

--
Chuck F (cb********@yahoo.com) (cb********@worldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!
Nov 14 '05 #10

This discussion thread is closed

Replies have been disabled for this discussion.