From 74d373342f799a45e9193c2f56189843b7b42c04 Mon Sep 17 00:00:00 2001 From: Justus Winter Date: Thu, 28 Apr 2016 23:59:26 +0200 Subject: libihash: fix index computation Previously, find_index would return a suboptimal slot if a tombstone was in the optimal slot. * libihash/ihash.c (find_index): Fix index computation. --- libihash/ihash.c | 7 +------ 1 file changed, 1 insertion(+), 6 deletions(-) diff --git a/libihash/ihash.c b/libihash/ihash.c index 4bc54fdb..01ba23bd 100644 --- a/libihash/ihash.c +++ b/libihash/ihash.c @@ -81,15 +81,9 @@ find_index (hurd_ihash_t ht, hurd_ihash_key_t key) idx = hash (ht, key) & mask; - if (ht->items[idx].value == _HURD_IHASH_EMPTY - || compare (ht, ht->items[idx].key, key)) - return idx; - up_idx = idx; - do { - up_idx = (up_idx + 1) & mask; if (ht->items[up_idx].value == _HURD_IHASH_EMPTY) return first_deleted_set ? first_deleted : up_idx; if (compare (ht, ht->items[up_idx].key, key)) @@ -97,6 +91,7 @@ find_index (hurd_ihash_t ht, hurd_ihash_key_t key) if (! first_deleted_set && ht->items[up_idx].value == _HURD_IHASH_DELETED) first_deleted = up_idx, first_deleted_set = 1; + up_idx = (up_idx + 1) & mask; } while (up_idx != idx); -- cgit v1.2.3