Mailing List Archive

commit db75092aea988b4be78c8273626f2ee40b4012b8
Author: Juergen Gross <jgross@suse.com>
AuthorDate: Wed Dec 14 12:02:21 2022 +0100
Commit: Jan Beulich <jbeulich@suse.com>
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@suse.com>
Reviewed-by: Julien Grall <jgrall@amazon.com>
---
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