From e122e5525ef044c25c2cd888bc267f7a2bd91b4f Mon Sep 17 00:00:00 2001 From: Bruce Hill Date: Tue, 24 Jun 2025 12:56:23 -0400 Subject: Minor performance improvement for hash collisions in tables --- src/stdlib/tables.c | 22 +++++++++------------- 1 file changed, 9 insertions(+), 13 deletions(-) (limited to 'src/stdlib') diff --git a/src/stdlib/tables.c b/src/stdlib/tables.c index 762afb06..9301914c 100644 --- a/src/stdlib/tables.c +++ b/src/stdlib/tables.c @@ -177,20 +177,16 @@ static void Table$set_bucket(Table_t *t, const void *entry, int32_t index, const // Move mid-chain entry to free space and update predecessor buckets[predecessor].next_bucket = t->bucket_info->last_free; buckets[t->bucket_info->last_free] = *bucket; - } else { // Collided with the start of a chain + + bucket->occupied = 1; + bucket->index = index; + bucket->next_bucket = END_OF_CHAIN; + } else { // Collided with the start of a chain, put the new entry in chain position #2 hdebug("Hit start of a chain\n"); - uint64_t end_of_chain = hash; - while (buckets[end_of_chain].next_bucket != END_OF_CHAIN) - end_of_chain = buckets[end_of_chain].next_bucket; - hdebug("Appending to chain\n"); - // Chain now ends on the free space: - buckets[end_of_chain].next_bucket = t->bucket_info->last_free; - bucket = &buckets[t->bucket_info->last_free]; - } - - bucket->occupied = 1; - bucket->index = index; - bucket->next_bucket = END_OF_CHAIN; + buckets[t->bucket_info->last_free] = (bucket_t){ + .occupied = 1, .index=index, .next_bucket=bucket->next_bucket}; + bucket->next_bucket = t->bucket_info->last_free; + } hshow(t); } -- cgit v1.2.3