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);
}

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.

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.

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.