Changeset 95062 in webkit

Timestamp:

Sep 13, 2011 6:03:47 PM (13 years ago)

Author:

commit-queue@webkit.org

Message:

GTK DumpRenderTree uses inefficient idioms to iterate over G[S]Lists
​https://bugs.webkit.org/show_bug.cgi?id=68024

Patch by Leandro Pereira <​leandro@profusion.mobi> on 2011-09-13
Reviewed by Gustavo Noronha Silva.

Using g_list_count() and g_list_nth_data() together on a loop is
inneficient since they're both O(n). Iterate over lists in a saner
way.

• DumpRenderTree/gtk/DumpRenderTree.cpp:

(dumpHistoryItem): Reduce the scope for the 'kids' variable, and
iterate on it using g_list_next(). Free the list after done with it.
(dumpBackForwardListForWebView): Instead of appending (which is
expensive in GLists) history items and then iterating from the tail
of the itemsToPrint list, prepend items and walk forwards as usual.
(dumpBackForwardListForAllWebViews): Walk the list in a saner way,
remove the (unneeded) viewList variable.

Location:

trunk/Tools

Files:

• ChangeLog (modified) (1 diff)
• DumpRenderTree/gtk/DumpRenderTree.cpp (modified) (4 diffs)

trunk/Tools/ChangeLog

@@ +1 @@
+2011-09-13  Leandro Pereira  <leandro@profusion.mobi>
+
+        GTK DumpRenderTree uses inefficient idioms to iterate over G[S]Lists
+        https://bugs.webkit.org/show_bug.cgi?id=68024
+
+        Reviewed by Gustavo Noronha Silva.
+        
+        Using g_list_count() and g_list_nth_data() together on a loop is
+        inneficient since they're both O(n). Iterate over lists in a saner
+        way.
+
+        * DumpRenderTree/gtk/DumpRenderTree.cpp:
+        (dumpHistoryItem): Reduce the scope for the 'kids' variable, and
+        iterate on it using g_list_next(). Free the list after done with it.
+        (dumpBackForwardListForWebView): Instead of appending (which is
+        expensive in GLists) history items and then iterating from the tail
+        of the itemsToPrint list, prepend items and walk forwards as usual.
+        (dumpBackForwardListForAllWebViews): Walk the list in a saner way,
+        remove the (unneeded) viewList variable.
+
 2011-09-13  Ryosuke Niwa  <rniwa@webkit.org>
 

trunk/Tools/DumpRenderTree/gtk/DumpRenderTree.cpp

@@ -331 +331 @@
         printf("  **nav target**");
     putchar('\n');
-    GList* kids = webkit_web_history_item_get_children(item);
-    if (kids) {
+
+    if (GList* kids = webkit_web_history_item_get_children(item)) {
         // must sort to eliminate arbitrary result ordering which defeats reproducible testing
-        kids = g_list_sort(kids, (GCompareFunc) compareHistoryItems);
-        for (unsigned i = 0; i < g_list_length(kids); i++)
-            dumpHistoryItem(WEBKIT_WEB_HISTORY_ITEM(g_list_nth_data(kids, i)), indent+4, FALSE);
+        for (GList* kid = g_list_sort(kids, (GCompareFunc) compareHistoryItems); kid; kid = g_list_next(kid)) {
+            WebKitWebHistoryItem* item = WEBKIT_WEB_HISTORY_ITEM(kid->data);
+            dumpHistoryItem(item, indent + 4, FALSE);
+            g_object_unref(item);
+        }
+        g_list_free(kids);
     }
     g_object_unref(item);
@@ -355 +358 @@
         ASSERT(item != prevTestBFItem);
         g_object_ref(item);
-        itemsToPrint = g_list_append(itemsToPrint, item);
+        itemsToPrint = g_list_prepend(itemsToPrint, item);
     }
 
     WebKitWebHistoryItem* currentItem = webkit_web_back_forward_list_get_current_item(bfList);
-
     g_object_ref(currentItem);
-    itemsToPrint = g_list_append(itemsToPrint, currentItem);
-
-    gint currentItemIndex = g_list_length(itemsToPrint) - 1;
+    itemsToPrint = g_list_prepend(itemsToPrint, currentItem);
+
     gint backListCount = webkit_web_back_forward_list_get_back_length(bfList);
     for (int i = -1; i >= -(backListCount); i--) {
@@ -370 +371 @@
             break;
         g_object_ref(item);
-        itemsToPrint = g_list_append(itemsToPrint, item);
-    }
-
-    for (int i = g_list_length(itemsToPrint) - 1; i >= 0; i--) {
-        WebKitWebHistoryItem* item = WEBKIT_WEB_HISTORY_ITEM(g_list_nth_data(itemsToPrint, i));
-        dumpHistoryItem(item, historyItemIndent, i == currentItemIndex);
+        itemsToPrint = g_list_prepend(itemsToPrint, item);
+    }
+
+    for (GList* itemToPrint = itemsToPrint; itemToPrint; itemToPrint = g_list_next(itemToPrint)) {
+        WebKitWebHistoryItem* item = WEBKIT_WEB_HISTORY_ITEM(itemToPrint->data);
+        dumpHistoryItem(item, historyItemIndent, item == currentItem);
         g_object_unref(item);
     }
+
     g_list_free(itemsToPrint);
     printf("===============================================\n");
@@ -388 +390 @@
 
     // The view list is prepended. Reverse the list so we get the order right.
-    GSList* viewList = g_slist_reverse(webViewList);
-    for (unsigned i = 0; i < g_slist_length(viewList); ++i)
-        dumpBackForwardListForWebView(WEBKIT_WEB_VIEW(g_slist_nth_data(viewList, i)));
+    for (GSList* currentView = g_slist_reverse(webViewList); currentView; currentView = g_slist_next(currentView))
+        dumpBackForwardListForWebView(WEBKIT_WEB_VIEW(currentView->data));
 }