From 209a81909942a07cb334d6dcae7626a3ecde141d Mon Sep 17 00:00:00 2001 From: Rusty Russell Date: Thu, 20 Feb 2020 10:18:10 +1030 Subject: [PATCH] htable: htable_pick helper to select a random entry. Signed-off-by: Rusty Russell --- ccan/htable/htable.c | 14 ++++++++++++++ ccan/htable/htable.h | 13 +++++++++++++ ccan/htable/htable_type.h | 10 +++++++++- ccan/htable/test/run-type.c | 5 ++++- ccan/htable/test/run.c | 9 ++++++++- 5 files changed, 48 insertions(+), 3 deletions(-) diff --git a/ccan/htable/htable.c b/ccan/htable/htable.c index d3c4f9b4..cffd0619 100644 --- a/ccan/htable/htable.c +++ b/ccan/htable/htable.c @@ -365,6 +365,20 @@ void htable_delval_(struct htable *ht, struct htable_iter *i) ht->deleted++; } +void *htable_pick_(const struct htable *ht, size_t seed, struct htable_iter *i) +{ + void *e; + struct htable_iter unwanted; + + if (!i) + i = &unwanted; + i->off = seed % ((size_t)1 << ht->bits); + e = htable_next(ht, i); + if (!e) + e = htable_first(ht, i); + return e; +} + struct htable *htable_check(const struct htable *ht, const char *abortstr) { void *p; diff --git a/ccan/htable/htable.h b/ccan/htable/htable.h index 0ecae726..eac57e37 100644 --- a/ccan/htable/htable.h +++ b/ccan/htable/htable.h @@ -267,6 +267,19 @@ void *htable_prev_(const struct htable *htable, struct htable_iter *i); htable_delval_(htable_debug(htable, HTABLE_LOC), i) void htable_delval_(struct htable *ht, struct htable_iter *i); +/** + * htable_pick - set iterator to a random valid entry. + * @ht: the htable + * @seed: a random number to use. + * @i: the htable_iter which is output (or NULL). + * + * Usually used with htable_delval to delete a random entry. Returns + * NULL iff the table is empty, otherwise a random entry. + */ +#define htable_pick(htable, seed, i) \ + htable_pick_(htable_debug(htable, HTABLE_LOC), seed, i) +void *htable_pick_(const struct htable *ht, size_t seed, struct htable_iter *i); + /** * htable_set_allocator - set calloc/free functions. * @alloc: allocator to use, must zero memory! diff --git a/ccan/htable/htable_type.h b/ccan/htable/htable_type.h index 9dad4b39..de4cd471 100644 --- a/ccan/htable/htable_type.h +++ b/ccan/htable/htable_type.h @@ -48,7 +48,8 @@ * type *_first(const struct *ht, struct _iter *i); * type *_next(const struct *ht, struct _iter *i); * type *_prev(const struct *ht, struct _iter *i); - * + * type *_pick(const struct *ht, size_t seed, + * struct _iter *i); * It's currently safe to iterate over a changing hashtable, but you might * miss an element. Iteration isn't very efficient, either. * @@ -146,6 +147,13 @@ return name##_del(ht, elem); \ return false; \ } \ + static inline UNNEEDED bool name##_pick(const struct name *ht, \ + size_t seed, \ + struct name##_iter *iter) \ + { \ + /* Note &iter->i == NULL iff iter is NULL */ \ + return htable_pick(&ht->raw, seed, &iter->i); \ + } \ static inline UNNEEDED type *name##_first(const struct name *ht, \ struct name##_iter *iter) \ { \ diff --git a/ccan/htable/test/run-type.c b/ccan/htable/test/run-type.c index 2fc38c3a..c4201ed0 100644 --- a/ccan/htable/test/run-type.c +++ b/ccan/htable/test/run-type.c @@ -116,7 +116,7 @@ int main(void) void *p; struct htable_obj_iter iter; - plan_tests(32); + plan_tests(35); for (i = 0; i < NUM_VALS; i++) val[i].key = i; dne = i; @@ -128,6 +128,7 @@ int main(void) /* We cannot find an entry which doesn't exist. */ ok1(!htable_obj_get(&ht, &dne)); + ok1(!htable_obj_pick(&ht, 0, NULL)); /* Fill it, it should increase in size. */ add_vals(&ht, val, NUM_VALS); @@ -142,6 +143,8 @@ int main(void) /* Find all. */ find_vals(&ht, val, NUM_VALS); ok1(!htable_obj_get(&ht, &dne)); + ok1(htable_obj_pick(&ht, 0, NULL)); + ok1(htable_obj_pick(&ht, 0, &iter)); /* Walk once, should get them all. */ i = 0; diff --git a/ccan/htable/test/run.c b/ccan/htable/test/run.c index 3608941d..ada85f95 100644 --- a/ccan/htable/test/run.c +++ b/ccan/htable/test/run.c @@ -105,7 +105,7 @@ int main(void) void *p; struct htable_iter iter; - plan_tests(38); + plan_tests(43); for (i = 0; i < NUM_VALS; i++) val[i] = i; dne = i; @@ -134,6 +134,12 @@ int main(void) /* Mask should be set. */ ok1(check_mask(&ht, val, 1)); + /* htable_pick should always return that value */ + ok1(htable_pick(&ht, 0, NULL) == val); + ok1(htable_pick(&ht, 1, NULL) == val); + ok1(htable_pick(&ht, 0, &iter) == val); + ok1(get_raw_ptr(&ht, ht.table[iter.off]) == val); + /* This should increase it again. */ add_vals(&ht, val, 1, 1); ok1(ht.bits == 2); @@ -210,6 +216,7 @@ int main(void) htable_clear(&ht); ok1(htable_count(&ht) == 0); + ok1(htable_pick(&ht, 0, NULL) == NULL); return exit_status(); } -- 2.39.2