From 5971ec743ffa28a0eaae65929475226c703678b9 Mon Sep 17 00:00:00 2001 From: Rusty Russell Date: Sun, 12 Jun 2022 13:28:52 +0930 Subject: [PATCH] Revert "htable: optimize a little more." This reverts commit 0f144bfe0ca3cc06564e19a7f3ea40177d1a3c2c. --- ccan/htable/htable.c | 22 ++++++++++++---------- ccan/htable/htable.h | 6 +++--- 2 files changed, 15 insertions(+), 13 deletions(-) diff --git a/ccan/htable/htable.c b/ccan/htable/htable.c index 70e0afc1..0371e81d 100644 --- a/ccan/htable/htable.c +++ b/ccan/htable/htable.c @@ -1,6 +1,5 @@ /* Licensed under LGPLv2+ - see LICENSE file for details */ #include -#include #include #include #include @@ -67,8 +66,9 @@ static inline uintptr_t *actually_valid_pair(const struct htable *ht) static inline bool entry_actually_valid(const struct htable *ht, size_t off) { const uintptr_t *valid = actually_valid_pair(ht); - /* In the empty case, these are "common_mask" and "rehash" - * which cannot be 0 */ + /* Empty table looks like this! */ + if (valid == &ht->common_bits + 1) + return false; return valid[0] == off || valid[1] == off; } @@ -115,6 +115,11 @@ static inline bool entry_is_valid(const struct htable *ht, size_t off) return entry_actually_valid(ht, off); } +static inline bool entry_is_deleted(const struct htable *ht, size_t off) +{ + return ht->table[off] == HTABLE_DELETED && !entry_actually_valid(ht, off); +} + static inline uintptr_t ht_perfect_mask(const struct htable *ht) { return (uintptr_t)2 << ht->perfect_bitnum; @@ -207,14 +212,11 @@ static void *htable_val(const struct htable *ht, struct htable_iter *i, size_t hash, uintptr_t perfect) { uintptr_t h2 = get_hash_ptr_bits(ht, hash) | perfect; - const uintptr_t *valid = actually_valid_pair(ht); - while (ht->table[i->off] || valid[0] == i->off || valid[1] == i->off) { - uintptr_t e = ht->table[i->off]; - if (e != HTABLE_DELETED || valid[0] == i->off || valid[1] == i->off) { - if (get_extra_ptr_bits(ht, e) == h2) { - return get_raw_ptr(ht, e); - } + while (ht->table[i->off] || entry_actually_valid(ht, i->off)) { + if (!entry_is_deleted(ht, i->off)) { + if (get_extra_ptr_bits(ht, ht->table[i->off]) == h2) + return get_raw_ptr(ht, ht->table[i->off]); } i->off = (i->off + 1) & ((1 << ht->bits)-1); h2 &= ~perfect; diff --git a/ccan/htable/htable.h b/ccan/htable/htable.h index 358b7428..eac57e37 100644 --- a/ccan/htable/htable.h +++ b/ccan/htable/htable.h @@ -22,12 +22,12 @@ * supply inline functions. */ struct htable { - /* These are the bits which are the same in all pointers. */ - uintptr_t common_bits, common_mask; size_t (*rehash)(const void *elem, void *priv); void *priv; unsigned int bits, perfect_bitnum; size_t elems, deleted; + /* These are the bits which are the same in all pointers. */ + uintptr_t common_mask, common_bits; uintptr_t *table; }; @@ -49,7 +49,7 @@ struct htable { * static struct htable ht = HTABLE_INITIALIZER(ht, rehash, NULL); */ #define HTABLE_INITIALIZER(name, rehash, priv) \ - { 0, -1, rehash, priv, 0, 0, 0, 0, &name.common_bits } + { rehash, priv, 0, 0, 0, 0, -1, 0, &name.common_bits } /** * htable_init - initialize an empty hash table. -- 2.39.2