Generic stack in C

Question

I tried to implement a generic stack in C using void pointers and tried to keep it as simple as possible by delegating all responsibility to the caller of the functions and avoiding more sophisticated approaches.

stack.h

#ifndef STACK_H
#define STACK_H
#include <stdbool.h>
struct Stack {
 void *data;
 struct Stack *next;
};
/*
 * We declare a pointer to a Stack structure thereby making use of incomplete
 * types. Clients that pull in stack.h will be able to declare variables of type
 * pstack which are pointers to pointers to Stack structures.
 * */
typedef struct Stack *pstack;
bool is_empty(pstack *s);
void make_empty(pstack *s);
void push(struct Stack **s, void *new_num);
void *pop(pstack *s);
#endif /* STACK_H */

stack.c

#include <stdio.h>
#include <stdlib.h>
#include "stack.h"
bool is_empty(pstack *s) { return !s; }
void make_empty(pstack *s)
{
 if (!is_empty(s))
 pop(s);
}
void *pop(pstack *s)
{
 struct Stack *tmp;
 void *i;
 if (is_empty(s))
 exit(EXIT_FAILURE);
 tmp = *s;
 i = (*s)->data;
 *s = (*s)->next;
 free(tmp);
 return i;
}
void push(struct Stack **s, void *new_num)
{
 struct Stack *new_node = malloc(sizeof(struct Stack));
 if (!new_node)
 exit(EXIT_FAILURE);
 new_node->data = new_num;
 new_node->next = *s;
 *s = new_node;
}

stackclient.c

#include <stdio.h>
#include <stdlib.h>
#include "stack.h"
int main(void)
{
 pstack s1;
 void *n;
 int i = 1;
 int j = 2;
 push(&s1, &i);
 push(&s1, &j);
 n = pop(&s1);
 printf("Popped %d from s1\n", *((int *)n));
 n = pop(&s1);
 printf("Popped %d from s1\n", *((int *)n));
 exit(EXIT_SUCCESS);
}

• Xaqq: About naming convention: consider naming your function stack_* instead. Since this is C and there is no namespace this will reduce the chance of functions' names clash.

Answer 1

I see some things that may help you improve your code.

Use all required #includes

The stack.c file has #include <stdio.h> but it appears to me that no functions from it are needed. On the other hand, it uses the bool from stdbool.h but doesn't include it directly. One might argue (correctly!) that because it include stack.h that it's included indirectly, but I'd advocate that it's also in the implementation file so that it's obvious that the bool used there is the stdbool.h version.

Use const where practical

The is_empty function does not alter the stack, so that argument should express that notion by using the const keyword:

bool is_empty(const pstack *s) { return !s; }

Combine typedef and structure declaration

It's a common C idiom to combine the typedef and the stack declaration.

typedef struct Stack {
 void *data;
 struct Stack *next;
} *pstack;

This keeps them together which helps the reader of the code.

Don't misuse exit

The final statement in main currently is:

exit(EXIT_SUCCESS);

However, code to return EXIT_SUCCESS is automatically generated if the code reaches the end of main so this is not needed. Also, it may be more appropriate to return NULL instead of aborting the program with exit if too many pop operations are requested.

Consider object ownership

The stack only stores pointers, but does not "own" the objects to which those pointers point. This means that if you push pointers to stack objects with auto scope, the stack will contain invalid pointers if the underlying items go out of scope. An alternative would be to create a copy of the object and allow the stack to own them.

Don't rely on values not set

The pstack relies on the value being 0, (in is_empty and make_empty) but does not explicity set it to that (r any) value. If your code checks for a specific value, it should also set it.

• lord.garbage: Thanks! Where should I set the value to 0? Do you mean when I declare pstack s1 in main() by setting s1 = NULL at the beginning?
• Edward: Yes, set s1 = NULL at the beginning and also change to bool is_empty(pstack *s) { return s != NULL; }
• lord.garbage: What I basically did was to implement a create() and destroy() function: pstack create(void) {pstack s = malloc(sizeof(struct Stack)); if (!s) {exit(EXIT_FAILURE)}; s->next = NULL; return s;} and void destroy(pstack s) {free(s);};. Thanks for your help!
• Lundin: "Combine typedef and structure declaration" this is bad advise and suggests that you don't know the meaning of opaque type. I would remove this part of your otherwise good answer, as it is incorrect in the context of creating an opaque type ADT. "Consider object ownership" is related to this: the ADT allocates the objects, since it is impossible for the caller to do so: it cannot create an instance of an incomplete type!
• Edward: @Lundin: whether the typedef and struct declaration are on the same line or two different ones has no bearing on whether it's an opaque type or not.

Answer 2

/*
 * We declare a pointer to a Stack structure thereby making use of incomplete
 * types. Clients that pull in stack.h will be able to declare variables of type
 * pstack which are pointers to pointers to Stack structures.
 * */

Few problems here. First, a variable of type pstack is just a pointer to Stack structure, not pointer to pointer to as the comment claims. Second, you do not use incomplete type as intended: the client still sees the implementation of struct Stack, and any change in implementation would result in client code being recompiled for no reason. A standard way to deal with it is to leave

typedef struct Stack stack;

in the header file stack.h, and declare

struct Stack {
 ...
};

in the implementation file stack.c.

• lord.garbage: Cheers. I know that pstack is not a pointer to a pointer but when I declare in stack.c with pstack s1 then s1 will be a pointer to a pstack pointer would it not?
• vnp: A declaration pstack s1; declares a pointer to struct Stack. To get a pointer to a pstack pointer one would declare pstack ** s.
• lord.garbage: Then I'm confused as to why I need to pass &s1 to my functions instead of just s1. (That confused me before. An example is my push() function which I declared without the typedef by using void push(struct Stack **s, int new_num).)
• vnp: Your functions must modify the argument (the top of stack changes). In C the only way to modify an argument is to pass a pointer to it.
• lord.garbage: Ah, I got it.. The functions expect a pointer to a pointer but pstack is just a pointer. Hence I need to pass the address of the pstack pointer in order to get a pointer to a pointer in order to be able to modify the argument.

Answer 3

This is not a working program, you have several bugs. Also, the program design is not the correct way to implement opaque type.

Program design

• Opaque type should not be typedef:ed to a pointer type. In general, it is very bad practice to hide pointers behind typedefs because it severely reduces readability. Instead, typedef the opaque type as an incomplete struct. typedef struct stack_t stack_t;
• Opaque type means that the struct definition should not be visible to the caller, so it shouldn't be in the "public" header file! But rather in the "private" c file.
• True opaque type means that the ADT is responsible for allocating all objects, because the caller can't create an object of incomplete type. Therefore you need one create() function and one delete() function which create/delete objects of type stack_t.
• You probably want to keep track of the size of the data somehow, for example with a data size member in the struct.
• exit(EXIT_FAILURE); in the middle of a function is very questionable practice. Instead, you should implement your functions with a returned error code and let the caller worry about which action to take.

Bugs

• make_empty() doesn't empty the stack, as one may think by reading its name. The if(!is_empty(s)) needs to be while (!is_empty(s)).
• Which leads to the next bug, pop doesn't modify the pointer (it can't), so an empty pointer is never set to NULL anywhere.
• Somewhere the first/last next pointer must be set to NULL.

Stylistic details

• Minor issue: since struct tags and typedefs reside in different scopes (namespaces), you can use the same name for the struct tag and the typedef. Then the code turns less confusing to read.
• It is usually convention to name types stack_t. Depends on coding style. So in the h file you should have something like typedef struct stack_t stack_t;
• Read up on const correctness. Functions that don't modify a pointed-to object should have the pointer declared as pointer-to-const.
• Since the h file in the public documentation of what a c file does, it is best to put all #include in the h file, to show which dependencies your module has on other libraries.
• Do not use the boolean logic not ! operator to compare integers or pointers, it should only be used for boolean logic. Instead, checks against null for a pointer should be made explicit, s == NULL.
• Always use braces { } (aka "compound statements") after every single if or loop. People who don't do this will write bugs, sooner or later. See Apple's "goto fail" bug as one perfect example. I don't think the person who wrote that billion dollar bug was a rookie, but rather an arrogant veteran insisting on not using braces, for no good reason.
• Always return from main() even though C allows the return statement to safely be omitted.

• Edward: Why do you assume that an opaque type was a design goal?
• jacwah: This would be a gret answer if you went a bit more into the why?, especially in the style part were you make some controversial claims (return from main and dont' use !) without backing them up.
• Lundin: @Edward Because that's how you properly design C programs with private encapsulation. Why would I assume that the OP doesn't want a proper program design?
• Lundin: @jacwah Because ! is a boolean operator and for the sake of readability it should only be used on expressions that are "effectively boolean". Good C programmers program as if C had a real, type safe boolean type. Don't mix up booleans with integers or pointers. In any other programming language such things wouldn't even compile. References MISRA-C:2004, MISRA-C:2012 etc.
• lord.garbage: @Lundin, thanks. Though MISRA states that !x as advisory (Rule 13.2) and not required and only in the interest of clarity. It is such a common C idiom that I do not necessarily see a problem with this unless required by a specific coding style.