summaryrefslogtreecommitdiff
path: root/src/libdatastruct
diff options
context:
space:
mode:
authorLaurent Bercot <ska-skaware@skarnet.org>2015-01-09 16:10:40 +0000
committerLaurent Bercot <ska-skaware@skarnet.org>2015-01-09 16:10:40 +0000
commitb59ce39f9779cf4b1ad423783b6a532f94a8e880 (patch)
tree4db0c2cc5de6b4fe5d01fb5cc762b6a74ce32d34 /src/libdatastruct
parent157ecd01d6cc4598ce4b0ec9bd477abbbf41d6c5 (diff)
downloadskalibs-b59ce39f9779cf4b1ad423783b6a532f94a8e880.tar.xz
Add cancellation to iterators over avltree(n) and genset(dyn)
Diffstat (limited to 'src/libdatastruct')
-rw-r--r--src/libdatastruct/avlnode_delete.c2
-rw-r--r--src/libdatastruct/avlnode_iter.c22
-rw-r--r--src/libdatastruct/avlnode_iter_withcancel.c17
-rw-r--r--src/libdatastruct/genset_iter.c16
-rw-r--r--src/libdatastruct/genset_iter_withcancel.c18
-rw-r--r--src/libdatastruct/gensetdyn_iter.c16
-rw-r--r--src/libdatastruct/gensetdyn_iter_withcancel.c18
7 files changed, 83 insertions, 26 deletions
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 ;
+}