From e57e0027de393d95172be8d3910d45bf4950469f Mon Sep 17 00:00:00 2001
From: Dan Nicholson <dbn.lists@gmail.com>
Date: Mon, 29 Oct 2012 17:30:18 -0700
Subject: [PATCH] Combine copying and  merging of flags to avoid repeated
 traversals

When combining the flags from all the packages together, each flags list
was being copied and then concatenated to then end of the combined list.
This was extremely inefficient because it caused the combined list to be
traversed multiple times to find the end. Instead, combine the copying
and merging of the flags together so the last element is always tracked
and can easily be appended to.

Freedesktop #54716 (https://bugs.freedesktop.org/show_bug.cgi?id=54716)
---
 pkg.c |   38 +++++++++++++++++++++++---------------
 1 files changed, 23 insertions(+), 15 deletions(-)

diff --git a/pkg.c b/pkg.c
index d725a08..bf304b9 100644
--- a/pkg.c
+++ b/pkg.c
@@ -613,16 +613,6 @@ packages_sort_by_path_position (GSList *list)
 }
 
 static void
-fill_one_level (Package *pkg, GetListFunc func, GSList **listp)
-{
-  GSList *copy;
-
-  copy = g_slist_copy ((*func)(pkg));
-
-  *listp = g_slist_concat (*listp, copy);
-}
-
-static void
 recursive_fill_list (Package *pkg, GetListFunc func, GSList **listp)
 {
   GSList *tmp;
@@ -663,6 +653,8 @@ fill_list (GSList *packages, GetListFunc func,
 {
   GSList *tmp;
   GSList *expanded;
+  GSList *last;
+  GSList *flags;
 
   expanded = NULL;
   tmp = packages;
@@ -684,14 +676,30 @@ fill_list (GSList *packages, GetListFunc func,
       spew_package_list ("sorted", expanded);
     }
   
-  tmp = expanded;
-  while (tmp != NULL)
+  /* merge the flags from the individual packages */
+  for (tmp = expanded, last = NULL; tmp != NULL; tmp = tmp->next)
     {
-      fill_one_level (tmp->data, func, listp);
-      
-      tmp = tmp->next;
+      /* manually copy the elements so we can keep track of the end */
+      for (flags = (*func) (tmp->data); flags != NULL; flags = flags->next)
+        {
+          if (last == NULL)
+            {
+              *listp = g_slist_alloc ();
+              last = *listp;
+            }
+          else
+            {
+              last->next = g_slist_alloc ();
+              last = last->next;
+            }
+          last->data = flags->data;
+        }
     }
 
+  /* terminate the last element */
+  if (last != NULL)
+    last->next = NULL;
+
   g_slist_free (expanded);
 }
 
-- 
1.7.7.6