summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorquinn <quinn@d7aaf104-2d23-0410-ae22-9d23157bf5a3>2007-02-14 10:49:03 +0000
committerquinn <quinn@d7aaf104-2d23-0410-ae22-9d23157bf5a3>2007-02-14 10:49:03 +0000
commitae246a17d627b0556cf9cdffaf3078991334f060 (patch)
tree0e784ce35cf78ac55a55291ebcc7ec77d45f192b
parentacde081891d082280424a5189edcc2e24a79022b (diff)
downloadmarex-dev-ae246a17d627b0556cf9cdffaf3078991334f060.tar.gz
marex-dev-ae246a17d627b0556cf9cdffaf3078991334f060.tar.bz2
beryl-core:
* Depth-First sort the plugin DAG instead of incorrect algo git-svn-id: file:///beryl/trunk@4050 d7aaf104-2d23-0410-ae22-9d23157bf5a3
-rw-r--r--beryl-core/src/plugin.c83
1 files changed, 35 insertions, 48 deletions
diff --git a/beryl-core/src/plugin.c b/beryl-core/src/plugin.c
index 81a439d..776f189 100644
--- a/beryl-core/src/plugin.c
+++ b/beryl-core/src/plugin.c
@@ -704,61 +704,48 @@ CompPlugin *getPlugins(void)
return plugins;
}
-
-static void sort_plugin_list(void)
+static void depth_first_plugin(CompPlugin * p, int cnt, CompPlugin ** list)
{
- CompPlugin *new_list = NULL, *todo;
-
- if (!plugins)
- {
- pr_debug_verbose("No plugins loaded.\n");
- return;
- }
-
- /* Put first plugin in new list */
- new_list = plugins;
- plugins = plugins->next;
- new_list->next = NULL;
- todo = plugins;
-
- pr_debug_verbose("Put %s at head of list.\n", new_list->vTable->name);
-
- while (todo)
+ if (p->state)
+ return; // already visited
+ p->state = 1; // visited this one now
+ int i;
+ for (i=0;i<cnt;i++)
{
- CompPlugin *insert_at = new_list, *prev =
- new_list, *next_todo = todo->next;
- int done = 0;
-
- pr_debug_verbose("Considering %s.\n", todo->vTable->name);
-
- while (insert_at && !done)
+ if (p!=list[i])
{
- if (comparePluginDeps(todo, insert_at) == 1)
- {
- pr_debug_verbose(" %s must be after %s.\n",
- todo->vTable->name, insert_at->vTable->name);
- todo->next = insert_at;
- if (insert_at == new_list)
- new_list = todo;
- else
- prev->next = todo;
- done = 1;
- }
- prev = insert_at;
- insert_at = insert_at->next;
- }
-
- if (!done)
- {
- pr_debug_verbose(" %s added to list tail.\n", todo->vTable->name);
- prev->next = todo;
- todo->next = NULL;
+ //depth-first into any plugin that this one must come after...first
+ if (comparePluginDeps(p,list[i])==1)
+ depth_first_plugin(list[i],cnt,list);
}
- todo = next_todo;
}
+ p->next=plugins;
+ plugins=p;
+}
- plugins = new_list;
+static void sort_plugin_list(void)
+{
+ CompPlugin * pl = NULL;
+ //DAG Depth-First sorting:
+ CompPlugin * p[256];
+ int pState[256];
+ //backing array of plugins, simple and succinct
+ //now, we'll abuse state to store if a plugin has been visited in depth-first
+ int cnt=0;
+ for (pl=plugins;pl;pl=pl->next)
+ {
+ pState[cnt]=pl->state;
+ p[cnt++]=pl;
+ pl->state=0; // not visited
+ }
+ plugins = NULL;
+ int i;
+ for (i=0;i<cnt;i++)
+ depth_first_plugin(p[i],cnt,p);
+ for (i=0;i<cnt;i++)
+ p[i]->state=pState[i]; // restore state
+ CompPlugin * new_list = plugins;
pr_debug("New list: ");
while (new_list)
{