Tukukkk

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.

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?