A (Sort of) Generic Stack Implementation in C using Macros

Question

I spent some time implementing a generic stack in C using macros. Apart from general bugs and bad practices in my code, I was wondering about the viability of an implementation like this that uses macros. Note that the use of assert is only for this code; if I were coding an actual implementation that would be served to users, I would find a better solution.

stack.h

#ifndef STACK_H
#define STACK_H
#include <assert.h>
#include <stdbool.h>
#include <stdlib.h>
#define stackdef(T, pfx) \
 typedef struct pfx##stack { \
 size_t capacity, N; \
 T *a; \
 } pfx##stack; \
 \
 /* returns a pointer to a stack */ \
 pfx##stack *s##pfx##_create(void) { \
 pfx##stack *st = malloc(sizeof *st); \
 \
 assert(st); \
 st->capacity = 1; \
 st->N = 0; \
 assert((st->a = malloc(sizeof *st->a))); \
 return st; \
 } \
 \
 /* frees all memory that was allocated for the stack */ \
 void s##pfx##_free(pfx##stack *st) { \
 assert(st); \
 free(st->a); \
 free(st); \
 } \
 \
 /* returns true if the stack is empty */ \
 bool s##pfx##_isempty(const pfx##stack *st) { \
 assert(st); \
 return st->N == 0; \
 } \
 \
 /* adds ITEM to the top of the stack */ \
 void s##pfx##_push(pfx##stack *st, T item) { \
 assert(st); \
 if (st->N == st->capacity) { \
 assert((st->a = realloc(st->a, (st->capacity *= 2) * sizeof st->a))); \
 } \
 st->a[st->N++] = item; \
 } \
 \
 /* removes and returns the top element of the stack */ \
 T s##pfx##_pop(pfx##stack *st) { \
 assert(st); \
 assert(st->N > 0); \
 if (st->N == st->capacity / 4) { \
 assert((st->a = realloc(st->a, (st->capacity /= 2) * sizeof st->a))); \
 } \
 return st->a[--(st->N)]; \
 } \
 \
 /* iterates through the stack and performs FN on each element */ \
 void s##pfx##_iterate(pfx##stack *st, void (*fn)(void *)) { \
 for (int i = st->N - 1; i >= 0; --i) { \
 fn(&st->a[i]); \
 } \
 }
#endif

Example client

#include "stack.h"
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
stackdef(char *, str);
int getword(char **s);
int main(void) {
 strstack *q = sstr_create();
 char *s;
 while (getword(&s)) {
 if (s[0] == '-' && s[1] == '0円') {
 printf("%s\n", (s = sstr_pop(q)));
 free(s);
 } else {
 sstr_push(q, s);
 }
 }
 return 0;
}
// read the next word from stdin into S and return its length
int getword(char **s) {
 int c;
 int len = 0;
 assert((*s = malloc(sizeof **s)));
 **s = '0円';
 while ((c = getchar()) == ' ' || c == '\t' || c == '\n') {}
 while (c != ' ' && c != '\t' && c != '\n' && c != EOF) {
 (*s)[len++] = c;
 assert((*s = realloc(*s, (len + 1) * sizeof **s)));
 (*s)[len] = '0円';
 c = getchar();
 }
 ungetc(c, stdin);
 return len;
}

Answer 1

Overall, your code looks good.

On naming

I would rename stackdef to DEFINE_STACK_TYPE since, in C, macros are UPPER_CASE.

typedef struct pfx##stack { 
 size_t capacity, N; 
 T *a; 
} pfx##stack; 

I would rather do:

typedef struct pfx##_stack { 
 size_t capacity; 
 size_t size; 
 T* storage_array; 
} pfx##_stack;

Note that I added _ in pfx##_stack in order to separate the type name and the stack.

void s##pfx##_free(pfx##stack *st)

I would write rather:

void stack_##pfx##_free(...)

That way, you are more verbose about the fact that the data structure is a stack.

Miscellaneous

if (st->N == st->capacity / 4) { 
 assert((st->a = realloc(st->a, (st->capacity /= 2) * sizeof st->a))); 
} 

Very good. That way, you keep the push/pop operations amortized constant time. However, you should not realloc if st->capacity == 1. Actually, I would define, for example, 8 as the MINIMUM_CAPACITY and rely on it.

Summa summarum

All in all, I had this rewrite in mind:

stack.h

#ifndef STACK_H
#define STACK_H
#include <assert.h>
#include <stdbool.h>
#include <stdlib.h>
static const size_t MINIMUM_CAPACITY = 8;
#define DEFINE_STACK_TYPE(T, pfx) \
 typedef struct pfx##_stack { \
 size_t capacity; \
 size_t size; \
 T* storage_array; \
 } pfx##_stack; \
 \
 /* returns a pointer to a stack */ \
 pfx##_stack* stack_##pfx##_create(void) { \
 pfx##_stack* stack = malloc(sizeof *stack); \
 \
 assert(stack); \
 stack->capacity = MINIMUM_CAPACITY; \
 stack->size = 0; \
 assert((stack->storage_array = \
 malloc(sizeof(*stack->storage_array) * stack->capacity))); \
 return stack; \
 } \
 \
 /* frees all memory that was allocated for the stack */ \
 void stack_##pfx##_free(pfx##_stack* stack) { \
 assert(stack); \
 free(stack->storage_array); \
 free(stack); \
 } \
 \
 /* returns true if the stack is empty */ \
 bool stack_##pfx##_isempty(const pfx##_stack* stack) { \
 assert(stack); \
 return stack->size == 0; \
 } \
 \
 /* adds ITEM to the top of the stack */ \
 void stack_##pfx##_push(pfx##_stack* stack, T item) { \
 assert(stack); \
 if (stack->size == stack->capacity) { \
 assert((stack->storage_array = \
 realloc(stack->storage_array, \
 (stack->capacity *= 2) * sizeof stack->storage_array))); \
 } \
 stack->storage_array[stack->size++] = item; \
 } \
 \
 /* removes and returns the top element of the stack */ \
 T stack_##pfx##_pop(pfx##_stack* stack) { \
 assert(stack); \
 assert(stack->size > 0); \
 if (stack->size == stack->capacity / 4 \
 && stack->size > MINIMUM_CAPACITY) { \
 /* Very good!:) */ \
 assert((stack->storage_array, \
 realloc(stack->storage_array, \
 (stack->capacity /= 2) * sizeof stack->storage_array))); \
 } \
 return stack->storage_array[--(stack->size)]; \
 } \
 \
 /* iterates through the stack and performs FN on each element */ \
 void stack_##pfx##_iterate(pfx##_stack* stack, void (*fn)(void *)) { \
 for (size_t i = stack->size - 1; i >= 0; --i) { \
 fn(&stack->storage_array[i]); \
 } \
 }
#endif

main.c

#include "stack.h"
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
DEFINE_STACK_TYPE(char*, string)
int getword(char** s);
int main(void) {
 string_stack* q = stack_string_create();
 char* s;
 while (getword(&s)) {
 if (s[0] == '-' && s[1] == '0円') {
 printf("%s\n", (s = stack_string_pop(q)));
 free(s);
 }
 else {
 stack_string_push(q, s);
 }
 }
 return 0;
}
// read the next word from stdin into S and return its length
int getword(char** s) {
 int c;
 int len = 0;
 assert((*s = malloc(sizeof * *s)));
 **s = '0円';
 while ((c = getchar()) == ' ' || c == '\t' || c == '\n') {}
 while (c != ' ' && c != '\t' && c != '\n' && c != EOF) {
 (*s)[len++] = c;
 assert((*s = realloc(*s, (len + 1) * sizeof * *s)));
 (*s)[len] = '0円';
 c = getchar();
 }
 ungetc(c, stdin);
 return len;
}
```