]> xenbits.xensource.com Git - libvirt.git/commit
snapshots: Support topological visits
authorEric Blake <eblake@redhat.com>
Fri, 8 Mar 2019 04:29:55 +0000 (22:29 -0600)
committerEric Blake <eblake@redhat.com>
Wed, 13 Mar 2019 01:46:09 +0000 (20:46 -0500)
commitb647d2195dc71aee25002121ca05ddc33396dff4
treeaf27ff123680dcb72d56d8079fd7539a29c6e6ce
parentd16e5b15edbd226f6e1d7c2ce7ea8bf91c3b21c7
snapshots: Support topological visits

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

Clients of snapshot_conf using virDomainSnapshotForEachDescendant()
are using a depth-first visit but with postfix visits of a given
node. Changing this to a prefix visit of the given node instantly
turns this into a topologically-ordered visit.  (A prefix
breadth-first visit would also be topologically sorted, but that
requires a queue while our recursion naturally has a stack).

With that change, we now always have a topological sort for
virDomainSnapshotListAllChildren() regardless of the new public API
flag. Then with one more tweak, we can also get a topological rather
than a faster random hash visit for virDomainListAllSnapshots(), by
doing a descendent walk from our internal metaroot (there, we let the
public API flag control behavior, because a topological sort DOES
require more stack and slightly more time).

Note that virDomainSnapshotForEach() still uses a random hash visit;
we could change that signature to take a tri-state for random, prefix,
or postfix 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@redhat.com>
Reviewed-by: Ján Tomko <jtomko@redhat.com>
Reviewed-by: Daniel P. Berrangé <berrange@redhat.com>
src/conf/snapshot_conf.c