[pacman-dev] [patch] IV/A patch for patch again, now sortbydeps is about O(e+n)

[Nagy Gabor]

Hi!
First, hopefully this is my last for this weekend ;-)
And subject was a little cheating because the O(n^2) prepare part still
exists, but the core part now O(n+e) where e is the number of depends
which is usually O(n), so the core algorithm is about O(n) now.
Here is the little patch:
-------------------------
diff -Naur pacman-lib/lib/libalpm/deps.c pacman-lib.new/lib/libalpm/deps.c
--- pacman-lib/lib/libalpm/deps.c	2007-04-22 19:46:40.000000000 +0200
+++ pacman-lib.new/lib/libalpm/deps.c	2007-04-22 19:46:09.000000000 +0200
@@ -69,9 +69,10 @@
 
 pmgraph_t *_alpm_graph_finduntouched(alpm_list_t *vertices)
 {
-	alpm_list_t *i;
+	static alpm_list_t *i = NULL;
+	if (!i)	i = vertices;
 	pmgraph_t *found = NULL;
-	for (i = vertices; i && !found; i = i->next) {
+	for (; i && !found; i = i->next) {
 		pmgraph_t *vertex = i->data;
 		if (vertex->state == 0) found = vertex;
 	}
--------------------------
Enjoy, ngaba