beryl-core:

* Depth-First sort the plugin DAG instead of incorrect algo


git-svn-id: file:///beryl/trunk@4050 d7aaf104-2d23-0410-ae22-9d23157bf5a3

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)
 	{