A generic/polymorphic stack implementation in plain C
I rather enjoy generic data structures in object oriented languages. After programming in an object oriented language for a while I decided to re-fresh some of my C skills by attempting to implement a generic stack in C.
Do you think you could achieve type safety within a generic data structure in C (without pre-processing commands or compiler specific checks like GCC's typeof() etc. ?). How would you implement a generic data structure such as a stack in C?
I toyed around for a little while and whipped up some code. Valgrind shows no memory loss so I think it's safe. I can't be quite sure though. I haven't done a lot of testing with it and it is by no means perfect. It doesn't guarantee any type safety and error handling is very basic since I was messing around. Not to mention the biggest annoyance is it doesn't support literals.
Do you think such constructs would be useful in plain C? or, does the type safety of a type specific data structure appeal more to you?
This is a pretty interesting topic and fun to mess around with. The Linux kernel code has some generic data structures done up using some pretty complex pre-processor commands and compiler tricks. It's pretty amazing what you can do~
cstacks.h
Code:
#ifndef CSTACKS_H_
#define CSTACKS_H_
#include <stdio.h>
#include <stdlib.h> /* malloc */
#include <strings.h> /* bcopy */
typedef struct Stack Stack;
struct Stack{
int counter;
int max;
void** container;
};
/***
* newStack - allocates space and sets up stack
* @size: the desired default container size (5 minimum)
*
**/
Stack* newStack(int size);
/***
* freeStack - frees container and stack memory
* @stack: target stack
*
**/
void freeStack(Stack* stack);
/***
* getSize - returns current stack counter position
* @stack: target stack
*
**/
int getSize(Stack* stack);
/***
* getMax - returns the current max stack size
* @stack: target stack
*
**/
int getMax(Stack* stack);
/***
* isEmpty - returns 1 if stack is empty, 0 if not
* @stack: target stack
*
**/
int isEmpty(Stack* stack);
/***
* resizeContainer - expands container to 2*max
* @stack: target stack
*
**/
void** resizeContainer(Stack* stack);
/***
* trace - prints the current stack layout
* @stack: target stack
*
**/
void trace(Stack* stack);
/***
* search - searches for value in stack and returns index of the found value
* or returns -1 if not found.
* @value: target value
* @stack: target stack
*
**/
int search(void* value, Stack* stack);
/***
* peek - returns top of the stack without removing it
* @stack: target stack
*
**/
void* peek(Stack* stack);
/***
* push - pushes an item onto a stack
* @item: target item
* @stack: target stack
*
**/
void push(void* item, Stack* stack);
/***
* pop - pops an item off the top of the target stack
* @stack: target stack
*
**/
void* pop(Stack* stack);
#endif /* CSTACKS_H_ */
cstacks.c
Code:
#include "cstacks.h"
Stack* newStack(int size){
/* NYI: better error checks */
if (size < 5){
size = 5;
}
Stack* stack = malloc(sizeof(Stack));
stack->container = malloc(sizeof(void**) * size);
stack->counter = 0;
stack->max = size;
return stack;
}
void freeStack(Stack* stack){
free(stack->container);
free(stack);
}
int getSize(Stack* stack){
return stack->counter;
}
int getMax(Stack* stack){
return stack->max;
}
int isEmpty(Stack* stack){
if(stack->counter == 0)
return 1;
return 0;
}
void** resizeContainer(Stack* stack){
/* NYI: error checks */
void** tmpContainer = malloc(sizeof(void**) * stack->max * 2);
bcopy(stack->container, tmpContainer, sizeof(void**)*stack->max);
stack->max *= 2;
return tmpContainer;
}
void trace(Stack* stack){
int i;
for(i = stack->counter - 1; i >= 0; i--)
printf("%d: %p \n", i, stack->container[i]);
}
int search(void* value, Stack* stack){
int i;
for(i = stack->counter - 1; i >= 0; i--){
if(stack->container[i] == value)
return i;
}
return -1;
}
void* peek(Stack* stack){
if (stack->counter > 0){
return stack->container[stack->counter - 1];
}
fprintf(stderr, "stack counter is 0... can't peek an empty stack.");
return NULL;
}
void push(void* item, Stack* stack){
if (stack->counter == stack->max)
stack->container = resizeContainer(stack);
stack->container[stack->counter] = item;
stack->counter++;
}
void* pop(Stack* stack){
if (stack->counter > 0){
stack->counter--;
return stack->container[stack->counter];
}
fprintf(stderr, "stack counter is 0... can't pop an empty stack.");
return NULL;
}
basictesting.c
Code:
#include <stdio.h>
#include "cstacks.h"
int main(void) {
Stack* intStack = newStack(10);
int x = 100, y = 200, z = 300;
if(isEmpty(intStack)){
printf("The stack is empty.\n");
} else {
printf("The stack is not empty.\n");
}
push(&x, intStack);
push(&y, intStack);
push(&z, intStack);
if(isEmpty(intStack)){
printf("The stack is empty.\n");
} else {
printf("The stack is not empty.\n");
}
trace(intStack);
printf("\nPopping %d\n", *(int*)pop(intStack));
printf("\nPopping %d\n", *(int*)pop(intStack));
printf("\nPopping %d\n", *(int*)pop(intStack));
Stack* stringStack = newStack(4);
char* hello = "Hello world!";
char* goodbye = "Goodbye cruel world!";
push(hello, stringStack);
push(goodbye, stringStack);
printf("We popped: %s\n", (char*)pop(stringStack));
printf("We popped: %s\n", (char*)pop(stringStack));
freeStack(intStack);
freeStack(stringStack);
return 0;
}
Thanks for any code or post comments~ :o
