For a recent project of mine I had to create various data structures in pure C with no external libraries (in other words, code I've written by myself), which lacks the templating and OOP capabilities of C++. However, I figured a macro might be easier than a void*-based solution, so here it is. It's functional as far as my needs go, but after several rewrites every time I need a data structure in C I figured I want something I can write once and for all. My code, however, probably has various holes I missed so please do let me know what I can do to improve it.
#ifndef DEFINE_SINGLY_LINKED_LIST_T(TKey, TData, FComparer)
#include <stdlib.h>
/**
* Defines a Singly Linked List storing data type TData which can be retrieved
* later on with TKey. Requires a 3-way comparison function FComparer_TData_TKey
* comparing data against a key to be provided to enable retrieval and deletion
* of the data.
*/
#define DEFINE_SINGLY_LINKED_LIST_T(TKey, TData, FComparer_TData_TKey) \
typedef struct SinglyLinkedList_##TData##_##TKey SinglyLinkedList_##TData##_##TKey; \
typedef struct SinglyLinkedListNode_##TData##_##TKey SinglyLinkedListNode_##TData##_##TKey; \
\
struct SinglyLinkedList_##TData##_##TKey { \
SinglyLinkedList_##TData##_##TKey *this; \
\
SinglyLinkedListNode_##TData##_##TKey *head; \
\
void (*add)(SinglyLinkedList_##TData##_##TKey * this, TData *data); \
void (*remove)(SinglyLinkedList_##TData##_##TKey * this, TKey *key); \
TData *(*find)(SinglyLinkedList_##TData##_##TKey * this, TKey *key); \
void (*clear)(SinglyLinkedList_##TData##_##TKey * this); \
}; \
\
struct SinglyLinkedListNode_##TData##_##TKey { \
TData *data; \
SinglyLinkedListNode_##TData##_##TKey *next; \
}; \
\
void sll_add_##TData##_##TKey(SinglyLinkedList_##TData##_##TKey *this, TData *data); \
void sll_remove_##TData##_##TKey(SinglyLinkedList_##TData##_##TKey *this, TKey *key); \
TData *sll_find_##TData##_##TKey(SinglyLinkedList_##TData##_##TKey *this, TKey *key); \
void sll_clear_##TData##_##TKey(SinglyLinkedList_##TData##_##TKey *this); \
\
SinglyLinkedList_##TData##_##TKey *newSinglyLinkedList_##TData##_##TKey(void) { \
SinglyLinkedList_##TData##_##TKey *list = malloc(sizeof(SinglyLinkedList_##TData##_##TKey)); \
if (list == NULL) return NULL; \
list->this = list; \
list->head = NULL; \
\
list->add = sll_add_##TData##_##TKey; \
list->remove = sll_remove_##TData##_##TKey; \
list->find = sll_find_##TData##_##TKey; \
list->clear = sll_clear_##TData##_##TKey; \
\
return list; \
} \
\
SinglyLinkedListNode_##TData##_##TKey *newSinglyLinkedListNode_##TData##_##TKey(void) { \
SinglyLinkedListNode_##TData##_##TKey *node = malloc(sizeof(SinglyLinkedListNode_##TData##_##TKey)); \
if (node == NULL) return NULL; \
node->data = NULL; \
node->next = NULL; \
\
return node; \
} \
\
void sll_add_##TData##_##TKey(SinglyLinkedList_##TData##_##TKey *this, TData *data) { \
SinglyLinkedListNode_##TData##_##TKey *newNode = newSinglyLinkedListNode_##TData##_##TKey(); \
newNode->data = data; \
\
SinglyLinkedListNode_##TData##_##TKey *node = this->head; \
\
if (node == NULL) { \
this->head = newNode; \
return; \
} \
\
while (node->next != NULL) node = node->next; \
node->next = newNode; \
} \
\
void sll_remove_##TData##_##TKey(SinglyLinkedList_##TData##_##TKey *this, TKey *key) { \
SinglyLinkedListNode_##TData##_##TKey *previous = NULL; \
SinglyLinkedListNode_##TData##_##TKey *node = this->head; \
\
while (node != NULL) { \
if (FComparer_TData_TKey(node->data, key) == 0) { \
if (previous != NULL) previous->next = node->next; \
free(node); \
return; \
} \
\
previous = node; \
node = node->next; \
} \
} \
\
TData *sll_find_##TData##_##TKey(SinglyLinkedList_##TData##_##TKey *this, TKey *key) { \
SinglyLinkedListNode_##TData##_##TKey *node = this->head; \
\
while (node != NULL) { \
if (FComparer_TData_TKey(node->data, key) == 0) return node->data; \
node = node->next; \
} \
\
return NULL; \
} \
\
void sll_clear_##TData##_##TKey(SinglyLinkedList_##TData##_##TKey *this) { \
SinglyLinkedListNode_##TData##_##TKey *node = this->head; \
while (node != NULL) { \
SinglyLinkedListNode_##TData##_##TKey *next = node->next; \
free(node); \
node = next; \
} \
}
#endif
The following shows the various things you might expect a linked list to be able to do:
#include <stdio.h>
#include <string.h>
#include "linkedlist.h"
// Data to store inside the linked list
typedef struct Cake {
char name[255];
size_t size;
} Cake;
// Function to find out if we have the correct data
int compare(Cake *data, size_t *key) {
return data->size - *key;
}
// Actually define the linked list storing the data we chose
DEFINE_SINGLY_LINKED_LIST_T(size_t, Cake, compare)
int main() {
// Create an instance of the linked list we just defined
SinglyLinkedList_Cake_size_t *list = newSinglyLinkedList_Cake_size_t();
// Push some data into it
Cake *c1 = malloc(sizeof(Cake));
strcpy(c1->name, "Cakeus Biggus");
c1->size = 420;
Cake *c2 = malloc(sizeof(Cake));
strcpy(c2->name, "Cakeus Smallus");
c2->size = 69;
list->add(list->this, c1);
list->add(list->this, c2);
// Find data we pushed earlier
size_t *key = malloc(sizeof(size_t)); // this is rather unfortunate
*key = 69;
Cake *cake = list->find(list->this, key);
// Data is still intact
if (cake != NULL) {
printf("Name: %s\nSize: %zu\n", cake->name, cake->size);
}
// Remove data
list->remove(list->this, key); // we can recycle the key we made earlier
// Sanity check to check the data really is gone
Cake *nocake = list->find(list->this, key);
if (nocake == NULL) {
printf("The cake is a lie\n");
}
// The OS would free our sanity cakes for us here, but otherwise we have to free it ourselves
free(cake);
free(nocake);
return 0;
}
```
