Generic fixed-size Stack implementation in C

Question

Coming mostly from C#/Java background, I'm trying to implement a simple fixed-size stack data structure in C. The main concern about the "fixed-size" part is that pushing new elements to a full stack will make the stack remove the bottom-most element in it, keeping it with a maximum capacity.

I chose implement it using a circular array, so FSAStack is Fixed-Size-Array-Stack.

FSAStack.h

#ifndef FSASTACK_H_
#define FSASTACK_H_

#include <stdlib.h>
#include <stddef.h>


typedef struct FSAStack_t FSAStack;

/**
 * Create new FSAStack instance.
 * @param   capacity    -   max capacity for current instance
 * @param   elementSize -   element size of each data to be added
 * @return  NULL if malloc failed
 *          FSAStack* instance otherwise
 */
FSAStack* FSAStack_Create(unsigned int capacity, size_t elementSize);

/**
 * Free all resources for a given FSAStack instance.
 * @param   stack       -   the instance to destroy
 */
void FSAStack_Destroy(FSAStack* stack);

/**
 * Signal if a given FSAStack instance has reached its capacity.
 * @param   stack       -   FSAStack instance
 * @return  0 if stack == NULL or stack is not full
 *          1 if stack is full
 */
int FSAStack_IsFull(const FSAStack* stack);

/**
 * Signal if a given FSAStack instance has no elements.
 * @param   stack       -   FSAStack instance
 * @return  0 if stack == NULL or stack is not empty
 *          1 if stack is full
 */
int FSAStack_IsEmpty(const FSAStack* stack);

/**
 * Push a given element to a given FSAStack instance.
 * Override bottom-most element if the stack is full.
 * Does nothing if stack == NULL.
 * @param   stack       -   FSAStack instance
 * @params  data        -   the data to be pushed, of size elementSize
 */
void FSAStack_Push(FSAStack* stack, void *data);

/**
 * Pop the top-most element of the fiven FSAStack instance.
 * @param   stack       -   FSAStack instance
 * @return  NULL if stack == NULL or stack is empty
 *          top-most element otherwise
 */
void* FSAStack_Pop(FSAStack* stack);


#endif

FSAStack.c

#include "FSAStack.h"


struct FSAStack_t {
    void **elements;
    size_t elementSize;
    unsigned int capacity;
    unsigned int startIndex;
    unsigned int size;
};


FSAStack* FSAStack_Create(unsigned int capacity, size_t elementSize) {
    FSAStack *stack = malloc(sizeof(FSAStack));
    if (!stack) return NULL;
    stack->elementSize = elementSize;
    stack->capacity = capacity;
    stack->startIndex = stack->size = 0;
    stack->elements = malloc(elementSize * capacity);
    if (!stack->elements) {
        FSAStack_Destroy(stack);
        return NULL;
    }
    return stack;
}

void FSAStack_Destroy(FSAStack* stack) {
    if (!stack) return;
    if (stack->elements) free(stack->elements);
    free(stack);
}

int FSAStack_IsFull(const FSAStack* stack) {
    if (!stack) return 0;
    return stack->size == stack->capacity;
}

int FSAStack_IsEmpty(const FSAStack* stack) {
    if (!stack) return 0;
    return stack->size == 0;
}

void FSAStack_Push(FSAStack* stack, void *data) {
    if (!stack) return;
    stack->elements[(stack->startIndex + stack->size) % stack->capacity] = data;
    if (FSAStack_IsFull(stack)) {
        stack->startIndex = (stack->startIndex + 1) % stack->capacity;
    } else {
        stack->size++;
    }
}

void* FSAStack_Pop(FSAStack* stack) {
    if (!stack || FSAStack_IsEmpty(stack)) return NULL;
    stack->size--;
    return stack->elements[(stack->startIndex + stack->size) % stack->capacity];
}

One Question

To create a stack of ints I'm doing:

FSAStack *stack = FSAStack_Create(3, sizeof(int));
FSAStack_Push(stack, (void *)1);
FSAStack_Push(stack, (void *)2);

But then to retrieve them I'm doing (int)(long)FSAStack_Pop(stack);, as casting straight to int yields an error: cast from pointer to integer of different size [-Werror=pointer-to-int-cast]. Is there a better way of doing that?

Besides that, I'm mostly concerned about the following things:

• Readability. The intent of every piece of code must be clear to the reader.
• Correctness. Everything is working as it should (I think it's clear what should happen).
• Universality. The data structure is capable to hold any kind of data.
• Portability. The data structure doesn't break on specific machines.
• Performance. What can be done to improve the performance of this code?

Thank You.

Answer 1

I started writing a comment, but it turned out too long. This is a comment on how you call your functions, rather than the functions themselves.

Your pop method returns a pointer. You need to cast it to a pointer of the type you pushed on the stack, then deterrence it: *(int*)pop().

Note that you have no way of knowing this type unless you always store elements of the same type. If you want to store heterogeneous types, you need to add a field that specifies the type (maybe an enum?). Note also that casting to a pointer of the wrong type is UB, and can lead to bad data at best, out-of-bounds reads and crashes at worst.

Likewise, when you push an element, you are casting an int to a void*. This is legal but meaningless. You mean to cast its address, I guess: push(&value) (the cast to void* is then implicit).

When doing so, make sure that the variable you're storing won't go out of scope before you pop it from the stack.

Alternatively, you might want to allocate memory to hold your value:

void* p = malloc(sizeof(int));
/* test p != NULL */
*(int*)p = 1;
push(p);

Now your stack "owns" the newly allocated memory until it's popped. When you pop you resume ownership, and must delete it after using the value:

int* p = (int*)pop();
/* compute using *p */
free(p);

All of this would be easier if you created the stack to hold elements of a specific type. If you're only going to hold ints, store them directly rather than a pointer to the value, so you don't need to worry about memory management outside of your stack.

---

Reading your actual functions, note that stack->elementSize should always be set to sizeof(void*), because that is what you store.

Maybe you are intending something different: maybe you want to store copies of things that are always the same size? If so, the assignment inside your push method should be a memcpy instead. Copy elementSize bytes into your stack. You still need to pass pointers to your data elements to the push function, but there is no transfer of ownership, so you can pass a pointer to a local variable. The value returned by pop is still a pointer, which needs to be cast to the right pointer type, but it points to data inside the stack, and should be copied out or used in some other way before pushing new data onto the stack (as it could be overwritten).

In this case, your stack has a char *elements instead of a void **elements member. That is, it has an array of bytes rather than an array of void pointers.