From: Rusty Russell <rusty@rustcorp.com.au>
Date: Tue, 26 Apr 2016 04:18:40 +0000 (+0930)
Subject: htable: add iterators to htable_type.
X-Git-Url: http://git.ozlabs.org/?p=ccan;a=commitdiff_plain;h=a0f174c63680a3dd8fc61333f79231ffdf7e96b1;ds=sidebyside

htable: add iterators to htable_type.

Useful if you have more than one object with same key.

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

diff --git a/ccan/htable/htable_type.h b/ccan/htable/htable_type.h
index 6764c3f2..2afa1484 100644
--- a/ccan/htable/htable_type.h
+++ b/ccan/htable/htable_type.h
@@ -31,9 +31,15 @@
  *	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);
@@ -84,6 +90,35 @@
 				  (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)	\
 	{								\
diff --git a/ccan/htable/test/run-type.c b/ccan/htable/test/run-type.c
index f97e7270..11ce54ba 100644
--- a/ccan/htable/test/run-type.c
+++ b/ccan/htable/test/run-type.c
@@ -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();
 }