#define LOADERDECLARATIONS
#ifdef HAVE_XORG_CONFIG_H
#include <xorg-config.h>
#endif
#include "loaderProcs.h"
#include "misc.h"
#include "xf86.h"
ExtensionModule *ExtensionModuleList = NULL;
static int numExtensionModules = 0;
static ExtensionModule *
NewExtensionModule(void)
{
ExtensionModule *save = ExtensionModuleList;
int n;
if (!ExtensionModuleList)
numExtensionModules = 0;
n = numExtensionModules + 1;
ExtensionModuleList = xrealloc(ExtensionModuleList,
(n + 1) * sizeof(ExtensionModule));
if (ExtensionModuleList == NULL) {
ExtensionModuleList = save;
return NULL;
} else {
numExtensionModules++;
ExtensionModuleList[numExtensionModules].name = NULL;
return ExtensionModuleList + (numExtensionModules - 1);
}
}
_X_EXPORT void
LoadExtension(ExtensionModule * e, Bool builtin)
{
ExtensionModule *newext;
if (e == NULL || e->name == NULL)
return;
if (!(newext = NewExtensionModule()))
return;
if (builtin)
xf86MsgVerb(X_INFO, 2, "Initializing built-in extension %s\n",
e->name);
else
xf86MsgVerb(X_INFO, 2, "Loading extension %s\n", e->name);
newext->name = e->name;
newext->initFunc = e->initFunc;
newext->disablePtr = e->disablePtr;
newext->setupFunc = e->setupFunc;
newext->initDependencies = e->initDependencies;
if (e->setupFunc != NULL)
e->setupFunc();
}
#define NF_MARK 0x1
#define NF_ACYCLIC 0x2
#define NF_NODEST 0x4
typedef struct node_str NODE;
struct node_str {
NODE **n_prevp;
NODE *n_next;
NODE **n_arcs;
int n_narcs;
int n_arcsize;
int n_refcnt;
int n_flags;
const char *n_name;
};
static NODE *graph = NULL, **cycle_buf = NULL, **longest_cycle = NULL;
static int longest = 0;
static NODE *sorted = NULL, *last = NULL;
static NODE *
get_node(const char *name)
{
NODE *n;
for (n = graph; n && n->n_name && strcmp(n->n_name, name);
n = n->n_next) ;
if (n)
return (n);
n = xnfalloc(sizeof(NODE));
n->n_narcs = 0;
n->n_arcsize = 0;
n->n_arcs = NULL;
n->n_refcnt = 0;
n->n_flags = 0;
n->n_name = name;
if ((n->n_next = graph) != NULL)
graph->n_prevp = &n->n_next;
n->n_prevp = &graph;
graph = n;
return (n);
}
static void
add_arc(const char *s1, const char *s2)
{
NODE *n1;
NODE *n2;
int bsize, i;
n1 = get_node(s1);
if (!strcmp(s1, s2))
return;
n2 = get_node(s2);
for (i = 0; i < n1->n_narcs; i++)
if (n1->n_arcs[i] == n2)
return;
if (n1->n_narcs == n1->n_arcsize) {
if (!n1->n_arcsize)
n1->n_arcsize = 10;
bsize = n1->n_arcsize * sizeof(*n1->n_arcs) * 2;
n1->n_arcs = xnfrealloc(n1->n_arcs, bsize);
n1->n_arcsize = bsize / sizeof(*n1->n_arcs);
}
n1->n_arcs[n1->n_narcs++] = n2;
++n2->n_refcnt;
}
static void
clear_cycle(void)
{
NODE *n;
for (n = graph; n != NULL; n = n->n_next)
n->n_flags &= ~NF_NODEST;
}
static void
remove_node(NODE * n)
{
NODE **np;
NODE *newnode;
int i;
#ifdef DEBUG
ErrorF("%s\n", n->n_name);
#endif
newnode = xnfalloc(sizeof(NODE));
memcpy(newnode, n, sizeof(NODE));
if (last)
last->n_next = newnode;
else
sorted = newnode;
last = newnode;
newnode->n_next = NULL;
for (np = n->n_arcs, i = n->n_narcs; --i >= 0; np++)
--(*np)->n_refcnt;
n->n_narcs = 0;
*n->n_prevp = n->n_next;
if (n->n_next)
n->n_next->n_prevp = n->n_prevp;
}
static void
free_nodes(NODE * nodelist)
{
NODE *n, *nextnode;
for (n = nodelist; n;) {
nextnode = n->n_next;
xfree(n);
n = nextnode;
}
}
static int
find_cycle(NODE * from, NODE * to, int longest_len, int depth)
{
NODE **np;
int i, len;
if (from->n_flags & (NF_NODEST | NF_MARK | NF_ACYCLIC))
return (0);
from->n_flags |= NF_MARK;
for (np = from->n_arcs, i = from->n_narcs; --i >= 0; np++) {
cycle_buf[depth] = *np;
if (*np == to) {
if (depth + 1 > longest_len) {
longest_len = depth + 1;
memcpy((char *)longest_cycle,
(char *)cycle_buf, longest_len * sizeof(NODE *));
}
} else {
if ((*np)->n_flags & (NF_MARK | NF_ACYCLIC | NF_NODEST))
continue;
len = find_cycle(*np, to, longest_len, depth + 1);
#ifdef DEBUG
ErrorF("%*s %s->%s %d\n", depth, "",
from->n_name, to->n_name, len);
#endif
if (len == 0)
(*np)->n_flags |= NF_NODEST;
if (len > longest_len)
longest_len = len;
if (len > 0 && !longest)
break;
}
}
from->n_flags &= ~NF_MARK;
return (longest_len);
}
static void
tsort(void)
{
NODE *n, *next;
int cnt, i;
while (graph != NULL) {
do {
for (cnt = 0, n = graph; n != NULL; n = next) {
next = n->n_next;
if (n->n_refcnt == 0) {
remove_node(n);
++cnt;
}
}
} while (graph != NULL && cnt);
if (graph == NULL)
break;
if (!cycle_buf) {
for (cnt = 0, n = graph; n != NULL; n = n->n_next)
++cnt;
cycle_buf = xnfalloc(sizeof(NODE *) * cnt);
longest_cycle = xnfalloc(sizeof(NODE *) * cnt);
if (cycle_buf == NULL || longest_cycle == NULL)
return;
}
for (n = graph; n != NULL; n = n->n_next)
if (!(n->n_flags & NF_ACYCLIC)) {
if ((cnt = find_cycle(n, n, 0, 0))) {
ErrorF("tsort: cycle in data");
for (i = 0; i < cnt; i++)
ErrorF("%s", longest_cycle[i]->n_name);
remove_node(n);
clear_cycle();
break;
} else {
n->n_flags |= NF_ACYCLIC;
clear_cycle();
}
}
if (n == NULL)
ErrorF("tsort: internal error -- could not find cycle");
}
if (cycle_buf)
xfree(cycle_buf);
if (longest_cycle)
xfree(longest_cycle);
if (graph)
free_nodes(graph);
}
void
LoaderSortExtensions()
{
int i, j;
ExtensionModule *ext, *newList;
NODE *node;
graph = NULL;
longest = 0;
sorted = NULL;
last = NULL;
cycle_buf = NULL;
longest_cycle = NULL;
for (i = numExtensionModules - 1; i >= 0; i--) {
ext = &ExtensionModuleList[i];
add_arc(ext->name, ext->name);
#ifdef DEBUG
ErrorF("Extension %s:\n", ext->name);
#endif
if (ext->initDependencies)
for (j = 0; ext->initDependencies[j]; j++) {
add_arc(ext->initDependencies[j], ext->name);
#ifdef DEBUG
ErrorF("\t%s\n", ext->initDependencies[j]);
#endif
}
}
tsort();
newList = xnfalloc((numExtensionModules + 1) * sizeof(ExtensionModule));
i = 0;
for (node = sorted; node; node = node->n_next) {
for (j = 0; j < numExtensionModules; j++)
if (!strcmp(node->n_name, ExtensionModuleList[j].name))
break;
if (j != numExtensionModules)
newList[i++] = ExtensionModuleList[j];
}
if (sorted)
free_nodes(sorted);
newList[i].name = NULL;
xfree(ExtensionModuleList);
ExtensionModuleList = newList;
#ifdef DEBUG
for (i = 0; ExtensionModuleList[i].name; i++)
ErrorF("Extension %s\n", ExtensionModuleList[i].name);
#endif
}