diff options
| author | Justus Winter <4winter@informatik.uni-hamburg.de> | 2014-05-08 18:33:57 +0200 |
|---|---|---|
| committer | Justus Winter <4winter@informatik.uni-hamburg.de> | 2014-05-13 21:36:18 +0200 |
| commit | 57341e5be12f79ee1916369679bb6507a10fcac9 (patch) | |
| tree | bbdbcb1e17aef48410a9ea2140a4783e34570459 /boot | |
| parent | 2d898893815a980f1b821fcec267eb8e7ded678e (diff) | |
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.
Diffstat (limited to 'boot')
0 files changed, 0 insertions, 0 deletions