[libvirt] [PATCH 2/5] Convert virDomainObjListPtr to use a hash of domain objects

[Daniel Veillard]

On Wed, Oct 14, 2009 at 11:48:51AM +0100, Daniel P. Berrange wrote:
> The current virDomainObjListPtr object stores domain objects in
> an array. This means that to find a particular objects requires
> O(n) time, and more critically acquiring O(n) mutex locks.
> 
> The new impl replaces the array with a virHashTable, keyed off
> UUID. Finding a object based on UUID is now O(1) time, and only
> requires a single mutex lock. Finding by name/id is unchanged
> in complexity.
> 
> In changing this, all code which iterates over the array had
> to be updated to use a hash table iterator function callback.
> Several of the functions which were identically duplicating
> across all drivers were pulled into domain_conf.c

  So we went from list to array, and now to hash table :-)

<nitpick>
I'm afraid the O(1) is an exageration since as the number grows
you would still need to lock each object on the clash list for
that hash. But for normal use we should end up in constant time,
but in theory I think it's still O(n) ...
</nitpick>
I expect that the gain will come from the fact all lookups intenally
are done though the UUID, the Name/ID being only convenience API.
I'm also wondering about the symetry for other kind of objects,
we probably don't need this for networks (less objects, less
operation and operation usually short), you really expect that
to be a single optimization and just for domains, right ?

Daniel


-- 
Daniel Veillard      | libxml Gnome XML XSLT toolkit  http://xmlsoft.org/
daniel at veillard.com  | Rpmfind RPM search engine http://rpmfind.net/
http://veillard.com/ | virtualization library  http://libvirt.org/