[PATCHv2 10/13] util: hash: Reimplement virHashTable using GHashTable

Tuesday, 27 October 2020

Glib's hash table provides basically the same functionality as our hash
table.

In most cases the only thing that remains in the virHash* wrappers is
NULL-checks of '@table' argument as glib's hash functions don't tolerate
NULL.

In case of iterators, we adapt the existing API of iterators to glibs to
prevent having rewrite all callers at this point.

Signed-off-by: Peter Krempa <pkrempa(a)redhat.com&gt;
---

v2:
 - don't drop hashcode.c
 - use our hash function instead, including random seed

 src/util/virhash.c | 432 +++++++++++++--------------------------------
 src/util/virhash.h |   4 +-
 2 files changed, 129 insertions(+), 307 deletions(-)

diff --git a/src/util/virhash.c b/src/util/virhash.c
index a5ab48dbf5..6d03d4035f 100644
--- a/src/util/virhash.c
+++ b/src/util/virhash.c
@@ -21,42 +21,15 @@

 #include "virerror.h"
 #include "virhash.h"
-#include "viralloc.h"
 #include "virlog.h"
 #include "virhashcode.h"
 #include "virrandom.h"
-#include "virstring.h"
 #include "virobject.h"

 #define VIR_FROM_THIS VIR_FROM_NONE

 VIR_LOG_INIT("util.hash");

-#define MAX_HASH_LEN 8
-
-/* #define DEBUG_GROW */
-
-/*
- * A single entry in the hash table
- */
-typedef struct _virHashEntry virHashEntry;
-typedef virHashEntry *virHashEntryPtr;
-struct _virHashEntry {
-    struct _virHashEntry *next;
-    char *name;
-    void *payload;
-};
-
-/*
- * The entire hash table
- */
-struct _virHashTable {
-    virHashEntryPtr *table;
-    uint32_t seed;
-    size_t size;
-    size_t nbElems;
-    virHashDataFree dataFree;
-};

 struct _virHashAtomic {
     virObjectLockable parent;
@@ -76,11 +49,28 @@ static int virHashAtomicOnceInit(void)

 VIR_ONCE_GLOBAL_INIT(virHashAtomic);

-static size_t
-virHashComputeKey(const virHashTable *table, const char *name)
+
+/**
+ * Our hash function uses a random seed to provide uncertainity from run to run
+ * to prevent pre-crafting of colliding hash keys.
+ */
+static uint32_t virHashTableSeed;
+
+static int virHashTableSeedOnceInit(void)
+{
+    virHashTableSeed = virRandomBits(32);
+    return 0;
+}
+
+VIR_ONCE_GLOBAL_INIT(virHashTableSeed);
+
+
+static unsigned int
+virHashTableStringKey(const void *vkey)
 {
-    uint32_t value = virHashCodeGen(name, strlen(name), table->seed);
-    return value % table->size;
+    const char *key = vkey;
+
+    return virHashCodeGen(key, strlen(key), virHashTableSeed);
 }


@@ -95,18 +85,9 @@ virHashComputeKey(const virHashTable *table, const char *name)
 virHashTablePtr
 virHashNew(virHashDataFree dataFree)
 {
-    virHashTablePtr table = NULL;
-
-    table = g_new0(virHashTable, 1);
-
-    table->seed = virRandomBits(32);
-    table->size = 32;
-    table->nbElems = 0;
-    table->dataFree = dataFree;
+    ignore_value(virHashTableSeedInitialize());

-    table->table = g_new0(virHashEntryPtr, table->size);
-
-    return table;
+    return g_hash_table_new_full(virHashTableStringKey, g_str_equal, g_free, dataFree);
 }


@@ -138,66 +119,6 @@ virHashAtomicDispose(void *obj)
 }


-/**
- * virHashGrow:
- * @table: the hash table
- * @size: the new size of the hash table
- *
- * resize the hash table
- *
- * Returns 0 in case of success, -1 in case of failure
- */
-static int
-virHashGrow(virHashTablePtr table, size_t size)
-{
-    size_t oldsize, i;
-    virHashEntryPtr *oldtable;
-
-#ifdef DEBUG_GROW
-    size_t nbElem = 0;
-#endif
-
-    if (table == NULL)
-        return -1;
-    if (size < 8)
-        return -1;
-    if (size > 8 * 2048)
-        return -1;
-
-    oldsize = table->size;
-    oldtable = table->table;
-    if (oldtable == NULL)
-        return -1;
-
-    table->table = g_new0(virHashEntryPtr, size);
-    table->size = size;
-
-    for (i = 0; i < oldsize; i++) {
-        virHashEntryPtr iter = oldtable[i];
-        while (iter) {
-            virHashEntryPtr next = iter->next;
-            size_t key = virHashComputeKey(table, iter->name);
-
-            iter->next = table->table[key];
-            table->table[key] = iter;
-
-#ifdef DEBUG_GROW
-            nbElem++;
-#endif
-            iter = next;
-        }
-    }
-
-    VIR_FREE(oldtable);
-
-#ifdef DEBUG_GROW
-    VIR_DEBUG("virHashGrow : from %d to %d, %ld elems", oldsize,
-              size, nbElem);
-#endif
-
-    return 0;
-}
-
 /**
  * virHashFree:
  * @table: the hash table
@@ -208,76 +129,12 @@ virHashGrow(virHashTablePtr table, size_t size)
 void
 virHashFree(virHashTablePtr table)
 {
-    size_t i;
-
     if (table == NULL)
         return;

-    for (i = 0; i < table->size; i++) {
-        virHashEntryPtr iter = table->table[i];
-        while (iter) {
-            virHashEntryPtr next = iter->next;
-
-            if (table->dataFree)
-                table->dataFree(iter->payload);
-            g_free(iter->name);
-            VIR_FREE(iter);
-            iter = next;
-        }
-    }
-
-    VIR_FREE(table->table);
-    VIR_FREE(table);
+    g_hash_table_unref(table);
 }

-static int
-virHashAddOrUpdateEntry(virHashTablePtr table, const char *name,
-                        void *userdata,
-                        bool is_update)
-{
-    size_t key, len = 0;
-    virHashEntryPtr entry;
-    virHashEntryPtr last = NULL;
-
-    if ((table == NULL) || (name == NULL))
-        return -1;
-
-    key = virHashComputeKey(table, name);
-
-    /* Check for duplicate entry */
-    for (entry = table->table[key]; entry; entry = entry->next) {
-        if (STREQ(entry->name, name)) {
-            if (is_update) {
-                if (table->dataFree)
-                    table->dataFree(entry->payload);
-                entry->payload = userdata;
-                return 0;
-            } else {
-                virReportError(VIR_ERR_INTERNAL_ERROR,
-                               _("Duplicate hash table key '%s'"),
name);
-                return -1;
-            }
-        }
-        last = entry;
-        len++;
-    }
-
-    entry = g_new0(virHashEntry, 1);
-    entry->name = g_strdup(name);
-    entry->payload = userdata;
-
-    if (last)
-        last->next = entry;
-    else
-        table->table[key] = entry;
-
-    table->nbElems++;
-
-    if (len > MAX_HASH_LEN)
-        virHashGrow(table, MAX_HASH_LEN * table->size);
-
-    return 0;
-}

 /**
  * virHashAddEntry:
@@ -293,7 +150,18 @@ virHashAddOrUpdateEntry(virHashTablePtr table, const char *name,
 int
 virHashAddEntry(virHashTablePtr table, const char *name, void *userdata)
 {
-    return virHashAddOrUpdateEntry(table, name, userdata, false);
+    if (!table || !name)
+        return -1;
+
+    if (g_hash_table_contains(table, name)) {
+        virReportError(VIR_ERR_INTERNAL_ERROR,
+                       _("Duplicate hash table key '%s'"), name);
+        return -1;
+    }
+
+    g_hash_table_insert(table, g_strdup(name), userdata);
+
+    return 0;
 }

 /**
@@ -312,7 +180,12 @@ int
 virHashUpdateEntry(virHashTablePtr table, const char *name,
                    void *userdata)
 {
-    return virHashAddOrUpdateEntry(table, name, userdata, true);
+    if (!table || !name)
+        return -1;
+
+    g_hash_table_insert(table, g_strdup(name), userdata);
+
+    return 0;
 }

 int
@@ -323,33 +196,13 @@ virHashAtomicUpdate(virHashAtomicPtr table,
     int ret;

     virObjectLock(table);
-    ret = virHashAddOrUpdateEntry(table->hash, name, userdata, true);
+    ret = virHashUpdateEntry(table->hash, name, userdata);
     virObjectUnlock(table);

     return ret;
 }


-static virHashEntryPtr
-virHashGetEntry(const virHashTable *table,
-                const char *name)
-{
-    size_t key;
-    virHashEntryPtr entry;
-
-    if (!table || !name)
-        return NULL;
-
-    key = virHashComputeKey(table, name);
-    for (entry = table->table[key]; entry; entry = entry->next) {
-        if (STREQ(entry->name, name))
-            return entry;
-    }
-
-    return NULL;
-}
-
-
 /**
  * virHashLookup:
  * @table: the hash table
@@ -363,12 +216,10 @@ void *
 virHashLookup(virHashTablePtr table,
               const char *name)
 {
-    virHashEntryPtr entry = virHashGetEntry(table, name);
-
-    if (!entry)
+    if (!table || !name)
         return NULL;

-    return entry->payload;
+    return g_hash_table_lookup(table, name);
 }


@@ -385,7 +236,10 @@ bool
 virHashHasEntry(virHashTablePtr table,
                 const char *name)
 {
-    return !!virHashGetEntry(table, name);
+    if (!table || !name)
+        return false;
+
+    return g_hash_table_contains(table, name);
 }


@@ -401,14 +255,19 @@ virHashHasEntry(virHashTablePtr table,
  */
 void *virHashSteal(virHashTablePtr table, const char *name)
 {
-    void *data = virHashLookup(table, name);
-    if (data) {
-        virHashDataFree dataFree = table->dataFree;
-        table->dataFree = NULL;
-        virHashRemoveEntry(table, name);
-        table->dataFree = dataFree;
-    }
-    return data;
+    g_autofree void *orig_name = NULL;
+    void *val = NULL;
+
+    if (!table || !name)
+        return NULL;
+
+    /* we can replace this by g_hash_table_steal_extended with glib 2.58 */
+    if (!(g_hash_table_lookup_extended(table, name, &orig_name, &val)))
+        return NULL;
+
+    g_hash_table_steal(table, name);
+
+    return val;
 }

 void *
@@ -439,7 +298,8 @@ virHashSize(virHashTablePtr table)
 {
     if (table == NULL)
         return -1;
-    return table->nbElems;
+
+    return g_hash_table_size(table);
 }


@@ -455,27 +315,14 @@ virHashSize(virHashTablePtr table)
  * Returns 0 if the removal succeeded and -1 in case of error or not found.
  */
 int
-virHashRemoveEntry(virHashTablePtr table, const char *name)
+virHashRemoveEntry(virHashTablePtr table,
+                   const char *name)
 {
-    virHashEntryPtr entry;
-    virHashEntryPtr *nextptr;
-
-    if (table == NULL || name == NULL)
+    if (!table || !name)
         return -1;

-    nextptr = table->table + virHashComputeKey(table, name);
-    for (entry = *nextptr; entry; entry = entry->next) {
-        if (STREQ(entry->name, name)) {
-            if (table->dataFree)
-                table->dataFree(entry->payload);
-            g_free(entry->name);
-            *nextptr = entry->next;
-            VIR_FREE(entry);
-            table->nbElems--;
-            return 0;
-        }
-        nextptr = &entry->next;
-    }
+    if (g_hash_table_remove(table, name))
+        return 0;

     return -1;
 }
@@ -511,23 +358,18 @@ virHashRemoveEntry(virHashTablePtr table, const char *name)
 int
 virHashForEach(virHashTablePtr table, virHashIterator iter, void *opaque)
 {
-    size_t i;
-    int ret = -1;
+    GHashTableIter htitr;
+    void *key;
+    void *value;

-    if (table == NULL || iter == NULL)
+    if (!table || !iter)
         return -1;

-    for (i = 0; i < table->size; i++) {
-        virHashEntryPtr entry = table->table[i];
-        while (entry) {
-            virHashEntryPtr next = entry->next;
-            ret = iter(entry->payload, entry->name, opaque);
+    g_hash_table_iter_init(&htitr, table);

-            if (ret < 0)
-                return ret;
-
-            entry = next;
-        }
+    while (g_hash_table_iter_next(&htitr, &key, &value)) {
+        if (iter(value, key, opaque) < 0)
+            return -1;
     }

     return 0;
@@ -574,6 +416,24 @@ virHashForEachSorted(virHashTablePtr table,
 }


+struct virHashSearcherWrapFuncData {
+    virHashSearcher iter;
+    const void *opaque;
+    const char *name;
+};
+
+static gboolean
+virHashSearcherWrapFunc(gpointer key,
+                        gpointer value,
+                        gpointer opaque)
+{
+    struct virHashSearcherWrapFuncData *data = opaque;
+
+    data->name = key;
+
+    return !!(data->iter(value, key, data->opaque));
+}
+
 /**
  * virHashRemoveSet
  * @table: the hash table to process
@@ -592,39 +452,12 @@ virHashRemoveSet(virHashTablePtr table,
                  virHashSearcher iter,
                  const void *opaque)
 {
-    size_t i, count = 0;
+    struct virHashSearcherWrapFuncData data = { iter, opaque, NULL };

     if (table == NULL || iter == NULL)
         return -1;

-    for (i = 0; i < table->size; i++) {
-        virHashEntryPtr *nextptr = table->table + i;
-
-        while (*nextptr) {
-            virHashEntryPtr entry = *nextptr;
-            if (!iter(entry->payload, entry->name, opaque)) {
-                nextptr = &entry->next;
-            } else {
-                count++;
-                if (table->dataFree)
-                    table->dataFree(entry->payload);
-                g_free(entry->name);
-                *nextptr = entry->next;
-                VIR_FREE(entry);
-                table->nbElems--;
-            }
-        }
-    }
-
-    return count;
-}
-
-static int
-_virHashRemoveAllIter(const void *payload G_GNUC_UNUSED,
-                      const char *name G_GNUC_UNUSED,
-                      const void *opaque G_GNUC_UNUSED)
-{
-    return 1;
+    return g_hash_table_foreach_remove(table, virHashSearcherWrapFunc, &data);
 }

 /**
@@ -637,7 +470,10 @@ _virHashRemoveAllIter(const void *payload G_GNUC_UNUSED,
 void
 virHashRemoveAll(virHashTablePtr table)
 {
-    virHashRemoveSet(table, _virHashRemoveAllIter, NULL);
+    if (!table)
+        return;
+
+    g_hash_table_remove_all(table);
 }

 /**
@@ -658,45 +494,19 @@ void *virHashSearch(virHashTablePtr table,
                     const void *opaque,
                     char **name)
 {
-    size_t i;
-
+    struct virHashSearcherWrapFuncData data = { iter, opaque, NULL };
+    void *ret;

-    if (table == NULL || iter == NULL)
+    if (!table || !iter)
         return NULL;

-    for (i = 0; i < table->size; i++) {
-        virHashEntryPtr entry;
-        for (entry = table->table[i]; entry; entry = entry->next) {
-            if (iter(entry->payload, entry->name, opaque)) {
-                if (name)
-                    *name = g_strdup(entry->name);
-                return entry->payload;
-            }
-        }
-    }
-
-    return NULL;
-}
-
-
-struct virHashGetItemsIteratorData {
-    virHashKeyValuePair *items;
-    size_t i;
-};
-
-
-static int
-virHashGetItemsIterator(void *payload,
-                        const char *key,
-                        void *opaque)
-{
-    struct virHashGetItemsIteratorData *data = opaque;
+    if (!(ret = g_hash_table_find(table, virHashSearcherWrapFunc, &data)))
+        return NULL;

-    data->items[data->i].key = key;
-    data->items[data->i].value = payload;
+    if (name)
+        *name = g_strdup(data.name);

-    data->i++;
-    return 0;
+    return ret;
 }


@@ -716,22 +526,34 @@ virHashGetItems(virHashTablePtr table,
                 size_t *nitems,
                 bool sortKeys)
 {
+    virHashKeyValuePair *items;
     size_t dummy;
-    struct virHashGetItemsIteratorData data = { .items = NULL, .i = 0 };
+    GHashTableIter htitr;
+    void *key;
+    void *value;
+    size_t i = 0;

     if (!nitems)
         nitems = &dummy;

-    *nitems = virHashSize(table);
+    if (!table)
+        return NULL;
+
+    *nitems = g_hash_table_size(table);
+    items = g_new0(virHashKeyValuePair, *nitems + 1);

-    data.items = g_new0(virHashKeyValuePair, *nitems + 1);
+    g_hash_table_iter_init(&htitr, table);

-    virHashForEach(table, virHashGetItemsIterator, &data);
+    while (g_hash_table_iter_next(&htitr, &key, &value)) {
+        items[i].key = key;
+        items[i].value = value;
+        i++;
+    }

     if (sortKeys)
-        qsort(data.items, *nitems, sizeof(* data.items), virHashGetItemsKeySorter);
+        qsort(items, *nitems, sizeof(*items), virHashGetItemsKeySorter);

-    return data.items;
+    return items;
 }


diff --git a/src/util/virhash.h b/src/util/virhash.h
index 3af4786e9b..70f74dbc5f 100644
--- a/src/util/virhash.h
+++ b/src/util/virhash.h
@@ -12,7 +12,7 @@
 /*
  * The hash table.
  */
-typedef struct _virHashTable virHashTable;
+typedef GHashTable virHashTable;
 typedef virHashTable *virHashTablePtr;

 typedef struct _virHashAtomic virHashAtomic;
@@ -142,4 +142,4 @@ ssize_t virHashRemoveSet(virHashTablePtr table, virHashSearcher iter,
const void
 void *virHashSearch(virHashTablePtr table, virHashSearcher iter,
                     const void *opaque, char **name);

-G_DEFINE_AUTOPTR_CLEANUP_FUNC(virHashTable, virHashFree);
+G_DEFINE_AUTOPTR_CLEANUP_FUNC(virHashTable, g_hash_table_unref);
-- 
2.26.2


    

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

2009

2008

2007

2006

2005

[PATCHv2 10/13] util: hash: Reimplement virHashTable using GHashTable