[qemu-xen master] qom: Make info qom-tree sort children more efficiently

[patchbot@xxxxxxx]

commit 0dde9fd12fd39762ff68fca80d2f0a735d66e7bd
Author:     Markus Armbruster <armbru@xxxxxxxxxx>
AuthorDate: Tue Jul 14 18:02:02 2020 +0200
Commit:     Markus Armbruster <armbru@xxxxxxxxxx>
CommitDate: Tue Jul 21 17:39:37 2020 +0200

    qom: Make info qom-tree sort children more efficiently
    
    Commit e8c9e65816 "qom: Make "info qom-tree" show children sorted"
    sorts children the simple, stupid, quadratic way.  I thought the
    number of children would be small enough for this not to matter.  I
    was wrong: there are outliers with several hundred children, e.g ARM
    machines nuri and smdkc210 each have a node with 513 children.
    
    While n^2 sorting isn't noticeable in normal, human usage even for
    n=513, it can be quite noticeable in certain automated tests.  In
    particular, the sort made device-introspect-test even slower.  Commit
    3e7b80f84d "tests: improve performance of device-introspect-test" just
    fixed that by cutting back its excessive use of "info qom-tree".
    Sorting more efficiently makes sense regardless, so do it.
    
    Signed-off-by: Markus Armbruster <armbru@xxxxxxxxxx>
    Message-Id: <20200714160202.3121879-6-armbru@xxxxxxxxxx>
    Reviewed-by: Dr. David Alan Gilbert <dgilbert@xxxxxxxxxx>
---
 qom/qom-hmp-cmds.c | 25 +++++++++++++------------
 1 file changed, 13 insertions(+), 12 deletions(-)

diff --git a/qom/qom-hmp-cmds.c b/qom/qom-hmp-cmds.c
index 4032c96089..8861a109d5 100644
--- a/qom/qom-hmp-cmds.c
+++ b/qom/qom-hmp-cmds.c
@@ -94,25 +94,23 @@ typedef struct QOMCompositionState {
 
 static void print_qom_composition(Monitor *mon, Object *obj, int indent);
 
-static int qom_composition_compare(const void *a, const void *b, void *ignore)
+static int qom_composition_compare(const void *a, const void *b)
 {
-    return g_strcmp0(object_get_canonical_path_component(a),
-                     object_get_canonical_path_component(b));
+    return g_strcmp0(object_get_canonical_path_component(*(Object **)a),
+                     object_get_canonical_path_component(*(Object **)b));
 }
 
 static int insert_qom_composition_child(Object *obj, void *opaque)
 {
-    GQueue *children = opaque;
-
-    g_queue_insert_sorted(children, obj, qom_composition_compare, NULL);
+    g_array_append_val(opaque, obj);
     return 0;
 }
 
 static void print_qom_composition(Monitor *mon, Object *obj, int indent)
 {
+    GArray *children = g_array_new(false, false, sizeof(Object *));
     const char *name;
-    GQueue children;
-    Object *child;
+    int i;
 
     if (obj == object_get_root()) {
         name = "";
@@ -122,11 +120,14 @@ static void print_qom_composition(Monitor *mon, Object 
*obj, int indent)
     monitor_printf(mon, "%*s/%s (%s)\n", indent, "", name,
                    object_get_typename(obj));
 
-    g_queue_init(&children);
-    object_child_foreach(obj, insert_qom_composition_child, &children);
-    while ((child = g_queue_pop_head(&children))) {
-        print_qom_composition(mon, child, indent + 2);
+    object_child_foreach(obj, insert_qom_composition_child, children);
+    g_array_sort(children, qom_composition_compare);
+
+    for (i = 0; i < children->len; i++) {
+        print_qom_composition(mon, g_array_index(children, Object *, i),
+                              indent + 2);
     }
+    g_array_free(children, TRUE);
 }
 
 void hmp_info_qom_tree(Monitor *mon, const QDict *dict)
--
generated by git-patchbot for /home/xen/git/qemu-xen.git#master