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

• πάντα ῥεῖ: Check the warnings here. Passing integers around as casted pointers is probably not what you want there.
• πάντα ῥεῖ: Hint: If you'll try this with other data types like double or any kind of struct this code will fail spectacularly.. What you're doing is wrong. void* looses any type information, including the size of the original type. Thus sizeof(void*) for allocation is futile from the beginning. You're allocating space for a pointer size.
• L. F.: @πάνταῥεῖ I guess OP is reusing the void* space to store an int under the assumption that sizeof(int) <= sizeof(void*). The practice of (ab)using the generic void* data itself to store the value instead of pointing to an external data block (and thus worrying about lifetime) is common in C.
• πάντα ῥεῖ: @L.F. I guess that the OP tries to store generic data types in the stack, and fundamentally failed to do that correctly. "store the value instead of pointing to an external data block (and thus worrying about lifetime) is common in C." That's not necessary if you want to handle int values only, and makes the stack interface quite confusing.
• Sᴀᴍ Onᴇᴌᴀ: Welcome to Code Review! Please see What to do when someone answers. I have rolled back Rev 2 → 1

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.

• L. F.: "Calling realloc repeatedly like this is very 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." Hmm ... C++ vectors do this, and usually outperform linked lists. Am I missing something special about realloc?
• Toby Speight: C++ vectors usually outperform linked lists, but it does depend on the access patterns. I expect the optimum data structure for a stack is more like a rope: a linked list of chunks; each chunk big enough to accommodate a decent number of items. No reallocation, but very few allocations, and very little pointer chaining.
• Lundin: @L.F. realloc or heap allocation in general is slow. Therefore, the implementation of std::vector uses an allocation scheme along the lines of: "allocate align * n bytes upon creation, when running out of memory reallocate align * 2n", doubling the size each time. This reduces the amount of calls. Similar algorithms are often used in C too when designing a string ADT or whatever. Of course a std::vector or any array outperforms a linked list in access time, since it has random access. Arrays vs linked lists is very basic computer science stuff.
• L. F.: Isn't OP doing what you are describing? stack->capacity *= 2; Also don't forget that linked lists have space implications.
• JiK: @Lundin Wouldn't linked list perform even worse for lots of pushing and popping, since you need to allocate memory from heap for every push, even if you are not reaching a new maximum size?

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

• NoOdle: Thanks, on my second revision I did add one like this. codereview.stackexchange.com/questions/238380/…