teythoon/hurd.git/libihash, branch masterPersonal Hurd development repositoryhttps://darnassus.sceen.net/cgit/teythoon/hurd.git/atom?h=master2016-05-03T15:19:50Zlibihash: enable fast insertions replacing tombstones2016-05-03T15:19:50ZJustus Winterjustus@gnupg.org2016-04-29T22:19:41Zurn:sha1:736fa7a565e28425220be797235913d0f7b96acd
* libihash/ihash.c (hurd_ihash_locp_add): Also replace tombstones.
libihash: fix corner case2016-05-03T15:19:50ZJustus Winterjustus@gnupg.org2016-04-29T22:03:40Zurn:sha1:8d4db629aa10189d3a545ec1639105cfb9bae650
* libihash/ihash.c (hurd_ihash_locp_find): Set SLOT to NULL if the
hash table has not been allocated.
libihash: rehash if effective load exceeds the threshold2016-04-29T21:18:34ZJustus Winterjustus@gnupg.org2016-04-28T19:12:58Zurn:sha1:9d29cfbf9fd8a0e26a3410194d1a060114973ad2
Previously, if a hash table was not growing anymore but entries were
regularly replaced, the tombstones would accumulate slowing down
lookups and insertions. A possible solution is to rehash the table if
the effective load exceeds the configured threshold. The effective
load also takes tombstones into account.
* libihash/ihash.c (hurd_ihash_locp_add): Use the effective load.
(hurd_ihash_add): Likewise. Use the load to decide whether we want to
enlarge the table, otherwise we merely rehash.
libihash: keep track of free slots2016-04-29T20:39:06ZJustus Winterjustus@gnupg.org2016-04-28T18:11:27Zurn:sha1:39031d37fd82c119b4b16af256a8ceae5d8c6ea8
* libihash/ihash.c (hurd_ihash_init): Init new field 'nr_free'.
(add_one): Decrement counter if a free slot is used.
(hurd_ihash_locp_add): Likewise.
(hurd_ihash_add): Reset counter on reallocation.
* libihash/ihash.h (struct hurd_ihash): New field 'nr_free'.
(hurd_ihash_get_effective_load): New function.
libihash: fix index computation2016-04-29T20:39:06ZJustus Winterjustus@gnupg.org2016-04-28T21:59:26Zurn:sha1:74d373342f799a45e9193c2f56189843b7b42c04
Previously, find_index would return a suboptimal slot if a tombstone
was in the optimal slot.
* libihash/ihash.c (find_index): Fix index computation.
fix compiler warnings in hurd/libihash2015-12-29T22:02:21ZFlavio Cruzflaviocruz@gmail.com2015-12-29T21:45:50Zurn:sha1:fb6b3f972b93358390871f17f2a93423daca7aa7libihash: provide a general purpose hash algorithm2015-11-29T22:57:56ZJustus Winter4winter@informatik.uni-hamburg.de2015-11-27T02:24:24Zurn:sha1:4e2d5a81bb2834f7393e9847bfa091f8a0a07556
* libdiskfs/name-cache.c: Move the Murmur3 algorithm...
* libihash/murmur3.c: ... here, and properly attribute the code.
* libihash/ihash.h (hurd_ihash_hash32): New prototype.
* libihash/Makefile (SRCS): Add new file.
libihash: fix item insertion2015-11-29T22:57:56ZJustus Winter4winter@informatik.uni-hamburg.de2015-11-22T20:04:51Zurn:sha1:1842a9dcd1056dac886e96071e8c5dcd2859d471
* libihash/ihash.c (find_index): Keep track and return the index where
we could insert the item.
(add_one): Use 'find_index'.
libihash: generalize the interface to support non-integer keys2015-11-29T22:57:56ZJustus Winter4winter@informatik.uni-hamburg.de2015-11-21T15:27:40Zurn:sha1:2c4b1db9c9760205979d22b721c324cf215987da
* libihash/ihash.c (hash, compare): New functions that are used
throughout libihash to hash and compare keys.
(hurd_ihash_set_gki): New function.
* libihash/ihash.h (hurd_ihash_fct_hash_t): New type for hash functions.
(hurd_ihash_fct_cmp_t): New type for comparison functions.
(struct hurd_ihash): New fields for hash and comparison functions.
(HURD_IHASH_INITIALIZER_GKI): New static initializer.
(hurd_ihash_set_gki): New prototype.
libihash: fix fast insertion corner case2015-11-29T22:57:56ZJustus Winter4winter@informatik.uni-hamburg.de2015-11-22T17:13:01Zurn:sha1:f564e5f4a62fb8ca54695c722c7e04803df869ec
* libihash/ihash.c (hurd_ihash_locp_add): Fix insertion if the key
doesn't match.