[libvirt] [PATCH 1/4] snapshot: framework for more efficient relation traversal

[Eric Blake]

On 10/09/2011 08:37 PM, Daniel Veillard wrote:
>> This layout intentionally hardcodes the size of each snapshot,
>> by tracking sibling pointers, rather than having to deal with
>> the headache of yet more memory management by directly sticking
>> a child[] on each parent.
>
> Okay, so you're using a 'first child'. But why try to maintain
> 'nchildren' since you can't get the list in 0(1) anyway and
> need to walk the sibling. It's just redundant data to me, but maybe
> I didn't understood the use :-)

See patch 3/4.  When no other flags are present, 
virDomainSnapshotNumChildren only needs to read the nchildren member 
[and virDomainSnapshotNum with LIST_ROOTS the nroots member] (for O(1) 
operation), rather than walk the list of first_child/sibling (for O(n) 
operation).  You are correct that virDomainSnapshotListChildrenNames has 
to walk the list, but since at least one API can benefit from not 
walking the list, we might as well track both pieces of information.

>>
>> +
>> +struct snapshot_set_relation {
>> +    virDomainSnapshotObjListPtr snapshots;
>> +    int err;
>> +};
>> +
>
>   The following function isn't trivial, worth adding a comment about
> expected use.
>
>> +static void
>> +virDomainSnapshotSetRelations(void *payload,
>> +                              const void *name ATTRIBUTE_UNUSED,
>> +                              void *data)

Indeed, although it is a callback function only used by 
virDomainSnapshotUpdateRelations.  Here's what I'll add:

/* Callback when iterating over a hash table of snapshots, where all
  * snapshots start with no metadata.  For each snapshot with a parent,
  * set the parent metadata field, and update the parent's list of
  * children.  Set the error flag if a parent is not found or would
  * cause a circular chain.  */

>
>    Okay, just wondering about the usefulness of nchidren/nroot :-)

Did I manage to explain it?

>
>    ACK

I'll wait on your feedback regarding whether I should attempt the 
meta-root concept now, or just push as-is and save a meta-root concept 
for later patches.

-- 
Eric Blake   eblake at redhat.com    +1-801-349-2682
Libvirt virtualization library http://libvirt.org