Skip to contentSkip to conversation

tools/xenstore: simplify hashtable implementation

PATCH Superseded Juergen Gross 2 participants 7 messages Jan 20, 2022 – Jan 21, 2022

v1 of 2 Superseded Latest is v2 →

lore
Share & tools
lore
#0 lore raw

cover tools/xenstore: simplify hashtable implementation

Do some simplifications in the hashtable implementation not touching the hashtable interfaces.

Juergen Gross (3):
tools/xenstore: merge hashtable_private.h into hashtable.c tools/xenstore: fix hashtable_expand() zeroing new area tools/xenstore: drop DEFINE_HASHTABLE_* macros and usage intro

 tools/xenstore/hashtable.c         | 34 ++++++++++--
 tools/xenstore/hashtable.h         | 76 --------------------------
 tools/xenstore/hashtable_private.h | 85 ------------------------------
 3 files changed, 29 insertions(+), 166 deletions(-)
 delete mode 100644 tools/xenstore/hashtable_private.h
Signature · 1 line
2.31.1
#1 lore raw

PATCH 1/3 tools/xenstore: merge hashtable_private.h into hashtable.c

hashtable_private.h is used in hashtable.c only.

---
 tools/xenstore/hashtable.c         | 31 +++++++++--
 tools/xenstore/hashtable_private.h | 85 ------------------------------
 2 files changed, 27 insertions(+), 89 deletions(-)
 delete mode 100644 tools/xenstore/hashtable_private.h
tools/xenstore/hashtable.c +27 -4
index 394b1cf9d0..39fb3ed338 100644
@@ -1,13 +1,29 @@
 /* Copyright (C) 2004 Christopher Clark <[email protected]> */
 
 #include "hashtable.h"
-#include "hashtable_private.h"
 #include <stdlib.h>
 #include <stdio.h>
 #include <string.h>
 #include <math.h>
 #include <stdint.h>
 
+struct entry
+{
+    void *k, *v;
+    unsigned int h;
+    struct entry *next;
+};
+
+struct hashtable {
+    unsigned int tablelength;
+    struct entry **table;
+    unsigned int entrycount;
+    unsigned int loadlimit;
+    unsigned int primeindex;
+    unsigned int (*hashfn) (void *k);
+    int (*eqfn) (void *k1, void *k2);
+};
+
 /*
 Credit for primes table: Aaron Krowne
  http://br.endernet.org/~akrowne/
@@ -25,6 +41,13 @@ static const unsigned int primes[] = {
 const unsigned int prime_table_length = sizeof(primes)/sizeof(primes[0]);
 const unsigned int max_load_factor = 65; /* percentage */
 
+/*****************************************************************************/
+/* indexFor */
+static inline unsigned int
+indexFor(unsigned int tablelength, unsigned int hashvalue) {
+    return (hashvalue % tablelength);
+}
+
 /*****************************************************************************/
 struct hashtable *
 create_hashtable(unsigned int minsize,
@@ -211,7 +234,7 @@ hashtable_remove(struct hashtable *h, void *k)
             *pE = e->next;
             h->entrycount--;
             v = e->v;
-            freekey(e->k);
+            free(e->k);
             free(e);
             return v;
         }
@@ -235,7 +258,7 @@ hashtable_destroy(struct hashtable *h, int free_values)
         {
             e = table[i];
             while (NULL != e)
-            { f = e; e = e->next; freekey(f->k); free(f->v); free(f); }
+            { f = e; e = e->next; free(f->k); free(f->v); free(f); }
         }
     }
     else
@@ -244,7 +267,7 @@ hashtable_destroy(struct hashtable *h, int free_values)
         {
             e = table[i];
             while (NULL != e)
-            { f = e; e = e->next; freekey(f->k); free(f); }
+            { f = e; e = e->next; free(f->k); free(f); }
         }
     }
     free(h->table);
tools/xenstore/hashtable_private.h deleted +0 -85

85 lines not on this page · raw message

Signature · 1 line
2.31.1
#3 lore raw

PATCH 2/3 tools/xenstore: fix hashtable_expand() zeroing new area

In reply to Juergen Gross

When realloc()ing the hashtable for expanding it, zero out all the new bytes at the end of the table, not only one byte for each new element.

Fixes 186f0e02a1c ("Added hashtable implementation")

---
This might be a backport candidate

---
 tools/xenstore/hashtable.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)
tools/xenstore/hashtable.c +2 -1
index 39fb3ed338..6ac336eff1 100644
@@ -136,7 +136,8 @@ hashtable_expand(struct hashtable *h)
                    realloc(h->table, newsize * sizeof(struct entry *));
         if (NULL == newtable) { (h->primeindex)--; return 0; }
         h->table = newtable;
-        memset(newtable[h->tablelength], 0, newsize - h->tablelength);
+        memset(newtable + h->tablelength, 0,
+               (newsize - h->tablelength) * sizeof(*newtable));
         for (i = 0; i < h->tablelength; i++) {
             for (pE = &(newtable[i]), e = *pE; e != NULL; e = *pE) {
                 index = indexFor(newsize,e->h);
Signature · 1 line
2.31.1
Reviewed-by on v1 2/3
#4 lore raw

Re: [PATCH 2/3] tools/xenstore: fix hashtable_expand() zeroing new area

Quoted 5 lines · Juergen Gross

When realloc()ing the hashtable for expanding it, zero out all the new bytes at the end of the table, not only one byte for each new element.

Fixes 186f0e02a1c ("Added hashtable implementation")

Thanks,

Signature · 1 line
Anthony PERARD
#5 lore raw

PATCH 3/3 tools/xenstore: drop DEFINE_HASHTABLE_* macros and usage intro

In reply to Juergen Gross

The DEFINE_HASHTABLE_* macros are used nowhere, so drop them. The usage intro isn't needed either with those macros dropped.

---
 tools/xenstore/hashtable.h | 76 --------------------------------------
 1 file changed, 76 deletions(-)
tools/xenstore/hashtable.h +0 -76
index b90781abd4..62fef6081a 100644
@@ -5,62 +5,6 @@
 
 struct hashtable;
 
-/* Example of use:
- *
- *      struct hashtable  *h;
- *      struct some_key   *k;
- *      struct some_value *v;
- *
- *      static unsigned int         hash_from_key_fn( void *k );
- *      static int                  keys_equal_fn ( void *key1, void *key2 );
- *
- *      h = create_hashtable(16, hash_from_key_fn, keys_equal_fn);
- *      k = (struct some_key *)     malloc(sizeof(struct some_key));
- *      v = (struct some_value *)   malloc(sizeof(struct some_value));
- *
- *      (initialise k and v to suitable values)
- * 
- *      if (! hashtable_insert(h,k,v) )
- *      {     exit(-1);               }
- *
- *      if (NULL == (found = hashtable_search(h,k) ))
- *      {    printf("not found!");                  }
- *
- *      if (NULL == (found = hashtable_remove(h,k) ))
- *      {    printf("Not found\n");                 }
- *
- */
-
-/* Macros may be used to define type-safe(r) hashtable access functions, with
- * methods specialized to take known key and value types as parameters.
- * 
- * Example:
- *
- * Insert this at the start of your file:
- *
- * DEFINE_HASHTABLE_INSERT(insert_some, struct some_key, struct some_value);
- * DEFINE_HASHTABLE_SEARCH(search_some, struct some_key, struct some_value);
- * DEFINE_HASHTABLE_REMOVE(remove_some, struct some_key, struct some_value);
- *
- * This defines the functions 'insert_some', 'search_some' and 'remove_some'.
- * These operate just like hashtable_insert etc., with the same parameters,
- * but their function signatures have 'struct some_key *' rather than
- * 'void *', and hence can generate compile time errors if your program is
- * supplying incorrect data as a key (and similarly for value).
- *
- * Note that the hash and key equality functions passed to create_hashtable
- * still take 'void *' parameters instead of 'some key *'. This shouldn't be
- * a difficult issue as they're only defined and passed once, and the other
- * functions will ensure that only valid keys are supplied to them.
- *
- * The cost for this checking is increased code size and runtime overhead
- * - if performance is important, it may be worth switching back to the
- * unsafe methods once your program has been debugged with the safe methods.
- * This just requires switching to some simple alternative defines - eg:
- * #define insert_some hashtable_insert
- *
- */
-
 /*****************************************************************************
  * create_hashtable
    
@@ -98,12 +42,6 @@ create_hashtable(unsigned int minsize,
 int 
 hashtable_insert(struct hashtable *h, void *k, void *v);
 
-#define DEFINE_HASHTABLE_INSERT(fnname, keytype, valuetype) \
-int fnname (struct hashtable *h, keytype *k, valuetype *v) \
-{ \
-    return hashtable_insert(h,k,v); \
-}
-
 /*****************************************************************************
  * hashtable_search
    
@@ -116,12 +54,6 @@ int fnname (struct hashtable *h, keytype *k, valuetype *v) \
 void *
 hashtable_search(struct hashtable *h, void *k);
 
-#define DEFINE_HASHTABLE_SEARCH(fnname, keytype, valuetype) \
-valuetype * fnname (struct hashtable *h, keytype *k) \
-{ \
-    return (valuetype *) (hashtable_search(h,k)); \
-}
-
 /*****************************************************************************
  * hashtable_remove
    
@@ -134,13 +66,6 @@ valuetype * fnname (struct hashtable *h, keytype *k) \
 void * /* returns value */
 hashtable_remove(struct hashtable *h, void *k);
 
-#define DEFINE_HASHTABLE_REMOVE(fnname, keytype, valuetype) \
-valuetype * fnname (struct hashtable *h, keytype *k) \
-{ \
-    return (valuetype *) (hashtable_remove(h,k)); \
-}
-
-
 /*****************************************************************************
  * hashtable_count
    
@@ -151,7 +76,6 @@ valuetype * fnname (struct hashtable *h, keytype *k) \
 unsigned int
 hashtable_count(struct hashtable *h);
 
-
 /*****************************************************************************
  * hashtable_destroy
    
Signature · 1 line
2.31.1
#6 lore raw

Re: [PATCH 3/3] tools/xenstore: drop DEFINE_HASHTABLE_* macros and usage intro

Quoted 2 lines · Juergen Gross

The DEFINE_HASHTABLE_* macros are used nowhere, so drop them. The usage intro isn't needed either with those macros dropped.

The first part of the intro "Example of use:" doesn't speak about the macro, so removing the macro part doesn't mean that the first part should be removed. But it is probably not necessary as the documentation for the functions are probably good enough to figure out how to use hashtable. Can you reword that last sentence?

Thanks,

Signature · 1 line
Anthony PERARD