9
\$\begingroup\$

I've been working on an intrusive linked list for the past few days for a personal project and I would like to have some feedback on it. :)

Personally, I would have preferred to make List and ListNode opaque. However, (I may be wrong here) that means I can only use pointers to them which would mean I have to use ListNode ** to calculate offsets correctly and that makes things complicated...

list.h

#ifndef LIST_H_INCLUDED_
#define LIST_H_INCLUDED_

#include <stdbool.h>
#include <stddef.h>

#define INIT_LIST_NODE (ListNode) { \
    .next = NULL,                   \
    .prev = NULL,                   \
}
#define list_new(type, member, ...) list_new_(offsetof(type, member), __VA_ARGS__)

typedef struct ListNode_ ListNode;

struct ListNode_ {
    ListNode *next;
    ListNode *prev;
};

typedef struct {
    void (*dtor)(void *);
} ListVtable;

typedef struct {
    ListNode *head;
    size_t offset;
    ListVtable *vtable;
} List;

List *list_new_(const size_t offset, ListVtable *vtable);
bool list_is_empty(List *list);
size_t list_size(List *list);
void *list_get(List *list, const size_t pos);
void list_insert(List *list, void *data, const size_t pos);
void list_prepend(List *list, void *data);
void list_append(List *list, void *data);
void list_remove(List *list, const size_t pos);
void list_delete(List **list);

#endif

list.c

strict_malloc does the same thing as xmalloc would.

#include "list.h"
#include "memory.h"

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

ListNode *new_sentinel_node(void)
{
    ListNode *node = strict_malloc(sizeof(*node));

    node->next = NULL;
    node->prev = NULL;
    return node;
}

static ListNode *init_sentinel_nodes(void)
{
    ListNode *head_sentinel = new_sentinel_node();
    ListNode *tail_sentinel = new_sentinel_node();

    head_sentinel->next = tail_sentinel;
    tail_sentinel->prev = head_sentinel;
    return head_sentinel;
}

List *list_new_(const size_t offset, ListVtable *vtable)
{
    List *list = strict_malloc(sizeof(*list));

    list->head = init_sentinel_nodes();
    list->offset = offset;
    list->vtable = vtable;
    return list;
}

static inline bool is_sentinel_node(ListNode *node)
{
    return node->next == NULL || node->prev == NULL;
}

static inline ListNode *front_node(List *list)
{
    return list->head->next;
}

bool list_is_empty(List *list)
{
    return is_sentinel_node(front_node(list));
}

static inline ListNode *get_node(List *list, void *data)
{
    return (ListNode *) (((char *) data) + list->offset);
}

static inline void *get_container(List *list, ListNode *node)
{
    return (void *) (((char *) node) - list->offset);
}

size_t list_size(List *list)
{
    ListNode *current_node = front_node(list);
    size_t size = 0;

    while (!is_sentinel_node(current_node)) {
        size++;
        current_node = current_node->next;
    }
    return size;
}

void *list_get(List *list, const size_t pos)
{
    ListNode *current_node = front_node(list);

    assert(pos < list_size(list));

    for (size_t i = 0; i < pos && !is_sentinel_node(current_node->next); i++) {
        current_node = current_node->next;
    }
    return get_container(list, current_node);
}

static bool contains_node(List *list, ListNode *node)
{
    ListNode *current_node = list->head;

    while (current_node != NULL) {
        if (current_node == node) {
            return true;
        }
        current_node = current_node->next;
    }
    return false;
}

void list_insert(List *list, void *data, const size_t pos)
{
    ListNode *current_node = front_node(list);
    ListNode *node = get_node(list, data);

    assert(pos <= list_size(list));
    assert(!contains_node(list, node));

    for (size_t i = 0; i < pos && !is_sentinel_node(current_node); i++) {
        current_node = current_node->next;
    }
    node->prev = current_node->prev;
    current_node->prev->next = node;
    node->next = current_node;
    current_node->prev = node;
}

void list_prepend(List *list, void *data)
{
    list_insert(list, data, 0);
}

void list_append(List *list, void *data)
{
    list_insert(list, data, list_size(list));
}

static void delete_node(List *list, ListNode *node)
{
    if (is_sentinel_node(node)) {
        free(node);
        return;
    }
    if (list->vtable->dtor != NULL) {
        list->vtable->dtor(get_container(list, node));
    }
}

void list_remove(List *list, const size_t pos)
{
    if (list_is_empty(list)) {
        return;
    }

    ListNode *current_node = front_node(list);

    assert(pos < list_size(list));

    for (size_t i = 0; i < pos && !is_sentinel_node(current_node->next); i++) {
        current_node = current_node->next;
    }
    current_node->prev->next = current_node->next;
    current_node->next->prev = current_node->prev;
    delete_node(list, current_node);
}

void list_delete(List **list)
{
    ListNode *current_node = (*list)->head;

    while (current_node != NULL) {
        ListNode *next_node = current_node->next;

        delete_node(*list, current_node);
        current_node = next_node;
    }
    FREE_AND_NULL(list);
}

demo.c

#include "list.h"

#include <stdio.h>
#include <stdlib.h>

struct dummy {
    int *x;
    ListNode node;
};

struct dummy *new_dummy(int x)
{
    struct dummy *d = malloc(sizeof(*d));

    d->x = malloc(sizeof(int));
    *d->x = x;
    d->node = INIT_LIST_NODE;
    return d;
}

void free_dummy(void *d)
{
    struct dummy *tmp = d;
    free(tmp->x);
    free(tmp);
}

int main(void)
{
    List *dummy_list = list_new(struct dummy, node, &(ListVtable) {
        .dtor = free_dummy,
    });

    for (int i = 0; i < 10; i++) {
        list_append(dummy_list, new_dummy(i));
    };

    for (int i = 0; i < 5; i++) {
        list_remove(dummy_list, 0);
    }

    for (size_t i = 0; i < list_size(dummy_list); i++) {
        struct dummy *tmp = list_get(dummy_list, i);
        printf(" %d ", *tmp->x);
    }
    printf("\n");

    list_delete(&dummy_list);
    return EXIT_SUCCESS;
}
\$\endgroup\$
2
  • \$\begingroup\$ "strict_malloc does the same thing as xmalloc would." is one unknown defined in terms of another unknown. Tell about non-standard xmalloc(). \$\endgroup\$ Sep 15, 2022 at 4:16
  • \$\begingroup\$ @chux-ReinstateMonica essentially, strict_malloc() is just a simple wrapper that exits the program when malloc() returns NULL. \$\endgroup\$ Sep 15, 2022 at 6:18

1 Answer 1

7
\$\begingroup\$
  1. You are quite right that intrusive linked list and opaque data-structure are mutually exclusive.
    That is, you could hide all the list-stuff in each node behind a pointer, but the extra-allocation negates all advantages of being intrusive.

  2. Your intrusive linked list is quite limited, as you only allow membership in a single one.
    By all means, have a name for the default one, but allow the user to name it himself so there is no conflict for multiples.

  3. Put all the list-type dependent stuff in the same place, instead of part with the head-pointer, and part in referenced data.

    Actually, read on.

  4. Too much automation by dynamic data means too much inefficiency. For an intrusive linked list, it contravenes the rationale for having one at all.

    Let the user provide the name on each use, and only provide dereferencing, linking, unlinking, and iterating, not anything else.

  5. Make it a circular linked list, potentially including the origin which is not part of an element, and you can avoid most special cases.

In the end, your intrusive linked list will be header-only, consisting of a single type and less than a handful macros.

\$\endgroup\$
2
  • \$\begingroup\$ Seems like I'm going to be writing a homebrewed version of linux/list.h :). Also, I would like to have some clarification on what #2 means. If I'm not mistaken a struct can have any amount of ListNodes. \$\endgroup\$ Sep 14, 2022 at 4:01
  • \$\begingroup\$ UV, especially for #5. \$\endgroup\$ Sep 15, 2022 at 4:18

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.