[libvirt] [PATCH v2] util: Simplify hash implementation

[Eric Blake]

On 04/12/2011 11:25 AM, Jiri Denemark wrote:
> So far first entries for each hash key are stored directly in the hash
> table while other entries mapped to the same key are linked through
> pointers. As a result of that, the code is cluttered with special
> handling for the first items.
> 
> This patch makes all entries (even the first ones) linked through
> pointers, which significantly simplifies the code and makes it more
> maintainable.
> ---
>  src/util/hash.c |  294 +++++++++++++++++--------------------------------------
>  1 files changed, 92 insertions(+), 202 deletions(-)

The diffstat proves the maintainability aspect, even if the code is
(slightly) less efficient now by doing more malloc calls.  Gnulib has
some hash modules, which might further offload some of our maintenance
burden, except that they are GPL rather than LGPLv2+, so I doubt we'll
ever be able to use them.

> 
> diff --git a/src/util/hash.c b/src/util/hash.c
> index fc7652d..dbb34ec 100644
> --- a/src/util/hash.c
> +++ b/src/util/hash.c
> @@ -50,14 +50,13 @@ struct _virHashEntry {
>      struct _virHashEntry *next;
>      void *name;
>      void *payload;
> -    int valid;
>  };
>  
>  /*
>   * The entire hash table
>   */
>  struct _virHashTable {
> -    struct _virHashEntry *table;
> +    virHashEntryPtr *table;

Makes sense - an array of pointers, rather than an array of first
entries with pointers to the rest of the chain.

> @@ -217,43 +214,18 @@ virHashGrow(virHashTablePtr table, int size)
>      }
>      table->size = size;
>  
> -    /* If the two loops are merged, there would be situations where
> -     * a new entry needs to allocated and data copied into it from
> -     * the main table. So instead, we run through the array twice, first
> -     * copying all the elements in the main array (where we can't get
> -     * conflicts) and then the rest, so we only free (and don't allocate)

Oh my.  That statement is only true if growth is always by a
power-of-two multiple (which happened to be the case, but could easily
be broken had we changed MAX_HASH_LEN to something other than 8).
Another good reason for this patch.

ACK - all the changes look correct, and certainly simpler.

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

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 620 bytes
Desc: OpenPGP digital signature
URL: <http://listman.redhat.com/archives/libvir-list/attachments/20110412/9f371ec4/attachment-0001.sig>