5
\$\begingroup\$

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;
}
```
\$\endgroup\$
2
  • 1
    \$\begingroup\$ A sample usage, perhaps in the .h file, would be appreciated. So far the scant documentation in code does not well reveal its use. \$\endgroup\$ Dec 3, 2022 at 2:14
  • \$\begingroup\$ @chux-ReinstateMonica Added a demonstration on how the structure is meant to be used \$\endgroup\$ Dec 3, 2022 at 8:17

2 Answers 2

2
\$\begingroup\$

General Observations

Very interesting code and question.

This looks like an attempt to write object oriented code in C. I've tried to do this myself, it has inherent problems. The use of list->this everywhere is an example of these problems. Another problem is that every time a bug is fixed in this code all the code that includes it must be recompiled and retested since all of the code is in the header file, the definitions of the functions should be in a C source file and only the function prototypes should be in the header file.

As a general observation macro code is very hard to debug and maintain, the fact that you got it working is impressive, but maintaining the code over years could be a problem. Remember that you might not be the one that needs to maintain the code. Putting malloc() and free() into macros can definitely lead to debug and maintenance problems.

Warning Messages

I compiled this in Visual Studio 2022 using the C11 standard, with the warnings set to W3 and using the -wall switch. I got the following warning messages:
1>main.c 1>C:\CodeReview\macrolinkedlist\macrolinkedlist\linkedlist.h(1,1): warning C4067: unexpected tokens following preprocessor directive - expected a newline 1>C:CodeReview\macrolinkedlist\macrolinkedlist\main.c(14,23): warning C4267: 'return': conversion from 'size_t' to 'int', possible loss of data

The type mismatch in the second warning is definitely a problem, the int value may switch from positive to negative.

For the first warning message, rather than using DEFINE_SINGLY_LINKED_LIST_T(TKey, TData, FComparer) as the include guard I would have a second macro just as an include guard:

#ifndef SINGLY_LINKED_LIST_H
#define SINGLY_LINKED_LIST_H
    ...
#endif // SINGLY_LINKED_LIST_H

Specific Observations

Test for Possible Memory Allocation Errors

The code is inconsistent for testing for memory allocation errors, there is a test in the macro in the header file, but the malloc() calls in main() are not tested.

In modern high-level languages such as C++, memory allocation errors throw an exception that the programmer can catch. This is not the case in the C programming language. While it is rare in modern computers because there is so much memory, memory allocation can fail, especially if the code is working in a limited memory application such as embedded control systems. In the C programming language when memory allocation fails, the functions malloc(), calloc() and realloc() return NULL. Referencing any memory address through a NULL pointer results in undefined behavior (UB).

Possible unknown behavior in this case can be a memory page error (in Unix this would be call Segmentation Violation), corrupted data in the program and in very old computers it could even cause the computer to reboot (corruption of the stack pointer).

To prevent this undefined behavior a best practice is to always follow the memory allocation statement with a test that the pointer that was returned is not NULL.

Convention When Using Memory Allocation in C

When using malloc(), calloc() or realloc() in C a common convention is to sizeof(*PTR) rather sizeof(PTR_TYPE), this make the code easier to maintain and less error prone, since less editing is required if the type of the pointer changes.

    // Push some data into it
    Cake* c1 = malloc(sizeof(*c1));
    if (c1)
    {
        strcpy(c1->name, "Cakeus Biggus");
        c1->size = 420;
    }

    Cake* c2 = malloc(sizeof(*c2));
    if (c2)
    {
        strcpy(c2->name, "Cakeus Smallus");
        c2->size = 69;
    }

    list->add(list->this, c1);
    list->add(list->this, c2);

Odd Sized Char Array

The declaration of Cake contains the declarations for a character array, but it is using 255 rather than 256, since 256 is an even binary number that is what I would expect to be used.

// Data to store inside the linked list
typedef struct Cake {
    char name[255];
    size_t size;
} Cake;

To not waste memory it might be better to make name a character pointer and use strdup() if it available or write your own strdup().

Magic Numbers

There are Magic Numbers in the main() function (255 above), it might be better to create symbolic constants for them to make the code more readable and easier to maintain. These numbers may be used in many places and being able to change them by editing only one line makes maintenance easier.

Numeric constants in code are sometimes referred to as Magic Numbers, because there is no obvious meaning for them. There is a discussion of this on stackoverflow.

\$\endgroup\$
2
  • \$\begingroup\$ Interesting that you got size_t to int conversion warning - I use clang -Wall -Wextra -pedantic -std=c17 and got no such warning. Regarding array size and magic numbers, I guess I've just always been 255 as the size, since the number 255 fits nicely in an unsigned char. Overall, the driver code was not as rigorously written as the linked list itself, since the bit I'm hoping to be able to recycle is the linked list, not the driver. Thanks for the review! \$\endgroup\$ Dec 5, 2022 at 10:10
  • \$\begingroup\$ Quick note that if writing your own strdup(), you can't use that exact name, as it's reserved (as are all identifiers beginning with str followed by a letter) for future expansion of standard library. \$\endgroup\$ Dec 5, 2022 at 11:46
3
\$\begingroup\$

[Just a short review, more later]

Not a 3-way compare

data->size - *key is never negative as it is a wide unsigned subtraction and so does not meet "Requires a 3-way comparison function".

Idiomatic compare is (a > b) - (a < b), which works for all numeric types.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.