Add cancellation to iterators over avltree(n) and genset(dyn)

12 files changed, 98 insertions, 30 deletions

diff --git a/src/include/skalibs/avlnode.h b/src/include/skalibs/avlnode.h
index faaee10..245eef4 100644
--- a/src/include/skalibs/avlnode.h
+++ b/src/include/skalibs/avlnode.h
@@ -39,6 +39,8 @@ extern unsigned int avlnode_insertnode (avlnode *, unsigned int, unsigned int, u
 extern unsigned int avlnode_delete (avlnode *, unsigned int, unsigned int *, void const *, dtokfunc_t_ref, cmpfunc_t_ref, void *) ;
 #define avlnode_deletenode(s, max, r, i, dtok, f, p) avlnode_delete(s, max, r, (*(dtok))((s)[i].data), dtok, f, p)
 
-extern int avlnode_iter (avlnode *, unsigned int, unsigned int, avliterfunc_t_ref, void *) ;
+extern unsigned int avlnode_iter_nocancel (avlnode *, unsigned int, unsigned int, unsigned int, avliterfunc_t_ref, void *) ;
+#define avlnode_iter(tree, max, root, f, stuff) (avlnode_iter_nocancel(tree, max, max, root, f, stuff) == (max))
+extern int avlnode_iter_withcancel (avlnode *, unsigned int, unsigned int, avliterfunc_t_ref, avliterfunc_t_ref, void *) ;
 
 #endif
diff --git a/src/include/skalibs/avltree.h b/src/include/skalibs/avltree.h
index cd035f6..0b74235 100644
--- a/src/include/skalibs/avltree.h
+++ b/src/include/skalibs/avltree.h
@@ -51,5 +51,7 @@ extern int avltree_insert (avltree *, unsigned int) ;
 extern int avltree_delete (avltree *, void const *) ;
 
 #define avltree_iter(t, f, p) avlnode_iter(avltree_nodes(t), avltree_totalsize(t), avltree_root(t), f, p)
+#define avltree_iter_nocancel(t, cut, f, p) avlnode_iter(avltree_nodes(t), avltree_totalsize(t), cut, avltree_root(t), f, p)
+#define avltree_iter_withcancel(t, f, cancelf, p) avlnode_iter_withcancel(avltree_nodes(t), avltree_totalsize(t), avltree_root(t), f, cancelf, p)
 
 #endif
diff --git a/src/include/skalibs/avltreen.h b/src/include/skalibs/avltreen.h
index c453b99..8b14db7 100644
--- a/src/include/skalibs/avltreen.h
+++ b/src/include/skalibs/avltreen.h
@@ -50,6 +50,8 @@ extern int avltreen_insert (avltreen *, unsigned int) ;
 extern int avltreen_delete (avltreen *, void const *) ;
 
 #define avltreen_iter(t, f, p) avlnode_iter(avltreen_nodes(t), avltreen_totalsize(t), avltreen_root(t), f, p)
+#define avltreen_iter_nocancel(t, cut, f, p) avlnode_iter_nocancel(avltreen_nodes(t), avltreen_totalsize(t), cut, avltreen_root(t), f, p)
+#define avltreen_iter_withcancel(t, f, cancelf, p) avlnode_iter_withcancel(avltreen_nodes(t), avltreen_totalsize(t), avltreen_root(t), f, cancelf, p)
 
 
  /* avltreeb: everything in one place. Stack or BSS, or heap if you insist */
@@ -83,5 +85,7 @@ extern int avltreen_delete (avltreen *, void const *) ;
 #define avltreeb_delete(t, k) avltreen_delete(&(t)->info, k)
 
 #define avltreeb_iter(t, f, p) avlnode_iter(avltreeb_nodes(t), avltreeb_totalsize(t), avltreeb_root(t), f, p)
+#define avltreeb_iter_nocancel(t, cut, f, p) avlnode_iter_nocancel(avltreeb_nodes(t), avltreeb_totalsize(t), cut, avltreeb_root(t), f, p)
+#define avltreeb_iter_withcancel(t, f, cancelf, p) avlnode_iter_withcancel(avltreeb_nodes(t), avltreeb_totalsize(t), avltreeb_root(t), f, cancelf, p)
 
 #endif
diff --git a/src/include/skalibs/genset.h b/src/include/skalibs/genset.h
index 5e27821..83e0519 100644
--- a/src/include/skalibs/genset.h
+++ b/src/include/skalibs/genset.h
@@ -23,8 +23,9 @@ extern void genset_init (genset *, void *, unsigned int *, unsigned int, unsigne
 extern unsigned int genset_new (genset *) ;
 extern int genset_delete (genset *, unsigned int) ;
 #define genset_n(g) ((g)->max - (g)->sp)
-extern unsigned int genset_iter (genset *, iterfunc_t_ref, void *) ;
-
+extern unsigned int genset_iter_nocancel (genset *, unsigned int, iterfunc_t_ref, void *) ;
+#define genset_iter(g, f, stuff) genset_iter_nocancel(g, (g)->max, f, stuff)
+extern int genset_iter_withcancel (genset *, iterfunc_t_ref, iterfunc_t_ref, void *) ;
 
 #define GENSETB_TYPE(type, size) struct { type storage[size] ; unsigned int freelist[size] ; genset info ; }
 #define GENSETB_init(type, g, size) GENSET_init(&(g)->info, type, (g)->storage, (g)->freelist, size)
diff --git a/src/include/skalibs/gensetdyn.h b/src/include/skalibs/gensetdyn.h
index 20dfde6..7a1cc47 100644
--- a/src/include/skalibs/gensetdyn.h
+++ b/src/include/skalibs/gensetdyn.h
@@ -35,6 +35,8 @@ extern int gensetdyn_delete (gensetdyn *, unsigned int) ;
 #define gensetdyn_p(g, i) ((g)->storage.s + (i) * (g)->esize)
 #define GENSETDYN_P(type, g, i) ((type *)gensetdyn_p(g, i))
 
-extern unsigned int gensetdyn_iter (gensetdyn *, iterfunc_t_ref, void *) ;
+extern unsigned int gensetdyn_iter_nocancel (gensetdyn *, unsigned int, iterfunc_t_ref, void *) ;
+#define gensetdyn_iter(g, f, stuff) gensetdyn_iter_nocancel(g, (g)->storage.len, f, stuff)
+extern int gensetdyn_iter_withcancel (gensetdyn *, iterfunc_t_ref, iterfunc_t_ref, void *) ;
 
 #endif
diff --git a/src/libdatastruct/avlnode_delete.c b/src/libdatastruct/avlnode_delete.c
index b0f9dd0..fffb212 100644
--- a/src/libdatastruct/avlnode_delete.c
+++ b/src/libdatastruct/avlnode_delete.c
@@ -4,7 +4,7 @@
 #include <skalibs/avlnode.h>
 #include "avlnode-internal.h"
 
-unsigned int avlnode_delete (avlnode_ref s, unsigned int max, unsigned int *root, void const *k, dtokfunc_t_ref dtok, cmpfunc_t_ref f, void *p)
+unsigned int avlnode_delete (avlnode *s, unsigned int max, unsigned int *root, void const *k, dtokfunc_t_ref dtok, cmpfunc_t_ref f, void *p)
 {
   unsigned int stack[AVLNODE_MAXDEPTH] ;
   int spin[AVLNODE_MAXDEPTH] ;
diff --git a/src/libdatastruct/avlnode_iter.c b/src/libdatastruct/avlnode_iter.c
index c6064f3..e1b17de 100644
--- a/src/libdatastruct/avlnode_iter.c
+++ b/src/libdatastruct/avlnode_iter.c
@@ -4,23 +4,27 @@
 
 struct avlnode_iter_s
 {
-  avlnode *s ;
+  avlnode const *s ;
   unsigned int max ;
+  unsigned int cut ;
   avliterfunc_t_ref f ;
   void *p ;
 } ;
 
-static int avlnode_iter_rec (struct avlnode_iter_s const *blah, unsigned int r, unsigned int h)
+static unsigned int avlnode_iter_rec (struct avlnode_iter_s const *blah, unsigned int r, unsigned int h)
 {
-  return (r < blah->max) ?
-    avlnode_iter_rec(blah, blah->s[r].child[0], h+1)
-    && (*blah->f)(blah->s[r].data, h, blah->p)
-    && avlnode_iter_rec(blah, blah->s[r].child[1], h+1)
-   : 1 ;
+  if (r >= blah->max) return blah->max ;
+  {
+    unsigned int res = avlnode_iter_rec(blah, blah->s[r].child[0], h+1) ;
+    if (res != blah->max) return res ;
+  }
+  if (r == blah->cut) return blah->max ;
+  if (!(*blah->f)(blah->s[r].data, h, blah->p)) return r ;
+  return avlnode_iter_rec(blah, blah->s[r].child[1], h+1) ;
 }
 
-int avlnode_iter (avlnode *s, unsigned int max, unsigned int r, avliterfunc_t_ref f, void *p)
+unsigned int avlnode_iter_nocancel (avlnode *s, unsigned int max, unsigned int cut, unsigned int r, avliterfunc_t_ref f, void *p)
 {
-  struct avlnode_iter_s blah = { s, max, f, p } ;
+  struct avlnode_iter_s blah = { .s = s, .max = max, .cut = cut, .f = f, .p = p } ;
   return avlnode_iter_rec(&blah, r, 0) ;
 }
diff --git a/src/libdatastruct/avlnode_iter_withcancel.c b/src/libdatastruct/avlnode_iter_withcancel.c
new file mode 100644
index 0000000..44ba12e
--- /dev/null
+++ b/src/libdatastruct/avlnode_iter_withcancel.c
@@ -0,0 +1,17 @@
+/* ISC license. */
+
+#include <errno.h>
+#include <skalibs/avlnode.h>
+
+int avlnode_iter_withcancel (avlnode *tree, unsigned int max, unsigned int root, avliterfunc_t_ref f, avliterfunc_t_ref cancelf, void *stuff)
+{
+  unsigned int cut = avlnode_iter_nocancel(tree, max, max, root, f, stuff) ;
+  if (cut != max)
+  {
+    int e = errno ;
+    avlnode_iter_nocancel(tree, max, cut, root, cancelf, stuff) ;
+    errno = e ;
+    return 0 ;
+  }
+  return 1 ;
+}
diff --git a/src/libdatastruct/genset_iter.c b/src/libdatastruct/genset_iter.c
index fba95de..f78945d 100644
--- a/src/libdatastruct/genset_iter.c
+++ b/src/libdatastruct/genset_iter.c
@@ -4,16 +4,16 @@
 #include <skalibs/functypes.h>
 #include <skalibs/genset.h>
 
-unsigned int genset_iter (genset *g, iterfunc_t_ref f, void *stuff)
+unsigned int genset_iter_nocancel (genset *g, unsigned int n, iterfunc_t_ref f, void *stuff)
 {
-  unsigned char bits[bitarray_div8(g->max)] ;
-  unsigned int i = 0, j = 0, n = 0, m = genset_n(g) ;
-  bitarray_setn(bits, 0, g->max) ;
-  for (; i < g->sp ; i++) bitarray_clear(bits, g->freelist[i]) ;
-  for (i = 0 ; (i < g->max) && (j < m) ; i++) if (bitarray_peek(bits, i))
+  unsigned char bits[bitarray_div8(n)] ;
+  unsigned int i = 0, j = 0, m = genset_n(g) ;
+  bitarray_setn(bits, 0, n) ;
+  for (; i < g->sp ; i++) if (g->freelist[i] < n) bitarray_clear(bits, g->freelist[i]) ;
+  for (i = 0 ; (i < n) && (j < m) ; i++) if (bitarray_peek(bits, i))
   {
     j++ ;
-    if ((*f)(g->storage + i * g->esize, stuff)) n++ ;
+    if (!(*f)(g->storage + i * g->esize, stuff)) break ;
   }
-  return n ;
+  return i ;
 }
diff --git a/src/libdatastruct/genset_iter_withcancel.c b/src/libdatastruct/genset_iter_withcancel.c
new file mode 100644
index 0000000..fa8074b
--- /dev/null
+++ b/src/libdatastruct/genset_iter_withcancel.c
@@ -0,0 +1,18 @@
+/* ISC license. */
+
+#include <errno.h>
+#include <skalibs/functypes.h>
+#include <skalibs/genset.h>
+
+int genset_iter_withcancel (genset *g, iterfunc_t_ref f, iterfunc_t_ref cancelf, void *stuff)
+{
+  unsigned int n = genset_iter(g, f, stuff) ;
+  if (n < g->max)
+  {
+    int e = errno ;
+    genset_iter_nocancel(g, n, cancelf, stuff) ;
+    errno = e ;
+    return 0 ;
+  }
+  return 1 ;
+}
diff --git a/src/libdatastruct/gensetdyn_iter.c b/src/libdatastruct/gensetdyn_iter.c
index 51d598b..586aa11 100644
--- a/src/libdatastruct/gensetdyn_iter.c
+++ b/src/libdatastruct/gensetdyn_iter.c
@@ -4,23 +4,23 @@
 #include <skalibs/functypes.h>
 #include <skalibs/gensetdyn.h>
 
-unsigned int gensetdyn_iter (gensetdyn *g, iterfunc_t_ref f, void *stuff)
+unsigned int gensetdyn_iter_nocancel (gensetdyn *g, unsigned int n, iterfunc_t_ref f, void *stuff)
 {
  /*
     XXX: we may be called by a freeing function, so we cannot alloc -
     XXX: so pray that the bitarray fits in the stack.
  */
-  unsigned char bits[bitarray_div8(g->storage.len)] ;
-  unsigned int i = 0, j = 0, n = 0, m = gensetdyn_n(g) ;
+  unsigned char bits[bitarray_div8(n)] ;
+  unsigned int i = 0, j = 0, m = gensetdyn_n(g) ;
   register unsigned int *fl = genalloc_s(unsigned int, &g->freelist) ;
   register unsigned int sp = genalloc_len(unsigned int, &g->freelist) ;
-  bitarray_setn(bits, 0, g->storage.len) ;
+  bitarray_setn(bits, 0, n) ;
   
-  for (; i < sp ; i++) bitarray_clear(bits, fl[i]) ;
-  for (i = 0 ; (i < g->storage.len) && (j < m) ; i++) if (bitarray_peek(bits, i))
+  for (; i < sp ; i++) if (fl[i] < n) bitarray_clear(bits, fl[i]) ;
+  for (i = 0 ; (i < n) && (j < m) ; i++) if (bitarray_peek(bits, i))
   {
     j++ ;
-    if ((*f)(gensetdyn_p(g, i), stuff)) n++ ;
+    if (!(*f)(gensetdyn_p(g, i), stuff)) break ;
   }
-  return n ;
+  return i ;
 }
diff --git a/src/libdatastruct/gensetdyn_iter_withcancel.c b/src/libdatastruct/gensetdyn_iter_withcancel.c
new file mode 100644
index 0000000..ffac1e0
--- /dev/null
+++ b/src/libdatastruct/gensetdyn_iter_withcancel.c
@@ -0,0 +1,18 @@
+/* ISC license. */
+
+#include <errno.h>
+#include <skalibs/functypes.h>
+#include <skalibs/gensetdyn.h>
+
+int gensetdyn_iter_withcancel (gensetdyn *g, iterfunc_t_ref f, iterfunc_t_ref cancelf, void *stuff)
+{
+  unsigned int n = gensetdyn_iter(g, f, stuff) ;
+  if (n < g->storage.len)
+  {
+    int e = errno ;
+    gensetdyn_iter_nocancel(g, n, cancelf, stuff) ;
+    errno = e ;
+    return 0 ;
+  }
+  return 1 ;
+}