On Fri, Oct 07, 2011 at 06:05:56PM -0600, Eric Blake wrote:
> Among other improvements, virDomainSnapshotForEachDescendant is
> changed from iterative O(n^2) to recursive O(n). A bit better
> than the O(n^3) implementation in virsh snapshot-list!
>
> * src/conf/domain_conf.c (virDomainSnapshotObjListNum)
> (virDomainSnapshotObjListNumFrom)
> (virDomainSnapshotObjeListGetNames, virDomainSnapshotForEachChild)
> (virDomainSnapshotForEachDescendant): Optimize.
> (virDomainSnapshotActOnDescendant): Tweak.
> (virDomainSnapshotActOnChild, virDomainSnapshotMarkDescendant):
> Delete, now that they are unused.
> ---
> src/conf/domain_conf.c | 148 ++++++++++++++----------------------------------
> 1 files changed, 43 insertions(+), 105 deletions(-)
>
> diff --git a/src/conf/domain_conf.c b/src/conf/domain_conf.c
> index d4e127d..e77257a 100644
> --- a/src/conf/domain_conf.c
> +++ b/src/conf/domain_conf.c
> @@ -12163,10 +12163,21 @@ int virDomainSnapshotObjListGetNames(virDomainSnapshotObjListPtr snapshots,
> char **const names, int maxnames,
> unsigned int flags)
> {
> - struct virDomainSnapshotNameData data = { 0, 0, maxnames, names, flags };
> + struct virDomainSnapshotNameData data = { 0, 0, maxnames, names, 0 };
> int i;
>
> - virHashForEach(snapshots->objs, virDomainSnapshotObjListCopyNames, &data);
> + data.flags = flags & ~VIR_DOMAIN_SNAPSHOT_LIST_ROOTS;
> +
> + if (!(flags & VIR_DOMAIN_SNAPSHOT_LIST_ROOTS)) {
> + virHashForEach(snapshots->objs, virDomainSnapshotObjListCopyNames,
> + &data);
> + } else {
> + virDomainSnapshotObjPtr root = snapshots->first_root;
> + while (root) {
> + virDomainSnapshotObjListCopyNames(root, root->def->name, &data);
> + root = root->sibling;
> + }
> + }
> if (data.oom) {
> virReportOOMError();
> goto cleanup;
> @@ -12231,9 +12242,21 @@ static void virDomainSnapshotObjListCount(void *payload,
> int virDomainSnapshotObjListNum(virDomainSnapshotObjListPtr snapshots,
> unsigned int flags)
> {
> - struct virDomainSnapshotNumData data = { 0, flags };
> + struct virDomainSnapshotNumData data = { 0, 0 };
>
> - virHashForEach(snapshots->objs, virDomainSnapshotObjListCount, &data);
> + data.flags = flags & ~VIR_DOMAIN_SNAPSHOT_LIST_ROOTS;
> +
> + if (!(flags & VIR_DOMAIN_SNAPSHOT_LIST_ROOTS)) {
> + virHashForEach(snapshots->objs, virDomainSnapshotObjListCount, &data);
> + } else if (data.flags) {
> + virDomainSnapshotObjPtr root = snapshots->first_root;
> + while (root) {
> + virDomainSnapshotObjListCount(root, root->def->name, &data);
> + root = root->sibling;
> + }
I was just wondering if a data structure with a meta-root snapshot
and unifying first_root as a first_children on that meta-root wouldn't
lead to simpler code overall.
> + } else {
> + data.count = snapshots->nroots;
> + }
>
> return data.count;
> }
> @@ -12251,9 +12274,11 @@ virDomainSnapshotObjListNumFrom(virDomainSnapshotObjPtr snapshot,
> virDomainSnapshotForEachDescendant(snapshots, snapshot,
> virDomainSnapshotObjListCount,
> &data);
> - else
> + else if (data.flags)
> virDomainSnapshotForEachChild(snapshots, snapshot,
> virDomainSnapshotObjListCount, &data);
> + else
> + data.count = snapshot->nchildren;
>
> return data.count;
> }
> @@ -12271,97 +12296,23 @@ void virDomainSnapshotObjListRemove(virDomainSnapshotObjListPtr snapshots,
> virHashRemoveEntry(snapshots->objs, snapshot->def->name);
> }
>
> -struct snapshot_act_on_child {
> - char *parent;
> - int number;
> - virHashIterator iter;
> - void *data;
> -};
> -
> -static void
> -virDomainSnapshotActOnChild(void *payload,
> - const void *name,
> - void *data)
> -{
> - virDomainSnapshotObjPtr obj = payload;
> - struct snapshot_act_on_child *curr = data;
> -
> - if (obj->def->parent && STREQ(curr->parent, obj->def->parent)) {
> - curr->number++;
> - if (curr->iter)
> - (curr->iter)(payload, name, curr->data);
> - }
> -}
> -
> /* Run iter(data) on all direct children of snapshot, while ignoring all
> * other entries in snapshots. Return the number of children
> * visited. No particular ordering is guaranteed. */
> int
> -virDomainSnapshotForEachChild(virDomainSnapshotObjListPtr snapshots,
> +virDomainSnapshotForEachChild(virDomainSnapshotObjListPtr snapshots ATTRIBUTE_UNUSED,
> virDomainSnapshotObjPtr snapshot,
> virHashIterator iter,
> void *data)
> {
> - struct snapshot_act_on_child act;
> + virDomainSnapshotObjPtr child = snapshot->first_child;
>
> - act.parent = snapshot->def->name;
> - act.number = 0;
> - act.iter = iter;
> - act.data = data;
> - virHashForEach(snapshots->objs, virDomainSnapshotActOnChild, &act);
> -
> - return act.number;
> -}
> -typedef enum {
> - MARK_NONE, /* No relation determined yet */
> - MARK_DESCENDANT, /* Descendant of target */
> - MARK_OTHER, /* Not a descendant of target */
> -} snapshot_mark;
> -
> -struct snapshot_mark_descendant {
> - const char *name; /* Parent's name on round 1, NULL on other rounds. */
> - virDomainSnapshotObjListPtr snapshots;
> - bool marked; /* True if descendants were found in this round */
> -};
> -
> -/* To be called in a loop until no more descendants are found.
> - * Additionally marking known unrelated snapshots reduces the number
> - * of total hash searches needed. */
> -static void
> -virDomainSnapshotMarkDescendant(void *payload,
> - const void *name ATTRIBUTE_UNUSED,
> - void *data)
> -{
> - virDomainSnapshotObjPtr obj = payload;
> - struct snapshot_mark_descendant *curr = data;
> - virDomainSnapshotObjPtr parent = NULL;
> -
> - /* Learned on a previous pass. */
> - if (obj->mark)
> - return;
> -
> - if (curr->name) {
> - /* First round can only find root nodes and direct children. */
> - if (!obj->def->parent) {
> - obj->mark = MARK_OTHER;
> - } else if (STREQ(obj->def->parent, curr->name)) {
> - obj->mark = MARK_DESCENDANT;
> - curr->marked = true;
> - }
> - } else {
> - /* All remaining rounds propagate marks from parents to children. */
> - parent = virDomainSnapshotFindByName(curr->snapshots, obj->def->parent);
> - if (!parent) {
> - VIR_WARN("snapshot hash table is inconsistent!");
> - obj->mark = MARK_OTHER;
> - return;
> - }
> - if (parent->mark) {
> - obj->mark = parent->mark;
> - if (obj->mark == MARK_DESCENDANT)
> - curr->marked = true;
> - }
> + while (child) {
> + (iter)(child, child->def->name, data);
> + child = child->sibling;
> }
> +
> + return snapshot->nchildren;
> }
>
> struct snapshot_act_on_descendant {
> @@ -12378,40 +12329,27 @@ virDomainSnapshotActOnDescendant(void *payload,
> virDomainSnapshotObjPtr obj = payload;
> struct snapshot_act_on_descendant *curr = data;
>
> - if (obj->mark == MARK_DESCENDANT) {
> - curr->number++;
> - (curr->iter)(payload, name, curr->data);
> - }
> - obj->mark = MARK_NONE;
> + curr->number++;
> + (curr->iter)(payload, name, curr->data);
> + virDomainSnapshotForEachDescendant(NULL, obj, curr->iter, curr->data);
> }
>
> /* Run iter(data) on all descendants of snapshot, while ignoring all
> * other entries in snapshots. Return the number of descendants
> * visited. No particular ordering is guaranteed. */
> int
> -virDomainSnapshotForEachDescendant(virDomainSnapshotObjListPtr snapshots,
> +virDomainSnapshotForEachDescendant(virDomainSnapshotObjListPtr snapshots ATTRIBUTE_UNUSED,
> virDomainSnapshotObjPtr snapshot,
> virHashIterator iter,
> void *data)
> {
> - struct snapshot_mark_descendant mark;
> struct snapshot_act_on_descendant act;
>
> - /* virHashForEach does not support nested traversal, so we must
> - * instead iterate until no more snapshots get marked. We
> - * guarantee that on exit, all marks have been cleared again. */
> - mark.name = snapshot->def->name;
> - mark.snapshots = snapshots;
> - mark.marked = true;
> - while (mark.marked) {
> - mark.marked = false;
> - virHashForEach(snapshots->objs, virDomainSnapshotMarkDescendant, &mark);
> - mark.name = NULL;
> - }
> act.number = 0;
> act.iter = iter;
> act.data = data;
> - virHashForEach(snapshots->objs, virDomainSnapshotActOnDescendant, &act);
> + virDomainSnapshotForEachChild(NULL, snapshot,
> + virDomainSnapshotActOnDescendant, &act);
>
> return act.number;
> }
ACK,
Daniel
--
Daniel Veillard | libxml Gnome XML XSLT toolkit http://xmlsoft.org/
daniel@xxxxxxxxxxxx | Rpmfind RPM search engine http://rpmfind.net/
http://veillard.com/ | virtualization library http://libvirt.org/
--
libvir-list mailing list
libvir-list@xxxxxxxxxx
https://www.redhat.com/mailman/listinfo/libvir-list