From 61b8cef1d42567d3029e0c7180cbd0f16cc4be2d Mon Sep 17 00:00:00 2001 From: "Emilio G. Cota" Date: Tue, 11 Jul 2017 18:47:38 -0400 Subject: qht: require a default comparison function MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit qht_lookup now uses the default cmp function. qht_lookup_custom is defined to retain the old behaviour, that is a cmp function is explicitly provided. qht_insert will gain use of the default cmp in the next patch. Note that we move qht_lookup_custom's @func to be the last argument, which makes the new qht_lookup as simple as possible. Instead of this (i.e. keeping @func 2nd): 0000000000010750 : 10750: 89 d1 mov %edx,%ecx 10752: 48 89 f2 mov %rsi,%rdx 10755: 48 8b 77 08 mov 0x8(%rdi),%rsi 10759: e9 22 ff ff ff jmpq 10680 1075e: 66 90 xchg %ax,%ax We get: 0000000000010740 : 10740: 48 8b 4f 08 mov 0x8(%rdi),%rcx 10744: e9 37 ff ff ff jmpq 10680 10749: 0f 1f 80 00 00 00 00 nopl 0x0(%rax) Reviewed-by: Richard Henderson Reviewed-by: Alex Bennée Signed-off-by: Emilio G. Cota Signed-off-by: Richard Henderson --- util/qht.c | 14 +++++++++++--- 1 file changed, 11 insertions(+), 3 deletions(-) (limited to 'util') diff --git a/util/qht.c b/util/qht.c index 55b0738..487e923 100644 --- a/util/qht.c +++ b/util/qht.c @@ -351,11 +351,14 @@ static struct qht_map *qht_map_create(size_t n_buckets) return map; } -void qht_init(struct qht *ht, size_t n_elems, unsigned int mode) +void qht_init(struct qht *ht, qht_cmp_func_t cmp, size_t n_elems, + unsigned int mode) { struct qht_map *map; size_t n_buckets = qht_elems_to_buckets(n_elems); + g_assert(cmp); + ht->cmp = cmp; ht->mode = mode; qemu_mutex_init(&ht->lock); map = qht_map_create(n_buckets); @@ -479,8 +482,8 @@ void *qht_lookup__slowpath(struct qht_bucket *b, qht_lookup_func_t func, return ret; } -void *qht_lookup(struct qht *ht, qht_lookup_func_t func, const void *userp, - uint32_t hash) +void *qht_lookup_custom(struct qht *ht, const void *userp, uint32_t hash, + qht_lookup_func_t func) { struct qht_bucket *b; struct qht_map *map; @@ -502,6 +505,11 @@ void *qht_lookup(struct qht *ht, qht_lookup_func_t func, const void *userp, return qht_lookup__slowpath(b, func, userp, hash); } +void *qht_lookup(struct qht *ht, const void *userp, uint32_t hash) +{ + return qht_lookup_custom(ht, userp, hash, ht->cmp); +} + /* call with head->lock held */ static bool qht_insert__locked(struct qht *ht, struct qht_map *map, struct qht_bucket *head, void *p, uint32_t hash, -- cgit v1.1 From 32359d529f30bea8124ed671b2e6a22f22540488 Mon Sep 17 00:00:00 2001 From: "Emilio G. Cota" Date: Tue, 11 Jul 2017 18:48:21 -0400 Subject: qht: return existing entry when qht_insert fails MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit The meaning of "existing" is now changed to "matches in hash and ht->cmp result". This is saner than just checking the pointer value. Suggested-by: Richard Henderson Reviewed-by: Richard Henderson Reviewed-by: Alex Bennée Signed-off-by: Emilio G. Cota Signed-off-by: Richard Henderson --- util/qht.c | 27 +++++++++++++++++---------- 1 file changed, 17 insertions(+), 10 deletions(-) (limited to 'util') diff --git a/util/qht.c b/util/qht.c index 487e923..c138777 100644 --- a/util/qht.c +++ b/util/qht.c @@ -511,9 +511,9 @@ void *qht_lookup(struct qht *ht, const void *userp, uint32_t hash) } /* call with head->lock held */ -static bool qht_insert__locked(struct qht *ht, struct qht_map *map, - struct qht_bucket *head, void *p, uint32_t hash, - bool *needs_resize) +static void *qht_insert__locked(struct qht *ht, struct qht_map *map, + struct qht_bucket *head, void *p, uint32_t hash, + bool *needs_resize) { struct qht_bucket *b = head; struct qht_bucket *prev = NULL; @@ -523,8 +523,9 @@ static bool qht_insert__locked(struct qht *ht, struct qht_map *map, do { for (i = 0; i < QHT_BUCKET_ENTRIES; i++) { if (b->pointers[i]) { - if (unlikely(b->pointers[i] == p)) { - return false; + if (unlikely(b->hashes[i] == hash && + ht->cmp(b->pointers[i], p))) { + return b->pointers[i]; } } else { goto found; @@ -553,7 +554,7 @@ static bool qht_insert__locked(struct qht *ht, struct qht_map *map, atomic_set(&b->hashes[i], hash); atomic_set(&b->pointers[i], p); seqlock_write_end(&head->sequence); - return true; + return NULL; } static __attribute__((noinline)) void qht_grow_maybe(struct qht *ht) @@ -577,25 +578,31 @@ static __attribute__((noinline)) void qht_grow_maybe(struct qht *ht) qemu_mutex_unlock(&ht->lock); } -bool qht_insert(struct qht *ht, void *p, uint32_t hash) +bool qht_insert(struct qht *ht, void *p, uint32_t hash, void **existing) { struct qht_bucket *b; struct qht_map *map; bool needs_resize = false; - bool ret; + void *prev; /* NULL pointers are not supported */ qht_debug_assert(p); b = qht_bucket_lock__no_stale(ht, hash, &map); - ret = qht_insert__locked(ht, map, b, p, hash, &needs_resize); + prev = qht_insert__locked(ht, map, b, p, hash, &needs_resize); qht_bucket_debug__locked(b); qemu_spin_unlock(&b->lock); if (unlikely(needs_resize) && ht->mode & QHT_MODE_AUTO_RESIZE) { qht_grow_maybe(ht); } - return ret; + if (likely(prev == NULL)) { + return true; + } + if (existing) { + *existing = prev; + } + return false; } static inline bool qht_entry_is_last(struct qht_bucket *b, int pos) -- cgit v1.1