Configurable datastructures with C macros

3 minute read Published:

Using C macros to create basic datastructures with configurable data types and storage backends using `gcc` switches. Part of my effort to refresh my CS basics by implementing datastructures from scratch.

Configurable type

Here’s a snippet from my array implemenation:

#ifndef TYPE
#define TYPE int
#endif

typedef struct array_t {
        TYPE * _arr;
        ssize_t len;
        int (*get)(const struct array_t * arr, int pos, TYPE * result);
        int (*insert)(struct array_t * arr, int pos, TYPE * elem);
        int (*delete)(struct array_t * arr, int pos);
        int (*search)(struct array_t * arr, TYPE * elem);
} array;

static inline int get(const array * arr, int pos, TYPE * result)
{
        if (arr->len != 0) {
                memcpy(result, &(arr->_arr[pos]), sizeof(TYPE));
                return 0;
        }
        return -1;
}

The code is written for elements of type TYPE, which is defined as int by default but can be configured with compiler switches e.g. gcc -D TYPE=int myprog.c array.c -o myprog.

This works rather well.

Configurable storage backend

This was trickier. In my implementation of the stack data structure, I chose to have a single file with a configurable storage backend (i.e. either array or linkedlist).

I used my own implementations of array and linkedlist.

String macro equality comparison

I learned this one the hard way - string macros in C cannot be compared for equality:

#ifndef BACKEND_TYPE
#define BACKEND_TYPE array
#endif /* BACKEND_TYPE */

Set BACKEND_TYPE to array (my custom array type) if undefined.

#define XSTR(x) STR(x)
#define STR(x) #x
#pragma message "The value of BACKEND_TYPE: " XSTR(BACKEND_TYPE)

Debug print the value of BACKEND_TYPE with -D BACKEND_TYPE=linked_list:

stack.c:20:9: note: #pragma message: The value of BACKEND_TYPE: linked_list
 #pragma message "The value of BACKEND_TYPE: " XSTR(BACKEND_TYPE)

Finally, the if/else to be able to change code based on which storage backend:

#if BACKEND_TYPE == array
#pragma message "BACKEND_TYPE is array"
#elif BACKEND_TYPE == linked_list
#pragma message "BACKEND_TYPE is linked list"
#endif /* BACKEND_TYPE */

Output:

stack.c:22:9: note: #pragma message: BACKEND_TYPE is array
                            ^~~~~~~

Comparison did not work as expected. Some hints online mentioned using ints or chars, so I settled for the following solution:

#define ARRAY 'A'
#define LLIST 'L'

#ifndef BACKEND
#define BACKEND ARRAY
#endif /* BACKEND */

#if BACKEND == ARRAY
#define BACKEND_TYPE array
#elif BACKEND == LLIST
#define BACKEND_TYPE linked_list
#endif /* BACKEND */

#ifndef BACKEND_TYPE
#define BACKEND_TYPE array
#endif /* BACKEND_TYPE */

The compiler switches I pass now are -D BACKEND=ARRAY or -D BACKEND=LLIST. These are defined as chars for the comparison. Finally, BACKEND_TYPE is set from the comparison and used later in the code:

static inline stack * init_stack()
{
#if BACKEND == ARRAY
        printf("ARRAY case\n");
        array *underlying_storage = init_arr();
#elif BACKEND == LLIST
        printf("LL case\n");
        linked_list *underlying_storage = NULL;
#else /* BACKEND */
        fprintf(stderr, "Unsupported BACKEND\n");
        exit(255);
#endif /* BACKEND */
        stack *ret = malloc(sizeof(stack));
        ret->_storage = (BACKEND_TYPE *) underlying_storage;
        ret->_top = -1;
        ret->push = push;
        ret->pop = pop;
        ret->peek = peek;
        return ret;
}

As the code is actually different based on whether the underlying storage element is an array or linked list, I need to check the macros inline in the code.

C++ templates

Doing similar things is much easier with C++ templates. A singly-linked list templated class:

template <class T>
class ListElement
{
public:
	ListElement( const T &value ): next( NULL ), data( value ) {}
	~ListElement() {}
	ListElement *getNext() const
	{
		return next;
	}
	const T& value() const
	{
		return data;
	}
	void setNext( ListElement *elem )
	{
		next = elem;
	}
	void setValue( const T &value )
	{
		data = value;
	}
private:
	ListElement *next;
	T data;
};

In action:

int main(int argc, char **argv)
{
	ListElement<int> l = ListElement<int>(5);
	std::cout << l.value() << std::endl;
}