Stack using Array

[arnuld]

OBJECTIVE: To implement a stack (LIFO) using C array
WHAT I GOT: Segfault

I know there is something wrong with Line 73, where I add an element to
the array but what exactly is wrong I am not sure (except that a pointer
to pointer is being passed in function argument):



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

enum { VAL_FALSE = 0, VAL_TRUE = 1, SIZE_STACK = 10 };

struct myStruct
{
char* title;
};


struct myStack
{
int top;
};


void initialize(struct myStack s);
int stackEmpty(struct myStack s);
void push(struct myStruct* arr[], struct myStack s, const char* ele);


int main(void)
{
struct myStruct* sof[SIZE_STACK+1] = {0};
struct myStack s;

initialize(s);
stackEmpty(s);
push(sof, s, "CLC");

return 0;
}



int stackEmpty(struct myStack s)
{
if(s.top) return VAL_FALSE;

return VAL_TRUE;
}



void initialize(struct myStack s)
{
s.top = 0;
}


void push(struct myStruct* arr[], struct myStack s, const char* ele)
{
if(NULL == arr || NULL == ele)
{
fprintf(stderr, "IN: %s @%d: Invalid Args\n", __FILE__, __LINE__);
}
else if(SIZE_STACK <= s.top)
{
printf("Stack Full, Can not add anymore elements\n");
}
else
{
struct myStruct* p = malloc( 1 * sizeof *p);
if(NULL == p)
{
fprintf(stderr, "IN: %s @%d: Out of Memory\n", __FILE__,
__LINE__);
}
else
{
strcpy(p->title, ele);
arr[s.top] = p;
s.top += 1;
}
}
}

 

[Ike Naar]

void push(struct myStruct* arr[], struct myStack s, const char* ele)
{
if(NULL == arr || NULL == ele)
{
fprintf(stderr, "IN: %s @%d: Invalid Args\n", __FILE__, __LINE__);
}
else if(SIZE_STACK <= s.top)
{
printf("Stack Full, Can not add anymore elements\n");
}
else
{
struct myStruct* p = malloc( 1 * sizeof *p);

This allocates memory for a myStruct, but the contents
of that memory is still uninitialized;
In particular, p->title is still an uninitialized pointer.

if(NULL == p)
{
fprintf(stderr, "IN: %s @%d: Out of Memory\n", __FILE__,
__LINE__);
}
else
{
strcpy(p->title, ele);

p->title is still an uninitialized pointer.

arr[s.top] = p;
s.top += 1;
}
}
}

 

[David RF]

OBJECTIVE:  To implement a stack (LIFO) using C array
WHAT I GOT: Segfault

I know there is something wrong with Line 73, where I add an element to
the array but what exactly is wrong I am not sure (except that a pointer
to pointer is being passed in function argument):

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

enum { VAL_FALSE = 0, VAL_TRUE = 1, SIZE_STACK = 10 };

struct myStruct
{
  char* title;

};

struct myStack
{
  int top;

};

void initialize(struct myStack s);
int stackEmpty(struct myStack s);
void push(struct myStruct* arr[], struct myStack s, const char* ele);

int main(void)
{
  struct myStruct* sof[SIZE_STACK+1] = {0};
  struct myStack s;

  initialize(s);
  stackEmpty(s);
  push(sof, s, "CLC");

  return 0;

}

int stackEmpty(struct myStack s)
{
  if(s.top) return VAL_FALSE;

  return VAL_TRUE;

}

void initialize(struct myStack s)
{
  s.top = 0;

}

void push(struct myStruct* arr[], struct myStack s, const char* ele)
{
  if(NULL == arr || NULL == ele)
    {
      fprintf(stderr, "IN: %s @%d: Invalid Args\n", __FILE__, __LINE__);
    }
  else if(SIZE_STACK <= s.top)
    {
      printf("Stack Full, Can not add anymore elements\n");
    }
  else
    {
      struct myStruct* p = malloc( 1 * sizeof *p);
      if(NULL == p)
        {
          fprintf(stderr, "IN: %s @%d: Out of Memory\n", __FILE__,
__LINE__);
        }
      else
        {
          strcpy(p->title, ele);
          arr[s.top] = p;
          s.top += 1;
        }
    }

}

You forgot to assign space for title:

struct myStruct* p = malloc( 1 * sizeof *p);
p->title = malloc(4);
p->title[0] = '\0'; /* strcpy needs a terminating null character
*/

or just declare title with fixed length

struct myStruct
{
char title[4];

};

 

[arnuld]

This allocates memory for a myStruct, but the contents of that memory is
still uninitialized; In particular, p->title is still an uninitialized
pointer.

I already know this.

p->title is still an uninitialized pointer.

How does it matter to strcpy ? strpcy(dest, src) will overwrite all the
characters, whether its garbage or not. 'src' does contain '\0' in the
(as its a character string), which will be written to ..... Oh.. wait a
minute.. I got it. p->title must be an array rather than a dangling
pointer.

 

[David RF]

OBJECTIVE:  To implement a stack (LIFO) using C array
WHAT I GOT: Segfault

I know there is something wrong with Line 73, where I add an element to
the array but what exactly is wrong I am not sure (except that a pointer
to pointer is being passed in function argument):

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

enum { VAL_FALSE = 0, VAL_TRUE = 1, SIZE_STACK = 10 };

struct myStruct
{
  char* title;

};

struct myStack
{
  int top;

};

void initialize(struct myStack s);
int stackEmpty(struct myStack s);
void push(struct myStruct* arr[], struct myStack s, const char* ele);

int main(void)
{
  struct myStruct* sof[SIZE_STACK+1] = {0};
  struct myStack s;

  initialize(s);
  stackEmpty(s);
  push(sof, s, "CLC");

  return 0;

int stackEmpty(struct myStack s)
{
  if(s.top) return VAL_FALSE;

  return VAL_TRUE;

}

void initialize(struct myStack s)
{
  s.top = 0;

}

void push(struct myStruct* arr[], struct myStack s, const char* ele)
{
  if(NULL == arr || NULL == ele)
    {
      fprintf(stderr, "IN: %s @%d: Invalid Args\n", __FILE__, __LINE__);
    }
  else if(SIZE_STACK <= s.top)
    {
      printf("Stack Full, Can not add anymore elements\n");
    }
  else
    {
      struct myStruct* p = malloc( 1 * sizeof *p);
      if(NULL == p)
        {
          fprintf(stderr, "IN: %s @%d: Out of Memory\n", __FILE__,
__LINE__);
        }
      else
        {
          strcpy(p->title, ele);
          arr[s.top] = p;
          s.top += 1;
        }
    }

}

You forgot to assign space for title:

      struct myStruct* p = malloc( 1 * sizeof *p);
      p->title = malloc(4);
      p->title[0] = '\0'; /* strcpy needs a terminating null character
*/

or just declare title with fixed length

struct myStruct
{
  char title[4];

};

Please, forget this: /* strcpy needs a terminating null character */

 

[arnuld]

Here is the code that works. I just wrote it with whatever half-brain I
have . Is it really a stack implementation using array ?



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

enum { VAL_FALSE = 0, VAL_TRUE = 1, SIZE_STACK = 10, SIZE_TITLE = 10 };

struct myStruct
{
char title[SIZE_TITLE+1];
};


struct myStack
{
int top;
};


void initialize(struct myStack** s);
int stackEmpty(struct myStack* s);
void push(struct myStruct* arr[], struct myStack* s, const char* ele);
struct myStruct* pop(struct myStruct* arr[], struct myStack* s);
void stackDel(struct myStruct** arr, struct myStack* s);
void stackPrint(struct myStruct** arr, const struct myStack* s);
void stackPrintUsingPointers(struct myStruct** arr);


int main(void)
{
int is_empty;
struct myStruct* sof[SIZE_STACK+1] = {0};
struct myStack* s;
initialize(&s);
is_empty = stackEmpty(s);
printf("is_empty = %d\n", is_empty);

push(sof, s, "A");
push(sof, s, "B");
push(sof, s, "C");
is_empty = stackEmpty(s);
printf("is_empty = %d\n", is_empty);

push(sof, s, "C");
push(sof, s, "C");
push(sof, s, "A");
pop(sof, s);
is_empty = stackEmpty(s);
printf("is_empty = %d\n", is_empty);

printf("\n----------\n");
stackPrintUsingPointers(sof);
stackDel(sof, s);
is_empty = stackEmpty(s);
printf("is_empty = %d\n", is_empty);

return 0;
}



int stackEmpty(struct myStack* s)
{
if(s->top) return VAL_FALSE;

return VAL_TRUE;
}



void initialize(struct myStack** s)
{
*s = malloc(1 * sizeof *s);
if(NULL == *s)
{
fprintf(stderr, "IN: %s @%d: Out of Memory\n", __FILE__, __LINE__);
}
else
{
(*s)->top = 0;
}
}


void push(struct myStruct* arr[], struct myStack* s, const char* ele)
{
if(NULL == arr || NULL == s || NULL == ele)
{
fprintf(stderr, "IN: %s @%d: Invalid Args\n", __FILE__, __LINE__);
}
else if(SIZE_STACK <= s->top)
{
printf("Stack Full, top = %d, Can not add anymore elements\n", s-

top);

}
else
{
struct myStruct* p = malloc( 1 * sizeof *p);
if(NULL == p)
{
fprintf(stderr, "IN: %s @%d: Out of Memory\n", __FILE__,
__LINE__);
}
else
{
strcpy(p->title, ele);
arr[s->top] = p;
s->top += 1;
printf("Adding %s, top = %d\n", ele, s->top);
}
}
}


struct myStruct* pop(struct myStruct* arr[], struct myStack* s)
{
struct myStruct* ele;

if(NULL == arr || NULL == s)
{
fprintf(stderr,"IN: %s @%d: Invalid Args\n", __FILE__, __LINE__);
ele = NULL;
}
else
{
ele = arr[s->top - 1];
printf("Removing: %s\n", ele->title);
arr[s->top - 1] = '\0';
s->top -= 1;
}

return ele;
}


void stackDel(struct myStruct** arr, struct myStack* s)
{
if(arr && s)
{
int i;
struct myStruct* ele;
for(i = s->top - 1; i >= 0; --i)
{
ele = arr;
free(ele);
arr = NULL;
s->top -= 1;
}
}
}


void stackPrint(struct myStruct** arr, const struct myStack* s)
{
if(arr)
{
int i = s->top - 1;
for(; i >= 0; --i)
{
struct myStruct* ele = arr;
printf("title = %s\n", ele->title);
}
}
}



void stackPrintUsingPointers(struct myStruct** arr)
{
if(arr)
{
for(; *arr; ++arr)
{
struct myStruct* ele = *arr;
printf("title = %s\n", ele->title);
}
}
}
===================== OUTPUT ==========================
[arnuld@dune C]$ gcc -ansi -pedantic -Wall -Wextra stack-using-array.c
[arnuld@dune C]$ ./a.out
is_empty = 1
Adding A, top = 1
Adding B, top = 2
Adding C, top = 3
is_empty = 0
Adding C, top = 4
Adding C, top = 5
Adding A, top = 6
Removing: A
is_empty = 0

----------
title = A
title = B
title = C
title = C
title = C
is_empty = 1

 

[BartC]

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

struct myStack
{
int top;
};

void initialize(struct myStack** s);

void initialize(struct myStack** s)
{
*s = malloc(1 * sizeof *s);

You are good at making code far more complicated than is necessary!

Anyway, here, I'm not sure what's going on, as I'm not too adept at
following all these **s, but you seem to be allocating space for a pointer
which doesn't quite seem right.

Presumably you want to allocate space for an instance of myStack? Then
perhaps you want sizeof **s. (If you add some dummy elements to myStack so
that it's size doesn't coincide with both pointer width, and int width, then
it makes it easier to see if these numbers make sense when you print them
out..)

 

[arnuld]

You are good at making code far more complicated than is necessary!

ouch! ..

Anyway, here, I'm not sure what's going on, as I'm not too adept at
following all these **s, but you seem to be allocating space for a
pointer which doesn't quite seem right.

Presumably you want to allocate space for an instance of myStack? Then
perhaps you want sizeof **s.

Ah.. you are right. I needed this.

(If you add some dummy elements to myStack
so that it's size doesn't coincide with both pointer width, and int
width, then it makes it easier to see if these numbers make sense when
you print them out..)

I am not sure what you meant but I my best guess is: you want me to add
more elements to myStack structure so that I can see garbage printing out
because of the mistake I did. Right ?

 

[BartC]

ouch! ..

That just means I couldn't follow your code and resorted to nit-picking
fragments.

Which reminds me of this bit that was slightly puzzling:

struct myStack* s;

Even disregarding myStack only having four bytes or so, I wasn't sure why
this struct wasn't just statically allocated. Assuming you are only going to
have a small number of distinct stacks.

I am not sure what you meant but I my best guess is: you want me to add
more elements to myStack structure so that I can see garbage printing out
because of the mistake I did. Right ?

When I added this debug code, I just kept getting 4s, until I made myStack a
bit bigger. Then one of these gave the right answer!

printf("SIZE*s %d\n",1*sizeof *s);
printf("SIZE**s %d\n",1*sizeof **s);

 

[arnuld]

struct myStack* s;

Even disregarding myStack only having four bytes or so, I wasn't sure
why this struct wasn't just statically allocated. Assuming you are only
going to have a small number of distinct stacks.

Even after working for 2 years in C (not exclusively) my brain is still
clunky when it comes to C basics. This struct definition:


struct myStack
{
int top;
};


can be allocated statically ? I don't have the exact code (function
definition of initialize is 100% same as the code I posted) but I tried
using:

struct myStack s;
initialize(&s);

And all I got was garbage value in s.top.

When I added this debug code, I just kept getting 4s, until I made
myStack a bit bigger. Then one of these gave the right answer!

printf("SIZE*s %d\n",1*sizeof *s);
printf("SIZE**s %d\n",1*sizeof **s);

Let me ask again, you make myStack bigger by adding more elements to this
structure ? I still wonder what these 2 printf()s giving debug
information.

P.S. May be my mind is too much full of office work right now that I
can't understand anything. Will surely re-read it tomorrow.

 

[James Kuyper]

Even after working for 2 years in C (not exclusively) my brain is still
clunky when it comes to C basics. This struct definition:


struct myStack
{
int top;
};


can be allocated statically ?

An object of any complete type can be allocated statically. 'struct
myStack' is a complete type.

... I don't have the exact code (function
definition of initialize is 100% same as the code I posted) but I tried
using:

struct myStack s;
initialize(&s);

And all I got was garbage value in s.top.

Your definition of initialize was:

void initialize(struct myStack s)
{
s.top = 0;
}

With that definition, the expression initialize(&s) is a constraint
violation, because &s has the type 'struct myStack*', which is not
compatible with 'struct myStack', which is the type that initialize was
expecting for its argument. A conforming compiler is required to issue a
diagnostic message. Did yours?

However, even if you avoided that problem, your code still won't do what
you want it to do. I'm going to change your definition slightly, in
order to make it easier to explain what's wrong with it:

void initialize(struct myStack t)
{
t.top = 0;
}

With that definition, initialize(s) is perfectly valid code. It results
in the creation of an object named t, which is initialized by copying
the current value of s. Then t.top is set to 0. Then t is discarded. s
remains unchanged.

Here's what you should have done:

void initialize(struct myStack *ps)
{
ps->top = 0;
}

With that definition, initialize(&s) is perfectly valid code. &s
produces a pointer value pointing at s. Initialize sets aside memory to
store the pointer parameter ps, and initializes it with the value of &s.
It then goes to the struct myStack object pointed at by that pointer,
and sets the 'top' member to 0. In other words, it's equivalent to
(&s)->top = 0, or s.top = 0, which is what you want.

 

[James Kuyper]

Even after working for 2 years in C (not exclusively) my brain is still
clunky when it comes to C basics. This struct definition:


struct myStack
{
int top;
};


can be allocated statically ?

An object of any complete type can be allocated statically. 'struct
myStack' is a complete type.

... I don't have the exact code (function
definition of initialize is 100% same as the code I posted) but I tried
using:

struct myStack s;
initialize(&s);

And all I got was garbage value in s.top.

Your definition of initialize was:

void initialize(struct myStack s)
{
s.top = 0;
}

With that definition, the expression initialize(&s) is a constraint
violation, because &s has the type 'struct myStack*', which is not
compatible with 'struct myStack', which is the type that initialize was
expecting for its argument. A conforming compiler is required to issue a
diagnostic message. Did yours?

However, even if you avoided that problem, your code still won't do what
you want it to do. I'm going to change your definition slightly, in
order to make it easier to explain what's wrong with it:

void initialize(struct myStack t)
{
t.top = 0;
}

With that definition, initialize(s) is perfectly valid code. It results
in the creation of an object named t, which is initialized by copying
the current value of s. Then t.top is set to 0. Then t is discarded. s
remains unchanged.

Here's what you should have done:

void initialize(struct myStack *ps)
{
ps->top = 0;
}

With that definition, initialize(&s) is perfectly valid code. &s
produces a pointer value pointing at s. Initialize sets aside memory to
store the pointer parameter ps, and initializes it with the value of &s.
It then goes to the struct myStack object pointed at by that pointer,
and sets the 'top' member to 0. In other words, it's equivalent to
(&s)->top = 0, or s.top = 0, which is what you want.

 

[BartC]

Even after working for 2 years in C (not exclusively) my brain is still
clunky when it comes to C basics. This struct definition:


struct myStack
{
int top;
};


can be allocated statically ?

Yes. Write:

struct myStack s;

initialise(&s);

This function then simplifies to:

void initialise(myStack *s) { s->top = 0;}

But everywhere you used s before, you'll have to write &s. In practice, code
will be in functions, that will be passed myStack objects via pointers (as
in initialise() above), so you won't need & except in a few places.

Or you can do this:

struct myStack s0 = {0};
struct myStack *s = &s0;

initialise(s); /* Although not really needed anymore */

If you still want to keep myStack objects on the heap as you'd intended,
then it might be easier to write like this:

struct myStack *s;

s=createstack();

Which function might look like this, avoiding those double-pointers:

struct myStack* createstack(void) {
struct myStack *t;

t=malloc(sizeof struct myStack);
.... /* checks */
t->top = 0;
return t;
}

(I'm not fond of having to write 'struct' everywhere, so I would probably do
this:

typedef struct {int top;} myStack;

myStack s;

which saves some typing, and hides the fact that a stack object is described
with a struct.)

 

[Ben Bacarisse]

struct myStack s;

initialise(&s);

This function then simplifies to:

void initialise(myStack *s) { s->top = 0;}

But everywhere you used s before, you'll have to write &s. In practice, code
will be in functions, that will be passed myStack objects via pointers (as
in initialise() above), so you won't need & except in a few places.

Or you can do this:

struct myStack s0 = {0};
struct myStack *s = &s0;

initialise(s); /* Although not really needed anymore */

Another method is to define a one-element array:

struct myStack s[1] = {0};

and now you can use s rather than &s everywhere. I am not a fan of
this, but I've found it useful to know because other people do it.

Sometime (it's worse, I think) the array-ness is hidden in a typedef:

typedef struct myStack Stack[1];
// ...
Stack s = {0};
do_something(s, ...);

<snip>

 

[Edward A. Falk]

I'll point out a few obvious bugs:

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

enum { VAL_FALSE = 0, VAL_TRUE = 1, SIZE_STACK = 10 };

I guess this is legal, but a little confusing to have constants from
different contexts defined in the same enum. Simpler to do:

#define false 0
#define true 1
#define SIZE_STACK 10

struct myStack
{
int top;
};

OK, but why not collect the actual stack and stack pointer together
in one place:

struct myStack {
int top;
struct myStruct *sof[SIZE_STACK+1];
};

void initialize(struct myStack s);
int stackEmpty(struct myStack s);
void push(struct myStruct* arr[], struct myStack s, const char* ele);


int main(void)
{
struct myStruct* sof[SIZE_STACK+1] = {0};
struct myStack s;

initialize(s);

stackEmpty(s);

stackEmpty() has no side effects and you're ignoring its return
value, so why call it at all?

push(sof, s, "CLC");

Here's a problem. s is a struct, and you're passing it
by value into push(). It's technically legal, but poor form, as
I'll point out a little further down. Should really have been

push(sof, &s, "CLC");

return 0;
}



void initialize(struct myStack s)
{
s.top = 0;
}

Here's your first bug. You passed s by value, then modified
it. But you only modified a copy. The original is still
untouched, which means it's still uninitialized.

Should have passed by reference instead:

initialize(&s);
...
void initialize(struct myStack *s)
{
s->top = 0;
}

void push(struct myStruct* arr[], struct myStack s, const char* ele)

Second bug. Again, you're modifying a local copy of s, leaving the
original unchanged. Should have been:

void push (struct myStruct* arr[], struct myStack *s, const char *ele)

with all references to "s.top" changed to "s->top".

Finally, it would be better if push() returned a boolean value
indicating the the push had failed. Error messages are good,
but program detecting problems is better.

{
if(NULL == arr || NULL == ele)
{
fprintf(stderr, "IN: %s @%d: Invalid Args\n", __FILE__, __LINE__);
}
else if(SIZE_STACK <= s.top)
{
printf("Stack Full, Can not add anymore elements\n");
}
else
{
struct myStruct* p = malloc( 1 * sizeof *p);
if(NULL == p)
{
fprintf(stderr, "IN: %s @%d: Out of Memory\n", __FILE__,
__LINE__);
}
else
{
strcpy(p->title, ele);

Third bug. Here's your segfault. You're copying the data pointed to
by ele into the space pointed to by p->title, but you never allocated
any such space. p->title is uninitialized and the strcpy() is pretty
much guaranteed to fault.

Better would be to do:

p->title = strdup(ele);

plus a check to make sure that p->title isn't NULL.

arr[s.top] = p;
s.top += 1;
}
}
}

Try this on for size:

#define true 1
#define false 0
typedef bool int;

#define SIZE_STACE 10

typedef struct {
int top;
struct myStruct *stack[SIZE_STACK];
} MyStack;

void
initialize(MyStack *s)
{
s->top = 0;
}

bool
push(MyStack *s, const char *ele)
{
struct myStruct *p;
if (s == NULL || ele == NULL) {
fprintf(stderr, "invalid pointer, yada yada\n");
return false;
}
if (s->top >= SIZE_STACK) {
fprintf(stderr, "full stack, yada yada\n");
return false;
}
if ((p = malloc(sizeof(*p))) == NULL ||
(p->title = strdup(ele)) = NULL)
{
fprintf(stderr, "out of memory, yada yada\n");
return false;
}
s->stack[s->top++] = p;
return true;
}


There are other tweaks and improvements you could make, but they're
not imporant.

 

[Keith Thompson]

I already know this.




How does it matter to strcpy ? strpcy(dest, src) will overwrite all the
characters, whether its garbage or not.

strcpy() will overwrite the characters *that p->title points to*.

p->title doesn't point to garbage. p->title *is* garbage.

Remember that arguments are always passed by reference, so you're
passing the garbage *value* of p->title to strcpy.

'src' does contain '\0' in the
(as its a character string), which will be written to ..... Oh.. wait a
minute.. I got it. p->title must be an array rather than a dangling
pointer.

No, p->title is a pointer, not an array. It needs to point to the first
element of an array object.

 

[Keith Thompson]

And in C99, one can do this:

struct myStack *s = &(struct myStack) { 0 };

which I have found useful once or twice.

Remember that the lifetime of the object created by a compound literal
(if it's inside a function definition) is the nearest enclosing block.
(This is quite unlike the behavior of string literals.)