tools/xenstore: simplify hashtable implementation
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 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
Re: [PATCH 1/3] tools/xenstore: merge hashtable_private.h into hashtable.c
Quoted 3 lines · Juergen Gross
hashtable_private.his used inhashtable.conly.Signed-off-by Juergen Gross <[email protected]>
Thanks,
Signature · 1 line
Anthony PERARD
PATCH 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
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")Signed-off-by Juergen Gross <[email protected]>
Thanks,
Signature · 1 line
Anthony PERARD
PATCH 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 needed either with those macros dropped.
--- 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 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