Skip to content

Instantly share code, notes, and snippets.

@louisswarren

louisswarren/list.c

Last active Apr 7, 2021
Embed
What would you like to do?
Ordered lists in 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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment