Linked lists can be expanded without invalidating pointers

expandable_list.c

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

struct node {
	struct node *next;
	long v;
};

struct list {
	struct node *head;
	struct node *empty;
	struct node *last_empty;
	struct node nodes[];
};

size_t
list_size(size_t len)
{
	if (len > (SIZE_MAX - sizeof(struct list)) / sizeof(struct node))
		return 0;
	else
		return sizeof(struct list) + len * sizeof(struct node);
}

void
list_init(struct list *xs, size_t len)
{
	size_t i;
	xs->head = NULL;
	xs->empty = &xs->nodes[0];
	for (i = 0; i < len - 1; ++i)
		xs->nodes[i].next = &xs->nodes[i+1];
	xs->nodes[i].next = NULL;
	xs->last_empty = &xs->nodes[i];
}

void
list_push(struct list *xs, long v)
{
	struct node *x;
	// Detach a new node from the empty list
	x = xs->empty;
	xs->empty = xs->empty->next;
	// Set it
	x->v = v;
	// Push it to the head
	x->next = xs->head;
	xs->head = x;
}

long
list_pop(struct list *xs)
{
	struct node *x;
	// Pop the node off the head
	x = xs->head;
	xs->head = xs->head->next;
	// Push it to the empty list
	x->next = xs->empty;
	xs->empty = x;
	return x->v;
}

void
list_expand(struct list *xs, struct node *mem, size_t len)
{
	size_t i;
	for (i = 0; i < len - 1; ++i)
		mem[i].next = &mem[i+1];
	mem[i].next = NULL;

	if (xs->empty == NULL) {
		xs->empty = mem;
	} else {
		xs->last_empty->next = mem;
		xs->last_empty = &mem[i];
	}
}

int
main(void)
{
	long a = 1, b = 1;
	struct list *xs = malloc(list_size(20));
	list_init(xs, 20);
	list_push(xs, 1);
	list_push(xs, 1);
	while (xs->empty) {
		list_push(xs, a + b);
		b = a + b;
		a = b - a;
		if (!(3 & (a ^ b))) {
			list_push(xs, list_pop(xs));
		}
	}
	struct node *mem = calloc(20, sizeof(*mem));
	list_expand(xs, mem, 20);
	while (xs->empty) {
		list_push(xs, a + b);
		b = a + b;
		a = b - a;
	}
	while (xs->head) {
		printf("%lld\n", list_pop(xs));
	}
}