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 -+-
