From b59ce39f9779cf4b1ad423783b6a532f94a8e880 Mon Sep 17 00:00:00 2001 From: Laurent Bercot Date: Fri, 9 Jan 2015 16:10:40 +0000 Subject: Add cancellation to iterators over avltree(n) and genset(dyn) --- package/deps.mak | 3 +++ src/include/skalibs/avlnode.h | 4 +++- src/include/skalibs/avltree.h | 2 ++ src/include/skalibs/avltreen.h | 4 ++++ src/include/skalibs/genset.h | 5 +++-- src/include/skalibs/gensetdyn.h | 4 +++- src/libdatastruct/avlnode_delete.c | 2 +- src/libdatastruct/avlnode_iter.c | 22 +++++++++++++--------- src/libdatastruct/avlnode_iter_withcancel.c | 17 +++++++++++++++++ src/libdatastruct/genset_iter.c | 16 ++++++++-------- src/libdatastruct/genset_iter_withcancel.c | 18 ++++++++++++++++++ src/libdatastruct/gensetdyn_iter.c | 16 ++++++++-------- src/libdatastruct/gensetdyn_iter_withcancel.c | 18 ++++++++++++++++++ 13 files changed, 101 insertions(+), 30 deletions(-) create mode 100644 src/libdatastruct/avlnode_iter_withcancel.c create mode 100644 src/libdatastruct/genset_iter_withcancel.c create mode 100644 src/libdatastruct/gensetdyn_iter_withcancel.c diff --git a/package/deps.mak b/package/deps.mak index b38f35d..e9c9165 100644 --- a/package/deps.mak +++ b/package/deps.mak @@ -103,6 +103,7 @@ src/libdatastruct/avlnode_extremenode.o src/libdatastruct/avlnode_extremenode.lo src/libdatastruct/avlnode_height.o src/libdatastruct/avlnode_height.lo: src/libdatastruct/avlnode_height.c src/include/skalibs/avlnode.h src/libdatastruct/avlnode_insertnode.o src/libdatastruct/avlnode_insertnode.lo: src/libdatastruct/avlnode_insertnode.c src/libdatastruct/avlnode-internal.h src/include/skalibs/avlnode.h src/include/skalibs/functypes.h src/libdatastruct/avlnode_iter.o src/libdatastruct/avlnode_iter.lo: src/libdatastruct/avlnode_iter.c src/include/skalibs/avlnode.h +src/libdatastruct/avlnode_iter_withcancel.o src/libdatastruct/avlnode_iter_withcancel.lo: src/libdatastruct/avlnode_iter_withcancel.c src/include/skalibs/avlnode.h src/libdatastruct/avlnode_rotate.o src/libdatastruct/avlnode_rotate.lo: src/libdatastruct/avlnode_rotate.c src/libdatastruct/avlnode-internal.h src/include/skalibs/avlnode.h src/libdatastruct/avlnode_search.o src/libdatastruct/avlnode_search.lo: src/libdatastruct/avlnode_search.c src/include/skalibs/avlnode.h src/libdatastruct/avlnode_searchnode.o src/libdatastruct/avlnode_searchnode.lo: src/libdatastruct/avlnode_searchnode.c src/libdatastruct/avlnode-internal.h src/include/skalibs/avlnode.h src/include/skalibs/functypes.h @@ -119,10 +120,12 @@ src/libdatastruct/avltreen_insert.o src/libdatastruct/avltreen_insert.lo: src/li src/libdatastruct/avltreen_newnode.o src/libdatastruct/avltreen_newnode.lo: src/libdatastruct/avltreen_newnode.c src/include/skalibs/avlnode.h src/include/skalibs/avltreen.h src/include/skalibs/genset.h src/libdatastruct/genset.o src/libdatastruct/genset.lo: src/libdatastruct/genset.c src/include/skalibs/genset.h src/libdatastruct/genset_iter.o src/libdatastruct/genset_iter.lo: src/libdatastruct/genset_iter.c src/include/skalibs/bitarray.h src/include/skalibs/functypes.h src/include/skalibs/genset.h +src/libdatastruct/genset_iter_withcancel.o src/libdatastruct/genset_iter_withcancel.lo: src/libdatastruct/genset_iter_withcancel.c src/include/skalibs/functypes.h src/include/skalibs/genset.h src/libdatastruct/gensetdyn_delete.o src/libdatastruct/gensetdyn_delete.lo: src/libdatastruct/gensetdyn_delete.c src/include/skalibs/genalloc.h src/include/skalibs/gensetdyn.h src/libdatastruct/gensetdyn_free.o src/libdatastruct/gensetdyn_free.lo: src/libdatastruct/gensetdyn_free.c src/include/skalibs/genalloc.h src/include/skalibs/gensetdyn.h src/include/skalibs/stralloc.h src/libdatastruct/gensetdyn_init.o src/libdatastruct/gensetdyn_init.lo: src/libdatastruct/gensetdyn_init.c src/include/skalibs/genalloc.h src/include/skalibs/gensetdyn.h src/include/skalibs/stralloc.h src/libdatastruct/gensetdyn_iter.o src/libdatastruct/gensetdyn_iter.lo: src/libdatastruct/gensetdyn_iter.c src/include/skalibs/bitarray.h src/include/skalibs/functypes.h src/include/skalibs/gensetdyn.h +src/libdatastruct/gensetdyn_iter_withcancel.o src/libdatastruct/gensetdyn_iter_withcancel.lo: src/libdatastruct/gensetdyn_iter_withcancel.c src/include/skalibs/functypes.h src/include/skalibs/gensetdyn.h src/libdatastruct/gensetdyn_new.o src/libdatastruct/gensetdyn_new.lo: src/libdatastruct/gensetdyn_new.c src/include/skalibs/genalloc.h src/include/skalibs/gensetdyn.h src/libdatastruct/gensetdyn_ready.o src/libdatastruct/gensetdyn_ready.lo: src/libdatastruct/gensetdyn_ready.c src/include/skalibs/genalloc.h src/include/skalibs/gensetdyn.h src/include/skalibs/stralloc.h src/libdatastruct/gensetdyn_zero.o src/libdatastruct/gensetdyn_zero.lo: src/libdatastruct/gensetdyn_zero.c src/include/skalibs/gensetdyn.h 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 #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 +#include + +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 #include -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 +#include +#include + +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 #include -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 +#include +#include + +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 ; +} -- cgit v1.2.3