Re: [PATCH 2/5] libihash: add hurd_ihash_get_load

[Samuel Thibault]

Justus Winter, le Thu 15 May 2014 23:10:48 +0200, a écrit :
> * libihash/ihash.c (hurd_ihash_add): Move the code computing the load
> factor of the hash table...
> * libihash/ihash.h (hurd_ihash_get_load): ... here, together with the
> comment describing the method and the rationale for chosing binary
> percent.

Ack.

> ---
>  libihash/ihash.c | 20 ++------------------
>  libihash/ihash.h | 24 ++++++++++++++++++++++++
>  2 files changed, 26 insertions(+), 18 deletions(-)
> 
> diff --git a/libihash/ihash.c b/libihash/ihash.c
> index f20ba61..4d9cc18 100644
> --- a/libihash/ihash.c
> +++ b/libihash/ihash.c
> @@ -273,24 +273,8 @@ hurd_ihash_add (hurd_ihash_t ht, hurd_ihash_key_t key, 
> hurd_ihash_value_t item)
>  
>    if (ht->size)
>      {
> -      /* Only fill the hash table up to its maximum load factor given
> -         as "binary percent", where 128b% corresponds to 100%.  As the
> -         size is always a power of two, and 128 is also, the quotient
> -         of both is also a power of two.  Therefore, we can use bit
> -         shifts to scale the number of items.
> -
> -         load = nr_items * 128 / size
> -              = nr_items * 2^{log2 (128) - log2 (size)}
> -              = nr_items >> (log2 (size) - log2 (128))
> -                                -- if size >= 128
> -              = nr_items << (log2 (128) - log2 (size))
> -                                -- otherwise
> -      */
> -      int d = __builtin_ctzl (ht->size) - 7;
> -      unsigned int load = d >= 0
> -        ? ht->nr_items >> d
> -        : ht->nr_items << -d;
> -      if (load <= ht->max_load)
> +      /* Only fill the hash table up to its maximum load factor.  */
> +      if (hurd_ihash_get_load (ht) <= ht->max_load)
>       if (add_one (ht, key, item))
>         return 0;
>      }
> diff --git a/libihash/ihash.h b/libihash/ihash.h
> index 809166f..345630d 100644
> --- a/libihash/ihash.h
> +++ b/libihash/ihash.h
> @@ -160,6 +160,30 @@ void hurd_ihash_set_cleanup (hurd_ihash_t ht, 
> hurd_ihash_cleanup_t cleanup,
>  void hurd_ihash_set_max_load (hurd_ihash_t ht, unsigned int max_load);
>  
>  
> +/* Get the current load factor of HT in binary percent, where 128b%
> +   corresponds to 100%.  The reason we do this is that it is so
> +   efficient to compute:
> +
> +   As the size is always a power of two, and 128 is also, the quotient
> +   of both is also a power of two.  Therefore, we can use bit shifts
> +   to scale the number of items.
> +
> +   load = nr_items * 128 / size
> +        = nr_items * 2^{log2 (128) - log2 (size)}
> +        = nr_items >> (log2 (size) - log2 (128))
> +                                -- if size >= 128
> +        = nr_items << (log2 (128) - log2 (size))
> +                                -- otherwise
> +
> +   If you want to convert this to percent, just divide by 1.28.  */
> +static inline unsigned int
> +hurd_ihash_get_load (hurd_ihash_t ht)
> +{
> +  int d = __builtin_ctzl (ht->size) - 7;
> +  return d >= 0 ? ht->nr_items >> d : ht->nr_items << -d;
> +}
> +
> +
>  /* Add ITEM to the hash table HT under the key KEY.  If there already
>     is an item under this key, call the cleanup function (if any) for
>     it before overriding the value.  If a memory allocation error
> -- 
> 2.0.0.rc0
> 

-- 
Samuel
<y> t1 faich
<y> les programmes ils segfaultent jamais quand on veut
 -+- #ens-mim en plein débogage -+-