Closed linked-list which uses sentinels to avoid passing itself

Question

This is a typical C implementation of a (doubly) linked-list.

I want to avoid passing the element and the list itself to functions which operate on and possibly modify the list; the element alone should be all I need. I separated the prev and next into it's own struct.

This is not closed; start has nothing pointing to it, so I still need to pass List.

This is closed, but it has no way to differentiate the struct List from the struct Link; not only will this go round-and-round, it will crash when I upcast start and expect Link.

This works. head and tail have a distinctive property that one of their pointers is null. I can test for this.

List.h, (C89/90,)

typedef void (*Action)(int *const);

struct X { struct X *prev, *next; };
struct Link { struct X x; int data; };
struct List { struct X head, tail; };

void ListClear(struct List *const list);
void ListPush(struct List *const list, int *const add);
void ListAddBefore(int *const data, int *const add);
void ListForEach(struct List *const list, const Action action);

List.c,

#include <stddef.h> /* offset_of */
#include "List.h"

/* Minimal example without checks. */

static struct Link *x_upcast(struct X *const x) {
    return (struct Link *)(void *)((char *)x - offsetof(struct Link, x));
}

static struct Link *data_upcast(int *const data) {
    return (struct Link *)(void *)((char *)data - offsetof(struct Link, data));
}

static void add_before(struct X *const x, struct X *const add) {
    add->prev = x->prev;
    add->next = x;
    x->prev->next = add;
    x->prev = add;
}

static void clear(struct List *const list) {
    list->head.prev = list->tail.next = 0;
    list->head.next = &list->tail;
    list->tail.prev = &list->head;
}

/** Clears and removes all values from {list}, thereby initialising the {List}.
 All previous values are un-associated. */
void ListClear(struct List *const list) {
    if(!list) return;
    clear(list);
}

/** Initialises the contents of the node which contains {add} to add it to the
 end of {list}. */
void ListPush(struct List *const list, int *const add) {
    if(!list || !add) return;
    add_before(&list->tail, &(data_upcast)(add)->x);
}

/** Initialises the contents of the node which contains {add} to add it
 immediately before {data}. */
void ListAddBefore(int *const data, int *const add) {
    if(!data || !add) return;
    add_before(&data_upcast(data)->x, &data_upcast(add)->x);
}

/** Performs {action} for each element in {list} in the order specified. */
void ListForEach(struct List *const list, const Action action) {
    struct X *x, *next_x;
    if(!list || !action) return;
    for(x = list->head.next; (next_x = x->next); x = next_x)
        action(&(x_upcast)(x)->data);
}

Use this as,

#include <stdio.h>  /* printf */
#include <stdlib.h> /* EXIT_ */
#include <errno.h>
#include "List.h"

/* Very basic fixed capacity; returns null after full. */
static struct Link links[20];
static const size_t links_no = sizeof links / sizeof *links;
static size_t links_used;
static int *get_link(const int data) {
    struct Link *link;
    if(links_used >= links_no) { errno = ERANGE; return 0; }
    link = links + links_used++;
    link->data = data;
    return &link->data;
}

static void sub_ten(int *const i) { ListAddBefore(i, get_link(*i - 10)); }

static void show(int *const i) { printf("%d.\n", *i); }

static struct List list;

int main(void) {
    size_t i;
    ListClear(&list);
    /* Create 10 nodes, [1, 10]. */
    for(i = 0; i < 10; i++) ListPush(&list, get_link(links_used + 1));
    /* Creates a copy of all the data minus ten. */
    ListForEach(&list, &sub_ten);
    /* Prints. */
    ListForEach(&list, &show);
    return errno ? perror("ints"), EXIT_FAILURE : EXIT_SUCCESS;
}

Prints,

-9.
1.
-8.
2.
-7.
3.
-6.
4.
-5.
5.
-4.
6.
-3.
7.
-2.
8.
-1.
9.
0.
10.

(If you go above the fixed number of elements, it will print an error.)

Do I really need four pointers in List to call it on Link alone? If I wanted to add the valid static initial state, I would have to branch each time I iterate on null/not-null. Further, how would I deal with two equivalent states, that is, head.next = tail.prev = null and head.next = tail; tail.prev = head, in the most robust way possible? Is it possible to initialise List statically?

Answer 1

Here are some things that may help you improve your code.

Use NULL instead of 0 for pointers

The value 0 is an integer, but the value NULL is an implementation-defined null-pointer constant. In a pointer context, they're equivalent, but NULL is a cue to the reader of the code that a pointer is involved.

Use include guards

There should be an include guard in the .h file. That is, start the file with:

#ifndef LIST_H
#define LIST_H
// file contents go here
#endif // LIST_H

Simplify your code

I'm not sure why the x_upcast and data_upcast code exists. Maybe the intent was to more cleanly separate the data type (an int here) from the rest of the code. However, consider that it could instead be written like this:

static struct Link *x_upcast(struct X *const x) {
    return (struct Link *)x;
}

Better though, in my opinion, would be to eliminate it entirely. The single place it's used is in ListForEach:

for(x = list->head.next; (next_x = x->next); x = next_x)
        action(&(x_upcast)(x)->data);

This could be more clearly written as:

for(x = list->head.next; (next_x = x->next); x = next_x)
        action(&((struct Link *)x)->data);

This also brings us to the next suggestion.

Use the appropriate data type

The code, as posted, appears to treat pointers to the data value and pointers to a Link identically. This is a problem because it misleads the reader. For example, the get_link code creates and partially initializes a Link but claims to be returning an int *. This would be much more clear if, instead, the code were to actually return a struct Link *. In other words, the interface should guide correct usage rather than encourage incorrect usage. As an example, this code compiles just fine:

int n = 99;
ListPush(&list, &n);

However this is a runtime disaster waiting to happen. We would probably prefer that it not even compile because what ListPush actually requires is a pointer to the data member of an already created struct Link. The next suggestion addresses this problem.

Rethink your interface

If LinkPush really requires a List and a Link, let's declare it that way. Instead of this:

void ListPush(struct List *const list, int *const add);

use this:

void ListPush(struct List *const list, struct Link *const newnode);

Now compiler will actually assist and point out bad usage like the code mentioned previously. This eliminates the type name X and also requires some redefinitions of other things such as List and Action which now look like this:

struct List { struct Link head, tail; };
typedef void (*Action)(struct Link *const);

Use better names

The type name List is good, but the type name X is not. The first name explains something about what the variable means within the context of the code, but the latter is opaque and non-descriptive.

Better describe the responsibilities of the data structure

It is quite important to note that this implementation of a linked list assumes that some other entity is creating (and presumably deleting) its nodes. It gives the user some flexibility, as it would allow the use of statically or dynamically allocated memory, but it's worth explicitly mentioning to the user of the code in a comment.

Answer 2

In addition to @Edward good answer.

Information hiding

I'd expect the calling code of List...() functions to not need to know nor be aware the inner structure of struct List in "List.h".

//struct X { struct X *prev, *next; };
//struct Link { struct X x; int data; };
//struct List { struct X head, tail; };
struct List;  // Just declare its existence.

Surprising name

I would not expect a type named Action() in List.h. Consider ListAction.

// typedef void (*Action)(int *const);
typedef void (*ListAction)(int *const);

Entire List Function

Instead of simply calling a function to apply to each element of the list, pass in a state variable and return value of int to allow for preemptive return should it be non-zero.

// typedef void (*Action)(int *const);
typedef int (*ListAction)(void *state, int *data);

// void ListForEach(struct List *const list, const Action action);
int ListForEach(struct List *const list, const ListAction action, void *state);

Inefficient design

Given the 4 function set, a double-linked list is not needed. A single linked list will do. e.g. Circular linked list

A double-linked list is only needed if code needs to walk the list in either order - which is not the case here.

This space savings is important when the link-list type is widely deployed. In such cases many lists are empty.

Answer 3

With regard to initialising list statically, ISO/IEC 9899 6.6.9 says that an address constant:

The array-subscript [] and member-access . and -> operators, the address & and indirection * unary operators, and pointer casts may be used in the creation of an address constant, but the value of an object shall not be accessed by use of these operators.

I didn't think this would work, but it does because it doesn't access the value,

static struct List list = { { 0, &list.tail }, { &list.head, 0 } };

This eliminates the need to call ListClear. It is much easier then having two cases, empty and a non-empty list.