lib: add const iteration & find to typesafe lists

Based on work originally by Mark Stapp <mjs@voltanet.io>.

Make it possible to iterate the typesafe lists in a const
context, as well as find items from them.

Signed-off-by: Mark Stapp <mjs@voltanet.io>
[above signoff was for the original version before modification]
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>

4 files changed, 144 insertions, 75 deletions

diff --git a/lib/typerb.c b/lib/typerb.c
index 7e8cd9d8f7..092faa4cc9 100644
--- a/lib/typerb.c
+++ b/lib/typerb.c
@@ -377,12 +377,13 @@ struct typed_rb_entry *typed_rb_insert(struct rbt_tree *rbt,
 }
 
 /* Finds the node with the same key as elm */
-struct rb_entry *typed_rb_find(struct rbt_tree *rbt, const struct rb_entry *key,
+const struct rb_entry *typed_rb_find(const struct rbt_tree *rbt,
+		const struct rb_entry *key,
 		int (*cmpfn)(
 			const struct typed_rb_entry *a,
 			const struct typed_rb_entry *b))
 {
-	struct rb_entry *tmp = RBH_ROOT(rbt);
+	const struct rb_entry *tmp = RBH_ROOT(rbt);
 	int comp;
 
 	while (tmp != NULL) {
@@ -398,13 +399,13 @@ struct rb_entry *typed_rb_find(struct rbt_tree *rbt, const struct rb_entry *key,
 	return NULL;
 }
 
-struct rb_entry *typed_rb_find_gteq(struct rbt_tree *rbt,
+const struct rb_entry *typed_rb_find_gteq(const struct rbt_tree *rbt,
 		const struct rb_entry *key,
 		int (*cmpfn)(
 			const struct typed_rb_entry *a,
 			const struct typed_rb_entry *b))
 {
-	struct rb_entry *tmp = RBH_ROOT(rbt), *best = NULL;
+	const struct rb_entry *tmp = RBH_ROOT(rbt), *best = NULL;
 	int comp;
 
 	while (tmp != NULL) {
@@ -421,13 +422,13 @@ struct rb_entry *typed_rb_find_gteq(struct rbt_tree *rbt,
 	return best;
 }
 
-struct rb_entry *typed_rb_find_lt(struct rbt_tree *rbt,
+const struct rb_entry *typed_rb_find_lt(const struct rbt_tree *rbt,
 		const struct rb_entry *key,
 		int (*cmpfn)(
 			const struct typed_rb_entry *a,
 			const struct typed_rb_entry *b))
 {
-	struct rb_entry *tmp = RBH_ROOT(rbt), *best = NULL;
+	const struct rb_entry *tmp = RBH_ROOT(rbt), *best = NULL;
 	int comp;
 
 	while (tmp != NULL) {
@@ -443,8 +444,10 @@ struct rb_entry *typed_rb_find_lt(struct rbt_tree *rbt,
 	return best;
 }
 
-struct rb_entry *typed_rb_next(struct rb_entry *rbe)
+struct rb_entry *typed_rb_next(const struct rb_entry *rbe_const)
 {
+	struct rb_entry *rbe = (struct rb_entry *)rbe_const;
+
 	if (RBE_RIGHT(rbe) != NULL) {
 		rbe = RBE_RIGHT(rbe);
 		while (RBE_LEFT(rbe) != NULL)
@@ -463,7 +466,7 @@ struct rb_entry *typed_rb_next(struct rb_entry *rbe)
 	return rbe;
 }
 
-struct rb_entry *typed_rb_min(struct rbt_tree *rbt)
+struct rb_entry *typed_rb_min(const struct rbt_tree *rbt)
 {
 	struct rb_entry *rbe = RBH_ROOT(rbt);
 	struct rb_entry *parent = NULL;
diff --git a/lib/typerb.h b/lib/typerb.h
index 2d7b0ba637..fca45e20d1 100644
--- a/lib/typerb.h
+++ b/lib/typerb.h
@@ -45,23 +45,23 @@ struct typed_rb_entry *typed_rb_insert(struct typed_rb_root *rbt,
 			const struct typed_rb_entry *b));
 struct typed_rb_entry *typed_rb_remove(struct typed_rb_root *rbt,
 				       struct typed_rb_entry *rbe);
-struct typed_rb_entry *typed_rb_find(struct typed_rb_root *rbt,
+const struct typed_rb_entry *typed_rb_find(const struct typed_rb_root *rbt,
 		const struct typed_rb_entry *rbe,
 		int (*cmpfn)(
 			const struct typed_rb_entry *a,
 			const struct typed_rb_entry *b));
-struct typed_rb_entry *typed_rb_find_gteq(struct typed_rb_root *rbt,
+const struct typed_rb_entry *typed_rb_find_gteq(const struct typed_rb_root *rbt,
 		const struct typed_rb_entry *rbe,
 		int (*cmpfn)(
 			const struct typed_rb_entry *a,
 			const struct typed_rb_entry *b));
-struct typed_rb_entry *typed_rb_find_lt(struct typed_rb_root *rbt,
+const struct typed_rb_entry *typed_rb_find_lt(const struct typed_rb_root *rbt,
 		const struct typed_rb_entry *rbe,
 		int (*cmpfn)(
 			const struct typed_rb_entry *a,
 			const struct typed_rb_entry *b));
-struct typed_rb_entry *typed_rb_min(struct typed_rb_root *rbt);
-struct typed_rb_entry *typed_rb_next(struct typed_rb_entry *rbe);
+struct typed_rb_entry *typed_rb_min(const struct typed_rb_root *rbt);
+struct typed_rb_entry *typed_rb_next(const struct typed_rb_entry *rbe);
 
 #define _PREDECL_RBTREE(prefix)                                                \
 struct prefix ## _head { struct typed_rb_root rr; };                           \
@@ -86,20 +86,21 @@ macro_inline type *prefix ## _add(struct prefix##_head *h, type *item)         \
 	re = typed_rb_insert(&h->rr, &item->field.re, cmpfn_uq);               \
 	return container_of_null(re, type, field.re);                          \
 }                                                                              \
-macro_inline type *prefix ## _find_gteq(struct prefix##_head *h,               \
-		const type *item)                                              \
+macro_inline const type *prefix ## _const_find_gteq(                           \
+		const struct prefix##_head *h, const type *item)               \
 {                                                                              \
-	struct typed_rb_entry *re;                                             \
+	const struct typed_rb_entry *re;                                       \
 	re = typed_rb_find_gteq(&h->rr, &item->field.re, cmpfn_nuq);           \
 	return container_of_null(re, type, field.re);                          \
 }                                                                              \
-macro_inline type *prefix ## _find_lt(struct prefix##_head *h,                 \
-		const type *item)                                              \
+macro_inline const type *prefix ## _const_find_lt(                             \
+		const struct prefix##_head *h, const type *item)               \
 {                                                                              \
-	struct typed_rb_entry *re;                                             \
+	const struct typed_rb_entry *re;                                       \
 	re = typed_rb_find_lt(&h->rr, &item->field.re, cmpfn_nuq);             \
 	return container_of_null(re, type, field.re);                          \
 }                                                                              \
+TYPESAFE_FIND_CMP(prefix, type)                                                \
 macro_inline type *prefix ## _del(struct prefix##_head *h, type *item)         \
 {                                                                              \
 	struct typed_rb_entry *re;                                             \
@@ -115,18 +116,20 @@ macro_inline type *prefix ## _pop(struct prefix##_head *h)                     \
 	typed_rb_remove(&h->rr, re);                                           \
 	return container_of(re, type, field.re);                               \
 }                                                                              \
-macro_pure type *prefix ## _first(struct prefix##_head *h)                     \
+macro_pure const type *prefix ## _const_first(const struct prefix##_head *h)   \
 {                                                                              \
-	struct typed_rb_entry *re;                                             \
+	const struct typed_rb_entry *re;                                       \
 	re = typed_rb_min(&h->rr);                                             \
 	return container_of_null(re, type, field.re);                          \
 }                                                                              \
-macro_pure type *prefix ## _next(struct prefix##_head *h, type *item)          \
+macro_pure const type *prefix ## _const_next(const struct prefix##_head *h,    \
+					     const type *item)                 \
 {                                                                              \
-	struct typed_rb_entry *re;                                             \
+	const struct typed_rb_entry *re;                                       \
 	re = typed_rb_next(&item->field.re);                                   \
 	return container_of_null(re, type, field.re);                          \
 }                                                                              \
+TYPESAFE_FIRST_NEXT(prefix, type)                                              \
 macro_pure type *prefix ## _next_safe(struct prefix##_head *h, type *item)     \
 {                                                                              \
 	struct typed_rb_entry *re;                                             \
@@ -149,12 +152,14 @@ macro_inline int prefix ## __cmp(const struct typed_rb_entry *a,               \
 	return cmpfn(container_of(a, type, field.re),                          \
 			container_of(b, type, field.re));                      \
 }                                                                              \
-macro_inline type *prefix ## _find(struct prefix##_head *h, const type *item)  \
+macro_inline const type *prefix ## _const_find(const struct prefix##_head *h,  \
+					       const type *item)               \
 {                                                                              \
-	struct typed_rb_entry *re;                                             \
+	const struct typed_rb_entry *re;                                       \
 	re = typed_rb_find(&h->rr, &item->field.re, &prefix ## __cmp);         \
 	return container_of_null(re, type, field.re);                          \
 }                                                                              \
+TYPESAFE_FIND(prefix, type)                                                    \
                                                                                \
 _DECLARE_RBTREE(prefix, type, field, prefix ## __cmp, prefix ## __cmp)         \
 /* ... */
diff --git a/lib/typesafe.c b/lib/typesafe.c
index a52b55b734..69796e2d81 100644
--- a/lib/typesafe.c
+++ b/lib/typesafe.c
@@ -158,7 +158,7 @@ void typesafe_hash_shrink(struct thash_head *head)
 
 /* skiplist */
 
-static inline struct sskip_item *sl_level_get(struct sskip_item *item,
+static inline struct sskip_item *sl_level_get(const struct sskip_item *item,
 			size_t level)
 {
 	if (level < SKIPLIST_OVERFLOW)
@@ -263,13 +263,14 @@ struct sskip_item *typesafe_skiplist_add(struct sskip_head *head,
 
 /* NOTE: level counting below is 1-based since that makes the code simpler! */
 
-struct sskip_item *typesafe_skiplist_find(struct sskip_head *head,
+const struct sskip_item *typesafe_skiplist_find(
+		const struct sskip_head *head,
 		const struct sskip_item *item, int (*cmpfn)(
 				const struct sskip_item *a,
 				const struct sskip_item *b))
 {
 	size_t level = SKIPLIST_MAXDEPTH;
-	struct sskip_item *prev = &head->hitem, *next;
+	const struct sskip_item *prev = &head->hitem, *next;
 	int cmpval;
 
 	while (level) {
@@ -290,13 +291,14 @@ struct sskip_item *typesafe_skiplist_find(struct sskip_head *head,
 	return NULL;
 }
 
-struct sskip_item *typesafe_skiplist_find_gteq(struct sskip_head *head,
+const struct sskip_item *typesafe_skiplist_find_gteq(
+		const struct sskip_head *head,
 		const struct sskip_item *item, int (*cmpfn)(
 				const struct sskip_item *a,
 				const struct sskip_item *b))
 {
 	size_t level = SKIPLIST_MAXDEPTH;
-	struct sskip_item *prev = &head->hitem, *next;
+	const struct sskip_item *prev = &head->hitem, *next;
 	int cmpval;
 
 	while (level) {
@@ -317,13 +319,14 @@ struct sskip_item *typesafe_skiplist_find_gteq(struct sskip_head *head,
 	return next;
 }
 
-struct sskip_item *typesafe_skiplist_find_lt(struct sskip_head *head,
+const struct sskip_item *typesafe_skiplist_find_lt(
+		const struct sskip_head *head,
 		const struct sskip_item *item, int (*cmpfn)(
 				const struct sskip_item *a,
 				const struct sskip_item *b))
 {
 	size_t level = SKIPLIST_MAXDEPTH;
-	struct sskip_item *prev = &head->hitem, *next, *best = NULL;
+	const struct sskip_item *prev = &head->hitem, *next, *best = NULL;
 	int cmpval;
 
 	while (level) {
diff --git a/lib/typesafe.h b/lib/typesafe.h
index c30d73d1b3..e134316dd9 100644
--- a/lib/typesafe.h
+++ b/lib/typesafe.h
@@ -44,6 +44,41 @@ extern "C" {
 		item;                                                          \
 		item = from, from = prefix##_next_safe(head, from))
 
+
+/* non-const variants.  these wrappers are the same for all the types, so
+ * bundle them together here.
+ */
+#define TYPESAFE_FIRST_NEXT(prefix, type)                                      \
+macro_pure type *prefix ## _first(struct prefix##_head *h)                     \
+{                                                                              \
+	return (type *)prefix ## _const_first(h);                              \
+}                                                                              \
+macro_pure type *prefix ## _next(struct prefix##_head *h, type *item)          \
+{                                                                              \
+	return (type *)prefix ## _const_next(h, item);                         \
+}                                                                              \
+/* ... */
+#define TYPESAFE_FIND(prefix, type)                                            \
+macro_inline type *prefix ## _find(struct prefix##_head *h,                    \
+				   const type *item)                           \
+{                                                                              \
+	return (type *)prefix ## _const_find(h, item);                         \
+}                                                                              \
+/* ... */
+#define TYPESAFE_FIND_CMP(prefix, type)                                        \
+macro_inline type *prefix ## _find_lt(struct prefix##_head *h,                 \
+				      const type *item)                        \
+{                                                                              \
+	return (type *)prefix ## _const_find_lt(h, item);                      \
+}                                                                              \
+macro_inline type *prefix ## _find_gteq(struct prefix##_head *h,               \
+					const type *item)                      \
+{                                                                              \
+	return (type *)prefix ## _const_find_gteq(h, item);                    \
+}                                                                              \
+/* ... */
+
+
 /* single-linked list, unsorted/arbitrary.
  * can be used as queue with add_tail / pop
  */
@@ -133,15 +168,17 @@ macro_inline type *prefix ## _pop(struct prefix##_head *h)                     \
 		h->sh.last_next = &h->sh.first;                                \
 	return container_of(sitem, type, field.si);                            \
 }                                                                              \
-macro_pure type *prefix ## _first(struct prefix##_head *h)                     \
+macro_pure const type *prefix ## _const_first(const struct prefix##_head *h)   \
 {                                                                              \
 	return container_of_null(h->sh.first, type, field.si);                 \
 }                                                                              \
-macro_pure type *prefix ## _next(struct prefix##_head * h, type *item)         \
+macro_pure const type *prefix ## _const_next(const struct prefix##_head *h,    \
+					     const type *item)                 \
 {                                                                              \
-	struct slist_item *sitem = &item->field.si;                            \
+	const struct slist_item *sitem = &item->field.si;                      \
 	return container_of_null(sitem->next, type, field.si);                 \
 }                                                                              \
+TYPESAFE_FIRST_NEXT(prefix, type)                                              \
 macro_pure type *prefix ## _next_safe(struct prefix##_head *h, type *item)     \
 {                                                                              \
 	struct slist_item *sitem;                                              \
@@ -232,20 +269,22 @@ macro_inline type *prefix ## _pop(struct prefix##_head *h)                     \
 	h->dh.count--;                                                         \
 	return container_of(ditem, type, field.di);                            \
 }                                                                              \
-macro_pure type *prefix ## _first(struct prefix##_head *h)                     \
+macro_pure const type *prefix ## _const_first(const struct prefix##_head *h)   \
 {                                                                              \
-	struct dlist_item *ditem = h->dh.hitem.next;                           \
+	const struct dlist_item *ditem = h->dh.hitem.next;                     \
 	if (ditem == &h->dh.hitem)                                             \
 		return NULL;                                                   \
 	return container_of(ditem, type, field.di);                            \
 }                                                                              \
-macro_pure type *prefix ## _next(struct prefix##_head * h, type *item)         \
+macro_pure const type *prefix ## _const_next(const struct prefix##_head *h,    \
+					     const type *item)	               \
 {                                                                              \
-	struct dlist_item *ditem = &item->field.di;                            \
+	const struct dlist_item *ditem = &item->field.di;                      \
 	if (ditem->next == &h->dh.hitem)                                       \
 		return NULL;                                                   \
 	return container_of(ditem->next, type, field.di);                      \
 }                                                                              \
+TYPESAFE_FIRST_NEXT(prefix, type)                                              \
 macro_pure type *prefix ## _next_safe(struct prefix##_head *h, type *item)     \
 {                                                                              \
 	if (!item)                                                             \
@@ -338,19 +377,21 @@ macro_inline type *prefix ## _pop(struct prefix##_head *h)                     \
 		typesafe_heap_resize(&h->hh, false);                           \
 	return container_of(hitem, type, field.hi);                            \
 }                                                                              \
-macro_pure type *prefix ## _first(struct prefix##_head *h)                     \
+macro_pure const type *prefix ## _const_first(const struct prefix##_head *h)   \
 {                                                                              \
 	if (h->hh.count == 0)                                                  \
 		return NULL;                                                   \
 	return container_of(h->hh.array[0], type, field.hi);                   \
 }                                                                              \
-macro_pure type *prefix ## _next(struct prefix##_head *h, type *item)          \
+macro_pure const type *prefix ## _const_next(const struct prefix##_head *h,    \
+					     const type *item)                 \
 {                                                                              \
 	uint32_t idx = item->field.hi.index + 1;                               \
 	if (idx >= h->hh.count)                                                \
 		return NULL;                                                   \
 	return container_of(h->hh.array[idx], type, field.hi);                 \
 }                                                                              \
+TYPESAFE_FIRST_NEXT(prefix, type)                                              \
 macro_pure type *prefix ## _next_safe(struct prefix##_head *h, type *item)     \
 {                                                                              \
 	if (!item)                                                             \
@@ -431,26 +472,27 @@ macro_inline type *prefix ## _add(struct prefix##_head *h, type *item)         \
 	h->sh.count++;                                                         \
 	return NULL;                                                           \
 }                                                                              \
-macro_inline type *prefix ## _find_gteq(struct prefix##_head *h,               \
-		const type *item)                                              \
+macro_inline const type *prefix ## _const_find_gteq(                           \
+		const struct prefix##_head *h, const type *item)               \
 {                                                                              \
-	struct ssort_item *sitem = h->sh.first;                                \
+	const struct ssort_item *sitem = h->sh.first;                          \
 	int cmpval = 0;                                                        \
 	while (sitem && (cmpval = cmpfn_nuq(                                   \
 			container_of(sitem, type, field.si), item)) < 0)       \
 		sitem = sitem->next;                                           \
 	return container_of_null(sitem, type, field.si);                       \
 }                                                                              \
-macro_inline type *prefix ## _find_lt(struct prefix##_head *h,                 \
-		const type *item)                                              \
+macro_inline const type *prefix ## _const_find_lt(                             \
+		const struct prefix##_head *h, const type *item)               \
 {                                                                              \
-	struct ssort_item *prev = NULL, *sitem = h->sh.first;                  \
+	const struct ssort_item *prev = NULL, *sitem = h->sh.first;            \
 	int cmpval = 0;                                                        \
 	while (sitem && (cmpval = cmpfn_nuq(                                   \
 			container_of(sitem, type, field.si), item)) < 0)       \
 		sitem = (prev = sitem)->next;                                  \
 	return container_of_null(prev, type, field.si);                        \
 }                                                                              \
+TYPESAFE_FIND_CMP(prefix, type)                                                \
 /* TODO: del_hint */                                                           \
 macro_inline type *prefix ## _del(struct prefix##_head *h, type *item)         \
 {                                                                              \
@@ -472,15 +514,17 @@ macro_inline type *prefix ## _pop(struct prefix##_head *h)                     \
 	h->sh.first = sitem->next;                                             \
 	return container_of(sitem, type, field.si);                            \
 }                                                                              \
-macro_pure type *prefix ## _first(struct prefix##_head *h)                     \
+macro_pure const type *prefix ## _const_first(const struct prefix##_head *h)   \
 {                                                                              \
 	return container_of_null(h->sh.first, type, field.si);                 \
 }                                                                              \
-macro_pure type *prefix ## _next(struct prefix##_head *h, type *item)          \
+macro_pure const type *prefix ## _const_next(const struct prefix##_head *h,    \
+					     const type *item)                 \
 {                                                                              \
-	struct ssort_item *sitem = &item->field.si;                            \
+	const struct ssort_item *sitem = &item->field.si;                      \
 	return container_of_null(sitem->next, type, field.si);                 \
 }                                                                              \
+TYPESAFE_FIRST_NEXT(prefix, type)                                              \
 macro_pure type *prefix ## _next_safe(struct prefix##_head *h, type *item)     \
 {                                                                              \
 	struct ssort_item *sitem;                                              \
@@ -497,10 +541,11 @@ macro_pure size_t prefix ## _count(const struct prefix##_head *h)              \
 
 #define DECLARE_SORTLIST_UNIQ(prefix, type, field, cmpfn)                      \
 	_DECLARE_SORTLIST(prefix, type, field, cmpfn, cmpfn)                   \
-                                                                               \
-macro_inline type *prefix ## _find(struct prefix##_head *h, const type *item)  \
+									       \
+macro_inline const type *prefix ## _const_find(const struct prefix##_head *h,  \
+					       const type *item)               \
 {                                                                              \
-	struct ssort_item *sitem = h->sh.first;                                \
+	const struct ssort_item *sitem = h->sh.first;                          \
 	int cmpval = 0;                                                        \
 	while (sitem && (cmpval = cmpfn(                                       \
 			container_of(sitem, type, field.si), item)) < 0)       \
@@ -509,6 +554,7 @@ macro_inline type *prefix ## _find(struct prefix##_head *h, const type *item)  \
 		return NULL;                                                   \
 	return container_of(sitem, type, field.si);                            \
 }                                                                              \
+TYPESAFE_FIND(prefix, type)                                                    \
 /* ... */
 
 #define DECLARE_SORTLIST_NONUNIQ(prefix, type, field, cmpfn)                   \
@@ -606,12 +652,13 @@ macro_inline type *prefix ## _add(struct prefix##_head *h, type *item)         \
 	*np = &item->field.hi;                                                 \
 	return NULL;                                                           \
 }                                                                              \
-macro_inline type *prefix ## _find(struct prefix##_head *h, const type *item)  \
+macro_inline const type *prefix ## _const_find(const struct prefix##_head *h,  \
+					       const type *item)               \
 {                                                                              \
 	if (!h->hh.tabshift)                                                   \
 		return NULL;                                                   \
 	uint32_t hval = hashfn(item), hbits = HASH_KEY(h->hh, hval);           \
-	struct thash_item *hitem = h->hh.entries[hbits];                       \
+	const struct thash_item *hitem = h->hh.entries[hbits];                 \
 	while (hitem && hitem->hashval < hval)                                 \
 		hitem = hitem->next;                                           \
 	while (hitem && hitem->hashval == hval) {                              \
@@ -621,6 +668,7 @@ macro_inline type *prefix ## _find(struct prefix##_head *h, const type *item)  \
 	}                                                                      \
 	return NULL;                                                           \
 }                                                                              \
+TYPESAFE_FIND(prefix, type)                                                    \
 macro_inline type *prefix ## _del(struct prefix##_head *h, type *item)         \
 {                                                                              \
 	if (!h->hh.tabshift)                                                   \
@@ -655,7 +703,7 @@ macro_inline type *prefix ## _pop(struct prefix##_head *h)                     \
 		}                                                              \
 	return NULL;                                                           \
 }                                                                              \
-macro_pure type *prefix ## _first(struct prefix##_head *h)                     \
+macro_pure const type *prefix ## _const_first(const struct prefix##_head *h)   \
 {                                                                              \
 	uint32_t i;                                                            \
 	for (i = 0; i < HASH_SIZE(h->hh); i++)                                 \
@@ -663,17 +711,19 @@ macro_pure type *prefix ## _first(struct prefix##_head *h)                     \
 			return container_of(h->hh.entries[i], type, field.hi); \
 	return NULL;                                                           \
 }                                                                              \
-macro_pure type *prefix ## _next(struct prefix##_head *h, type *item)          \
+macro_pure const type *prefix ## _const_next(const struct prefix##_head *h,    \
+                                             const type *item)                 \
 {                                                                              \
-	struct thash_item *hitem = &item->field.hi;                            \
+	const struct thash_item *hitem = &item->field.hi;                      \
 	if (hitem->next)                                                       \
 		return container_of(hitem->next, type, field.hi);              \
 	uint32_t i = HASH_KEY(h->hh, hitem->hashval) + 1;                      \
-        for (; i < HASH_SIZE(h->hh); i++)                                      \
+	for (; i < HASH_SIZE(h->hh); i++)				       \
 		if (h->hh.entries[i])                                          \
 			return container_of(h->hh.entries[i], type, field.hi); \
 	return NULL;                                                           \
 }                                                                              \
+TYPESAFE_FIRST_NEXT(prefix, type)                                              \
 macro_pure type *prefix ## _next_safe(struct prefix##_head *h, type *item)     \
 {                                                                              \
 	if (!item)                                                             \
@@ -742,20 +792,21 @@ macro_inline type *prefix ## _add(struct prefix##_head *h, type *item)         \
 	si = typesafe_skiplist_add(&h->sh, &item->field.si, cmpfn_uq);         \
 	return container_of_null(si, type, field.si);                          \
 }                                                                              \
-macro_inline type *prefix ## _find_gteq(struct prefix##_head *h,               \
-		const type *item)                                              \
+macro_inline const type *prefix ## _const_find_gteq(                           \
+		const struct prefix##_head *h, const type *item)               \
 {                                                                              \
-	struct sskip_item *sitem = typesafe_skiplist_find_gteq(&h->sh,         \
+	const struct sskip_item *sitem = typesafe_skiplist_find_gteq(&h->sh,   \
 			&item->field.si, cmpfn_nuq);                           \
 	return container_of_null(sitem, type, field.si);                       \
 }                                                                              \
-macro_inline type *prefix ## _find_lt(struct prefix##_head *h,                 \
-		const type *item)                                              \
+macro_inline const type *prefix ## _const_find_lt(                             \
+		const struct prefix##_head *h, const type *item)               \
 {                                                                              \
-	struct sskip_item *sitem = typesafe_skiplist_find_lt(&h->sh,           \
+	const struct sskip_item *sitem = typesafe_skiplist_find_lt(&h->sh,     \
 			&item->field.si, cmpfn_nuq);                           \
 	return container_of_null(sitem, type, field.si);                       \
 }                                                                              \
+TYPESAFE_FIND_CMP(prefix, type)                                                \
 macro_inline type *prefix ## _del(struct prefix##_head *h, type *item)         \
 {                                                                              \
 	struct sskip_item *sitem = typesafe_skiplist_del(&h->sh,               \
@@ -767,16 +818,18 @@ macro_inline type *prefix ## _pop(struct prefix##_head *h)                     \
 	struct sskip_item *sitem = typesafe_skiplist_pop(&h->sh);              \
 	return container_of_null(sitem, type, field.si);                       \
 }                                                                              \
-macro_pure type *prefix ## _first(struct prefix##_head *h)                     \
+macro_pure const type *prefix ## _const_first(const struct prefix##_head *h)   \
 {                                                                              \
-	struct sskip_item *first = h->sh.hitem.next[0];                        \
+	const struct sskip_item *first = h->sh.hitem.next[0];                  \
 	return container_of_null(first, type, field.si);                       \
 }                                                                              \
-macro_pure type *prefix ## _next(struct prefix##_head *h, type *item)          \
+macro_pure const type *prefix ## _const_next(const struct prefix##_head *h,    \
+					     const type *item)		       \
 {                                                                              \
-	struct sskip_item *next = item->field.si.next[0];                      \
+	const struct sskip_item *next = item->field.si.next[0];                \
 	return container_of_null(next, type, field.si);                        \
 }                                                                              \
+TYPESAFE_FIRST_NEXT(prefix, type)                                              \
 macro_pure type *prefix ## _next_safe(struct prefix##_head *h, type *item)     \
 {                                                                              \
 	struct sskip_item *next;                                               \
@@ -792,19 +845,21 @@ macro_pure size_t prefix ## _count(const struct prefix##_head *h)              \
 #define PREDECL_SKIPLIST_UNIQ(prefix)                                          \
 	_PREDECL_SKIPLIST(prefix)
 #define DECLARE_SKIPLIST_UNIQ(prefix, type, field, cmpfn)                      \
-                                                                               \
+									       \
 macro_inline int prefix ## __cmp(const struct sskip_item *a,                   \
 		const struct sskip_item *b)                                    \
 {                                                                              \
 	return cmpfn(container_of(a, type, field.si),                          \
 			container_of(b, type, field.si));                      \
 }                                                                              \
-macro_inline type *prefix ## _find(struct prefix##_head *h, const type *item)  \
+macro_inline const type *prefix ## _const_find(const struct prefix##_head *h,  \
+					       const type *item)               \
 {                                                                              \
-	struct sskip_item *sitem = typesafe_skiplist_find(&h->sh,              \
+	const struct sskip_item *sitem = typesafe_skiplist_find(&h->sh,        \
 			&item->field.si, &prefix ## __cmp);                    \
 	return container_of_null(sitem, type, field.si);                       \
 }                                                                              \
+TYPESAFE_FIND(prefix, type)                                                    \
                                                                                \
 _DECLARE_SKIPLIST(prefix, type, field,                                         \
 		prefix ## __cmp, prefix ## __cmp)                              \
@@ -843,15 +898,18 @@ extern struct sskip_item *typesafe_skiplist_add(struct sskip_head *head,
 		struct sskip_item *item, int (*cmpfn)(
 			const struct sskip_item *a,
 			const struct sskip_item *b));
-extern struct sskip_item *typesafe_skiplist_find(struct sskip_head *head,
+extern const struct sskip_item *typesafe_skiplist_find(
+		const struct sskip_head *head,
 		const struct sskip_item *item, int (*cmpfn)(
 			const struct sskip_item *a,
 			const struct sskip_item *b));
-extern struct sskip_item *typesafe_skiplist_find_gteq(struct sskip_head *head,
+extern const struct sskip_item *typesafe_skiplist_find_gteq(
+		const struct sskip_head *head,
 		const struct sskip_item *item, int (*cmpfn)(
 			const struct sskip_item *a,
 			const struct sskip_item *b));
-extern struct sskip_item *typesafe_skiplist_find_lt(struct sskip_head *head,
+extern const struct sskip_item *typesafe_skiplist_find_lt(
+		const struct sskip_head *head,
 		const struct sskip_item *item, int (*cmpfn)(
 			const struct sskip_item *a,
 			const struct sskip_item *b));