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 int
s 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.
void *
is a little weird. Typically you should make the data elementsvoid *
if they are going to hold pointers to different kinds of things. Since the data you want to store isint
you could make the data elementsint
or you couldmalloc
space for each one andfree
when you discard. \$\endgroup\$int
is just a certain weirdness I stumbled upon which won't occur when I'll store structs, or other non-simple data types. Please correct me if I'm wrong here. \$\endgroup\$