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

From: Michael Wojcik (mwojcik_at_newsguy.com)
Date: 10/08/04 

Date: 8 Oct 2004 15:23:54 GMT

In article <ck683f$hu1$1@news1brm.Central.Sun.COM>, Eric Sosman <eric.sosman@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                  michael.wojcik@microfocus.com
Recently, they appeared at the reopening of the Brookdale Library,
luring passersby with the opportunity to be anonymously silly.

Relevant Pages

  • Re: you cant bash Microsoft enough
    ... even on products with user interfaces and eternet. ... That ain't a lot of room to save even three contexts on three stacks. ... all the regs onto the current stack on a hardware interrupt or an SWI. ...
    (sci.electronics.design)
  • [PATCH for review] [108/145] x86_64: Some preparationary cleanup for stack trace
    ... - * If all_contexts is set, all contexts (hardirq, softirq and process) ... unsigned long stack, unsigned long stack_end) ...
    (Linux-Kernel)
  • Re: Device Driver Etiquette
    ... I maintain a device driver that has been bitten by the transition to 4K ... It used the stack for a number of large data ... sleep-capable work from interrupts-disabled contexts to user ... so if you're stack-heavy and suffer a concurrent interrupt (which ...
    (Linux-Kernel)
Loading