Array implementation of Stack

[Shao Miller]

WANTED: To write an array implementation of Stack.
WHAT I GOT: It works fine.

I think program is still little too complex. Any ideas to improve ?



/* Array implementation of Stack - Aho, Hopcraft and Ullman, page 68-70
* section 2.3. We will add element at the bottom and we will grow the
* stack to top. top_index will keep track of index where element was
* added as latest. We will use top_index to push/pop elements.
*
* VERSION 0.0.
*
*/

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

enum {
SIZE_NAME = 10, SIZE_ARR = 3,
VAL_SUCC = 0, VAL_ERR = 1
};

If you use a source control system such as 'git' or even simply have
'diff'-style patches, it might be nice to put each of the enumeration
values on their own lines. Otherwise, a change in choice of 'SIZE_NAME'
happens in the same line as 'SIZE_ARR', but 'SIZE_ARR' is not affected
by the change (but a reader might look twice to be sure).

struct elm
{
int num;
char name[SIZE_NAME+1];
};


struct elm_stack
{
int top_index;
struct elm* arr[SIZE_ARR];
};

So it appears that your stack contains an array of pointers to elements,
rather than an array of the elements.

It appears to be a pretty short stack.

Just following along "out loud."

int push(struct elm_stack* , struct elm* );
void pop(struct elm_stack* );

Above, if 'push' and 'pop' are supposed to have a symmetrical sense
about them, you might wish to return the "popped" element with 'pop',
since you are offered a "pushed" element in 'push'. If a "popped"
element needn't ever be examined, I guess it doesn't matter.

struct elm_stack* stack_init(void);
void print_stack(struct elm_stack* );
struct elm* get_element(const char* c, int n);

Above, it appears that 'n' might be used as an index into the stack.
That suggests to me that the kind of stack you are thinking of is not
restricted to examination of only the top value. Ok.

int main(void)
{
struct elm_stack* s = stack_init();

'stack_init' must be responsible for allocating the stack or returning a
reference to a stack with static duration, by the looks of it.

struct elm* e0 = get_element("comp", 2);
struct elm* e1 = get_element("lang", 1);
struct elm* e2 = get_element("c", 0);

'get_element'? Hmm...

int ret_elem = push(s, e0);
if(VAL_ERR == ret_elem)
{
printf("IN: %s @%d: Memory Full\n", __FILE__, __LINE__);
free(e0);
}

ret_elem = push(s, e1);
if(VAL_ERR == ret_elem)
{
printf("IN: %s @%d: Memory Full\n", __FILE__, __LINE__);
free(e1);
}

ret_elem = push(s, e2);
if(VAL_ERR == ret_elem)
{
printf("IN: %s @%d: Memory Full\n", __FILE__, __LINE__);
free(e2);
}

print_stack(s);


printf("-----------------------------------------\n\n");
pop(s);
print_stack(s);
printf("-----------------------------------------\n\n");

pop(s);
print_stack(s);
printf("-----------------------------------------\n\n");

pop(s);
print_stack(s);

return EXIT_SUCCESS;
}



int push(struct elm_stack* s, struct elm* e)
{
int ret;

if(NULL == s || NULL == e)
{
printf("IN:%s @%d Invalid Args!\n", __FILE__, __LINE__);
ret = VAL_ERR;
}
else if(s->top_index == 0)
{
ret = VAL_ERR;
}
else
{
--(s->top_index);
/* printf("s->top_index = %d\n", s->top_index); */
s->arr[s->top_index] = e;
/* printf("%s = %d\n", e->name, e->num); */
ret = VAL_SUCC;
}

return ret;
}

It's interesting that a caller uses two steps to create an element on
the stack ('get_element', 'push'), but the 'pop' removes the element in
one step. You might reconsider this.

void pop(struct elm_stack* s)
{
if(NULL == s)
{
printf("IN:%s @%d: Invalid Args!\n", __FILE__, __LINE__);
}
else if(SIZE_ARR<= s->top_index)
{
printf("Nothing to pop()\n");
}
else
{
struct elm* e = s->arr[s->top_index];
free(e);
++(s->top_index);
}
}

Above, you do not set 's->arr[s->top_index]' to 'NULL' as you do in
'stack_init', below.

It seems that you are no longer interested in the element, so I can
understand why you do not return the element.

struct elm_stack* stack_init(void)
{
int idx;
struct elm_stack* p = malloc(1 * sizeof *p);
if(NULL == p)
{
printf("IN: %s @%d: Out of Memory!\n", __FILE__, __LINE__);
}
else
{
p->top_index = SIZE_ARR;
for(idx = 0; idx< SIZE_ARR; ++idx) p->arr[idx] = NULL;
}

Your choice for where you declare 'idx' above doesn't seem stylistically
consistent with where you declare it in 'print_stack', below.

If you 'return p;' within the 'if' block, you don't need the 'else'
block and can takes its content into the function's block. Why? If you
had further conditions for "success," you could end up with something like:

if (condition1) {
/* ... */
} else {
if (condition2) {
/* ... */
} else {
if (condition3) {
/* ... */
} else {
/* ... */
}
}
}

which is ever-indenting towards the right. Or you could have:

if (condition1) {
/* ... */
} else if (condition2) {
/* ... */
} else if (condition3) {
/* ... */
} else {
/* ... */
}

If all of the conditions are failure-checks and a reader recognizes
that, then they know that the last block depends on passing all tests.
Using 'return' in failure-checks is perhaps a more aggressive indication
that a check is a failure-check for the function, rather than making a
behavioural choice which doesn't affect the overall success of the
function. But that's just an opinion about style, too.

return p;
}


struct elm* get_element(const char* c, int n)
{
struct elm* p = malloc(1 * sizeof *p);

Why use '1 * sizeof *p' rather than 'sizeof *p', above?

if(NULL == p)

'if (!p)' is another option, but is a stylistic difference for people.
I don't think the behavioural equivalence will be changing any time soon.

{
printf("IN:%s @%d: Out of Memory!\n", __FILE__, __LINE__);
}
else if(SIZE_NAME< strlen(c))
{
printf("IN: %s @ %d: ", __FILE__, __LINE__);
printf("Name too big, Not adding element\n");
free(p);
p = NULL;
}
else
{
p->num = n;

The line above appears to suggest that the caller could potentially
specify duplicate indices.

strcpy(p->name,c);
}

return p;
}

Would 'make_element' or 'new_element' make more sense for the function
above? 'get_element' makes me think that an element already exists, but
you allocate one.

void print_stack(struct elm_stack* s)
{
if(NULL == s)
{
printf("IN:%s @%d: Invalid Args!\n", __FILE__, __LINE__);
}
else
{
int idx = SIZE_ARR - 1;
struct elm* e;
/*printf("idx %d, top_index = %d\n", idx, s->top_index); */
for(; (idx>= 0)&& (idx>= s->top_index); --idx)
{

Why not declare 'idx' without an initializer (as you do with 'e') and
then assign to it in the 'for' loop's "clause-1"?

If you used 'unsigned int' for 'idx', you could avoid potential signed
arithmetic overflow. Then 'idx >= 0' could also become 'idx'.

/*printf("idx %d, top_index = %d\n", idx, s->top_index);*/
e = s->arr[idx];
printf("%s = %d\n", e->name, e->num);
}
}
}

=================== OUTPUT ========================
[arnuld@dune C]$ gcc -ansi -pedantic -Wall -Wextra lifo-array.c
[arnuld@dune C]$ ./a.out
comp = 2
lang = 1
c = 0

It appears to work. I hope this brief review helps with "I think
program is still little too complex. Any ideas to improve ?"

 

[Kleuskes & Moos]

Maybe the names are just poorly chosen. I always think of pop()
returning the top value and shrinking the stack. I would use drop() to
just shrink the stack. A push() without arguments could just duplicate
the top of the stack, but then you'd be better off calling that dup().

Hmmm... Usually i like pop to just pop things off the stack, no more,
no less. I developed a strong dislike for 'two-for-one' operations. I
developed an even stronger dislike for all kinds of renaming schemes
which only obfuscate basically very simple operations. And 'dup' is a
commonly used stack primitive in it's own right, which exists neatly
alongside push, pop and top.

 

[Shao Miller]

Why not declare 'idx' without an initializer (as you do with 'e') and
then assign to it in the 'for' loop's "clause-1"?

If you used 'unsigned int' for 'idx', you could avoid potential signed
arithmetic overflow. Then 'idx >= 0' could also become 'idx'.

Oops. Never mind. I misread '>=' as '>'. Sorry.

 

[Willem]

Kleuskes & Moos wrote:
) Hmmm... Usually i like pop to just pop things off the stack, no more,
) no less. I developed a strong dislike for 'two-for-one' operations. I
) developed an even stronger dislike for all kinds of renaming schemes
) which only obfuscate basically very simple operations. And 'dup' is a
) commonly used stack primitive in it's own right, which exists neatly
) alongside push, pop and top.

Then why should push() do two things at once ?
It extends the stack, and then places something in the top slot.
I have a strong dislike for inconsistent operations.


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

 

[Keith Thompson]

Kleuskes & Moos wrote:
) Hmmm... Usually i like pop to just pop things off the stack, no more,
) no less. I developed a strong dislike for 'two-for-one' operations. I
) developed an even stronger dislike for all kinds of renaming schemes
) which only obfuscate basically very simple operations. And 'dup' is a
) commonly used stack primitive in it's own right, which exists neatly
) alongside push, pop and top.

Then why should push() do two things at once ?
It extends the stack, and then places something in the top slot.
I have a strong dislike for inconsistent operations.

Because after you extend the stack, you have to put *something* in the
top slot. Requiring the user to provide a value means you don't have to
complicate the semantics by inventing something to put there.

push() and pop() are two different operations. They don't have to
be consistent if that consistency comes at the cost of convenience.

 

[Ralf Damaschke]

Because after you extend the stack, you have to put *something*
in the top slot. Requiring the user to provide a value means
you don't have to complicate the semantics by inventing
something to put there.

That's thought too short. You could also first supply a value to
be placed on the stack with the next push operation.

push() and pop() are two different operations. They don't have
to be consistent if that consistency comes at the cost of
convenience.

So you find it convinient to be tied to a hosted implementation
where you can redirect the output to a file and then analyse
this file for getting the value of "top of stack", as you are
required with the OP's implementation?

-- Ralf

 

[Keith Thompson]

That's thought too short. You could also first supply a value to
be placed on the stack with the next push operation.

Seriously?

How is that supplied value associated with a particular stack? Would
it ever make sense to do something with it other than immediately
pushing it? What happens if you push without specifying a value?

So you find it convinient to be tied to a hosted implementation
where you can redirect the output to a file and then analyse
this file for getting the value of "top of stack", as you are
required with the OP's implementation?

Um, no. I was commenting only on the question of whether push()
should take a value and whether pop() should return a value.

 

[Rui Maciel]

push() not taking a value makes some sense if you think that
expanding the stack and setting the top element should be
separate operations.

What's the point of that, besides needlessly allocating memory that your
program does not use?

pop() without a return value would have to discard the value it
takes from the stack.

Well. that's the point of pop(). You store your data with push(), you
access the data with top() and you discard your data with pop().


Rui Maciel

 

[Keith Thompson]

What's the point of that, besides needlessly allocating memory that your
program does not use?



Well. that's the point of pop(). You store your data with push(), you
access the data with top() and you discard your data with pop().

*Or* you use pop() to retrieve the value of the top element *and*
shorten the stack, since it's common to want to do both at once.

Or you have two different pop() operations (perhaps with different
names), one that returns the value and one that discards it.

Or pop() returns the value, but you can discard it yourself if
you like.

That's not to suggest that there shouldn't also be a top() operation.

 

[Willem]

Rui Maciel wrote:
) Willem wrote:
)
)> push() not taking a value makes some sense if you think that
)> expanding the stack and setting the top element should be
)> separate operations.
)
) What's the point of that, besides needlessly allocating memory that your
) program does not use?

What part of 'and setting the top element' do you not understand ?

But I will make it easy for you: top() returns an lvalue, which can
be used to both read and set the top element.

)> pop() without a return value would have to discard the value it
)> takes from the stack.
)
) Well. that's the point of pop(). You store your data with push(), you
) access the data with top() and you discard your data with pop().

Do you know what "begging the question" means ?

Here's an example for you:

The point of pop() is to give you the top element of the stack.
So there's no point in having a separate top() operation.


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

 

[Willem]

Keith Thompson wrote:
)> Kleuskes & Moos wrote:
)> ) Hmmm... Usually i like pop to just pop things off the stack, no more,
)> ) no less. I developed a strong dislike for 'two-for-one' operations. I
)> ) developed an even stronger dislike for all kinds of renaming schemes
)> ) which only obfuscate basically very simple operations. And 'dup' is a
)> ) commonly used stack primitive in it's own right, which exists neatly
)> ) alongside push, pop and top.
)>
)> Then why should push() do two things at once ?
)> It extends the stack, and then places something in the top slot.
)> I have a strong dislike for inconsistent operations.
)
) Because after you extend the stack, you have to put *something* in the
) top slot. Requiring the user to provide a value means you don't have to
) complicate the semantics by inventing something to put there.

For the record: this is comp.lang.c.
If you extend the stack you don't have to put *anything* in the top slot.

) push() and pop() are two different operations. They don't have to
) be consistent if that consistency comes at the cost of convenience.

What is inconvenient about pop() returning whatever it takes off
the stack ? push() takes two values for convenience,
pop() returns a value for convenience. And it's consistent to boot.

So, I stay by my statement, that pop() returns a value for the same
reason as push() takes two values, without stating what that reason is.

You seem to think it's convenience, fine by me.


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

 

[Dr Nick]

That's thought too short. You could also first supply a value to
be placed on the stack with the next push operation.

Even better, you could have a structure to allow you to queue up a list
of items that will be put on the stack one per push operation.

You'd need an operation to push an item onto the queue of course. But I
have an idea: why not instead first supply a value to be placed on the
queue with the next queue-push operation.

Even better, you could ...

 

[Ike Naar]

The point of pop() is to give you the top element of the stack.
So there's no point in having a separate top() operation.

pop() gives you the top element, but it also has the side effect
of removing the top element from the stack.
Sometimes you want to look at the top element without modifying the stack.
If there isn't a separate top() operation, then of course

dosomethingwith(top());

can be emulated by

temp = pop(); push(temp); dosomethingwith(temp);

but the latter looks a bit awkward.

 

[Ralf Damaschke]

Seriously?

Not too much.

How is that supplied value associated with a particular stack?

As usual: with a parameter specifying the stack and some storage.

Would it ever make sense to do something with it other than
immediately pushing it?

Who knows...

What happens if you push without specifying a value?

Some error recovery, as would be also necessary when there are
more pop() than push(), or top() applied to an empty stack.

I find it strange that the question "Why would pop() not return
a value?" was answered with that's what the top() operation is for
but there was no top() either.

-- Ralf

 

[Keith Thompson]

Rui Maciel wrote:
) Willem wrote:
)
)> push() not taking a value makes some sense if you think that
)> expanding the stack and setting the top element should be
)> separate operations.
)
) What's the point of that, besides needlessly allocating memory that your
) program does not use?

What part of 'and setting the top element' do you not understand ?

"and setting the top element" is perfectly clear. What's not clear is
why it should be a separate operation from expanding the stack.

Of course you *could* provide a function that extends the stack
by one element and leaves the top element with some default or
unspecified value. But I can't think of a realistic scenario where
you'd want to do that without already knowing what value you want
to store.

But I will make it easy for you: top() returns an lvalue, which can
be used to both read and set the top element.

How does a function return an lvalue? Or do you intend top() to be a
macro?

top() could return a *pointer* value, but I don't recall ever seeing a
stack implementation that does that.

Have you actually seen a stack implementation whose push() operation
extends the stack without storing a value in the new top element?

[...]

 

[Keith Thompson]

Keith Thompson wrote:
)> Kleuskes & Moos wrote:
)> ) Hmmm... Usually i like pop to just pop things off the stack, no more,
)> ) no less. I developed a strong dislike for 'two-for-one' operations. I
)> ) developed an even stronger dislike for all kinds of renaming schemes
)> ) which only obfuscate basically very simple operations. And 'dup' is a
)> ) commonly used stack primitive in it's own right, which exists neatly
)> ) alongside push, pop and top.
)>
)> Then why should push() do two things at once ?
)> It extends the stack, and then places something in the top slot.
)> I have a strong dislike for inconsistent operations.
)
) Because after you extend the stack, you have to put *something* in the
) top slot. Requiring the user to provide a value means you don't have to
) complicate the semantics by inventing something to put there.

For the record: this is comp.lang.c.

I'm aware of that.

If you extend the stack you don't have to put *anything* in the top slot.

Ok, you don't *have* to, but there's no reason not to do so.

) push() and pop() are two different operations. They don't have to
) be consistent if that consistency comes at the cost of convenience.

What is inconvenient about pop() returning whatever it takes off
the stack ? push() takes two values for convenience,
pop() returns a value for convenience. And it's consistent to boot.

I never said that pop() shouldn't return the top value -- but it
doesn't really need to.

Extending the stack and storing a value in the new top element are
logically tied together. I can't think of a scenario where it would
make sense to extend the stack *without* storing a value. Because of
that, I don't think it makes sense to have a push() operation that
doesn't take an argument specifying the new value to be stored.

Accessing the top element and shrinking the stack by one element
are not tied together in the same way. I might want to access the
same top element multiple times, or I might want to discard the
top element without caring what it was; either leaves the stack in
a well defined state.

If I want a conceptually pure stack implementation (perhaps in a
classroom setting), I might just provide a push() that takes an
element value and pop() that returns an element value. If I want
something more convenient for real-world use, I might provide those
operations *plus* a top() function that returns the top element
value, an function that returns the Nth element from the top, and
a pop()-like function that discards the result. (The latter isn't
necessary in C, since the caller can easily discard the result.)

So, I stay by my statement, that pop() returns a value for the same
reason as push() takes two values, without stating what that reason is.

You seem to think it's convenience, fine by me.

Did you have some other reason in mind? I'm not even entirely sure
what you're arguing.

 

[Pranav]

WANTED:  To write an array implementation of Stack.
WHAT I GOT:  It works fine.

I think program is still little too complex. Any ideas to improve ?

/* Array implementation of Stack - Aho, Hopcraft and Ullman, page 68-70
 * section 2.3. We will add element at the bottom and we will grow the
 * stack to top. top_index will keep track of index where element was
 * added as latest. We will use top_index to push/pop elements.
 *
 * VERSION 0.0.
 *
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

enum {
  SIZE_NAME = 10, SIZE_ARR = 3,
  VAL_SUCC = 0, VAL_ERR = 1

};

struct elm
{
  int num;
  char name[SIZE_NAME+1];

};

struct elm_stack
{
  int top_index;
  struct elm* arr[SIZE_ARR];

};

int push(struct elm_stack* , struct elm* );
void pop(struct elm_stack* );
struct elm_stack* stack_init(void);
void print_stack(struct elm_stack* );
struct elm* get_element(const char* c, int n);

int main(void)
{
  struct elm_stack* s = stack_init();

  struct elm* e0 = get_element("comp", 2);
  struct elm* e1 = get_element("lang", 1);
  struct elm* e2 = get_element("c", 0);

  int ret_elem = push(s, e0);
  if(VAL_ERR == ret_elem)
    {
      printf("IN: %s @%d: Memory Full\n", __FILE__, __LINE__);
      free(e0);
    }

  ret_elem = push(s, e1);
  if(VAL_ERR == ret_elem)
    {
      printf("IN: %s @%d: Memory Full\n", __FILE__, __LINE__);
      free(e1);
    }

  ret_elem = push(s, e2);
  if(VAL_ERR == ret_elem)
    {
      printf("IN: %s @%d: Memory Full\n", __FILE__, __LINE__);
      free(e2);
    }

  print_stack(s);

  printf("-----------------------------------------\n\n");
  pop(s);
  print_stack(s);
  printf("-----------------------------------------\n\n");

  pop(s);
  print_stack(s);
  printf("-----------------------------------------\n\n");

  pop(s);
  print_stack(s);

  return EXIT_SUCCESS;

}

int push(struct elm_stack* s, struct elm* e)
{
  int ret;

  if(NULL == s || NULL == e)
    {
      printf("IN:%s @%d Invalid Args!\n", __FILE__, __LINE__);
      ret = VAL_ERR;
    }
  else if(s->top_index == 0)
    {
      ret = VAL_ERR;
    }
  else
    {
      --(s->top_index);
      /*      printf("s->top_index = %d\n", s->top_index); */
      s->arr[s->top_index] = e;
      /*      printf("%s = %d\n", e->name, e->num); */
      ret = VAL_SUCC;
    }

  return ret;

}

void pop(struct elm_stack* s)
{
  if(NULL == s)
    {
      printf("IN:%s @%d: Invalid Args!\n", __FILE__, __LINE__);
    }
  else if(SIZE_ARR <= s->top_index)
    {
      printf("Nothing to pop()\n");
    }
  else
    {
      struct elm* e = s->arr[s->top_index];
      free(e);
      ++(s->top_index);
    }

}

struct elm_stack* stack_init(void)
{
  int idx;
  struct elm_stack* p = malloc(1 * sizeof *p);
  if(NULL == p)
    {
      printf("IN: %s @%d: Out of Memory!\n", __FILE__, __LINE__);
    }
  else
    {
      p->top_index = SIZE_ARR;
      for(idx = 0; idx < SIZE_ARR; ++idx) p->arr[idx] = NULL;
    }

  return p;

}

struct elm* get_element(const char* c, int n)
{
  struct elm* p = malloc(1 * sizeof *p);

  if(NULL == p)
    {
      printf("IN:%s @%d: Out of Memory!\n", __FILE__, __LINE__);
    }
  else if(SIZE_NAME < strlen(c))
    {
      printf("IN: %s @ %d: ", __FILE__, __LINE__);
      printf("Name too big, Not adding element\n");
      free(p);
      p = NULL;
    }
  else
    {
      p->num = n;
      strcpy(p->name,c);
    }

  return p;

}

void print_stack(struct elm_stack* s)
{
  if(NULL == s)
    {
      printf("IN:%s @%d: Invalid Args!\n", __FILE__, __LINE__);
    }
  else
    {
      int idx = SIZE_ARR - 1;
      struct elm* e;
      /*printf("idx %d, top_index = %d\n", idx, s->top_index); */
      for(; (idx >= 0) && (idx >= s->top_index); --idx)
        {
          /*printf("idx %d, top_index = %d\n", idx, s->top_index);*/
          e = s->arr[idx];
          printf("%s = %d\n", e->name, e->num);
        }
    }

}

=================== OUTPUT ========================  
[arnuld@dune C]$ gcc -ansi -pedantic -Wall -Wextra lifo-array.c
[arnuld@dune C]$ ./a.out
comp = 2
lang = 1
c = 0
-----------------------------------------

comp = 2
lang = 1
-----------------------------------------

comp = 2
-----------------------------------------

[arnuld@dune C]$

--www.lispmachine.wordpress.com
find my email-ID @above blog

struct elm
{
int num;
char name[SIZE_NAME+1];

};

Do you really want to preallocate SIZE_NAME amount of char bytes in
advance in each element "elm" fo "name"? You can still control the
length of the data "name" by using strlen, strlcpy/strdup. You can use
a "char *" for "name". Though there will be couple function call
overhead and memory management of allocated memory.

 

[Rui Maciel]

Rui Maciel wrote:
) Willem wrote:
)
)> push() not taking a value makes some sense if you think that
)> expanding the stack and setting the top element should be
)> separate operations.
)
) What's the point of that, besides needlessly allocating memory that your
) program does not use?

What part of 'and setting the top element' do you not understand ?

I don't understand how you use the word "separately" without understanding
what it means. If you understood what it meant then you would understand
that, in a scenario where "expanding the stack and setting the top element"
are separate operations, the "expanding the stack" bit involves allocating
memory and nothing more, without having the faintest guarantee that your
program will ever use that memory or even initialize the memory it
allocates.

So, while the push(value) approach guarantees that whenever you call
push(value) your program always initializes the memory which is allocated,
if you set your push() to do nothing more than allocate memory, then you
only gain a way to needlessly allocate memory to your stack which you may or
may not use. By doing this, your push() represents an excellent way to
needlessly fill a stack with uninitialized variables, which is a frequent
cause of countless bugs, including security vulnerabilities.

But I will make it easy for you: top() returns an lvalue, which can
be used to both read and set the top element.

Tweaking push() has absolutely no impacto on what top() does. So, this is a
non-issue.

)> pop() without a return value would have to discard the value it
)> takes from the stack.
)
) Well. that's the point of pop(). You store your data with push(), you
) access the data with top() and you discard your data with pop().

Do you know what "begging the question" means ?

Here's an example for you:

The point of pop() is to give you the top element of the stack.

No, it is not. That's what top() is designed to do. Do you even know what
a stack is?

So there's no point in having a separate top() operation.

For you to make such a claim then it becomes quite clear that you never used
a stack. If you are interested in learning why is there a need to top()
without pop()ing the stack then be my guest and write a small LL parser
using a stack to store the parser states and try to do that without calling
top().


Rui Maciel

 

[luser- -droog]

WANTED:  To write an array implementation of Stack.
WHAT I GOT:  It works fine.

I think program is still little too complex. Any ideas to improve ?

FWIW, here's my own crazy implementation of a stack.
I think I may have out-"over-complicated" you.
The complexity supports the ability for stacks to
grow while maintaining access times at a fixed divisor
of linear to size. To do this the stack is "segmented"
in a linked list of tables (arrays). The segment size
is set small (10) for testing and maybe increased later
when fine-tuning the application performance (ie. optimizing).

It uses two routines from another module that I won't bore
you with. They simply allocate and free objects from the
memory pool. All objects are refered to by integer offsets
from the base of the memory pool so the pool itself can
move (via realloc or mremap).

For now you don't need to see the object type either, just
think of it as a 64bit integer like the comment suggest
(this was the definition used while building the module).
But in main() where the objects are initialized you can
see that it's a union of structs. For these tests, it just
holds an integer in the "integer value" slot, so it's really
an extraneous detail that I should stop dwelling upon very
soon.

The API squarely follows the notion that push() and pop()
are 'transitive verbs', ie. you must push or pop *something*.

unsigned initstack(mfile *mem); /* return "address" in the pool */
void pr_stack(mfile *mem, unsigned stackadr); /* debugging dump */
void sfree(mfile *mem, unsigned stackadr); /* free all linked segments
*/
unsigned count(mfile *mem, unsigned stackadr); /* how big is the stack
now? */
void push(mfile *mem, unsigned stackadr, object o);
object top(mfile *mem, unsigned stackadr, integer i); /* index from
top->down */
object pop(mfile *mem, unsigned stackadr);

One problem I haven't yet solved is top() is limited to indexing
only from the top 2 linked segments of a stack. At some point I
plan to modify this code to work with variable-sized segments
as part of a compacting garbage collecting scheme, but for now
the segment sizes are fixed

And here's the lovely code dump.
Any and all comments appreciated.
(please trim code unless commenting upon it directly;
for the convenience of readers, only)

/* s.c - a segmented, extendable stack */
//#define TESTMODULE

#include <stdlib.h> /* NULL */
#include "m.h" /* mfile mfalloc findtabent */

#include "ob.h" /* object size */
/*typedef long long object;*/

#include "s.h"
/*#define STACKSEGSZ 10*/

/*
typedef struct {
unsigned nextseg;
unsigned top;
object data[STACKSEGSZ];
} stack;
*/

unsigned initstack(mfile *mem) {
unsigned adr = mfalloc(mem, sizeof(stack));
stack *s = (void *)(mem->base + adr);
s->nextseg = 0;
s->top = 0;
return adr;
}

void pr_stack(mfile *mem, unsigned stackadr) {
stack *s = (void *)(mem->base + stackadr);
int i;
while(1) {
for (i=0; i < s->top; i++) {
pr_obj(s->data);
}
if (i != STACKSEGSZ) break;
s = (void *)(mem->base + s->nextseg);
}
}

void sfree(mfile *mem, unsigned stackadr) {
stack *s = (void *)(mem->base + stackadr);
if (s->nextseg) sfree(mem, s->nextseg);
mtab *tab;
unsigned e = mtalloc(mem, 0, 0);
findtabent(mem, &tab, &e);
tab->tab[e].adr = stackadr;
tab->tab[e].sz = sizeof(stack);
}

unsigned count(mfile *mem, unsigned stackadr) {
stack *s = (void *)(mem->base + stackadr);
unsigned ct = 0;
while (s->top == STACKSEGSZ) {
ct += STACKSEGSZ;
s = (void *)(mem->base + s->nextseg);
}
return ct + s->top;
}

void push(mfile *mem, unsigned stackadr, object o) {
stack *s = (void *)(mem->base + stackadr); /* load the stack */

while (s->top == STACKSEGSZ) { /* find top segment */
s = (void *)(mem->base + s->nextseg);
}

s->data[s->top++] = o; /* push value */

/* if push maxxed the topmost segment, link a new one */
if (s->top == STACKSEGSZ)
if (s->nextseg == 0)
s->nextseg = initstack(mem);
}

/* index the stack from top-down */
object top(mfile *mem, unsigned stackadr, integer i) {
stack *s = (void *)(mem->base + stackadr);
stack *p = NULL;

/* find top segment */
while (s->top == STACKSEGSZ) {
p = s;
s = (void *)(mem->base + stackadr);
}
if (s->top == 0) {
if (p != NULL)
s = p;
else
error("stack underflow");
}
return s->data[s->top-1-i];
}

object pop(mfile *mem, unsigned stackadr) {
stack *s = (void *)(mem->base + stackadr); /* load the stack */
stack *p = NULL;

while (s->top == STACKSEGSZ) { /* find top segment */
p = s;
s = (void *)(mem->base + s->nextseg);
}
if (s->top == 0) {
if (p != NULL)
s = p; /* back up if top is empty */
else
error("stack underflow");
}

return s->data[--s->top]; /* pop value */
}

#ifdef TESTMODULE

#include <stdio.h>
#include <unistd.h>

mfile mem;
unsigned s, t;

/* initialize everything */
void init(void) {
pgsz = getpagesize();
initmem(&mem);
s = initstack(&mem);
t = initstack(&mem);
}

/* destroy everything */
void xit(void) {
exitmem(&mem);
}

int main() {
init();

printf("test stack by reversing a sequence\n");
object a = { .int_.val = 2 }, b = { .int_.val = 12 }, c =
{ .int_.val = 0xF00 };
object x,y,z;

push(&mem, s, a);
push(&mem, s, b);
push(&mem, s, c);

x = pop(&mem, s); /* x = c */
push(&mem, t, x);
y = pop(&mem, s); /* y = b */
push(&mem, t, y);
z = pop(&mem, s); /* z = a */
push(&mem, t, z);
printf("x = %d, y = %d, z = %d\n", x.int_.val, y.int_.val,
z.int_.val);

x = pop(&mem, t); /* x = a */
y = pop(&mem, t); /* y = b */
z = pop(&mem, t); /* z = c */
printf("x = %d, y = %d, z = %d\n", x.int_.val, y.int_.val,
z.int_.val);
//z = pop(&mem, t);

xit();
return 0;
}

#endif

 

[Willem]

Rui Maciel wrote:
) in a scenario where "expanding the stack and setting the top element"
) are separate operations, the "expanding the stack" bit involves allocating
) memory and nothing more, without having the faintest guarantee that your
) program will ever use that memory or even initialize the memory it
) allocates.

Yes, and ?

) if you set your push() to do nothing more than allocate memory, then you
) only gain a way to needlessly allocate memory to your stack which you may or
) may not use.

You're contradicting yourself. It's only needless if you don't use it.

)> )> pop() without a return value would have to discard the value it
)> )> takes from the stack.
)> )
)> ) Well. that's the point of pop(). You store your data with push(), you
)> ) access the data with top() and you discard your data with pop().
)>
)> Do you know what "begging the question" means ?
)>
)> Here's an example for you:
^^^^^^^^^^^^^^^^^^^^^^^^^^

Are you really too stupid to read properly ?

)> The point of pop() is to give you the top element of the stack.
)
) No, it is not. That's what top() is designed to do. Do you even know what
) a stack is?

BEGGING THE QUESTION AGAIN.
We're arguing about what the different stack operations should do.
So using "it's defined to do that" is begging the question.

There, I hope I spelled it out for you enough.

)> So there's no point in having a separate top() operation.
)
) For you to make such a claim then it becomes quite clear that you never used
) a stack.

You're an idiot too, dear.


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT