[libvirt] [PATCH 2/5] snapshots: Support topological visits

[Eric Blake]

Wire up support for VIR_DOMAIN_SNAPSHOT_LIST_TOPOLOGICAL in the
domain-agnostic support code.

Clients of snapshot_conf were previously getting a depth-first search
on anything that used virDomainSnapshotForEachDescendant(); but a
switch to a breadth-first search will give a topological search.

With that change, we now always have a topological sort for
virDomainSnapshotListAllChildren(); then with one more tweak, we
can get a topological rather than a faster random hash visit
for virDomainListAllSnapshots().

Note that virDomainSnapshotForEach() still uses a random hash
visit; we could change that signature to take a tri-state for
random, depth-first, or breadth-first visit if we ever had clients
that cared about the distinctions, but for now, none of the
drivers seem to care.

Signed-off-by: Eric Blake <eblake at redhat.com>
---
 src/conf/snapshot_conf.c | 15 ++++++++++-----
 1 file changed, 10 insertions(+), 5 deletions(-)

diff --git a/src/conf/snapshot_conf.c b/src/conf/snapshot_conf.c
index 224f3e6ca1..e2c91a5072 100644
--- a/src/conf/snapshot_conf.c
+++ b/src/conf/snapshot_conf.c
@@ -1213,9 +1213,10 @@ virDomainSnapshotObjListGetNames(virDomainSnapshotObjListPtr snapshots,
         from = &snapshots->metaroot;
     }

-    /* We handle LIST_ROOT/LIST_DESCENDANTS directly, mask that bit
-     * out to determine when we must use the filter callback.  */
-    data.flags &= ~VIR_DOMAIN_SNAPSHOT_LIST_DESCENDANTS;
+    /* We handle LIST_ROOT/LIST_DESCENDANTS and LIST_TOPOLOGICAL directly,
+     * mask those bits out to determine when we must use the filter callback. */
+    data.flags &= ~(VIR_DOMAIN_SNAPSHOT_LIST_DESCENDANTS |
+                    VIR_DOMAIN_SNAPSHOT_LIST_TOPOLOGICAL);

     /* If this common code is being used, we assume that all snapshots
      * have metadata, and thus can handle METADATA up front as an
@@ -1240,7 +1241,11 @@ virDomainSnapshotObjListGetNames(virDomainSnapshotObjListPtr snapshots,
         data.flags &= ~VIR_DOMAIN_SNAPSHOT_FILTERS_LOCATION;

     if (flags & VIR_DOMAIN_SNAPSHOT_LIST_DESCENDANTS) {
-        if (from->def)
+        /* We could just always do a topological visit; but it is
+         * possible to optimize for less stack usage and time when a
+         * simpler full hashtable visit or counter will do. */
+        if (from->def || (names &&
+                          (flags & VIR_DOMAIN_SNAPSHOT_LIST_TOPOLOGICAL)))
             virDomainSnapshotForEachDescendant(from,
                                                virDomainSnapshotObjListCopyNames,
                                                &data);
@@ -1327,10 +1332,10 @@ virDomainSnapshotActOnDescendant(void *payload,
     virDomainSnapshotObjPtr obj = payload;
     struct snapshot_act_on_descendant *curr = data;

+    (curr->iter)(payload, name, curr->data);
     curr->number += 1 + virDomainSnapshotForEachDescendant(obj,
                                                            curr->iter,
                                                            curr->data);
-    (curr->iter)(payload, name, curr->data);
     return 0;
 }

-- 
2.20.1