Permalink
Find file
Fetching contributors…
Cannot retrieve contributors at this time
89 lines (71 sloc) 2.3 KB
/*
* Copyright 2004 Jim Radford <radford@blackbean.org>
* Copyright 2007 David Caldwell <david@porkrind.org>
*/
#include "autolist.h"
struct autolist {
struct autolist *next;
};
struct autolist *__autolist_chain(void *_head, void *_next, size_t offset_of_first)
{
struct autolist *head = _head + offset_of_first, *next = _next, **start = &head->next;
//while (*start) start = &(*start)->next; // call in order of construction
struct autolist *orig = *start;
*start = next;
next->next = orig;
return orig;
}
autolist_declare(void *, generic); // Not a real autolist, just used to get structures defined.
typedef struct __autolist_struct(generic) autolist; // Trust me, it's impossible to read without this.
static autolist *unhook(autolist *item, autolist **rest)
{
// Remove item from rest.
for (autolist *i = *rest, *last = NULL; i; last=i, i=i->next)
if (i == item) {
if (last)
last->next = i->next;
else
*rest = (*rest)->next;
break;
}
item->next = NULL;
return item;
}
static void append(autolist ***next, autolist *list)
{
**next = list;
for (autolist *i=list; i; i=i->next)
if (!i->next) // only advance next when we hit the end of list
*next = &i->next;
}
#include <stdio.h>
static autolist *autolist_deps(autolist *item, autolist **rest)
{
unhook(item, rest);
item->state = as_sorting;
autolist *deps, **next=&deps;
for (struct __autolist_order(generic) *after = item->after; after; after=after->next) {
if (after->dependency->state == as_sorting)
fprintf(stderr, "Circular dependency! Dropping \"%s\"\n", after->description);
if (after->dependency->state == as_unsorted)
append(&next, autolist_deps(after->dependency, rest));
}
item->state = as_sorted;
append(&next, item);
return deps;
}
static autolist *autolist_sort(autolist *rest)
{
autolist *list, **next=&list;
while (rest)
append(&next, autolist_deps(rest, &rest));
return list;
}
void *__autolist__first(void *_list)
{
struct __autolist_kind(generic) *list = _list;
if (!list->unsorted) return list->first;
list->first = autolist_sort(list->first);
list->unsorted = false;
return list->first;
}