C pointer based growable stack

Question

This is my first attempt at writing a C program, it a generic stack that can grow accordingly. It appears to work correctly, however I am worried that is just a fluke and I could be doing something very wrong.

I would greatly appreciate any feedback/criticism.

I am aware I should split this out into a .h and .c file but for demonstration purposes I have listed it as one.

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

typedef struct Stack
{
    void** data;
    int capacity;
    int count;
} Stack;

void stack_init(Stack *stack, int capacity)
{
    stack->data = (void**)malloc(capacity * sizeof(void*));
    stack->capacity = capacity;
    stack->count = 0;
}

void stack_push(Stack *stack, void* entry)
{
    if (stack->count >= stack->capacity)
    {
        stack->capacity *= 2;
        stack->data = (void**)realloc(stack->data, stack->capacity * sizeof(void*));
    }

    stack->data[stack->count] = entry;
    stack->count++;
}

void* stack_pop(Stack *stack)
{
    stack->count--;
    return stack->data[stack->count];
}

bool stack_is_empty(Stack *stack)
{
    return (stack->count == 0);
}

int main()
{
    Stack myStack;

    stack_init(&myStack, 2);

    for (int i = 0; i < 2; i++)
    {
        stack_push(&myStack, i);
    }

    while (!stack_is_empty(&myStack))
    {
        printf("%d\n", (int)stack_pop(&myStack));
    }

    return 0;
}

Answer 1

I suggest that you do more error checking:

• malloc or realloc may fail.

• I can initialize the stack with negative capacity.

• I can pop more elements than I pushed.

In all these cases, your implementation silently swallows the errors and accesses invalid addresses.

As πάντα ῥεῖ said in comments, if you want to store generic elements that exceed void* in size, you need to allocate memory for them and let the void* point to them, e.g.:

typedef struct {
    // ...
} BigStruct;

// pushing
BigStruct* data = malloc(sizeof(BigStruct));
// initialize *data
stack_push(&stack, data);

// popping
BigStruct* data = stack_pop(&stack);
// use *data
free(data);

Some small issues:

• It is not common to cast the result of malloc or realloc in C.

• If the stack is initialized to capacity 0, then the stack will never grow and elements will be stored at invalid positions. A solution is to adjust the capacity to 1 automatically.

Answer 2

There are two main problems with the code that must be addressed:

• You store pointers to data in an array, rather than actual data. This is not useful, since pointers may point to data that goes out of scope or otherwise becomes obsolete. When writing a container class such as a stack/LIFO, one should store so-called "hard copies" of the data passed.

• The code is not valid C. You implicitly convert from an int which is data, to a void* which is a pointer. Details here: “Pointer from integer/integer from pointer without a cast” issues. To prevent non-C from compiling without errors then set gcc/clang/icc to always compile with -std=c11 -pedantic-errors.

  Apart from the implicit conversion itself being invalid, there is no guarantee that you can safely convert from int to void* and back even if you use a cast. This conversion relies on poorly specified behavior.

Because of these two remarks, the code cannot be fixed, it must be rewritten from scratch. To rewrite this into a proper stack container, it must be rewritten to use bytes of raw data (uint8_t) and make hard copies of the data passed.

---

Other remarks:

• When popping from the stack, check count to see if there actually are any items left!
• typedef struct Stack { ... } Stack; The "struct tag in this case is superfluous, you can just write typedef struct { ... } Stack;.
• int main() is an obsolete form of main() declaration, always use int main (void) instead (or the version with argv+argc).
• You don't use const correctness. Functions that do not change the passed Stack* should const qualify it: bool stack_is_empty(const Stack *stack).
• When storing the size of an array, the integer type size_t is more correct to use than int, since int may not be large enough and in addition it is signed.
• return (stack->count == 0); No parenthesis needed here, it's just clutter.
• (void**)malloc etc. No cast needed here, it's just clutter.
• When calling malloc and realloc, always check if they succeeded by checking the result against NULL. -Calling realloc repeatedly like this is inefficient. That's why a stack is usually implemented as a double linked linked list. You may not have learnt about these yet, but they are the most suitable way to implement containers that often add/remove items at the top or bottom, at the case of slower access time for items located at a random place inside the container. You will not use this stack like that, so a linked list would be more suitable.

Answer 3

Ease of clean-up

Consider a function to empty a Stack and free its allocated memory.

void stack_clean_up(Stack *stack) {
  free(stack->data);
  stack->data = NULL;
  stack->capacity = 0;
  stack->count = 0;
}


int foo() {
  Stack myStack;
  ....
  // Preceding code all done, time to clean up
  stack_clean_up(&myStack);
  return 0;
}