Generic data structures in C | andreinc https://www.andreinc.net/2010/09/30/generic-data-stru...
Generic data structures in C
September 30, 2010 • 8 minute read
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:
• Hacking with the #preprocessor
• Using the flexibility of the void pointer ( void* )
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 (http://library.gnome.org/devel/
glib/)).
An existing github project (https://github.com/nomemory/blog-generic-data-structures-in-c) 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 (http://gcc.gnu.org/onlinedocs/cpp/
Macros.html). 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).
1 of 13 7/3/24, 12:08
Generic data structures in C | andreinc https://www.andreinc.net/2010/09/30/generic-data-stru...
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 .
2 of 13 7/3/24, 12:08
Generic data structures in C | andreinc https://www.andreinc.net/2010/09/30/generic-data-stru...
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 (http://gcc.gnu.org/).
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:
3 of 13 7/3/24, 12:08
Generic data structures in C | andreinc https://www.andreinc.net/2010/09/30/generic-data-stru...
#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()):
4 of 13 7/3/24, 12:08
Generic data structures in C | andreinc https://www.andreinc.net/2010/09/30/generic-data-stru...
#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:
5 of 13 7/3/24, 12:08
Generic data structures in C | andreinc https://www.andreinc.net/2010/09/30/generic-data-stru...
#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:
6 of 13 7/3/24, 12:08
Generic data structures in C | andreinc https://www.andreinc.net/2010/09/30/generic-data-stru...
/* 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
7 of 13 7/3/24, 12:08
Generic data structures in C | andreinc https://www.andreinc.net/2010/09/30/generic-data-stru...
#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) \
8 of 13 7/3/24, 12:08
Generic data structures in C | andreinc https://www.andreinc.net/2010/09/30/generic-data-stru...
#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.
9 of 13 7/3/24, 12:08
Generic data structures in C | andreinc https://www.andreinc.net/2010/09/30/generic-data-stru...
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;
}
10 of 13 7/3/24, 12:08
Generic data structures in C | andreinc https://www.andreinc.net/2010/09/30/generic-data-stru...
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:
11 of 13 7/3/24, 12:08
Generic data structures in C | andreinc https://www.andreinc.net/2010/09/30/generic-data-stru...
#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");
12 of 13 7/3/24, 12:08
Generic data structures in C | andreinc https://www.andreinc.net/2010/09/30/generic-data-stru...
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);
}
Updated: September 30, 2010
COMMENTS
13 of 13 7/3/24, 12:08
