[U-Boot] [Patch] Fix hash table deletion to prevent lost entries

[Wolfgang Denk]

Dear Peter Barada,

In message <4D371208.3090801 at 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

-- 
DENX Software Engineering GmbH,     MD: Wolfgang Denk & Detlev Zundel
HRB 165235 Munich, Office: Kirchenstr.5, D-82194 Groebenzell, Germany
Phone: (+49)-8142-66989-10 Fax: (+49)-8142-66989-80 Email: wd at denx.de
As far as the laws of mathematics refer to reality, they are not cer-
tain, and as far as they are certain, they do not refer  to  reality.
                                                   -- Albert Einstein