2
\$\begingroup\$

Generate a linked list of any type using macros. The linked list contains functions for adding and removing elements to both ends and also at the middle. You can also add elements relatively to a list node. It also comes with an iterator that can go back and forwards through the list.

Macros that generate a linked list:

  • LINKEDLIST_GENERATE - Generate a linked list in a single file

If you want to generate the linked list in a separate source file and have a header to access its functions you have two options:

  • PUBLIC (have access to the struct internals)
    • LINKEDLIST_GENERATE_HEADER_PUBLIC - Generate header
    • LINKEDLIST_GENERATE_SOURCE_PUBLIC - Generate source
    • This way the user will have full access to all functions and members of a struct
  • PRIVATE (no access to the struct internals)
    • LINKEDLIST_GENERATE_HEADER_PRIVATE - Generate header
    • LINKEDLIST_GENERATE_SOURCE_PRIVATE - Generate source
    • This way the user won't have access to the struct internals an functions that are part of the linked list implementation.

The above macros (except for LINKEDLIST_GENERATE) are made to interface with one of my previous question that didn't get much attention, but it is part of the same collections library.

macro_collections.h

#ifndef CMC_MACRO_COLLECTIONS
#define CMC_MACRO_COLLECTIONS

#include <stdlib.h>
#include <stdbool.h>

#define CONCATH_(C, P) C##_GENERATE_HEADER##_##P
#define CONCATC_(C, P) C##_GENERATE_SOURCE##_##P

#define CONCATH(C, P) CONCATH_(C, P)
#define CONCATC(C, P) CONCATC_(C, P)

#define COLLECTION_GENERATE(C, P, PFX, SNAME, FMOD, K, V)    \
    COLLECTION_GENERATE_HEADER(C, P, PFX, SNAME, FMOD, K, V) \
    COLLECTION_GENERATE_SOURCE(C, P, PFX, SNAME, FMOD, K, V)

#define COLLECTION_GENERATE_HEADER(C, P, PFX, SNAME, FMOD, K, V) \
    CONCATH(C, P)                                                \
    (PFX, SNAME, FMOD, K, V)

#define COLLECTION_GENERATE_SOURCE(C, P, PFX, SNAME, FMOD, K, V) \
    CONCATC(C, P)                                                \
    (PFX, SNAME, FMOD, K, V)

#endif /* CMC_MACRO_COLLECTIONS */
  • C - The container you want (the uppercase name, e.g., LINKEDLIST);
  • P - If you want your data structure's fields visible;
  • PFX - Functions prefix, or namespace;
  • SNAME - Structure name (typedef SNAME##_s SNAME;);
  • FMOD - Functions modifier (static or empty);
  • K - Used by associative containers (leave empty for LINKEDLIST);
  • V - Your data type to be worked with.

linkedlist.h

#ifndef CMC_LINKEDLIST_H
#define CMC_LINKEDLIST_H

#include <stdlib.h>
#include <stdbool.h>

#define LINKEDLIST_GENERATE(PFX, SNAME, FMOD, V)    \
    LINKEDLIST_GENERATE_STRUCT(PFX, SNAME, FMOD, V) \
    LINKEDLIST_GENERATE_HEADER(PFX, SNAME, FMOD, V) \
    LINKEDLIST_GENERATE_SOURCE(PFX, SNAME, FMOD, V)

/* PRIVATE *******************************************************************/
#define LINKEDLIST_GENERATE_HEADER_PRIVATE(PFX, SNAME, FMOD, K, V) \
    LINKEDLIST_GENERATE_HEADER(PFX, SNAME, FMOD, V)
#define LINKEDLIST_GENERATE_SOURCE_PRIVATE(PFX, SNAME, FMOD, K, V) \
    LINKEDLIST_GENERATE_STRUCT(PFX, SNAME, FMOD, V)                \
    LINKEDLIST_GENERATE_SOURCE(PFX, SNAME, FMOD, V)
/* PUBLIC ********************************************************************/
#define LINKEDLIST_GENERATE_HEADER_PUBLIC(PFX, SNAME, FMOD, K, V) \
    LINKEDLIST_GENERATE_STRUCT(PFX, SNAME, FMOD, V)               \
    LINKEDLIST_GENERATE_HEADER(PFX, SNAME, FMOD, V)
#define LINKEDLIST_GENERATE_SOURCE_PUBLIC(PFX, SNAME, FMOD, K, V) \
    LINKEDLIST_GENERATE_SOURCE(PFX, SNAME, FMOD, V)
/* STRUCT ********************************************************************/
#define LINKEDLIST_GENERATE_STRUCT(PFX, SNAME, FMOD, V) \
                                                        \
    struct SNAME##_s                                    \
    {                                                   \
        struct SNAME##_node_s *head;                    \
        struct SNAME##_node_s *tail;                    \
        size_t count;                                   \
    };                                                  \
                                                        \
    struct SNAME##_node_s                               \
    {                                                   \
        V data;                                         \
        struct SNAME##_s *owner;                        \
        struct SNAME##_node_s *next;                    \
        struct SNAME##_node_s *prev;                    \
    };                                                  \
                                                        \
    struct SNAME##_iter_s                               \
    {                                                   \
        struct SNAME##_s *target;                       \
        struct SNAME##_node_s *cursor;                  \
        size_t index;                                   \
        bool start;                                     \
        bool end;                                       \
    };                                                  \
                                                        \
/* HEADER ********************************************************************/
#define LINKEDLIST_GENERATE_HEADER(PFX, SNAME, FMOD, V)                              \
                                                                                     \
    typedef struct SNAME##_s SNAME;                                                  \
    typedef struct SNAME##_node_s SNAME##_node;                                      \
    typedef struct SNAME##_iter_s SNAME##_iter;                                      \
                                                                                     \
    FMOD SNAME *PFX##_new(void);                                                     \
    FMOD void PFX##_free(SNAME *_list_);                                             \
    FMOD bool PFX##_push_front(SNAME *_list_, V element);                            \
    FMOD bool PFX##_push(SNAME *_list_, V element, size_t index);                    \
    FMOD bool PFX##_push_back(SNAME *_list_, V element);                             \
    FMOD bool PFX##_pop_front(SNAME *_list_);                                        \
    FMOD bool PFX##_pop(SNAME *_list_, size_t index);                                \
    FMOD bool PFX##_pop_back(SNAME *_list_);                                         \
    FMOD bool PFX##_push_if(SNAME *_list_, V element, size_t index, bool condition); \
    FMOD bool PFX##_pop_if(SNAME *_list_, size_t index, bool condition);             \
    FMOD V PFX##_front(SNAME *_list_);                                               \
    FMOD V PFX##_get(SNAME *_list_, size_t index);                                   \
    FMOD V PFX##_back(SNAME *_list_);                                                \
    FMOD bool PFX##_empty(SNAME *_list_);                                            \
    FMOD size_t PFX##_count(SNAME *_list_);                                          \
                                                                                     \
    FMOD SNAME##_node *PFX##_new_node(SNAME *_owner_, V element);                    \
    FMOD SNAME##_node *PFX##_front_node(SNAME *_list_);                              \
    FMOD SNAME##_node *PFX##_get_node(SNAME *_list_, size_t index);                  \
    FMOD SNAME##_node *PFX##_back_node(SNAME *_list_);                               \
    FMOD bool PFX##_insert_nxt(SNAME##_node *node, V element);                       \
    FMOD bool PFX##_insert_prv(SNAME##_node *node, V element);                       \
    FMOD bool PFX##_remove_nxt(SNAME##_node *node);                                  \
    FMOD bool PFX##_remove_cur(SNAME##_node *node);                                  \
    FMOD bool PFX##_remove_prv(SNAME##_node *node);                                  \
    FMOD SNAME##_node *PFX##_next_node(SNAME##_node *node);                          \
    FMOD SNAME##_node *PFX##_prev_node(SNAME##_node *node);                          \
                                                                                     \
    FMOD void PFX##_iter_new(SNAME##_iter *iter, SNAME *target);                     \
    FMOD bool PFX##_iter_start(SNAME##_iter *iter);                                  \
    FMOD bool PFX##_iter_end(SNAME##_iter *iter);                                    \
    FMOD void PFX##_iter_tostart(SNAME##_iter *iter);                                \
    FMOD void PFX##_iter_toend(SNAME##_iter *iter);                                  \
    FMOD bool PFX##_iter_next(SNAME##_iter *iter, V *result, size_t *index);         \
    FMOD bool PFX##_iter_prev(SNAME##_iter *iter, V *result, size_t *index);         \
                                                                                     \
/* SOURCE ********************************************************************/
#define LINKEDLIST_GENERATE_SOURCE(PFX, SNAME, FMOD, V)                             \
                                                                                    \
    FMOD SNAME *PFX##_new(void)                                                     \
    {                                                                               \
        SNAME *_list_ = malloc(sizeof(SNAME));                                      \
                                                                                    \
        if (!_list_)                                                                \
            return NULL;                                                            \
                                                                                    \
        _list_->count = 0;                                                          \
        _list_->head = NULL;                                                        \
        _list_->tail = NULL;                                                        \
                                                                                    \
        return _list_;                                                              \
    }                                                                               \
                                                                                    \
    FMOD void PFX##_free(SNAME *_list_)                                             \
    {                                                                               \
        SNAME##_node *scan = _list_->head;                                          \
        while (_list_->head != NULL)                                                \
        {                                                                           \
            _list_->head = _list_->head->next;                                      \
            free(scan);                                                             \
            scan = _list_->head;                                                    \
        }                                                                           \
        free(_list_);                                                               \
    }                                                                               \
                                                                                    \
    FMOD bool PFX##_push_front(SNAME *_list_, V element)                            \
    {                                                                               \
        SNAME##_node *node = PFX##_new_node(_list_, element);                       \
                                                                                    \
        if (!node)                                                                  \
            return false;                                                           \
                                                                                    \
        if (PFX##_empty(_list_))                                                    \
        {                                                                           \
            _list_->head = node;                                                    \
            _list_->tail = node;                                                    \
        }                                                                           \
        else                                                                        \
        {                                                                           \
            node->next = _list_->head;                                              \
            _list_->head->prev = node;                                              \
            _list_->head = node;                                                    \
        }                                                                           \
                                                                                    \
        _list_->count++;                                                            \
                                                                                    \
        return true;                                                                \
    }                                                                               \
                                                                                    \
    FMOD bool PFX##_push(SNAME *_list_, V element, size_t index)                    \
    {                                                                               \
        if (index > _list_->count)                                                  \
            return false;                                                           \
                                                                                    \
        if (index == 0)                                                             \
        {                                                                           \
            return PFX##_push_front(_list_, element);                               \
        }                                                                           \
        else if (index == _list_->count)                                            \
        {                                                                           \
            return PFX##_push_back(_list_, element);                                \
        }                                                                           \
                                                                                    \
        SNAME##_node *node = PFX##_new_node(_list_, element);                       \
                                                                                    \
        if (!node)                                                                  \
            return false;                                                           \
                                                                                    \
        SNAME##_node *scan = PFX##_get_node(_list_, index - 1);                     \
                                                                                    \
        node->next = scan->next;                                                    \
        node->prev = scan;                                                          \
        node->next->prev = node;                                                    \
        node->prev->next = node;                                                    \
                                                                                    \
        _list_->count++;                                                            \
                                                                                    \
        return true;                                                                \
    }                                                                               \
                                                                                    \
    FMOD bool PFX##_push_back(SNAME *_list_, V element)                             \
    {                                                                               \
        SNAME##_node *node = PFX##_new_node(_list_, element);                       \
                                                                                    \
        if (!node)                                                                  \
            return false;                                                           \
                                                                                    \
        if (PFX##_empty(_list_))                                                    \
        {                                                                           \
            _list_->head = node;                                                    \
            _list_->tail = node;                                                    \
        }                                                                           \
        else                                                                        \
        {                                                                           \
            node->prev = _list_->tail;                                              \
            _list_->tail->next = node;                                              \
            _list_->tail = node;                                                    \
        }                                                                           \
                                                                                    \
        _list_->count++;                                                            \
                                                                                    \
        return true;                                                                \
    }                                                                               \
                                                                                    \
    FMOD bool PFX##_pop_front(SNAME *_list_)                                        \
    {                                                                               \
        if (PFX##_empty(_list_))                                                    \
            return false;                                                           \
                                                                                    \
        SNAME##_node *node = _list_->head;                                          \
        _list_->head = _list_->head->next;                                          \
                                                                                    \
        free(node);                                                                 \
                                                                                    \
        if (_list_->head == NULL)                                                   \
            _list_->tail = NULL;                                                    \
        else                                                                        \
            _list_->head->prev = NULL;                                              \
                                                                                    \
        _list_->count--;                                                            \
                                                                                    \
        return true;                                                                \
    }                                                                               \
                                                                                    \
    FMOD bool PFX##_pop(SNAME *_list_, size_t index)                                \
    {                                                                               \
        if (PFX##_empty(_list_))                                                    \
            return false;                                                           \
                                                                                    \
        if (index >= _list_->count)                                                 \
            return false;                                                           \
                                                                                    \
        if (index == 0)                                                             \
        {                                                                           \
            return PFX##_pop_front(_list_);                                         \
        }                                                                           \
        else if (index == _list_->count - 1)                                        \
        {                                                                           \
            return PFX##_pop_back(_list_);                                          \
        }                                                                           \
                                                                                    \
        SNAME##_node *node = PFX##_get_node(_list_, index);                         \
                                                                                    \
        if (!node)                                                                  \
            return false;                                                           \
                                                                                    \
        node->next->prev = node->prev;                                              \
        node->prev->next = node->next;                                              \
                                                                                    \
        free(node);                                                                 \
                                                                                    \
        _list_->count--;                                                            \
                                                                                    \
        return true;                                                                \
    }                                                                               \
                                                                                    \
    FMOD bool PFX##_pop_back(SNAME *_list_)                                         \
    {                                                                               \
        if (PFX##_empty(_list_))                                                    \
            return false;                                                           \
                                                                                    \
        SNAME##_node *node = _list_->tail;                                          \
        _list_->tail = _list_->tail->prev;                                          \
                                                                                    \
        free(node);                                                                 \
                                                                                    \
        if (_list_->tail == NULL)                                                   \
            _list_->head = NULL;                                                    \
        else                                                                        \
            _list_->tail->next = NULL;                                              \
                                                                                    \
        _list_->count--;                                                            \
                                                                                    \
        return true;                                                                \
    }                                                                               \
                                                                                    \
    FMOD bool PFX##_push_if(SNAME *_list_, V element, size_t index, bool condition) \
    {                                                                               \
        if (condition)                                                              \
            return PFX##_push(_list_, element, index);                              \
                                                                                    \
        return false;                                                               \
    }                                                                               \
                                                                                    \
    FMOD bool PFX##_pop_if(SNAME *_list_, size_t index, bool condition)             \
    {                                                                               \
        if (condition)                                                              \
            return PFX##_pop(_list_, index);                                        \
                                                                                    \
        return false;                                                               \
    }                                                                               \
                                                                                    \
    FMOD V PFX##_front(SNAME *_list_)                                               \
    {                                                                               \
        if (PFX##_empty(_list_))                                                    \
            return 0;                                                               \
                                                                                    \
        return _list_->head->data;                                                  \
    }                                                                               \
                                                                                    \
    FMOD V PFX##_get(SNAME *_list_, size_t index)                                   \
    {                                                                               \
        if (index >= _list_->count)                                                 \
            return 0;                                                               \
                                                                                    \
        if (PFX##_empty(_list_))                                                    \
            return 0;                                                               \
                                                                                    \
        SNAME##_node *scan = PFX##_get_node(_list_, index);                         \
                                                                                    \
        if (scan == NULL)                                                           \
            return 0;                                                               \
                                                                                    \
        return scan->data;                                                          \
    }                                                                               \
                                                                                    \
    FMOD V PFX##_back(SNAME *_list_)                                                \
    {                                                                               \
        if (PFX##_empty(_list_))                                                    \
            return 0;                                                               \
                                                                                    \
        return _list_->tail->data;                                                  \
    }                                                                               \
                                                                                    \
    FMOD bool PFX##_empty(SNAME *_list_)                                            \
    {                                                                               \
        return _list_->count == 0;                                                  \
    }                                                                               \
                                                                                    \
    FMOD size_t PFX##_count(SNAME *_list_)                                          \
    {                                                                               \
        return _list_->count;                                                       \
    }                                                                               \
                                                                                    \
    FMOD SNAME##_node *PFX##_new_node(SNAME *_owner_, V element)                    \
    {                                                                               \
        SNAME##_node *node = malloc(sizeof(SNAME##_node));                          \
                                                                                    \
        if (!node)                                                                  \
            return NULL;                                                            \
                                                                                    \
        node->owner = _owner_;                                                      \
        node->data = element;                                                       \
        node->next = NULL;                                                          \
        node->prev = NULL;                                                          \
                                                                                    \
        return node;                                                                \
    }                                                                               \
                                                                                    \
    FMOD SNAME##_node *PFX##_front_node(SNAME *_list_)                              \
    {                                                                               \
        return _list_->head;                                                        \
    }                                                                               \
                                                                                    \
    FMOD SNAME##_node *PFX##_get_node(SNAME *_list_, size_t index)                  \
    {                                                                               \
        if (index >= _list_->count)                                                 \
            return NULL;                                                            \
                                                                                    \
        if (PFX##_empty(_list_))                                                    \
            return NULL;                                                            \
                                                                                    \
        SNAME##_node *scan = NULL;                                                  \
                                                                                    \
        if (index <= _list_->count / 2)                                             \
        {                                                                           \
            scan = _list_->head;                                                    \
            for (size_t i = 0; i < index; i++)                                      \
            {                                                                       \
                scan = scan->next;                                                  \
            }                                                                       \
        }                                                                           \
        else                                                                        \
        {                                                                           \
            scan = _list_->tail;                                                    \
            for (size_t i = _list_->count - 1; i > index; i--)                      \
            {                                                                       \
                scan = scan->prev;                                                  \
            }                                                                       \
        }                                                                           \
                                                                                    \
        return scan;                                                                \
    }                                                                               \
                                                                                    \
    FMOD SNAME##_node *PFX##_back_node(SNAME *_list_)                               \
    {                                                                               \
        return _list_->tail;                                                        \
    }                                                                               \
                                                                                    \
    FMOD bool PFX##_insert_nxt(SNAME##_node *node, V element)                       \
    {                                                                               \
        SNAME##_node *new_node = PFX##_new_node(node->owner, element);              \
                                                                                    \
        if (!new_node)                                                              \
            return false;                                                           \
                                                                                    \
        new_node->next = node->next;                                                \
        if (node->next != NULL)                                                     \
            node->next->prev = new_node;                                            \
        else                                                                        \
            node->owner->tail = new_node;                                           \
                                                                                    \
        new_node->prev = node;                                                      \
        node->next = new_node;                                                      \
                                                                                    \
        node->owner->count++;                                                       \
                                                                                    \
        return true;                                                                \
    }                                                                               \
                                                                                    \
    FMOD bool PFX##_insert_prv(SNAME##_node *node, V element)                       \
    {                                                                               \
        SNAME##_node *new_node = PFX##_new_node(node->owner, element);              \
                                                                                    \
        if (!new_node)                                                              \
            return false;                                                           \
                                                                                    \
        new_node->prev = node->prev;                                                \
        if (node->prev != NULL)                                                     \
            node->prev->next = new_node;                                            \
        else                                                                        \
            node->owner->head = new_node;                                           \
                                                                                    \
        new_node->next = node;                                                      \
        node->prev = new_node;                                                      \
                                                                                    \
        node->owner->count++;                                                       \
                                                                                    \
        return true;                                                                \
    }                                                                               \
                                                                                    \
    FMOD bool PFX##_remove_nxt(SNAME##_node *node)                                  \
    {                                                                               \
        if (node->next == NULL)                                                     \
            return false;                                                           \
                                                                                    \
        SNAME##_node *tmp = node->next;                                             \
                                                                                    \
        if (node->next != NULL)                                                     \
        {                                                                           \
            node->next = node->next->next;                                          \
            node->next->prev = node;                                                \
        }                                                                           \
        else                                                                        \
            node->owner->tail = node;                                               \
                                                                                    \
        node->owner->count--;                                                       \
                                                                                    \
        free(tmp);                                                                  \
                                                                                    \
        return true;                                                                \
    }                                                                               \
                                                                                    \
    FMOD bool PFX##_remove_cur(SNAME##_node *node)                                  \
    {                                                                               \
        if (node->prev != NULL)                                                     \
            node->prev->next = node->next;                                          \
        else                                                                        \
            node->owner->head = node->next;                                         \
                                                                                    \
        if (node->next != NULL)                                                     \
            node->next->prev = node->prev;                                          \
        else                                                                        \
            node->owner->tail = node->prev;                                         \
                                                                                    \
        node->owner->count--;                                                       \
                                                                                    \
        free(node);                                                                 \
                                                                                    \
        return true;                                                                \
    }                                                                               \
                                                                                    \
    FMOD bool PFX##_remove_prv(SNAME##_node *node)                                  \
    {                                                                               \
        if (node->prev == NULL)                                                     \
            return false;                                                           \
                                                                                    \
        SNAME##_node *tmp = node->prev;                                             \
                                                                                    \
        if (node->prev != NULL)                                                     \
        {                                                                           \
            node->prev = node->prev->prev;                                          \
            node->prev->next = node;                                                \
        }                                                                           \
        else                                                                        \
            node->owner->head = node;                                               \
                                                                                    \
        free(tmp);                                                                  \
                                                                                    \
        return true;                                                                \
    }                                                                               \
                                                                                    \
    FMOD SNAME##_node *PFX##_next_node(SNAME##_node *node)                          \
    {                                                                               \
        return node->next;                                                          \
    }                                                                               \
                                                                                    \
    FMOD SNAME##_node *PFX##_prev_node(SNAME##_node *node)                          \
    {                                                                               \
        return node->prev;                                                          \
    }                                                                               \
                                                                                    \
    FMOD void PFX##_iter_new(SNAME##_iter *iter, SNAME *target)                     \
    {                                                                               \
        iter->target = target;                                                      \
        iter->cursor = target->head;                                                \
        iter->index = 0;                                                            \
        iter->start = true;                                                         \
        iter->end = PFX##_empty(target);                                            \
    }                                                                               \
                                                                                    \
    FMOD bool PFX##_iter_start(SNAME##_iter *iter)                                  \
    {                                                                               \
        return iter->cursor->prev == NULL && iter->start;                           \
    }                                                                               \
                                                                                    \
    FMOD bool PFX##_iter_end(SNAME##_iter *iter)                                    \
    {                                                                               \
        return iter->cursor->next == NULL && iter->end;                             \
    }                                                                               \
                                                                                    \
    FMOD void PFX##_iter_tostart(SNAME##_iter *iter)                                \
    {                                                                               \
        iter->cursor = iter->target->head;                                          \
        iter->index = 0;                                                            \
        iter->start = true;                                                         \
        iter->end = PFX##_empty(iter->target);                                      \
    }                                                                               \
                                                                                    \
    FMOD void PFX##_iter_toend(SNAME##_iter *iter)                                  \
    {                                                                               \
        iter->cursor = iter->target->tail;                                          \
        iter->index = iter->target->count - 1;                                      \
        iter->start = PFX##_empty(iter->target);                                    \
        iter->end = true;                                                           \
    }                                                                               \
                                                                                    \
    FMOD bool PFX##_iter_next(SNAME##_iter *iter, V *result, size_t *index)         \
    {                                                                               \
        if (iter->end)                                                              \
            return false;                                                           \
                                                                                    \
        *index = iter->index;                                                       \
        *result = iter->cursor->data;                                               \
        iter->start = false;                                                        \
                                                                                    \
        if (iter->cursor->next == NULL)                                             \
            iter->end = true;                                                       \
        else                                                                        \
        {                                                                           \
            iter->cursor = iter->cursor->next;                                      \
            iter->index++;                                                          \
        }                                                                           \
                                                                                    \
        return true;                                                                \
    }                                                                               \
                                                                                    \
    FMOD bool PFX##_iter_prev(SNAME##_iter *iter, V *result, size_t *index)         \
    {                                                                               \
        if (iter->start)                                                            \
            return false;                                                           \
                                                                                    \
        *index = iter->index;                                                       \
        *result = iter->cursor->data;                                               \
        iter->end = false;                                                          \
                                                                                    \
        if (iter->cursor->prev == NULL)                                             \
            iter->start = true;                                                     \
        else                                                                        \
        {                                                                           \
            iter->cursor = iter->cursor->prev;                                      \
            iter->index--;                                                          \
        }                                                                           \
                                                                                    \
        return true;                                                                \
    }

#endif /* CMC_LINKEDLIST_H */

EXAMPLE 1

If you want to have access to the struct members:

header.h

#include "macro_collections.h"
#include "linkedlist.h"

COLLECTION_GENERATE_HEADER(LINKEDLIST, PUBLIC, l, list, /* static */, /* K */, int)
// You can also generate other linked lists of other types

source.c

#include "header.h"

COLLECTION_GENERATE_SOURCE(LINKEDLIST, PUBLIC, l, list, /* static */, /* K */, int)
// You can also generate other linked lists of other types

main.c

#include "header.h"

int main(int argc, char const *argv[])
{
    list *int_list = l_new(100); // New integer list of capacity 100
    // Do stuff
    size_t list_count1 = int_list->count; // Valid if PUBLIC
    size_t list_count2 = l_count(int_list); // Valid for PUBLIC and PRIVATE
    // Do more stuff
    l_free(int_list); // Free internal buffer and list struct
}

Now you just have to compile source.c and main.c and link them in the end.

EXAMPLE 2

Another example, now using some of the functionalities of the linked list.

#include <stdio.h>
#include <assert.h>
#include "linkedlist.h"

LINKEDLIST_GENERATE(l, list, static, int)

int main(int argc, char const *argv[])
{
    list *l = l_new();

    for (int i = 0; i < 97; i++)
        l_push_back(l, i);

    // Add 99 after and 33 before every node where its data is divisible by 3
    for (list_node *node = l->head; node != NULL; node = node->next)
    {
        if (node->data % 3 == 0)
        {
            l_insert_prv(node, 33);
            l_insert_nxt(node, 99);
            node = node->next; // skip 99
        }
    }

    size_t s = 0;
    for (list_node *node = l_front_node(l); node != NULL; node = l_next_node(node), s++)
    {
        if (node->prev == NULL)
            printf("[ %d, ", node->data);
        else if (node->next == NULL)
            printf("%d ]\n", node->data);
        else
            printf("%d, ", node->data);
    }

    printf("List Head: %d\nList Tail: %d\nList Count: %d\n", l->head->data, l->tail->data, l->count);

    assert(s == l->count);

    l_free(l);

    return 0;
}

CONCERNS

I have not been able to write intensive tests to check if the list ever gets into some invalid state. Also, allowing the user to deal with nodes is something I was very against at the beginning, but it seems to be working.

I have not had the time to add some functions that are essential to linked lists like splice or concat.

\$\endgroup\$
2
\$\begingroup\$

I have only questions, but maybe some of these are useful.

  • It is desirable to fail fast and in a predictable manner to improper LINKEDLIST_GENERATE commands, maybe with a comment saying what's wrong.
  • LINKEDLIST_GENERATE_HEADER_PUBLIC, etc is probably too confusing; could it could be simplified? You include FMOD; these defines appear interconnected.
  • owner for every node is potentially wasteful, are you sure you need it? Same thing, count, are you sure you need it? It makes it so much harder to maintain the proper state.
  • Are you sure that you want to do memory allocation internal to the list? It would be much simpler to hand that over to the user. I see l_new(100), that contradicts PFX##_new(void); not sure what's going on there.
  • Are all of those functions needed? Eg, PFX##_remove_prv, cur, nxt, but the user could easily duplicate pointers.
  • In your examples, it's possible to have a l_new that's null and crash. I'm not sure whether checking the pre-conditions in each function is better, or the user is required to verify that the list is not null, but I think you should document it.
  • Floyd's algorithm provides great cycle-detection with minimal code. Might be useful when you implement splice and concat. Maybe a debug function that checks if it's in a valid state.

I think it's a very valid use of the pre-processor to generate repeated code.

\$\endgroup\$
  • 2
    \$\begingroup\$ Thanks for the review! Indeed I plan to change this linked list. It looks very derpy. Also I've written this question a bit too fast so some inconsistencies passed through like the l_new(100). \$\endgroup\$ – LeoVen Apr 13 at 2:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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