Re: [libvirt] [PATCH v2] util: Simplify hash implementation
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(a)redhat.com +1-801-349-2682
Libvirt virtualization library http://libvirt.org
Attachments:
- signature.asc (application/pgp-signature — 620 bytes)