[SCM] Hurd branch, master, updated. v0.5-253-ge2be899

[Justus Winter]

This is an automated email from the git hooks/post-receive script. It was
generated because a ref change was pushed to the repository containing
the project "Hurd".

The branch, master has been updated
       via  e2be8995642cd962b7d61c9c231980de88302d50 (commit)
       via  57341e5be12f79ee1916369679bb6507a10fcac9 (commit)
       via  2d898893815a980f1b821fcec267eb8e7ded678e (commit)
       via  6dcf53606fc7d46447176aab15954a897e19d6e5 (commit)
      from  1a3d809146c95cd138bad7bd42eb923af0a23493 (commit)

Those revisions listed above that are new to this repository have
not appeared on any other notification email; so we list those
revisions in full, below.

- Log -----------------------------------------------------------------
commit e2be8995642cd962b7d61c9c231980de88302d50
Author: Justus Winter <address@hidden>
Date:   Tue May 13 18:59:10 2014 +0200

    libihash: use fast binary scaling to determine the load
    
    Expressing the maximum load in binary percent (where 128b% corresponds
    to 100%) allows us to use fast binary scaling to determine if the
    maximum load has been reached without losing precision.
    
    Furthermore, the previously used expression 'ht->nr_items * 100'
    overflows int at 2^25 (unsigned int at 2^26).  When a hash table
    reached that limit, it would fail to resize and fill up the table.
    This change fixes that.
    
    * libihash/ihash.c (hurd_ihash_set_max_load): Update the comment.
    (hurd_ihash_add): Use fast binary scaling to determine the current
    load.
    * libihash/ihash.h (struct hurd_ihash): Update comment for max_load.
    (hurd_ihash_set_max_load): Update the comment.

commit 57341e5be12f79ee1916369679bb6507a10fcac9
Author: Justus Winter <address@hidden>
Date:   Thu May 8 18:33:57 2014 +0200

    libihash: use linear probing and fast modulo operation
    
    libihash uses open addressing.  Previously, quadratic probing in both
    directions was used to resolve collisions.  Quadratic probing might
    result in a less efficient use of caches.
    
    Also, prime numbers of the form 4 * i + 3 were used as array sizes.
    This was used in combination with the integer modulo operation for
    hashing.  It has been known for some time that libihash suffers from
    collisions, so a integer hash function is now applied to the keys to
    derive the index.
    
    Use linear probing instead.  Also, use powers of two for the array
    sizes, so a bit mask can be used for the modulo operation.
    
    * libihash/ihash.c (ihash_sizes, ihash_nsizes): Remove.
    (find_index): Use linear probing and fast modulo operation.
    (add_one): Likewise.
    * libihash/ihash.h (HURD_IHASH_MIN_SIZE): New macro.

commit 2d898893815a980f1b821fcec267eb8e7ded678e
Author: Justus Winter <address@hidden>
Date:   Thu May 8 15:45:00 2014 +0200

    libihash: use an integer hash function on the keys
    
    Use an integer hash function to derive the index from the key.  This
    should reduce the number of collisions.
    
    * libihash/ihash.c (hash_int32): New function.
    (find_index): Use hash_int32 on the key to derive the index.
    (add_one): Likewise.

commit 6dcf53606fc7d46447176aab15954a897e19d6e5
Author: Justus Winter <address@hidden>
Date:   Tue May 13 19:00:04 2014 +0200

    libihash: fix type of max_load
    
    Previously, int was used for the field max_load of struct hurd_ihash.
    There is no reason for this as far as I can tell.  Furthermore,
    hurd_ihash_set_max_load takes an unsigned int max_load.
    
    * libihash/ihash.h (struct hurd_ihash): Use unsigned int for field
    max_load.

-----------------------------------------------------------------------

Summary of changes:
 libihash/ihash.c |  167 ++++++++++++++++-------------------------------------
 libihash/ihash.h |   30 ++++++----
 2 files changed, 69 insertions(+), 128 deletions(-)


hooks/post-receive
-- 
Hurd