Loader: Remove extension initialisation sorting

Extensions could previously declare initialisation dependencies on other
extensions, which would then get nicely sorted by the loader.  We only
had one user for this, GLX, which had one pointless (Composite) and one
possibly useful dependency (DBE).  As DBE is now a built-in, it will
always be sorted by GLX, so we no longer have any users for it.

Signed-off-by: Daniel Stone <daniel@fooishbar.org>
Reviewed-by: Peter Hutterer <peter.hutterer@who-t.net>
Signed-off-by: Keith Packard <keithp@keithp.com>

7 files changed, 16 insertions, 374 deletions

diff --git a/COPYING b/COPYING
index cd9e80a48..7aa0df080 100644
--- a/COPYING
+++ b/COPYING
@@ -1788,7 +1788,7 @@ TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
 PERFORMANCE OF THIS SOFTWARE.
 
 
-Copyright (c) 1989, 1990, 1993, 1994
+Copyright (c) 1987, 1990, 1993
      The Regents of the University of California.  All rights reserved.
 
 This code is derived from software contributed to Berkeley by
diff --git a/hw/xfree86/common/xf86Extensions.c b/hw/xfree86/common/xf86Extensions.c
index 15bab42ad..8cbeedf3b 100644
--- a/hw/xfree86/common/xf86Extensions.c
+++ b/hw/xfree86/common/xf86Extensions.c
@@ -59,7 +59,6 @@ static ExtensionModule extensionModules[] = {
 	XFree86VidModeExtensionInit,
 	XF86VIDMODENAME,
 	&noXFree86VidModeExtension,
-	NULL,
 	NULL
     },
 #endif
@@ -68,7 +67,6 @@ static ExtensionModule extensionModules[] = {
 	XFree86DGAExtensionInit,
 	XF86DGANAME,
 	&noXFree86DGAExtension,
-	NULL,
 	NULL
     },
 #endif
@@ -77,7 +75,6 @@ static ExtensionModule extensionModules[] = {
         XFree86DRIExtensionInit,
         "XFree86-DRI",
         &noXFree86DRIExtension,
-        NULL,
         NULL
     },
 #endif
@@ -86,7 +83,6 @@ static ExtensionModule extensionModules[] = {
         DRI2ExtensionInit,
         DRI2_NAME,
         &noDRI2Extension,
-        NULL,
         NULL
     }
 #endif
diff --git a/hw/xfree86/common/xf86Module.h b/hw/xfree86/common/xf86Module.h
index dc5d0a8e8..d528a5d4c 100644
--- a/hw/xfree86/common/xf86Module.h
+++ b/hw/xfree86/common/xf86Module.h
@@ -175,7 +175,6 @@ typedef struct {
     const char *name;
     Bool *disablePtr;
     InitExtension setupFunc;
-    const char **initDependencies;
 } ExtensionModule;
 
 extern _X_EXPORT ExtensionModule *ExtensionModuleList;
diff --git a/hw/xfree86/dixmods/glxmodule.c b/hw/xfree86/dixmods/glxmodule.c
index a2b06a26d..2f0a3dd2e 100644
--- a/hw/xfree86/dixmods/glxmodule.c
+++ b/hw/xfree86/dixmods/glxmodule.c
@@ -50,7 +50,6 @@ static ExtensionModule GLXExt = {
     GlxExtensionInit,
     "GLX",
     &noGlxExtension,
-    NULL,
     NULL
 };
 
diff --git a/hw/xfree86/loader/loaderProcs.h b/hw/xfree86/loader/loaderProcs.h
index a7b752b9a..8b4b53f28 100644
--- a/hw/xfree86/loader/loaderProcs.h
+++ b/hw/xfree86/loader/loaderProcs.h
@@ -80,7 +80,6 @@ ModuleDescPtr LoadModule(const char *, const char *, const char **,
 ModuleDescPtr DuplicateModule(ModuleDescPtr mod, ModuleDescPtr parent);
 void UnloadDriver(ModuleDescPtr);
 void LoaderSetPath(const char *path);
-void LoaderSortExtensions(void);
 
 void LoaderUnload(const char *, void *);
 unsigned long LoaderGetModuleVersion(ModuleDescPtr mod);
diff --git a/hw/xfree86/loader/loadext.c b/hw/xfree86/loader/loadext.c
index 0754ea986..62355bb3f 100644
--- a/hw/xfree86/loader/loadext.c
+++ b/hw/xfree86/loader/loadext.c
@@ -91,354 +91,7 @@ LoadExtension(ExtensionModule * e, Bool builtin)
     newext->initFunc = e->initFunc;
     newext->disablePtr = e->disablePtr;
     newext->setupFunc = e->setupFunc;
-    newext->initDependencies = e->initDependencies;
 
     if (e->setupFunc != NULL)
         e->setupFunc();
 }
-
-/*
- * Sort ExtensionModuleList according to the initialisation order
- * dependencies.  The code for this is taken from BSD's tsort,
- * and carries the following copyright/license:
- *
- *
- * Copyright (c) 1989, 1993, 1994
- *      The Regents of the University of California.  All rights reserved.
- *
- * This code is derived from software contributed to Berkeley by
- * Michael Rendell of Memorial University of Newfoundland.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- * 1. Redistributions of source code must retain the above copyright
- *    notice, this list of conditions and the following disclaimer.
- * 2. Redistributions in binary form must reproduce the above copyright
- *    notice, this list of conditions and the following disclaimer in the
- *    documentation and/or other materials provided with the distribution.
- * 3. All advertising materials mentioning features or use of this software
- *    must display the following acknowledgement:
- *      This product includes software developed by the University of
- *      California, Berkeley and its contributors.
- * 4. Neither the name of the University nor the names of its contributors
- *    may be used to endorse or promote products derived from this software
- *    without specific prior written permission.
- *
- * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
- * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
- * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
- * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
- * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
- * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
- * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
- * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
- * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
- * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
- * SUCH DAMAGE.
- */
-
-#define	NF_MARK		0x1     /* marker for cycle detection */
-#define	NF_ACYCLIC	0x2     /* this node is cycle free */
-#define	NF_NODEST	0x4     /* Unreachable */
-
-typedef struct node_str NODE;
-struct node_str {
-    NODE **n_prevp;             /* pointer to previous node's n_next */
-    NODE *n_next;               /* next node in graph */
-    NODE **n_arcs;              /* array of arcs to other nodes */
-    int n_narcs;                /* number of arcs in n_arcs[] */
-    int n_arcsize;              /* size of n_arcs[] array */
-    int n_refcnt;               /* # of arcs pointing to this node */
-    int n_flags;                /* NF_* */
-    const char *n_name;         /* name of this node */
-};
-
-static NODE *graph = NULL, **cycle_buf = NULL, **longest_cycle = NULL;
-static int longest = 0;
-static NODE *sorted = NULL, *last = NULL;
-
-/* Find a node in the graph (insert if not found) and return a pointer to it. */
-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;
-
-    /* Add to linked list. */
-    if ((n->n_next = graph) != NULL)
-        graph->n_prevp = &n->n_next;
-    n->n_prevp = &graph;
-    graph = n;
-
-    return n;
-}
-
-/*
- * add an arc from node s1 to node s2 in the graph.  If s1 or s2 are not in
- * the graph, then add them.
- */
-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);
-
-    /*
-     * Check if this arc is already here.
-     */
-    for (i = 0; i < n1->n_narcs; i++)
-        if (n1->n_arcs[i] == n2)
-            return;
-    /*
-     * Add it.
-     */
-    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;
-}
-
-/*
- * Clear the NODEST flag from all nodes.
- */
-static void
-clear_cycle(void)
-{
-    NODE *n;
-
-    for (n = graph; n != NULL; n = n->n_next)
-        n->n_flags &= ~NF_NODEST;
-}
-
-/* print node and remove from graph (does not actually free node) */
-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;
-        free(n);
-        n = nextnode;
-    }
-}
-
-/* look for the longest? cycle from node from to node to. */
-static int
-find_cycle(NODE * from, NODE * to, int longest_len, int depth)
-{
-    NODE **np;
-    int i, len;
-
-    /*
-     * avoid infinite loops and ignore portions of the graph known
-     * to be acyclic
-     */
-    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;
-}
-
-/* do topological sort on graph */
-static void
-tsort(void)
-{
-    NODE *n, *next;
-    int cnt, i;
-
-    while (graph != NULL) {
-        /*
-         * Keep getting rid of simple cases until there are none left,
-         * if there are any nodes still in the graph, then there is
-         * a cycle in it.
-         */
-        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) {
-            /*
-             * Allocate space for two cycle logs - one to be used
-             * as scratch space, the other to save the longest
-             * cycle.
-             */
-            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 {
-                    /* to avoid further checks */
-                    n->n_flags |= NF_ACYCLIC;
-                    clear_cycle();
-                }
-            }
-
-        if (n == NULL)
-            ErrorF("tsort: internal error -- could not find cycle");
-    }
-    free(cycle_buf);
-    free(longest_cycle);
-    if (graph)
-        free_nodes(graph);
-}
-
-void
-LoaderSortExtensions(void)
-{
-    int i, j;
-    ExtensionModule *ext, *newList;
-    NODE *node;
-
-    graph = NULL;
-    longest = 0;
-    sorted = NULL;
-    last = NULL;
-    cycle_buf = NULL;
-    longest_cycle = NULL;
-
-    /*
-     * Parse list and build the graph.  Enter them in reverse order
-     * because tsort() will reverse those that have no depedencies.
-     */
-    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);
-    if (graph)
-        free_nodes(graph);
-    newList[i].name = NULL;
-    free(ExtensionModuleList);
-    ExtensionModuleList = newList;
-#ifdef DEBUG
-    for (i = 0; ExtensionModuleList[i].name; i++)
-        ErrorF("Extension %s\n", ExtensionModuleList[i].name);
-#endif
-}
diff --git a/mi/miinitext.c b/mi/miinitext.c
index 30c428c8a..a2bbdaafd 100644
--- a/mi/miinitext.c
+++ b/mi/miinitext.c
@@ -358,38 +358,37 @@ InitExtensions(int argc, char *argv[])
 #else                           /* XFree86LOADER */
 /* List of built-in (statically linked) extensions */
 static ExtensionModule staticExtensions[] = {
-    {GEExtensionInit, "Generic Event Extension", &noGEExtension, NULL, NULL},
-    {ShapeExtensionInit, "SHAPE", NULL, NULL, NULL},
+    {GEExtensionInit, "Generic Event Extension", &noGEExtension, NULL},
+    {ShapeExtensionInit, "SHAPE", NULL, NULL},
 #ifdef MITSHM
-    {ShmExtensionInit, SHMNAME, &noMITShmExtension, NULL, NULL},
+    {ShmExtensionInit, SHMNAME, &noMITShmExtension, NULL},
 #endif
-    {XInputExtensionInit, "XInputExtension", NULL, NULL, NULL},
+    {XInputExtensionInit, "XInputExtension", NULL, NULL},
 #ifdef XTEST
-    {XTestExtensionInit, XTestExtensionName, &noTestExtensions, NULL, NULL},
+    {XTestExtensionInit, XTestExtensionName, &noTestExtensions, NULL},
 #endif
-    {BigReqExtensionInit, "BIG-REQUESTS", NULL, NULL, NULL},
-    {SyncExtensionInit, "SYNC", NULL, NULL, NULL},
-    {XkbExtensionInit, XkbName, NULL, NULL, NULL},
-    {XCMiscExtensionInit, "XC-MISC", NULL, NULL, NULL},
+    {BigReqExtensionInit, "BIG-REQUESTS", NULL, NULL},
+    {SyncExtensionInit, "SYNC", NULL, NULL},
+    {XkbExtensionInit, XkbName, NULL, NULL},
+    {XCMiscExtensionInit, "XC-MISC", NULL, NULL},
 #ifdef XCSECURITY
-    {SecurityExtensionInit, SECURITY_EXTENSION_NAME, &noSecurityExtension, NULL,
-     NULL},
+    {SecurityExtensionInit, SECURITY_EXTENSION_NAME, &noSecurityExtension, NULL},
 #endif
 #ifdef PANORAMIX
     {PanoramiXExtensionInit, PANORAMIX_PROTOCOL_NAME, &noPanoramiXExtension,
-     NULL, NULL},
+     NULL},
 #endif
 #ifdef XFIXES
     /* must be before Render to layer DisplayCursor correctly */
-    {XFixesExtensionInit, "XFIXES", &noXFixesExtension, NULL, NULL},
+    {XFixesExtensionInit, "XFIXES", &noXFixesExtension, NULL},
 #endif
 #ifdef XF86BIGFONT
     {XFree86BigfontExtensionInit, XF86BIGFONTNAME, &noXFree86BigfontExtension,
-     NULL, NULL},
+     NULL},
 #endif
-    {RenderExtensionInit, "RENDER", &noRenderExtension, NULL, NULL},
+    {RenderExtensionInit, "RENDER", &noRenderExtension, NULL},
 #ifdef RANDR
-    {RRExtensionInit, "RANDR", &noRRExtension, NULL, NULL},
+    {RRExtensionInit, "RANDR", &noRRExtension, NULL},
 #endif
 #ifdef COMPOSITE
     {CompositeExtensionInit, "COMPOSITE", &noCompositeExtension, NULL},
@@ -442,10 +441,7 @@ InitExtensions(int argc, char *argv[])
     int i;
     ExtensionModule *ext;
 
-    /* Make sure all static extensions have been added, then sort the
-     * extensions according to their init dependencies. */
     AddStaticExtensions();
-    LoaderSortExtensions();
 
     for (i = 0; ExtensionModuleList[i].name != NULL; i++) {
         ext = &ExtensionModuleList[i];