summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid Robillard <d@drobilla.net>2021-10-27 11:25:17 -0400
committerDavid Robillard <d@drobilla.net>2021-10-27 11:25:17 -0400
commit87068dfe16c8f08b515df152145fb73c95cd5039 (patch)
treea2fb5e27007ee992454767f3dc34c91f63425796
parent7a26258b1208ca174cbeaf0bc455f459578c623c (diff)
downloadzix-87068dfe16c8f08b515df152145fb73c95cd5039.tar.gz
zix-87068dfe16c8f08b515df152145fb73c95cd5039.tar.bz2
zix-87068dfe16c8f08b515df152145fb73c95cd5039.zip
Improve hash table performance slightly
-rw-r--r--src/hash.c15
1 files changed, 9 insertions, 6 deletions
diff --git a/src/hash.c b/src/hash.c
index fa920b0..adee4d4 100644
--- a/src/hash.c
+++ b/src/hash.c
@@ -149,8 +149,8 @@ find_entry(const ZixHash* const hash,
{
size_t i = h;
- while (!is_match(hash, code, i, hash->equal_func, key) &&
- !is_empty(&hash->entries[i])) {
+ while (!is_empty(&hash->entries[i]) &&
+ !is_match(hash, code, i, hash->equal_func, key)) {
i = next_index(hash, i);
}
@@ -263,13 +263,14 @@ zix_hash_plan_insert_prehashed(const ZixHash* const hash,
// Search for a free position starting at the ideal one
const size_t start_index = pos.index;
- size_t first_tombstone = SIZE_MAX;
+ size_t first_tombstone = 0;
+ bool found_tombstone = false;
while (!is_empty(&hash->entries[pos.index])) {
if (is_match(hash, code, pos.index, predicate, user_data)) {
return pos;
}
- if (first_tombstone == SIZE_MAX && !hash->entries[pos.index].value) {
+ if (!found_tombstone && !hash->entries[pos.index].value) {
assert(hash->entries[pos.index].hash == tombstone);
first_tombstone = pos.index; // Remember the first/best free index
}
@@ -281,9 +282,11 @@ zix_hash_plan_insert_prehashed(const ZixHash* const hash,
}
// If we found a tombstone before an empty slot, place the new element there
- pos.index = first_tombstone < SIZE_MAX ? first_tombstone : pos.index;
- assert(!hash->entries[pos.index].value);
+ if (found_tombstone) {
+ pos.index = first_tombstone;
+ }
+ assert(!hash->entries[pos.index].value);
return pos;
}