Ordered lists in C

list.c

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

struct list_entry {
	struct list_entry *next;
	int value;
};

struct list {
	struct list_entry *head;
	size_t capacity;
	size_t capacity_used;
	struct list_entry entries[];
};

size_t
list_size(size_t capacity)
{
	return sizeof(struct list) + capacity * sizeof(struct list_entry);
}

void
list_init(struct list *xs, size_t capacity)
{
	xs->capacity = capacity;
	xs->capacity_used = 0;
	xs->head = NULL;
}

struct list_entry *
list_push(struct list *xs, int value)
{
	struct list_entry *new_entry;
	struct list_entry **pos;

	if (xs->capacity_used == xs->capacity)
		return NULL;

	new_entry = &xs->entries[xs->capacity_used++];
	new_entry->value = value;

	for (pos = &xs->head; *pos != NULL; pos = &(*pos)->next) {
		if (value < (*pos)->value) {
			new_entry->next = *pos;
			*pos = new_entry;
			return new_entry;
		}
	}
	new_entry->next = NULL;
	*pos = new_entry;
	return new_entry;
}

int
list_pop(struct list *xs)
{
	int x;
	struct list_entry *p;
	if (xs->head->next == NULL) {
		x = xs->head->value;
		xs->head = NULL;
		return x;
	}
	for (p = xs->head; p->next->next != NULL; p = p->next);
	x = p->next->value;
	p->next = NULL;
	return x;
}

void
print_internal(struct list *xs)
{
	for (size_t i = 0; i < xs->capacity_used; ++i) {
		if (xs->head == &xs->entries[i])
			printf("HEAD: ");
		if (xs->entries[i].next != NULL)
			printf("%d (-> %d) | ", xs->entries[i].value, xs->entries[i].next->value);
		else
			printf("%d (NULL) | ", xs->entries[i].value);
	}
	printf("\n");
}

void
list_reflow(struct list *xs)
{
	size_t i;
	struct list_entry *p, *n;
	struct list_entry tmp;

	if (xs->head == NULL)
		return;

	printf("Reflowing\n");
	for (i = 0, p = xs->head; ; ++i, p = n) {
		//printf("Swapping %d to %d\n", p->value, xs->entries[i].value);
		/* Store next element to move for later */
		n = p->next;
		//if (n != NULL) printf("\tnext is set to %d", n->value);
		/* Swap element at p into the ith entry */
		tmp = xs->entries[i];
		xs->entries[i] = *p;
		*p = tmp;

		if (n == NULL)
			break;
		/* Temporarily set the entry to point to its old value */
		xs->entries[i].next = p;

		/* Find the real next element if it's been relocated */
		while (n <= &xs->entries[i])
			n = n->next;

		//if (n != NULL) printf(" but is really %d\n", n->value);
		//print_internal(xs);
	}
	printf("Finished reflowing. Resetting pointers.\n");

	/* Reset the next pointers */
	xs->head = xs->entries;
	for (i = 0; xs->entries[i].next != NULL; i++)
		xs->entries[i].next = &xs->entries[i+1];

	printf("Done\n");

	xs->capacity_used = i + 1;
}

int
main(void)
{
	int x;
	size_t count;
	struct list_entry *p;
	struct list *xs;

	xs = calloc(1, list_size(64));
	list_init(xs, 64);

	for (count = 0; scanf("%d", &x) == 1 && count < 64; ++count) {
		list_push(xs, x);
	}

	list_pop(xs);
	list_pop(xs);
	list_pop(xs);
	list_push(xs, 103);
	list_push(xs, 101);
	list_push(xs, 102);
	print_internal(xs);
	list_reflow(xs);
	print_internal(xs);


#ifdef DEBUG
	/* This should not affect the list order */
	list_reflow(xs);
	/* Check that it's the case */
	for (x = 1; x < count; ++x) {
		if (xs->entries[x].value < xs->entries[x - 1].value)
			return 1;
		if (xs->entries[x - 1].next != & xs->entries[x])
			return 1;
	}
#endif

	for (p = xs->head; p != NULL; p = p->next)
		printf("%d\n", p->value);

	return 0;
}