Dear Peter Barada,
In message 4D371208.3090801@logicpd.com you wrote:
The hash delete code is in error; instead of just removing the deleted key, it should instead allocate a new hashtable, hash all the keys into the new table except for the deleted key and then reclaim the old table (and deleted key).
Can you please come up with a patch?
Hashtable delete is broken since freeing entry could break collision chain for other entries. Instead free key/data pair and mark entry as deleted (via negative used value) and then skip deleted entries while probing.
Break up hsearch_r into separate henter_r/hfind_r functions for readability. Recycle first deleted entry in probe chain when adding entry to table. Factor primary/secondary hash calculations into functions and use in henter_r/hfind_r/hdelete_r.
include/search.h | 16 ++- lib/hashtable.c | 382 ++++++++++++++++++++++++++++++++--------------------- 2 files changed, 241 insertions(+), 157 deletions(-)
diff --git a/include/search.h b/include/search.h index a7c1293..4466731 100644 --- a/include/search.h +++ b/include/search.h @@ -66,12 +66,16 @@ extern int hcreate_r(size_t __nel, struct hsearch_data *__htab); extern void hdestroy_r(struct hsearch_data *__htab);
/*
- Search for entry matching ITEM.key in internal hash table. If
- ACTION is `FIND' return found entry or signal error by returning
- NULL. If ACTION is `ENTER' replace existing data (if any) with
- ITEM.data.
- */
-extern int hsearch_r(ENTRY __item, ACTION __action, ENTRY ** __retval,
- Search for entry matching ITEM.key in internal hash table. Return
- found entry or signal error by returning NULL.
- */
+extern int hfind_r(ENTRY __item, ENTRY ** __retval,
struct hsearch_data *__htab);+/*
- Add entry matching ITEM.key in internal hash table. Replace
- existing data (if any) with ITEM.data.
- */
+extern int henter_r(ENTRY __item, ENTRY ** __retval, struct hsearch_data *__htab);
/* diff --git a/lib/hashtable.c b/lib/hashtable.c index 9f069c0..7b5153a 100644 --- a/lib/hashtable.c +++ b/lib/hashtable.c @@ -65,7 +65,7 @@
- which describes the current status.
*/ typedef struct _ENTRY {
- unsigned int used;
- int used; ENTRY entry; } _ENTRY;
@@ -152,7 +152,7 @@ void hdestroy_r(struct hsearch_data *htab)
/* free used memory */ for (i = 1; i <= htab->size; ++i) {
if (htab->table[i].used) {
if (htab->table[i].used > 0) { ENTRY *ep = &htab->table[i].entry; free(ep->key);@@ -165,77 +165,20 @@ void hdestroy_r(struct hsearch_data *htab) htab->table = NULL; }
-/*
- hsearch()
- */
-/*
- This is the search function. It uses double hashing with open
addressing.
- The argument item.key has to be a pointer to an zero terminated, most
- probably strings of chars. The function for generating a number of the
- strings is simple but fast. It can be replaced by a more complex
function
Your patch is line-wrapped and does not apply.
Also, insteadof imlementing just the discussed fix, it appears to me a major rewrite - you thow away lots of (useful, in my opinion) comments, debug code, etc., and even replace major parts of the code.
In the result, the code looks pretty much different from the standard C library function it was derived from.
I don't think all this was needed only to fix the observed problem?
What is your rationale for all these changes?
Best regards,
Wolfgang Denk