htable: htable_pick helper to select a random entry.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

diff --git a/ccan/htable/htable.c b/ccan/htable/htable.c
index d3c4f9b41187a9ef0481e332d710e95e42b29bea..cffd0619d338d8146365abd3f10e1b308ef4c4d4 100644 (file)
--- 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 0ecae726c0bd560a5a1ba598e4d544d7480041a4..eac57e37a326612226f6cd7907c04bcbc589c360 100644 (file)
--- 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 9dad4b3927186ab661f6099eeb7e801ed9204277..de4cd471404f1d4f22a4e184366a0efe9934da7c 100644 (file)
--- a/ccan/htable/htable_type.h
+++ b/ccan/htable/htable_type.h
@@ -48,7 +48,8 @@
  *     type *<name>_first(const struct <name> *ht, struct <name>_iter *i);
  *     type *<name>_next(const struct <name> *ht, struct <name>_iter *i);
  *     type *<name>_prev(const struct <name> *ht, struct <name>_iter *i);
- *
+ *      type *<name>_pick(const struct <name> *ht, size_t seed,
+ *                        struct <name>_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 2fc38c3ac0a8d81530b199cf6ca575f46c3eb5ae..c4201ed0cc5f5a6b151603f015ece212d5484d9a 100644 (file)
--- 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 3608941d97a9de42fde9a96d60d761e00662fc8e..ada85f95a93d803d3db678e292bb2e33a23666cc 100644 (file)
--- 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();
 }