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 <4win...@informatik.uni-hamburg.de> 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 <4win...@informatik.uni-hamburg.de> 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 <4win...@informatik.uni-hamburg.de> 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 <4win...@informatik.uni-hamburg.de> 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