[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[xen master] tools/xenstore: enhance hashtable implementation



commit db75092aea988b4be78c8273626f2ee40b4012b8
Author:     Juergen Gross <jgross@xxxxxxxx>
AuthorDate: Wed Dec 14 12:02:21 2022 +0100
Commit:     Jan Beulich <jbeulich@xxxxxxxx>
CommitDate: Wed Dec 14 12:02:21 2022 +0100

    tools/xenstore: enhance hashtable implementation
    
    Today it is possible to set a flag when calling hashtable_destroy() in
    order to specify whether the data associated with the hashtable entries
    should be freed or not. The keys of the entries will always be freed.
    
    Change that by replacing the flag of hashtable_destroy() by two flags
    for create_hashtable() which will specify whether the data and/or the
    key of each entry should be freed or not.
    
    This will enable users to have the key e.g. as part of the data.
    
    Add a new function hashtable_iterate() to call a user specified
    function for each entry in the hashtable.
    
    Add new primes to the primetable in order to support smaller sizes of
    the hashtable. The primes are selected according to:
    
    https://planetmath.org/goodhashtableprimes
    
    Update the URL in the source as the old one wasn't correct any longer.
    
    Signed-off-by: Juergen Gross <jgross@xxxxxxxx>
    Reviewed-by: Julien Grall <jgrall@xxxxxxxxxx>
---
 tools/xenstore/hashtable.c      | 66 ++++++++++++++++++++++++++++-------------
 tools/xenstore/hashtable.h      | 35 ++++++++++++++++++++--
 tools/xenstore/xenstored_core.c |  7 +++--
 3 files changed, 82 insertions(+), 26 deletions(-)

diff --git a/tools/xenstore/hashtable.c b/tools/xenstore/hashtable.c
index 6ac336eff1..299549c51e 100644
--- a/tools/xenstore/hashtable.c
+++ b/tools/xenstore/hashtable.c
@@ -16,6 +16,7 @@ struct entry
 
 struct hashtable {
     unsigned int tablelength;
+    unsigned int flags;
     struct entry **table;
     unsigned int entrycount;
     unsigned int loadlimit;
@@ -25,12 +26,11 @@ struct hashtable {
 };
 
 /*
-Credit for primes table: Aaron Krowne
- http://br.endernet.org/~akrowne/
- http://planetmath.org/encyclopedia/GoodHashTablePrimes.html
-*/
+ * Credit for primes table: Aaron Krowne
+ * https://planetmath.org/goodhashtableprimes
+ */
 static const unsigned int primes[] = {
-53, 97, 193, 389,
+11, 23, 53, 97, 193, 389,
 769, 1543, 3079, 6151,
 12289, 24593, 49157, 98317,
 196613, 393241, 786433, 1572869,
@@ -52,7 +52,8 @@ indexFor(unsigned int tablelength, unsigned int hashvalue) {
 struct hashtable *
 create_hashtable(unsigned int minsize,
                  unsigned int (*hashf) (void*),
-                 int (*eqf) (void*,void*))
+                 int (*eqf) (void*,void*),
+                 unsigned int flags)
 {
     struct hashtable *h;
     unsigned int pindex, size = primes[0];
@@ -73,6 +74,7 @@ create_hashtable(unsigned int minsize,
         goto err1;
 
     h->tablelength  = size;
+    h->flags        = flags;
     h->primeindex   = pindex;
     h->entrycount   = 0;
     h->hashfn       = hashf;
@@ -235,7 +237,8 @@ hashtable_remove(struct hashtable *h, void *k)
             *pE = e->next;
             h->entrycount--;
             v = e->v;
-            free(e->k);
+            if (h->flags & HASHTABLE_FREE_KEY)
+                free(e->k);
             free(e);
             return v;
         }
@@ -246,29 +249,52 @@ hashtable_remove(struct hashtable *h, void *k)
 }
 
 /*****************************************************************************/
-/* destroy */
-void
-hashtable_destroy(struct hashtable *h, int free_values)
+int
+hashtable_iterate(struct hashtable *h,
+                  int (*func)(const void *k, void *v, void *arg), void *arg)
 {
+    int ret;
     unsigned int i;
     struct entry *e, *f;
     struct entry **table = h->table;
-    if (free_values)
+
+    for (i = 0; i < h->tablelength; i++)
     {
-        for (i = 0; i < h->tablelength; i++)
+        e = table[i];
+        while (e)
         {
-            e = table[i];
-            while (NULL != e)
-            { f = e; e = e->next; free(f->k); free(f->v); free(f); }
+            f = e;
+            e = e->next;
+            ret = func(f->k, f->v, arg);
+            if (ret)
+                return ret;
         }
     }
-    else
+
+    return 0;
+}
+
+/*****************************************************************************/
+/* destroy */
+void
+hashtable_destroy(struct hashtable *h)
+{
+    unsigned int i;
+    struct entry *e, *f;
+    struct entry **table = h->table;
+
+    for (i = 0; i < h->tablelength; i++)
     {
-        for (i = 0; i < h->tablelength; i++)
+        e = table[i];
+        while (NULL != e)
         {
-            e = table[i];
-            while (NULL != e)
-            { f = e; e = e->next; free(f->k); free(f); }
+            f = e;
+            e = e->next;
+            if (h->flags & HASHTABLE_FREE_KEY)
+                free(f->k);
+            if (h->flags & HASHTABLE_FREE_VALUE)
+                free(f->v);
+            free(f);
         }
     }
     free(h->table);
diff --git a/tools/xenstore/hashtable.h b/tools/xenstore/hashtable.h
index 62fef6081a..6d65431f96 100644
--- a/tools/xenstore/hashtable.h
+++ b/tools/xenstore/hashtable.h
@@ -12,13 +12,21 @@ struct hashtable;
  * @param   minsize         minimum initial size of hashtable
  * @param   hashfunction    function for hashing keys
  * @param   key_eq_fn       function for determining key equality
+ * @param   flags           flags HASHTABLE_*
  * @return                  newly created hashtable or NULL on failure
  */
 
+/* Let hashtable_destroy() free the entries' values. */
+#define HASHTABLE_FREE_VALUE (1U << 0)
+/* Let hashtable_remove() and hashtable_destroy() free the entries' keys. */
+#define HASHTABLE_FREE_KEY   (1U << 1)
+
 struct hashtable *
 create_hashtable(unsigned int minsize,
                  unsigned int (*hashfunction) (void*),
-                 int (*key_eq_fn) (void*,void*));
+                 int (*key_eq_fn) (void*,void*),
+                 unsigned int flags
+);
 
 /*****************************************************************************
  * hashtable_insert
@@ -76,16 +84,37 @@ hashtable_remove(struct hashtable *h, void *k);
 unsigned int
 hashtable_count(struct hashtable *h);
 
+/*****************************************************************************
+ * hashtable_iterate
+
+ * @name           hashtable_iterate
+ * @param   h      the hashtable
+ * @param   func   function to call for each entry
+ * @param   arg    user supplied parameter for func
+ * @return         0 if okay, non-zero return value of func (and iteration
+ *                 was aborted)
+ *
+ * Iterates over all entries in the hashtable and calls func with the
+ * key, value, and the user supplied parameter.
+ * func returning a non-zero value will abort the iteration. In case func is
+ * removing an entry other than itself from the hashtable, it must return a
+ * non-zero value in order to abort the iteration. Inserting entries is
+ * allowed, but it is undefined whether func will be called for those new
+ * entries during this iteration.
+ */
+int
+hashtable_iterate(struct hashtable *h,
+                  int (*func)(const void *k, void *v, void *arg), void *arg);
+
 /*****************************************************************************
  * hashtable_destroy
    
  * @name        hashtable_destroy
  * @param   h   the hashtable
- * @param       free_values     whether to call 'free' on the remaining values
  */
 
 void
-hashtable_destroy(struct hashtable *h, int free_values);
+hashtable_destroy(struct hashtable *h);
 
 #endif /* __HASHTABLE_CWC22_H__ */
 
diff --git a/tools/xenstore/xenstored_core.c b/tools/xenstore/xenstored_core.c
index f68f82cb19..78a3edaa4e 100644
--- a/tools/xenstore/xenstored_core.c
+++ b/tools/xenstore/xenstored_core.c
@@ -2514,7 +2514,9 @@ void check_store(void)
                .enoent = check_store_enoent,
        };
 
-       reachable = create_hashtable(16, hash_from_key_fn, keys_equal_fn);
+       /* Don't free values (they are all void *1) */
+       reachable = create_hashtable(16, hash_from_key_fn, keys_equal_fn,
+                                    HASHTABLE_FREE_KEY);
        if (!reachable) {
                log("check_store: ENOMEM");
                return;
@@ -2528,8 +2530,7 @@ void check_store(void)
                clean_store(reachable);
        log("Checking store complete.");
 
-       hashtable_destroy(reachable, 0 /* Don't free values (they are all
-                                         (void *)1) */);
+       hashtable_destroy(reachable);
 }
 
 
--
generated by git-patchbot for /home/xen/git/xen.git#master



 


Rackspace

Lists.xenproject.org is hosted with RackSpace, monitoring our
servers 24x7x365 and backed by RackSpace's Fanatical Support®.