Hash: iterable now per partes by an iterator

It's now possible to pause iteration through hash. This requires
struct hash_iterator to be allocated somewhere handy.

The iteration itself is surrounded by HASH_WALK_ITER and
HASH_WALK_ITER_END. Call HASH_WALK_ITER_PUT to ask for pausing; it may
still do some more iterations until it comes to a suitable pausing
point. The iterator must be initalized to an empty structure. No cleanup
is needed if iteration is abandoned inbetween.

1 files changed, 30 insertions, 10 deletions

diff --git a/lib/hash.h b/lib/hash.h
index 8febb33f..ebb2857a 100644
--- a/lib/hash.h
+++ b/lib/hash.h
@@ -10,7 +10,7 @@
 #ifndef _BIRD_HASH_H_
 #define _BIRD_HASH_H_
 
-#define HASH(type)		struct { type **data; uint count, order; }
+#define HASH(type)		struct { type **data; uint count; u16 iterators; u8 order; u8 down_requested:1; }
 #define HASH_TYPE(v)		typeof(** (v).data)
 #define HASH_SIZE(v)		(1U << (v).order)
 
@@ -125,20 +125,26 @@
 
 #define HASH_MAY_STEP_DOWN_(v,pool,rehash_fn,args)			\
   ({                                                                    \
-    if (((v).count < (HASH_SIZE(v) REHASH_LO_MARK(args))) &&		\
-	((v).order > (REHASH_LO_BOUND(args))))				\
+    if ((v).iterators)							\
+      (v).down_requested = 1;						\
+    else if (((v).count < (HASH_SIZE(v) REHASH_LO_MARK(args))) &&	\
+	     ((v).order > (REHASH_LO_BOUND(args))))			\
       rehash_fn(&(v), pool, -(REHASH_LO_STEP(args)));			\
   })
 
 #define HASH_MAY_RESIZE_DOWN_(v,pool,rehash_fn,args)			\
   ({                                                                    \
-    uint _o = (v).order;							\
-    while (((v).count < ((1U << _o) REHASH_LO_MARK(args))) &&		\
-	   (_o > (REHASH_LO_BOUND(args))))				\
-      _o -= (REHASH_LO_STEP(args));					\
-    if (_o < (v).order)							\
-      rehash_fn(&(v), pool, _o - (v).order);				\
-  })
+    if ((v).iterators)							\
+      (v).down_requested = 1;						\
+    else {								\
+      uint _o = (v).order;						\
+      while (((v).count < ((1U << _o) REHASH_LO_MARK(args))) &&		\
+	     (_o > (REHASH_LO_BOUND(args))))				\
+	_o -= (REHASH_LO_STEP(args));					\
+      if (_o < (v).order)						\
+	rehash_fn(&(v), pool, _o - (v).order);				\
+    }									\
+   })
 
 
 #define HASH_INSERT2(v,id,pool,node)					\
@@ -195,6 +201,20 @@
 #define HASH_WALK_FILTER_END } while (0)
 
 
+#define HASH_WALK_ITER(v, id, n, iter)					\
+  do {									\
+    uint _hash_walk_iter_put = 0;					\
+    uint _shift = 32 - (v).order;					\
+    for ( ; !_hash_walk_iter_put; (iter) += (1U << _shift)) {		\
+      _hash_walk_iter_put = ((iter) + (1U << _shift) == 0);		\
+      for (HASH_TYPE(v) *n = (v).data[(iter) >> _shift]; n; n = id##_NEXT((n)))\
+	if (HASH_FN(v, id, id##_KEY(n)) >= ((iter) >> _shift))		\
+
+#define HASH_WALK_ITER_PUT	(_hash_walk_iter_put = 1)
+
+#define HASH_WALK_ITER_END } } while (0)
+
+
 static inline void
 mem_hash_init(u64 *h)
 {