htable: add iterators to htable_type.
authorRusty Russell <rusty@rustcorp.com.au>
Tue, 26 Apr 2016 04:18:40 +0000 (13:48 +0930)
committerRusty Russell <rusty@rustcorp.com.au>
Tue, 26 Apr 2016 04:18:40 +0000 (13:48 +0930)
Useful if you have more than one object with same key.

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
ccan/htable/htable_type.h
ccan/htable/test/run-type.c

index 6764c3f24ae103c8bccbcc8949c283ff56dcca1e..2afa1484756025c21ee122dcd31dbc59623fab24 100644 (file)
  *     bool <name>_del(struct <name> *ht, const <type> *e);
  *     bool <name>_delkey(struct <name> *ht, const <keytype> *k);
  *
- * Find function return the matching element, or NULL:
+ * Find and return the (first) matching element, or NULL:
  *     type *<name>_get(const struct @name *ht, const <keytype> *k);
  *
+ * Find and return all matching elements, or NULL:
+ *     type *<name>_getfirst(const struct @name *ht, const <keytype> *k,
+ *                           struct <name>_iter *i);
+ *     type *<name>_getnext(const struct @name *ht, const <keytype> *k,
+ *                          struct <name>_iter *i);
+ *
  * Iteration over hashtable is also supported:
  *     type *<name>_first(const struct <name> *ht, struct <name>_iter *i);
  *     type *<name>_next(const struct <name> *ht, struct <name>_iter *i);
                                  (bool (*)(const void *, void *))(eqfn), \
                                  k);                                   \
        }                                                               \
+       static inline UNNEEDED type *name##_getmatch_(const struct name *ht, \
+                                        const HTABLE_KTYPE(keyof) k,   \
+                                        size_t h,                      \
+                                        type *v,                       \
+                                        struct name##_iter *iter)      \
+       {                                                               \
+               while (v) {                                             \
+                       if (eqfn(v, k))                                 \
+                               break;                                  \
+                       v = htable_nextval(&ht->raw, &iter->i, h);      \
+               }                                                       \
+               return v;                                               \
+       }                                                               \
+       static inline UNNEEDED type *name##_getfirst(const struct name *ht, \
+                                        const HTABLE_KTYPE(keyof) k,   \
+                                        struct name##_iter *iter)      \
+       {                                                               \
+               size_t h = hashfn(k);                                   \
+               type *v = htable_firstval(&ht->raw, &iter->i, h);       \
+               return name##_getmatch_(ht, k, h, v, iter);                     \
+       }                                                               \
+       static inline UNNEEDED type *name##_getnext(const struct name *ht, \
+                                        const HTABLE_KTYPE(keyof) k,   \
+                                        struct name##_iter *iter)      \
+       {                                                               \
+               size_t h = hashfn(k);                                   \
+               type *v = htable_nextval(&ht->raw, &iter->i, h);        \
+               return name##_getmatch_(ht, k, h, v, iter);             \
+       }                                                               \
        static inline UNNEEDED bool name##_delkey(struct name *ht,      \
                                         const HTABLE_KTYPE(keyof) k)   \
        {                                                               \
index f97e7270b2fa65afd83e75cc9fcf33220d06d357..11ce54bac7fd889338893264822ac6be022159ca 100644 (file)
@@ -111,12 +111,12 @@ int main(int argc, char *argv[])
 {
        unsigned int i;
        struct htable_obj ht;
-       struct obj val[NUM_VALS];
+       struct obj val[NUM_VALS], *result;
        unsigned int dne;
        void *p;
        struct htable_obj_iter iter;
 
-       plan_tests(20);
+       plan_tests(26);
        for (i = 0; i < NUM_VALS; i++)
                val[i].key = i;
        dne = i;
@@ -169,7 +169,33 @@ int main(int argc, char *argv[])
 
        /* Delete them all by key. */
        del_vals_bykey(&ht, val, NUM_VALS);
-       htable_obj_clear(&ht);
 
+       /* Write two of the same value. */
+       val[1] = val[0];
+       htable_obj_add(&ht, &val[0]);
+       htable_obj_add(&ht, &val[1]);
+       i = 0;
+
+       result = htable_obj_getfirst(&ht, &i, &iter);
+       ok1(result == &val[0] || result == &val[1]);
+       if (result == &val[0]) {
+               ok1(htable_obj_getnext(&ht, &i, &iter) == &val[1]);
+               ok1(htable_obj_getnext(&ht, &i, &iter) == NULL);
+
+               /* Deleting first should make us iterate over the other. */
+               ok1(htable_obj_del(&ht, &val[0]));
+               ok1(htable_obj_getfirst(&ht, &i, &iter) == &val[1]);
+               ok1(htable_obj_getnext(&ht, &i, &iter) == NULL);
+       } else {
+               ok1(htable_obj_getnext(&ht, &i, &iter) == &val[0]);
+               ok1(htable_obj_getnext(&ht, &i, &iter) == NULL);
+
+               /* Deleting first should make us iterate over the other. */
+               ok1(htable_obj_del(&ht, &val[1]));
+               ok1(htable_obj_getfirst(&ht, &i, &iter) == &val[0]);
+               ok1(htable_obj_getnext(&ht, &i, &iter) == NULL);
+       }
+
+       htable_obj_clear(&ht);
        return exit_status();
 }