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

Monday, 26 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;
---
 src/libvirt_private.syms |   4 -
 src/util/meson.build     |   1 -
 src/util/virhash.c       | 416 ++++++++++-----------------------------
 src/util/virhash.h       |   4 +-
 src/util/virhashcode.c   | 125 ------------
 src/util/virhashcode.h   |  33 ----
 6 files changed, 107 insertions(+), 476 deletions(-)
 delete mode 100644 src/util/virhashcode.c
 delete mode 100644 src/util/virhashcode.h

diff --git a/src/libvirt_private.syms b/src/libvirt_private.syms
index f7b0d11ca2..9a5269fd0b 100644
--- a/src/libvirt_private.syms
+++ b/src/libvirt_private.syms
@@ -2219,10 +2219,6 @@ virHashSteal;
 virHashUpdateEntry;


-# util/virhashcode.h
-virHashCodeGen;
-
-
 # util/virhook.h
 virHookCall;
 virHookInitialize;
diff --git a/src/util/meson.build b/src/util/meson.build
index 3b711b1dc2..99f72cb04a 100644
--- a/src/util/meson.build
+++ b/src/util/meson.build
@@ -36,7 +36,6 @@ util_sources = [
   'virgettext.c',
   'virgic.c',
   'virhash.c',
-  'virhashcode.c',
   'virhook.c',
   'virhostcpu.c',
   'virhostmem.c',
diff --git a/src/util/virhash.c b/src/util/virhash.c
index a5ab48dbf5..ed658714e8 100644
--- a/src/util/virhash.c
+++ b/src/util/virhash.c
@@ -21,42 +21,13 @@

 #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,13 +47,6 @@ static int virHashAtomicOnceInit(void)

 VIR_ONCE_GLOBAL_INIT(virHashAtomic);

-static size_t
-virHashComputeKey(const virHashTable *table, const char *name)
-{
-    uint32_t value = virHashCodeGen(name, strlen(name), table->seed);
-    return value % table->size;
-}
-

 /**
  * virHashNew:
@@ -95,18 +59,7 @@ 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;
-
-    table->table = g_new0(virHashEntryPtr, table->size);
-
-    return table;
+    return g_hash_table_new_full(g_str_hash, g_str_equal, g_free, dataFree);
 }


@@ -138,66 +91,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 +101,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 +122,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 +152,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 +168,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 +188,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 +208,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 +227,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 +270,8 @@ virHashSize(virHashTablePtr table)
 {
     if (table == NULL)
         return -1;
-    return table->nbElems;
+
+    return g_hash_table_size(table);
 }


@@ -455,27 +287,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 +330,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 +388,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 +424,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 +442,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 +466,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 +498,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);
diff --git a/src/util/virhashcode.c b/src/util/virhashcode.c
deleted file mode 100644
index baa7a0b1c0..0000000000
--- a/src/util/virhashcode.c
+++ /dev/null
@@ -1,125 +0,0 @@
-/*
- * virhashcode.c: hash code generation
- *
- * Copyright (C) 2012 Red Hat, Inc.
- *
- * This library is free software; you can redistribute it and/or
- * modify it under the terms of the GNU Lesser General Public
- * License as published by the Free Software Foundation; either
- * version 2.1 of the License, or (at your option) any later version.
- *
- * This library is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
- * Lesser General Public License for more details.
- *
- * You should have received a copy of the GNU Lesser General Public
- * License along with this library.  If not, see
- * <http://www.gnu.org/licenses/>;.
- *
- * The hash code generation is based on the public domain MurmurHash3 from Austin
Appleby:
- * https://code.google.com/p/smhasher/source/browse/trunk/MurmurHash3.cpp
- *
- * We use only the 32 bit variant because the 2 produce different results while
- * we need to produce the same result regardless of the architecture as
- * clients can be both 64 or 32 bit at the same time.
- */
-
-#include <config.h>
-
-#include "virhashcode.h"
-
-static uint32_t rotl32(uint32_t x, int8_t r)
-{
-    return (x << r) | (x >> (32 - r));
-}
-
-/* slower than original but handles platforms that do only aligned reads */
-static inline uint32_t getblock(const uint8_t *p, int i)
-{
-    uint32_t r;
-    size_t size = sizeof(r);
-
-    memcpy(&r, &p[i * size], size);
-
-    return r;
-}
-
-/*
- * Finalization mix - force all bits of a hash block to avalanche
- */
-static inline uint32_t fmix(uint32_t h)
-{
-    h ^= h >> 16;
-    h *= 0x85ebca6b;
-    h ^= h >> 13;
-    h *= 0xc2b2ae35;
-    h ^= h >> 16;
-
-    return h;
-}
-
-
-uint32_t virHashCodeGen(const void *key, size_t len, uint32_t seed)
-{
-    const uint8_t *blocks;
-    const uint8_t *tail;
-    size_t nblocks;
-    uint32_t h1;
-    uint32_t k1;
-    uint32_t c1;
-    uint32_t c2;
-    size_t i;
-
-    blocks = (const uint8_t *)key;
-    nblocks = len / 4;
-    h1 = seed;
-    c1 = 0xcc9e2d51;
-    c2 = 0x1b873593;
-
-    /* body */
-
-    for (i = 0; i < nblocks; i++) {
-
-        k1 = getblock(blocks, i);
-
-        k1 *= c1;
-        k1 = rotl32(k1, 15);
-        k1 *= c2;
-
-        h1 ^= k1;
-        h1 = rotl32(h1, 13);
-        h1 = h1 * 5 + 0xe6546b64;
-    }
-
-    /* tail */
-
-    tail = (const uint8_t *)key + nblocks * 4;
-
-    k1 = 0;
-
-    switch (len & 3) {
-    case 3:
-        k1 ^= tail[2] << 16;
-        G_GNUC_FALLTHROUGH;
-    case 2:
-        k1 ^= tail[1] << 8;
-        G_GNUC_FALLTHROUGH;
-    case 1:
-        k1 ^= tail[0];
-        k1 *= c1;
-        k1 = rotl32(k1, 15);
-        k1 *= c2;
-        h1 ^= k1;
-        G_GNUC_FALLTHROUGH;
-    default:
-        break;
-    }
-
-    /* finalization */
-
-    h1 ^= len;
-    h1 = fmix(h1);
-
-    return h1;
-}
diff --git a/src/util/virhashcode.h b/src/util/virhashcode.h
deleted file mode 100644
index 10d8451795..0000000000
--- a/src/util/virhashcode.h
+++ /dev/null
@@ -1,33 +0,0 @@
-/*
- * virhashcode.h: hash code generation
- *
- * Copyright (C) 2012 Red Hat, Inc.
- *
- * This library is free software; you can redistribute it and/or
- * modify it under the terms of the GNU Lesser General Public
- * License as published by the Free Software Foundation; either
- * version 2.1 of the License, or (at your option) any later version.
- *
- * This library is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
- * Lesser General Public License for more details.
- *
- * You should have received a copy of the GNU Lesser General Public
- * License along with this library.  If not, see
- * <http://www.gnu.org/licenses/>;.
- *
- * The hash code generation is based on the public domain MurmurHash3 from Austin
Appleby:
- * https://code.google.com/p/smhasher/source/browse/trunk/MurmurHash3.cpp
- *
- * We use only the 32 bit variant because the 2 produce different result while
- * we need to produce the same result regardless of the architecture as
- * clients can be both 64 or 32 bit at the same time.
- */
-
-#pragma once
-
-#include "internal.h"
-
-uint32_t virHashCodeGen(const void *key, size_t len, uint32_t seed)
-    G_GNUC_NO_INLINE;
-- 
2.26.2


    

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

2009

2008

2007

2006

2005

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