Creating
generic containers is little tough in c as compared to Java and C++. Templates
in C++ would give you different containers for each type that you use where
Java gives you only one container which is capable of holding any type due to
its singly rooted object base class hierarchy. Generic containers in C are bit
like Java containers in a sense that it would give you only one container as
opposed to the container for each type in C++.
It is
tricky because we have to deal with void
type for variables where we lose the size information and malloc for memory allocation which only deals with raw number of
bytes. But it is fun alright!
So
first lets see the header file and see why this and that is there. I mean the
purpose of having all kinds of stuff in header.
#ifndef STACK_H_
#define STACK_H_
#include <stdio.h>
#include <stdlib.h>
typedef struct {
int size;
int currentIndex;
int elementSize;
void* items;
void
(*clearmem)(void*);
} Stack;
void newStack(Stack* stack ,int size,int elementSize,void
(*clearmem)(void* ));
void push(Stack* stack,void* item);
void pop(Stack* stack,void* destination);
void dispose(Stack* stack);
#endif
Let’s first look at the struct. The size variable defines
max number of items that we are going to keep in our stack. The elementSize
variable holds the size of a single item that would be kept in our stack. This
is needed because we are going generic and we would be taking void type items, therefore we don’t
have size information using lets say sizeof
. The currentIndex keep track of the
number of elements in the stack and will be used for pointer arithmetic to locate addresses of items in push and pop
operations. Void* items refer to a memory location in the heap which points to
the starting address of our stack. Last void (*clearmem)(void*) is a function
pointer which knows how to free the memory used by items stored in the stack.
This is needed because we don’t know how to free the memory if our stack is
holding pointers to strings in heap or pointers to structs etc. if we only
deals with data types such as int, double etc. this is not needed because it
would totally be within our stack.
Let’s recap what we have at the moment. We have size and
elementSize which collectively defines the amount of memory or number of bytes
that is needed for our stack. Then we have currentIndex and items to find out
addresses of the items inside the stack and elementSize tells us how far from
these addresses that we need to consider as single item.
Wow! This is getting long. Function prototypes and
implementation next time.
Note: this is an old post moved here from a different location.
