[PATCH v2 05/19] tools/xenstore: enhance hashtable implementation

[Juergen Gross <jgross@xxxxxxxx>]

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>
---
V2:
- add const to hashtable_iterate() callback (Julien Grall)
---
 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 8c2cca62b7..1650821922 100644
--- a/tools/xenstore/xenstored_core.c
+++ b/tools/xenstore/xenstored_core.c
@@ -2512,7 +2512,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;
@@ -2526,8 +2528,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);
 }
 
 
-- 
2.35.3