Thread: 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~

Originally Posted by \007

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?

C is a weakly typed language so type security as such isn't a big deal but natural alignment of each type is.
Wondering what applications are you thinking of with such a data structure, besides the obvious rpn calc.

I haven't used a generic stack too often (though I don't write many RPN calculators these days), but I certainly have used generic queues, lists, trees and hash tables (GLib has a nice set I've used often). I haven't had too much need for type safety, but When you're stuck using C (e.g. working in a legacy system), I think there's a great use for them, since rewriting everything in C++ or Java is not an option. If you need this feature in a new project, I would go straight for some OO language.

Depending on how you want to set up your type system in C, you can achieve a degree of type safety. One method I've used I borrowed from the PostgreSQL source. There is a "base object" struct that contains a type ID (you can add other stuff if you want). That base object is the first element of every object/struct in your type system, an enum list of type IDs, and some macros to do some allocating and token gluing. Creating/initializing a variable of that type sets the type ID field. Pass in the type you want (e.g. T_int) to your newStack function, and make sure the object you pass in to push is of the right type for that stack before allowing the push to succeed. Mix in some of the inheritance and polymorphism tricks here, and you can have a pretty sexy framework, even if it is a nightmare to debug.

I find this stuff fascinating too, and it makes for a great academic exercise. You can learn a lot about what's under the hood of an OO language like C++. But out in the real world, the time to create such a framework, and the complexity and maintenance issues it creates often isn't worth it. I usually find it quicker/easier to write a set of wrappers around a generic data structure that enforce type correctness. The data structure itself is completely type agnostic, the wrappers are type safe. At most you need a tiny struct to wrap up your generic data structure for total type safety.

Thanks-- lots of great replies.

I also think C isn't a great choice for data types like this-- and I am not entirely sure how useful they would be.

I also believe if you need structures like this it's probably a good idea to head over to an object oriented language if it is possible.

It is still fun as heck to mess around with them though~! I also agree it's a good way to learn the ins and outs of how object oriented languages work. Heck-- as someone mentioned building data structures from scratch is an excellent exercise in any language.