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;
}
xmalloc(). \$\endgroup\$strict_malloc()is just a simple wrapper that exits the program whenmalloc()returnsNULL. \$\endgroup\$