468,457 Members | 1,654 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 468,457 developers. It's quick & easy.

traversing a stack

We kno that data can be pushed onto the stack or popped 4m it. Can
stack be traversed ??
Dec 1 '07 #1
30 3842
asit wrote:
We kno that data can be pushed onto the stack or popped 4m it. Can
stack be traversed ??
C3rt41n1y.

Dec 1 '07 #2
asit wrote, On 01/12/07 15:01:
We kno that data can be pushed onto the stack or popped 4m it.
Do we? Which stack would that be anyway? The return address stack built
in to the processor or a stack implemented using one of the normal index
registers? Or possibly a stack implemented as a data structure in C?
Can
stack be traversed ??
If your C implementation uses a stack for auto variables and/or return
addresses (which not all do, although they use something that implements
similar semantics) then the answer is it depends, but not in portable C.
If you mean a stack data structure implemented in C then the answer is
it depends.
--
Flash Gordon
Dec 1 '07 #3
On Dec 1, 8:01 pm, asit <lipu...@gmail.comwrote:
We kno that data can be pushed onto the stack or popped 4m it. Can
stack be traversed ??
yes stack can be traversed whether it is in static or dynamic memory
allocation
if it is static implementation using arrays then it can be traversed
by simply for loop as in case of arrays
or if it is in dynamic or linked list repesentation it can be
traversed by setting a pointer to the top and then traversing address
of the next pointer until its null
Dec 1 '07 #4
asit wrote:
We kno that data can be pushed onto the stack or popped 4m it. Can
stack be traversed ??
What stack does the abstract C machine have?

--
Tor <bw****@wvtqvm.vw | tr i-za-h a-z>
Dec 2 '07 #5
Tor Rustad wrote:
asit wrote:
>We kno that data can be pushed onto the stack or popped 4m it.
Can stack be traversed ??

What stack does the abstract C machine have?
Just in case this is a serious question, none.

--
Chuck F (cbfalconer at maineline dot net)
<http://cbfalconer.home.att.net>
Try the download section.

--
Posted via a free Usenet account from http://www.teranews.com

Dec 2 '07 #6
CBFalconer wrote:
Tor Rustad wrote:
>asit wrote:
>>We kno that data can be pushed onto the stack or popped 4m it.
Can stack be traversed ??
What stack does the abstract C machine have?

Just in case this is a serious question, none.
This is wrong.

When a function is called, the value of the local variables is no longer
active and is preserved until the called function returns.

When the called function returns, the local variables are reactivated.
If this is not a stack, I do not know what a stack is...

A function call is a push into this stack, a function return is
a pop.

--
jacob navia
jacob at jacob point remcomp point fr
logiciels/informatique
http://www.cs.virginia.edu/~lcc-win32
Dec 2 '07 #7
jacob navia wrote:
CBFalconer wrote:
>Tor Rustad wrote:
>>asit wrote:

We kno that data can be pushed onto the stack or popped 4m it.
Can stack be traversed ??

What stack does the abstract C machine have?

Just in case this is a serious question, none.

This is wrong.
When a function is called, the value of the local variables is no
longer active and is preserved until the called function returns.
Wrong. The variables remain in active existence. To reach them, a
pointer needs to be passed to the called routine. In better
designed languages, such as Pascal and Ada, the passed pointer is
not required.

--
Chuck F (cbfalconer at maineline dot net)
<http://cbfalconer.home.att.net>
Try the download section.
--
Posted via a free Usenet account from http://www.teranews.com

Dec 2 '07 #8
jacob navia <ja***@nospam.comwrites:
[...]
There are things that are self evident except for some people here that
like to confuse beginners when they ask a question.

"There is no stack in C".

The only objective with this answer is to confuse people.
No the objective is to point out that C doesn't require a *hardware
stack*.
And nobody here (nor the OP) is speaking about a hardware stack. It is
conceptually a stack!
How do you *know* the OP wasn't talking about a hardware stack?

--
Keith Thompson (The_Other_Keith) <ks***@mib.org>
Looking for software development work in the San Diego area.
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
Dec 2 '07 #9
ravi wrote:
On Dec 1, 8:01 pm, asit <lipu...@gmail.comwrote:
>We kno that data can be pushed onto the stack or popped 4m it. Can
stack be traversed ??

yes stack can be traversed whether it is in static or dynamic memory
allocation
if it is static implementation using arrays then it can be traversed
by simply for loop as in case of arrays
or if it is in dynamic or linked list repesentation it can be
traversed by setting a pointer to the top and then traversing address
of the next pointer until its null
No. There is no 'stack', dynamic or otherwise, in C.

--
Joe Wright
"Everything should be made as simple as possible, but not simpler."
--- Albert Einstein ---
Dec 2 '07 #10
Joe Wright <jo********@comcast.netwrites:
ravi wrote:
>On Dec 1, 8:01 pm, asit <lipu...@gmail.comwrote:
>>We kno that data can be pushed onto the stack or popped 4m it. Can
stack be traversed ??

yes stack can be traversed whether it is in static or dynamic
memory allocation if it is static implementation using arrays then
it can be traversed by simply for loop as in case of arrays or if
it is in dynamic or linked list repesentation it can be traversed
by setting a pointer to the top and then traversing address of the
next pointer until its null

No. There is no 'stack', dynamic or otherwise, in C.
That's quite correct given one common and useful definition of the
word "stack" (i.e., a contiguous hardware stack). (But even given
that definition, it should be made clear that although the C standard
doesn't require this kind of stack, it's certainly an allowed and
quite common implementation choice; saying "There is no 'stack'" could
easily obscure that point.)

It's quite incorrect given another common and useful definition of the
word "stack" (i.e., the abstract data structure).

I suggest that your response is therefore incomplete and potentially
misleading. See my followup elsewhere in this thread for details.

--
Keith Thompson (The_Other_Keith) <ks***@mib.org>
Looking for software development work in the San Diego area.
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
Dec 2 '07 #11
jacob navia wrote:
Of course it is a stack. The standard doesn't mandate a stack because
everybody knows what a stack is, and uses a stack.
No. The standard doesn't mandate a stack because C can be, and has been,
implemented on machines which don't use a stack. For example, the
PowerPC annd Sparc chips have so many registers that function parameters
are passed through these.

Note that within computer programming, "the stack" has a specific
meaning, and does not apply to general purpose software stacks
implemented by the programmer.
"There is no stack in C".

The only objective with this answer is to confuse people.
Bollocks. The objective is to free people from the mistaken belief that
C requires a stack.
Dec 3 '07 #12
Mark McIntyre <ma**********@spamcop.netwrites:
jacob navia wrote:
[...]
>"There is no stack in C".

The only objective with this answer is to confuse people.

Bollocks. The objective is to free people from the mistaken belief
that C requires a stack.
The objective *should* be to help people understand that the word
"stack" has more than one meaning. Since the C standard doesn't
happen to define, or even use, the word "stack", we should make the
meaning clear when we talk about "stacks" here. Assuming that only
one meaning is relevant and deliberately ignoring the other, as both
Mark and jacob have been doing, is not helpful. (Though I don't
believe for a moment that either of you has the objective of confusing
people.)

The OP didn't give us enough information to be sure what he meant by
the word "stack". Until he does so, this discussion is not useful in
answering the OP's question.

--
Keith Thompson (The_Other_Keith) <ks***@mib.org>
Looking for software development work in the San Diego area.
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
Dec 3 '07 #13
RoS
In data Mon, 03 Dec 2007 00:06:33 +0000, Mark McIntyre scrisse:
>jacob navia wrote:
>Of course it is a stack. The standard doesn't mandate a stack because
everybody knows what a stack is, and uses a stack.

No. The standard doesn't mandate a stack because C can be, and has been,
implemented on machines which don't use a stack. For example, the
PowerPC annd Sparc chips have so many registers that function parameters
are passed through these.
i think the above is not true for recursive functions
Dec 3 '07 #14
Mark McIntyre wrote:
jacob navia wrote:
>Of course it is a stack. The standard doesn't mandate a stack because
everybody knows what a stack is, and uses a stack.

No. The standard doesn't mandate a stack because C can be, and has been,
implemented on machines which don't use a stack. For example, the
PowerPC annd Sparc chips have so many registers that function parameters
are passed through these.
Yeah of course. Like windows 64, like linux 64 in the AMD chips...

You are telling NONSENSE. The power PC architecture has a dedicated
stack register! (Register 1)

In non AIX architectures it could be another register but
ALL of them have a hardware stack.

Note that within computer programming, "the stack" has a specific
meaning, and does not apply to general purpose software stacks
implemented by the programmer.
It is interesting that you leave out the sentence from my
message where I say:

<quote>
And nobody here (nor the OP) is speaking about a hardware stack. It is
conceptually a stack!
<end quote>

--
jacob navia
jacob at jacob point remcomp point fr
logiciels/informatique
http://www.cs.virginia.edu/~lcc-win32
Dec 3 '07 #15
Mark McIntyre wrote:
jacob navia wrote:
>Of course it is a stack. The standard doesn't mandate a stack because
everybody knows what a stack is, and uses a stack.

No. The standard doesn't mandate a stack because C can be, and has been,
implemented on machines which don't use a stack. For example, the
PowerPC annd Sparc chips have so many registers that function parameters
are passed through these.
Only as many parameters as there are input/output registers, beyond
that, the stack is used (at least for Sparc and probably PPC versions
with a finite number of registers).

--
Ian Collins.
Dec 3 '07 #16
In article <13*************@corp.supernews.com>,
Mark McIntyre <ma**********@spamcop.netwrote:
>No. The standard doesn't mandate a stack because C can be, and has been,
implemented on machines which don't use a stack. For example, the
PowerPC annd Sparc chips have so many registers that function parameters
are passed through these.
Of course they use a stack. Where do you think they put large local
arrays?

Anyway, those registers are effectively just a cache of the top of the
stack. if you recurse deeply enough, the registers will be written
out to memory. Or to look at it another way, part of the stack is in
registers. There's still a stack.

-- Richard
--
"Consideration shall be given to the need for as many as 32 characters
in some alphabets" - X3.4, 1963.
Dec 3 '07 #17
On Dec 1, 11:01 pm, asit <lipu...@gmail.comwrote:
We kno that data can be pushed onto the stack or popped 4m it. Can
stack be traversed ??
If you mean the stack data structure, it of course can be tranversed,
the way to tranverse the stack depends on the stack implementation.

If you mean the stack supported by the push/pop commands of the
processor and managed by the OS, it can also be tranversed with ease,
but you have to know sth about the internal operating system data
structure and compiler impl.

Dec 3 '07 #18
On Dec 1, 11:01 pm, asit <lipu...@gmail.comwrote:
We kno that data can be pushed onto the stack or popped 4m it. Can
stack be traversed ??
Anyway, the stack-tranversing-operation is not defined in the standard
stack interface.If you need to tranverse a stack data structure, the
platform independent method is as follows:

You need one additional stack for temporary storage of the stack
elements.

void tranverseStack(struct Stack* pStack,void (*TRANVERSE)(void*))
{
void *pElem;
struct Stack local_stack;
while( NULL != (pElem=pStack->pop()) )
{
TRANVERSE(pElem);
local_stack.push(pElem);
}
while( NULL != (pElem=local_stack.pop()) )
{
pStack->push(pElem);
}
}
Thanks and Regards,
James Fang
Dec 3 '07 #19
jacob navia wrote:

[...]
It is interesting that you leave out the sentence from my
message where I say:

<quote>
And nobody here (nor the OP) is speaking about a hardware stack. It is
conceptually a stack!
<end quote>
Nonsense.

Most C programs does not have any recursive function calls, also MISRA C
ban such functions. In case there are no recursive calls, the translator
don't need a stack for the return address. Storage for local objects can
be allocated in global area, at fixed addresses known at link-time.

The function call tree, can be used to identify which function life
times are mutually exclusive, hence storage of object with automatic
storage duration, can be overlaid.

This is not just some theoretical observation, but can be expected in
real world C implementations. For example, when targeting the Intel 8051
(only a 128 byte stack), make such an approach quite interesting.
--
Tor <bw****@wvtqvm.vw | tr i-za-h a-z>
Dec 3 '07 #20
On Mon, 03 Dec 2007 20:50:21 +0100, Tor Rustad
<to********@hotmail.comwrote:
>jacob navia wrote:

[...]
>It is interesting that you leave out the sentence from my
message where I say:

<quote>
And nobody here (nor the OP) is speaking about a hardware stack. It is
conceptually a stack!
<end quote>

Nonsense.

Most C programs does not have any recursive function calls, also MISRA C
ban such functions. In case there are no recursive calls, the translator
don't need a stack for the return address. Storage for local objects can
be allocated in global area, at fixed addresses known at link-time.

The function call tree, can be used to identify which function life
times are mutually exclusive, hence storage of object with automatic
storage duration, can be overlaid.

This is not just some theoretical observation, but can be expected in
real world C implementations. For example, when targeting the Intel 8051
(only a 128 byte stack), make such an approach quite interesting.

You're missing the point. It doesn't matter where the storage
for is; the pattern of usage is that of an abstract stack.


Richard Harter, cr*@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
In the fields of Hell where the grass grows high
Are the graves of dreams allowed to die
Dec 4 '07 #21
Tor Rustad <to********@hotmail.comwrites:
jacob navia wrote:

[...]
>It is interesting that you leave out the sentence from my
message where I say:

<quote>
And nobody here (nor the OP) is speaking about a hardware stack. It is
conceptually a stack!
<end quote>

Nonsense.

Most C programs does not have any recursive function calls, also MISRA
C ban such functions. In case there are no recursive calls, the
translator don't need a stack for the return address. Storage for
local objects can be allocated in global area, at fixed addresses
known at link-time.

The function call tree, can be used to identify which function life
times are mutually exclusive, hence storage of object with automatic
storage duration, can be overlaid.

This is not just some theoretical observation, but can be expected in
real world C implementations. For example, when targeting the Intel
8051 (only a 128 byte stack), make such an approach quite interesting.
Which part of "conceptually" do you not understand? Does the whole
idea of call stack (call tree...) go out of the window? The storage
method is immaterial. The concept is still that of an abstract stack.
Dec 4 '07 #22
In article <0n************@news.individual.net>,
Richard <rg****@gmail.comwrote:
>Which part of "conceptually" do you not understand? Does the whole
idea of call stack (call tree...) go out of the window? The storage
method is immaterial. The concept is still that of an abstract stack.
Oh, *conceptually*. Well, *conceptually* it is really four enormous
elephants riding on the back of a turtle that is swimming through
space. If it isn't immediately clear why so, then the secret is to
"Bang the rocks together, guys".

--
"I was very young in those days, but I was also rather dim."
-- Christopher Priest
Dec 4 '07 #23
Richard Harter wrote:

[...]
You're missing the point.
If not context here was "traversing a stack", I must indeed be missing
something. :)

It doesn't matter where the storage
for is; the pattern of usage is that of an abstract stack.
Since when, was traversing overlaid memory similar to traversing a stack?

In particular, I recommend that you give some thought to where the
function return address could be, before considering how to pop it.

As it turns out, the abstract C machine has no requirement for
implementations to use a "stack", and a search for the word "stack" in
the C standard, gave me nada... zero.

The *relevant point* is that translators can take advantage of this, and
use overlaid memory (in some cases), which is a highly relevant point in
the context of traversing such a memory arena, while "usage pattern" is
not.

--
Tor <bw****@wvtqvm.vw | tr i-za-h a-z>
Dec 5 '07 #24
Richard Tobin wrote:
In article <13*************@corp.supernews.com>,
Mark McIntyre <ma**********@spamcop.netwrote:
>No. The standard doesn't mandate a stack because C can be, and has been,
implemented on machines which don't use a stack. For example, the
PowerPC annd Sparc chips have so many registers that function parameters
are passed through these.

Of course they use a stack. Where do you think they put large local
arrays?
a) We snipped too much context. The point was being made in relation to
function parameters, not local variables.

b) I've no idea. But note that no stack is *necessary* to store local
variables.
Anyway, those registers are effectively just a cache of the top of the
stack.
Eh? Registers are hardware locations.
Dec 5 '07 #25
On Sun, 02 Dec 2007 10:36:21 -0500, CBFalconer <cb********@yahoo.com>
wrote:
jacob navia wrote:
<snip: does C 'have a stack'>
When a function is called, the value of the local variables is no
longer active and is preserved until the called function returns.

Wrong. The variables remain in active existence. To reach them, a
pointer needs to be passed to the called routine. In better
designed languages, such as Pascal and Ada, the passed pointer is
not required.
They continue to exist and may be accessed, yes.

Nothing needs to be passed if, and only if, the called routine is
nested (directly or indirectly) within the routine, or module or
package respectively, whose local/private(s) it wants to access.
And there is not a more-local declaration of the same name(s).

Anywhere else, you do need to pass something. In Pascal (always) and
Ada (usually) this can be a reference parameter so what you pass isn't
_written as_ a pointer, but in fact is one under the covers.

I hope you meant the former, as the latter is mostly sophistry.

- formerly david.thompson1 || achar(64) || worldnet.att.net
Dec 17 '07 #26
David Thompson wrote:
CBFalconer <cb********@yahoo.comwrote:
>jacob navia wrote:
<snip: does C 'have a stack'>
>>
>>When a function is called, the value of the local variables is no
longer active and is preserved until the called function returns.

Wrong. The variables remain in active existence. To reach them, a
pointer needs to be passed to the called routine. In better
designed languages, such as Pascal and Ada, the passed pointer is
not required.

They continue to exist and may be accessed, yes.

Nothing needs to be passed if, and only if, the called routine is
nested (directly or indirectly) within the routine, or module or
package respectively, whose local/private(s) it wants to access.
And there is not a more-local declaration of the same name(s).
This is c.l.c. There are NO nested routines in C. NONE. Illegal.

--
Merry Christmas, Happy Hanukah, Happy New Year
Joyeux Noel, Bonne Annee.
Chuck F (cbfalconer at maineline dot net)
<http://cbfalconer.home.att.net>

--
Posted via a free Usenet account from http://www.teranews.com

Dec 20 '07 #27
On Mon, 17 Dec 2007 01:52:27 -0500, CBFalconer
<cb********@yahoo.comwrote:
>David Thompson wrote:
>CBFalconer <cb********@yahoo.comwrote:
>>jacob navia wrote:
<snip: does C 'have a stack'>
>>>
When a function is called, the value of the local variables is no
longer active and is preserved until the called function returns.

Wrong. The variables remain in active existence. To reach them, a
pointer needs to be passed to the called routine. In better
designed languages, such as Pascal and Ada, the passed pointer is
not required.

They continue to exist and may be accessed, yes.

Nothing needs to be passed if, and only if, the called routine is
nested (directly or indirectly) within the routine, or module or
package respectively, whose local/private(s) it wants to access.
And there is not a more-local declaration of the same name(s).

This is c.l.c. There are NO nested routines in C. NONE. Illegal.
Perhaps you should address your comments to CBFalconer, the
person who brought up "in better designed languages".
Dec 20 '07 #28
Richard Harter wrote:
<cb********@yahoo.comwrote:
>David Thompson wrote:
>>CBFalconer <cb********@yahoo.comwrote:
jacob navia wrote:

<snip: does C 'have a stack'>

When a function is called, the value of the local variables is no
longer active and is preserved until the called function returns.

Wrong. The variables remain in active existence. To reach them, a
pointer needs to be passed to the called routine. In better
designed languages, such as Pascal and Ada, the passed pointer is
not required.

They continue to exist and may be accessed, yes.

Nothing needs to be passed if, and only if, the called routine is
nested (directly or indirectly) within the routine, or module or
package respectively, whose local/private(s) it wants to access.
And there is not a more-local declaration of the same name(s).

This is c.l.c. There are NO nested routines in C. NONE. Illegal.

Perhaps you should address your comments to CBFalconer, the
person who brought up "in better designed languages".
Err - I suggest you read the attributions. My last comment was
about nested functions. :-)

--
Merry Christmas, Happy Hanukah, Happy New Year
Joyeux Noel, Bonne Annee.
Chuck F (cbfalconer at maineline dot net)
<http://cbfalconer.home.att.net>

--
Posted via a free Usenet account from http://www.teranews.com

Dec 20 '07 #29
CBFalconer said:
Richard Harter wrote:
><cb********@yahoo.comwrote:
<snip>
>>This is c.l.c. There are NO nested routines in C. NONE. Illegal.

Perhaps you should address your comments to CBFalconer, the
person who brought up "in better designed languages".

Err - I suggest you read the attributions. My last comment was
about nested functions. :-)
Err - I suggest you read closely the material that Richard Harter quoted,
because it contained an earlier comment from *you*, regarding "better
designed languages".

Richard Harter's point is that, since *you* introduced the discussion of
"better designed languages", you have no justification for playing
topic-cop when other people then discuss those "better designed languages"
- you can't switch topicality on and off when it suits you, any more than
you can change netiquette rules to sui... er, never mind.

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999
Dec 20 '07 #30
Richard Heathfield wrote:
CBFalconer said:
>Richard Harter wrote:
>><cb********@yahoo.comwrote:

<snip>
>>>This is c.l.c. There are NO nested routines in C. NONE. Illegal.

Perhaps you should address your comments to CBFalconer, the
person who brought up "in better designed languages".

Err - I suggest you read the attributions. My last comment was
about nested functions. :-)

Err - I suggest you read closely the material that Richard Harter
quoted, because it contained an earlier comment from *you*,
regarding "better designed languages".
Err - he directed his comment to 'you', who is the author of the
material with '>>>' quotes above, and turns out to be me. And yes,
I did earlier, in a separate message, mention "better designed
languages". And finally, this is not worth wasting electrons
over. Out.

--
Merry Christmas, Happy Hanukah, Happy New Year
Joyeux Noel, Bonne Annee.
Chuck F (cbfalconer at maineline dot net)
<http://cbfalconer.home.att.net>

--
Posted via a free Usenet account from http://www.teranews.com

Dec 21 '07 #31

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

7 posts views Thread by wallacej | last post: by
4 posts views Thread by plmanikandan | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.