Dynamic stack C implementation

Question

I'm a C beginner. I'm studying and implementing some data structures. I'd like to get feedback.

This is a stack implemented with an dynamic array.

In main there is some test code which use a basic testing function.

INITIAL_CAPACITY is set to 1 to "stress test" the API.

All the code is in one file because I'd like to store all these implementations in single files (as snippets) for future reference, this is also the reason why not all the #includes are at the top: only those strictly necessary for the implementation are at the beginning.

/*
 * Dynamic stack, C implementation.
 *
 * Simple stack implementation with a dynamic array: the array doubles its
 * capacity if the stack is full, halves its capacity if the stack is full for a
 * quarter.
 */


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

#define INITIAL_CAPACITY 1

typedef struct
{
        unsigned int capacity;
        unsigned int top;
        int *items;
} dstack;

/*
 * create_stack:  creates and return a (pointer to a) new empty dynamic stack.
 *                Dies if fails.
 */
dstack *create_stack(void);

/*
 * size:  return the number of items stored in stack.
 */
unsigned int size(const dstack *stack);

/*
 * is_empty:  return true if stack does not contains items, false otherwise.
 */
bool is_empty(const dstack *stack);

/*
 * peek:  return (but does not remove) the last item added to stack.
 */
int peek(dstack *stack);

/*
 * push:  adds item to stack.
 */
void push(dstack *stack, int item);

/*
 * pop:  removes and returns the last item added to stack.
 *       Dies if stack is empty.
 */
int pop(dstack *stack);

/*
 * resize_stack:  changes stack total capacity to new_capacity.
 *                Dies if fails.
 */
static void resize_stack(dstack *stack, unsigned int new_capacity);

/*
 * free_stack:  frees the memory occupied by stack.
 */
void free_stack(dstack *stack);

/*
 * die:  prints message on stderr and calls exit(EXIT_FAILURE).
 */
static void die(const char *message);


dstack *create_stack(void)
{
        dstack *new_stack = malloc(sizeof(*new_stack));

        if (new_stack == NULL) {
                die("stack creation failed");
        }
        new_stack->capacity = 0;
        new_stack->top = 0;
        new_stack->items = NULL;
        resize_stack(new_stack, INITIAL_CAPACITY);

        return new_stack;
}

unsigned int size(const dstack *stack)
{
        return stack->top;
}

bool is_empty(const dstack *stack)
{
        return stack->top == 0;
}

int peek(dstack *stack)
{
        if (is_empty(stack)) {
                free_stack(stack);
                die("attempt to peek from an empty stack");
        }
        return stack->items[stack->top - 1];
}

void push(dstack *stack, int item)
{
        if (stack->top == stack->capacity) {
                resize_stack(stack, 2 * stack->capacity);
        }
        stack->items[stack->top++] = item;
}

int pop(dstack *stack)
{
        if (is_empty(stack)) {
                free_stack(stack);
                die("attempt to pop from an empty stack");
        }
        int item = stack->items[--stack->top];

        if (stack->top > 0 && stack->top == stack->capacity / 4) {
                resize_stack(stack, stack->capacity / 2);
        }
        return item;
}

static void resize_stack(dstack *stack, unsigned int new_capacity)
{
        void *new_pointer = realloc(stack->items,
                                    sizeof(*(stack->items)) * new_capacity);
        if (new_pointer == NULL) {
                free_stack(stack);
                die("array resize failed");
        }
        stack->items = new_pointer;
        stack->capacity = new_capacity;
}

void free_stack(dstack *stack)
{
        free(stack->items);
        free(stack);
}

static void die(const char *message)
{
        fputs("Error: stack: ", stderr);
        fputs(message, stderr);
        puts("");
        exit(EXIT_FAILURE);
}


#include <assert.h>


static void loop_test(dstack *stack, unsigned int n)
{
        assert(size(stack) == 0);
        assert(is_empty(stack));

        for (int i = 0; i < n; i++) {
                push(stack, i);
                assert(peek(stack) == i);
        }
        assert(size(stack) == n);
        if (n > 0) {
                assert( ! is_empty(stack));
        }

        for (int i = n - 1; i >= 0; i--) {
                assert(peek(stack) == i);
                assert(pop(stack) == i);
        }
        assert(size(stack) == 0);
        assert(is_empty(stack));
}

int main(void)
{
        dstack *s = create_stack();

        loop_test(s, 0);
        loop_test(s, 1);
        loop_test(s, 10);
        loop_test(s, 100);
        loop_test(s, 1000);
        loop_test(s, 10000);

        push(s, 'k');
        push(s, 'o');
        push(s, ' ');
        push(s, 't');
        push(s, 's');
        push(s, 'e');
        push(s, 't');

        while ( ! is_empty(s)) {
                printf("%c", pop(s));
        }
        puts("");

        free_stack(s);
}

Answer 1

So you have build a dynamic size stack containing integers, and you guarantee that the allocated size if a power of 2 and the used size is between the allocated size and its quarter.

This automatic down-resizing of the stack is a rather uncommon requirement, so you should think twice before implementing it in real world code, but it is not really the point.

You have consistently declared and commented your functions, so it could be used as a nice .h file. Good point.

You code gave me one warning in loop test at for (int i = 0; i < n; i++) { ... because n is unsigned. While generally harmless, this kind of warning should be avoided because it can lead to undefined result. So here, you really should use for (unsigned int i = 0; i < n; i++) {.... In fact size_t should be even more appropriate, both for i and n.

In resize_stack, you use an unnecessary void * new_pointer where you could directly use stack->items. Not really expensive (only wastes a void *) but IMHO it does not really make the code more clear nor more maintainable.

But I strongly urge you not to use a die function for error processing in an utility library. I did it (I was a beginner too...) once, and the library was later used in a program that had its standard output connected to the equivalent of /dev/null and a special logging library. As you can imagine, the program sometimes was stopping with no message in the log system and this took some time to be identified because everybody had forgotten the ugly die.

So if this should be an utility library, please use an error code and let the caller do the error processing. For the same reason, I would not destroy the stack on error: let the caller decide whether the error is really a fatal one. That is just an application of the general separation of concerns rule.