Generic data structures in C
This tutorial assumes the reader is familiar with C macros, C pointers, and basic data-structures.
Let’s face it, The C Language is not friendly towards generic programming, but we can use a few tricks:
You can always try both of the approaches and see which one is more suitable for your particular case .
Also note that there are already generic C libraries available (see GLib).
An existing github project contains all the code from this article, to clone it:
gh repo clone nomemory/blog-generic-data-structures-in-c
Hacking with the #preprocessor
To understand the magic (not really) behind this approach you will need to be familiar with C macros and the associated concepts: function-like macros, macro arguments, stringification and concatenation. You can find a very nice tutorial on macros here. If you already know this, you can skip the following paragraphs (or you can read them to refresh your memory / find errors and correct me).
What is a macro ?
A macro is a piece of code that was labeled with a name. Whenever the preprocessor encounters it, the label is replaced by the associated code. Basically there are two kinds of macros : object-like macros (resemble data objects when used) and function-like macros (resemble function calls).
Example for object-like macros:
#include <stdio.h>
// Macro bellow !
#define HELLO "Hello World Macro!"
int main(){
printf(HELLO);
return 0;
}
In the above example the label is HELLO, and the associated data is "Hello World Macro!".
Before the compile-time the preprocessor will replace the label with the associated code. If we compile and run the above code the output will be:
Hello World Macro!
Example for function-like macros:
#include <stdio.h>
#define MAX(a, b) ((a) > (b)) ? (a) : (b)
int main(){
printf("%dn", MAX(1,3));
return 0;
}
In the case above MAX works exactly as a function that receives two arguments a, b and returns the maximum of the two .
Note that the arguments are generic and appear to be typeless, the preprocessor is not performing any validation on types (that’s the compiler job) - but bear in mind this an advantage is also a disadvantage.
If we want to expand the above macro (seeing with the eyes of the compiler) you can use the -E switch with gcc.
After the macro is expanded, the sample code above becomes:
int main(){
printf("%dn", ((1) > (3)) ? (1) : (3));
return 0;
}
Note that the notion of macro will be unknown for the compiler, as the code has been already replaced: ((1) > (3)) ? (1) : (3)
Now let’s focus on a more important aspect: macro concatenation.
How do we proceed when we want to merge two tokens into one while expanding macros ? The ## preprocessing operator performs token pasting .
Example for macro-concatenation:
#include <stdio.h>
#define SHOW(type, msg) show_##type(msg)
void show_error(char *);
void show_info(char *);
void show_error(char *message) {
fprintf(stderr, "ERROR: %s", message);
}
void show_info(char *message){
fprintf(stdout, "INFO: %s", message);
}
int main(){
SHOW(error, "An errorn");
SHOW(info, "Some messagen");
return (0);
}
Output:
ERROR: An error
INFO: Some message
As you can see we supplied the token arguments (not strings!) error / info to the SHOW macro.
The tokens were concatenated with show_?, and the resulting two tokens were actually two real functions: show_error and show_info .
Now lets jump into writing our generic<> Stack data structure:
Declaring the (Stack) data structure, and the associated functions (pop() and push()):
#define STACK_DECLARE(type) \
typedef struct stack_##type##_s { \
type data; \
struct stack_##type##_s *next; \
} stack_##type; \
void stack_##type##_push(stack_##type **stack, type data); \
type stack_##type##_pop(stack_##type **stack); \
Depending on the type supplied as the argument, different code will be generated.
A macro can be associated with blocks of code, we just need to use \ to signal a multi-line macro.
#define STACK_DEFINE(type) \
void stack_##type##_push(stack_##type **stack, type data) { \
stack_##type *new_node = malloc(sizeof(*new_node)); \
if (NULL == new_node) { \
fputs("Couldn't allocate memoryn", stderr); \
abort(); \
} \
new_node->data = data; \
new_node->next = *stack; \
*stack = new_node; \
} \
type stack_##type##_pop(stack_##type **stack) { \
if (NULL == stack || NULL == *stack){ \
fputs("Stack underflow", stderr); \
abort(); \
} \
stack_##type *top = *stack; \
type value = top->data; \
*stack = top->next; \
free(top); \
return value; \
} \
Defining the STACK functions (push() and pop()) declared in the previous step:
#define STACK_DEFINE(type) \
void stack_##type##_push(stack_##type **stack, type data) { \
stack_##type *new_node = malloc(sizeof(*new_node)); \
if (NULL == new_node) { \
fputs("Couldn't allocate memoryn", stderr); \
abort(); \
} \
new_node->data = data; \
new_node->next = *stack; \
*stack = new_node; \
} \
type stack_##type##_pop(stack_##type **stack) { \
if (NULL == stack || NULL == *stack){ \
fputs("Stack underflow", stderr); \
abort(); \
} \
stack_##type *top = *stack; \
type value = top->data; \
*stack = top->next; \
free(top); \
return value; \
} \
Expanding the macro:
/* Expansion if int is supplied as the macro argument */
void stack_int_push(stack_int **stack, int data) {
stack_int *new_node = malloc(sizeof(*new_node));
if (NULL == new_node) {
fputs("Couldn't allocate memoryn", stderr);
abort();
}
new_node->data = data;
new_node->next = *stack;
*stack = new_node;
}
int stack_int_pop(stack_int **stack) {
if (NULL == stack || NULL == *stack) {
fputs("Stack underflow.n", stderr);
abort();
}
stack_int *top = *stack;
int value = top->data;
*stack = top->next;
free(top);
return value;
}
Wrapping the generic functions into macros
#define STACK_TYPE(type) \
stack_##type \
#define STACK_DATA(stack) \
(stack)->data \
#define STACK_PUSH(type, stack, data) \
stack_##type##_push(stack, data) \
#define STACK_POP(type, stack) \
stack_##type##_pop(stack) \
Putting all together
#include <stdio.h>
#include <stdlib.h>
#define STACK_DECLARE(type) \
typedef struct stack_##type##_s { \
type data; \
struct stack_##type##_s *next; \
} stack_##type; \
void stack_##type##_push(stack_##type **stack, type data); \
type stack_##type##_pop(stack_##type **stack); \
#define STACK_DEFINE(type) \
void stack_##type##_push(stack_##type **stack, type data) { \
stack_##type *new_node = malloc(sizeof(*new_node)); \
if (NULL == new_node) { \
fputs("Couldn't allocate memoryn", stderr); \
abort(); \
} \
new_node->data = data; \
new_node->next = *stack; \
*stack = new_node; \
} \
type stack_##type##_pop(stack_##type **stack) { \
if (NULL == stack || NULL == *stack){ \
fputs("Stack underflow", stderr); \
abort(); \
} \
stack_##type *top = *stack; \
type value = top->data; \
*stack = top->next; \
free(top); \
return value; \
} \
#define STACK_TYPE(type) \
stack_##type \
#define STACK_DATA(stack) \
(stack)->data \
#define STACK_PUSH(type, stack, data) \
stack_##type##_push(stack, data) \
#define STACK_POP(type, stack) \
stack_##type##_pop(stack) \
//
// If you want to work with a stack that holds integers you should
// use those macros. They will expand and the associated functions will be
// generated .
//
STACK_DECLARE(int)
STACK_DEFINE(int)
STACK_DECLARE(double)
STACK_DEFINE(double)
int main(int argc, char** argv) {
int i;
//New stack . Alaways assign NULL
STACK_TYPE(int) *st = NULL;
STACK_TYPE(double) *st2 = NULL;
for (i = 0; i < 100; ++i) {
printf("PUSH: %d\n", i);
STACK_PUSH(int, &st, i);
STACK_PUSH(double, &st2, i);
}
while (i--> 0) {
printf("POP: %d %2.2f\n", STACK_POP(int, &st), STACK_POP(double, &st2));
}
return (0);
}
Note: The type argument cannot contain * or spaces. For example, STACK_DECLARE(char*) won’t work, a typedef should be used instead.
Using the void pointer (void*)
Typecasting is one of the powerful features of C, and it represents the ability to convert between different type variables.
Not let’s focus on pointers: there are pointers of type int*, char*, or float*, however there’s a certain pointer that does not have a type known as the void pointer. Any type of pointer can be cast to a void pointer, and conversely, any void pointer can be cast to a pointer of a type .
Generic data, can be referenced using *void.
typedef struct stack_s {
void *data; // Can reference "anything"
struct stack_s *next; // The stack is built as a linked list
} stack;
The next step would be now to declare & define the functions involved in the stack manipulation: push() and pop().
Their signatures could look like this:
void stack_push(stack **head, void *data);
void *stack_pop(stack **head);
void stack_push(stack **head, void *data) {
stack *new_node = malloc(sizeof(*new_node));
if (NULL == new_node) {
fputs("Couldn't allocate memory\n", stderr);
abort();
}
new_node->data = data;
new_node->next = *head;
*head = new_node;
}
void *stack_pop(stack **head) {
stack *top;
void *value;
if (NULL == head || NULL == *head) {
fputs("Stack underflow\n", stderr);
abort();
}
top = *head;
value = top->data;
*head = top->next;
free(top);
return value;
}
Main method:
int main() {
stack *s = NULL;
int i, *tmp;
/* Add values from [1..100] into the stack */
printf("Pushing: \n");
for (i = 0; i < 100; ++i) {
tmp = malloc(sizeof (*tmp));
if (NULL == tmp) {
fputs("Couldn't allocate memory \n", stderr);
abort();
}
*tmp = i;
printf("%d ", *tmp);
stack_push(&s, tmp);
}
// Remove all elements of the stack
printf("\nPopping: \n");
while(i-->0){
tmp = stack_pop(&s);
printf("%d \n", *tmp);
free(tmp);
}
return (0);
}
Putting all together:
#include <stdio.h>
#include <stdlib.h>
typedef struct stack_s {
void *data; // Can reference "anything"
struct stack_s *next; // The stack is built as a linked list
} stack;
void stack_push(stack **head, void *data);
void *stack_pop(stack **head);
void stack_push(stack **head, void *data) {
stack *new_node = malloc(sizeof(*new_node));
if (NULL == new_node) {
fputs("Couldn't allocate memoryn", stderr);
abort();
}
new_node->data = data;
new_node->next = *head;
*head = new_node;
}
void *stack_pop(stack **head) {
stack *top;
void *value;
if (NULL == head || NULL == *head) {
fputs("Stack underflow\n", stderr);
abort();
}
top = *head;
value = top->data;
*head = top->next;
free(top);
return value;
}
int main() {
stack *s = NULL;
int i, *tmp;
/* Add values from [1..100] into the stack */
printf("Pushing: \n");
for (i = 0; i < 100; ++i) {
tmp = malloc(sizeof (*tmp));
if (NULL == tmp) {
fputs("Couldn't allocate memory\n", stderr);
abort();
}
*tmp = i;
printf("%d ", *tmp);
stack_push(&s, tmp);
}
// Remove all elements of the stack
printf("\nPopping: n");
while(i-->0){
tmp = stack_pop(&s);
printf("%d ", *tmp);
free(tmp);
}
return (0);
}
Comments