tools/xenstore: simplify hashtable implementation
v2 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
PATCH v2 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
@@ -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
PATCH v2 2/3 tools/xenstore: fix hashtable_expand() zeroing new area
In reply to Juergen GrossWhen 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.
---
This might be a backport candidate
--- tools/xenstore/hashtable.c | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-)
tools/xenstore/hashtable.c +2 -1
@@ -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
PATCH v2 3/3 tools/xenstore: drop DEFINE_HASHTABLE_* macros and usage intro
In reply to Juergen GrossThe DEFINE_HASHTABLE_* macros are used nowhere, so drop them. The usage intro isn't really needed either.
---
V2:
- reword commit message (Anthony PERARD)
--- tools/xenstore/hashtable.h | 76 -------------------------------------- 1 file changed, 76 deletions(-)
tools/xenstore/hashtable.h +0 -76
@@ -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
Re: [PATCH v2 3/3] tools/xenstore: drop DEFINE_HASHTABLE_* macros and usage intro
Quoted 4 lines · Juergen Gross
The DEFINE_HASHTABLE_* macros are used nowhere, so drop them. The usage intro isn't really needed either.
Signed-off-by Juergen Gross <[email protected]>
Thanks,
Signature · 1 line
Anthony PERARD