summaryrefslogtreecommitdiff
path: root/src/libdatastruct
diff options
context:
space:
mode:
Diffstat (limited to 'src/libdatastruct')
-rw-r--r--src/libdatastruct/avlnode-internal.h15
-rw-r--r--src/libdatastruct/avlnode_delete.c72
-rw-r--r--src/libdatastruct/avlnode_doublerotate.c19
-rw-r--r--src/libdatastruct/avlnode_extreme.c12
-rw-r--r--src/libdatastruct/avlnode_extremenode.c10
-rw-r--r--src/libdatastruct/avlnode_height.c15
-rw-r--r--src/libdatastruct/avlnode_insertnode.c42
-rw-r--r--src/libdatastruct/avlnode_iter.c26
-rw-r--r--src/libdatastruct/avlnode_rotate.c15
-rw-r--r--src/libdatastruct/avlnode_search.c12
-rw-r--r--src/libdatastruct/avlnode_searchnode.c16
-rw-r--r--src/libdatastruct/avlnode_zero.c5
-rw-r--r--src/libdatastruct/avltree_delete.c16
-rw-r--r--src/libdatastruct/avltree_free.c10
-rw-r--r--src/libdatastruct/avltree_init.c16
-rw-r--r--src/libdatastruct/avltree_insert.c11
-rw-r--r--src/libdatastruct/avltree_newnode.c18
-rw-r--r--src/libdatastruct/avltree_zero.c5
-rw-r--r--src/libdatastruct/avltreen_delete.c16
-rw-r--r--src/libdatastruct/avltreen_init.c15
-rw-r--r--src/libdatastruct/avltreen_insert.c11
-rw-r--r--src/libdatastruct/avltreen_newnode.c18
-rw-r--r--src/libdatastruct/genset.c27
-rw-r--r--src/libdatastruct/genset_iter.c19
-rw-r--r--src/libdatastruct/gensetdyn_delete.c11
-rw-r--r--src/libdatastruct/gensetdyn_free.c12
-rw-r--r--src/libdatastruct/gensetdyn_init.c15
-rw-r--r--src/libdatastruct/gensetdyn_iter.c26
-rw-r--r--src/libdatastruct/gensetdyn_new.c14
-rw-r--r--src/libdatastruct/gensetdyn_ready.c26
-rw-r--r--src/libdatastruct/gensetdyn_zero.c5
31 files changed, 550 insertions, 0 deletions
diff --git a/src/libdatastruct/avlnode-internal.h b/src/libdatastruct/avlnode-internal.h
new file mode 100644
index 0000000..0342695
--- /dev/null
+++ b/src/libdatastruct/avlnode-internal.h
@@ -0,0 +1,15 @@
+/* ISC license. */
+
+#ifndef AVLNODE_INTERNAL_H
+#define AVLNODE_INTERNAL_H
+
+#include <skalibs/avlnode.h>
+
+#define avlnode_ufroms(c) ((c) > 0)
+#define avlnode_sfromu(h) ((h) ? 1 : -1)
+
+extern unsigned int avlnode_rotate (avlnode_ref, unsigned int, unsigned int, int) ;
+extern unsigned int avlnode_doublerotate (avlnode_ref, unsigned int, unsigned int, int) ;
+#define avlnode_rotate_maydouble(s, max, r, h, isdouble) ((isdouble) ? avlnode_doublerotate(s, max, r, h) : avlnode_rotate(s, max, r, h))
+
+#endif
diff --git a/src/libdatastruct/avlnode_delete.c b/src/libdatastruct/avlnode_delete.c
new file mode 100644
index 0000000..b0f9dd0
--- /dev/null
+++ b/src/libdatastruct/avlnode_delete.c
@@ -0,0 +1,72 @@
+/* ISC license. */
+
+#include <skalibs/functypes.h>
+#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 stack[AVLNODE_MAXDEPTH] ;
+ int spin[AVLNODE_MAXDEPTH] ;
+ unsigned int sp = 0 ;
+ unsigned int r = *root ;
+ unsigned int itodel ;
+
+ for (; r < max ; sp++)
+ {
+ register int c = (*f)(k, (*dtok)(s[r].data, p), p) ;
+ if (!c) break ;
+ spin[sp] = avlnode_ufroms(c) ;
+ stack[sp] = r ;
+ r = s[r].child[spin[sp]] ;
+ }
+ if (r >= max) return max ;
+ itodel = r ;
+
+ if ((s[r].child[0] < max) || (s[r].child[1] < max))
+ {
+ int subspin = s[r].child[1] < max ;
+ stack[sp] = r ;
+ spin[sp++] = subspin ;
+ r = s[r].child[subspin] ;
+ for (; r < max ; sp++)
+ {
+ stack[sp] = r ;
+ spin[sp] = !subspin ;
+ r = s[r].child[!subspin] ;
+ }
+ r = stack[--sp] ;
+ s[itodel].data = s[r].data ;
+ itodel = s[r].child[subspin] ;
+ if (itodel < max)
+ {
+ s[r].data = s[itodel].data ;
+ stack[sp] = r ;
+ spin[sp++] = subspin ;
+ }
+ else itodel = r ;
+ }
+
+ r = max ;
+ while (sp--)
+ {
+ s[stack[sp]].child[spin[sp]] = r ;
+ r = stack[sp] ;
+ if (!s[r].balance) goto easyfix ;
+ else if (spin[sp] == avlnode_ufroms(s[r].balance)) s[r].balance = 0 ;
+ else if (!s[s[r].child[!spin[sp]]].balance) goto hardfix ;
+ else r = avlnode_rotate_maydouble(s, max, r, spin[sp], spin[sp] == avlnode_ufroms(s[s[r].child[!spin[sp]]].balance)) ;
+ }
+ *root = r ;
+ return itodel ;
+
+ easyfix:
+ s[r].balance = -avlnode_sfromu(spin[sp]) ;
+ return itodel ;
+
+ hardfix:
+ r = avlnode_rotate(s, max, r, spin[sp]) ;
+ if (!sp--) *root = r ;
+ else s[stack[sp]].child[spin[sp]] = r ;
+ return itodel ;
+}
diff --git a/src/libdatastruct/avlnode_doublerotate.c b/src/libdatastruct/avlnode_doublerotate.c
new file mode 100644
index 0000000..da1f31b
--- /dev/null
+++ b/src/libdatastruct/avlnode_doublerotate.c
@@ -0,0 +1,19 @@
+/* ISC license. */
+
+#include <skalibs/avlnode.h>
+#include "avlnode-internal.h"
+
+unsigned int avlnode_doublerotate (avlnode_ref s, unsigned int max, unsigned int i, int h)
+{
+ register unsigned int j = s[i].child[!h] ;
+ register unsigned int k = s[j].child[h] ;
+ s[i].child[!h] = s[k].child[h] ;
+ s[j].child[h] = s[k].child[!h] ;
+ s[k].child[!h] = j ;
+ s[k].child[h] = i ;
+ s[h ? i : j].balance = (s[k].balance < 0) ;
+ s[h ? j : i].balance = -(s[k].balance > 0) ;
+ s[k].balance = 0 ;
+ (void)max ;
+ return k ;
+}
diff --git a/src/libdatastruct/avlnode_extreme.c b/src/libdatastruct/avlnode_extreme.c
new file mode 100644
index 0000000..42d991d
--- /dev/null
+++ b/src/libdatastruct/avlnode_extreme.c
@@ -0,0 +1,12 @@
+/* ISC license. */
+
+#include <errno.h>
+#include <skalibs/avlnode.h>
+
+int avlnode_extreme (avlnode const *s, unsigned int max, unsigned int r, int h, unsigned int *k)
+{
+ register unsigned int i = avlnode_extremenode(s, max, r, h) ;
+ if (i >= max) return (errno = ESRCH, 0) ;
+ *k = s[i].data ;
+ return 1 ;
+}
diff --git a/src/libdatastruct/avlnode_extremenode.c b/src/libdatastruct/avlnode_extremenode.c
new file mode 100644
index 0000000..57a8e59
--- /dev/null
+++ b/src/libdatastruct/avlnode_extremenode.c
@@ -0,0 +1,10 @@
+/* ISC license. */
+
+#include <skalibs/avlnode.h>
+
+unsigned int avlnode_extremenode (avlnode const *s, unsigned int max, unsigned int r, int h)
+{
+ register unsigned int oldr = r ;
+ for (; r < max ; oldr = r, r = s[r].child[h]) ;
+ return oldr ;
+}
diff --git a/src/libdatastruct/avlnode_height.c b/src/libdatastruct/avlnode_height.c
new file mode 100644
index 0000000..e78448e
--- /dev/null
+++ b/src/libdatastruct/avlnode_height.c
@@ -0,0 +1,15 @@
+/* ISC license. */
+
+#include <skalibs/avlnode.h>
+
+unsigned int avlnode_height (avlnode const *s, unsigned int max, unsigned int r)
+{
+ if (r >= max) return 0 ;
+ else if (s[r].balance) return 1 + avlnode_height(s, max, s[r].child[s[r].balance > 0]) ;
+ else
+ {
+ unsigned int h1 = avlnode_height(s, max, s[r].child[0]) ;
+ unsigned int h2 = avlnode_height(s, max, s[r].child[1]) ;
+ return 1 + ((h1 > h2) ? h1 : h2) ;
+ }
+}
diff --git a/src/libdatastruct/avlnode_insertnode.c b/src/libdatastruct/avlnode_insertnode.c
new file mode 100644
index 0000000..c69b34e
--- /dev/null
+++ b/src/libdatastruct/avlnode_insertnode.c
@@ -0,0 +1,42 @@
+/* ISC license. */
+
+#include <skalibs/functypes.h>
+#include <skalibs/avlnode.h>
+#include "avlnode-internal.h"
+
+unsigned int avlnode_insertnode (avlnode_ref s, unsigned int max, unsigned int r, unsigned int i, dtokfunc_t_ref dtok, cmpfunc_t_ref f, void *p)
+{
+ unsigned int stack[AVLNODE_MAXDEPTH] ;
+ int spin[AVLNODE_MAXDEPTH] ;
+ unsigned int sp = 0 ;
+
+ {
+ register void const *k = (*dtok)(s[i].data, p) ;
+ for (; r < max ; sp++)
+ {
+ spin[sp] = avlnode_ufroms((*f)(k, (*dtok)(s[r].data, p), p)) ;
+ stack[sp] = r ;
+ r = s[r].child[spin[sp]] ;
+ }
+ }
+ r = i ;
+ while (sp--)
+ {
+ s[stack[sp]].child[spin[sp]] = r ;
+ r = stack[sp] ;
+ if (s[r].balance) goto lastfix ;
+ s[r].balance = avlnode_sfromu(spin[sp]) ;
+ }
+ return r ;
+
+ lastfix:
+ if (avlnode_ufroms(s[r].balance) != spin[sp])
+ {
+ s[r].balance = 0 ;
+ return stack[0] ;
+ }
+ r = avlnode_rotate_maydouble(s, max, r, !spin[sp], spin[sp] != spin[sp+1]) ;
+ if (!sp--) return r ;
+ s[stack[sp]].child[spin[sp]] = r ;
+ return stack[0] ;
+}
diff --git a/src/libdatastruct/avlnode_iter.c b/src/libdatastruct/avlnode_iter.c
new file mode 100644
index 0000000..9e1d698
--- /dev/null
+++ b/src/libdatastruct/avlnode_iter.c
@@ -0,0 +1,26 @@
+/* ISC license. */
+
+#include <skalibs/avlnode.h>
+
+struct avlnode_iter_s
+{
+ avlnode_ref s ;
+ unsigned int max ;
+ avliterfunc_t_ref f ;
+ void *p ;
+} ;
+
+static 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 ;
+}
+
+int avlnode_iter (avlnode_ref s, unsigned int max, unsigned int r, avliterfunc_t_ref f, void *p)
+{
+ struct avlnode_iter_s blah = { s, max, f, p } ;
+ return avlnode_iter_rec(&blah, r, 0) ;
+}
diff --git a/src/libdatastruct/avlnode_rotate.c b/src/libdatastruct/avlnode_rotate.c
new file mode 100644
index 0000000..fe06994
--- /dev/null
+++ b/src/libdatastruct/avlnode_rotate.c
@@ -0,0 +1,15 @@
+/* ISC license. */
+
+#include <skalibs/avlnode.h>
+#include "avlnode-internal.h"
+
+unsigned int avlnode_rotate (avlnode_ref s, unsigned int max, unsigned int i, int h)
+{
+ register unsigned int j = s[i].child[!h] ;
+ s[i].child[!h] = s[j].child[h] ;
+ s[j].child[h] = i ;
+ if (s[j].balance * avlnode_sfromu(h) < 0) s[i].balance = s[j].balance = 0 ;
+ else s[j].balance = avlnode_sfromu(h) ;
+ (void)max ;
+ return j ;
+}
diff --git a/src/libdatastruct/avlnode_search.c b/src/libdatastruct/avlnode_search.c
new file mode 100644
index 0000000..e12b0a4
--- /dev/null
+++ b/src/libdatastruct/avlnode_search.c
@@ -0,0 +1,12 @@
+/* ISC license. */
+
+#include <errno.h>
+#include <skalibs/avlnode.h>
+
+int avlnode_search (avlnode const *s, unsigned int max, unsigned int r, void const *k, unsigned int *data, dtokfunc_t_ref dtok, cmpfunc_t_ref f, void *p)
+{
+ register unsigned int i = avlnode_searchnode(s, max, r, k, dtok, f, p) ;
+ if (i >= max) return (errno = ESRCH, 0) ;
+ *data = s[i].data ;
+ return 1 ;
+}
diff --git a/src/libdatastruct/avlnode_searchnode.c b/src/libdatastruct/avlnode_searchnode.c
new file mode 100644
index 0000000..4ab015c
--- /dev/null
+++ b/src/libdatastruct/avlnode_searchnode.c
@@ -0,0 +1,16 @@
+/* ISC license. */
+
+#include <skalibs/functypes.h>
+#include <skalibs/avlnode.h>
+#include "avlnode-internal.h"
+
+unsigned int avlnode_searchnode (avlnode const *s, unsigned int max, unsigned int r, void const *k, dtokfunc_t_ref dtok, cmpfunc_t_ref f, void *p)
+{
+ while (r < max)
+ {
+ register int h = (*f)(k, (*dtok)(s[r].data, p), p) ;
+ if (!h) break ;
+ r = s[r].child[avlnode_ufroms(h)] ;
+ }
+ return r ;
+}
diff --git a/src/libdatastruct/avlnode_zero.c b/src/libdatastruct/avlnode_zero.c
new file mode 100644
index 0000000..caf4adb
--- /dev/null
+++ b/src/libdatastruct/avlnode_zero.c
@@ -0,0 +1,5 @@
+/* ISC license. */
+
+#include <skalibs/avlnode.h>
+
+avlnode const avlnode_zero = AVLNODE_ZERO ;
diff --git a/src/libdatastruct/avltree_delete.c b/src/libdatastruct/avltree_delete.c
new file mode 100644
index 0000000..5127f01
--- /dev/null
+++ b/src/libdatastruct/avltree_delete.c
@@ -0,0 +1,16 @@
+/* ISC license. */
+
+#include <errno.h>
+#include <skalibs/gensetdyn.h>
+#include <skalibs/avlnode.h>
+#include <skalibs/avltree.h>
+
+int avltree_delete (avltree_ref t, void const *k)
+{
+ unsigned int r = avltree_root(t) ;
+ unsigned int i = avlnode_delete(avltree_nodes(t), avltree_totalsize(t), &r, k, t->dtok, t->kcmp, t->external) ;
+ if (i >= avltree_totalsize(t)) return (errno = ESRCH, 0) ;
+ avltree_setroot(t, r) ;
+ if (!gensetdyn_delete(&t->x, i)) return 0 ;
+ return 1 ;
+}
diff --git a/src/libdatastruct/avltree_free.c b/src/libdatastruct/avltree_free.c
new file mode 100644
index 0000000..14198fe
--- /dev/null
+++ b/src/libdatastruct/avltree_free.c
@@ -0,0 +1,10 @@
+/* ISC license. */
+
+#include <skalibs/gensetdyn.h>
+#include <skalibs/avltree.h>
+
+void avltree_free (avltree_ref t)
+{
+ gensetdyn_free(&t->x) ;
+ *t = avltree_zero ;
+}
diff --git a/src/libdatastruct/avltree_init.c b/src/libdatastruct/avltree_init.c
new file mode 100644
index 0000000..290ff64
--- /dev/null
+++ b/src/libdatastruct/avltree_init.c
@@ -0,0 +1,16 @@
+/* ISC license. */
+
+#include <errno.h>
+#include <skalibs/functypes.h>
+#include <skalibs/gensetdyn.h>
+#include <skalibs/avlnode.h>
+#include <skalibs/avltree.h>
+
+void avltree_init (avltree_ref t, unsigned int base, unsigned int fracnum, unsigned int fracden, dtokfunc_t_ref dtok, cmpfunc_t_ref f, void *p)
+{
+ gensetdyn_init(&t->x, sizeof(avlnode), base, fracnum, fracden) ;
+ t->root = (unsigned int)-1 ;
+ t->dtok = dtok ;
+ t->kcmp = f ;
+ t->external = p ;
+}
diff --git a/src/libdatastruct/avltree_insert.c b/src/libdatastruct/avltree_insert.c
new file mode 100644
index 0000000..308990a
--- /dev/null
+++ b/src/libdatastruct/avltree_insert.c
@@ -0,0 +1,11 @@
+/* ISC license. */
+
+#include <skalibs/avltree.h>
+
+int avltree_insert (avltree_ref t, unsigned int d)
+{
+ unsigned int i ;
+ if (!avltree_newnode(t, d, &i)) return 0 ;
+ avltree_insertnode(t, i) ;
+ return 1 ;
+}
diff --git a/src/libdatastruct/avltree_newnode.c b/src/libdatastruct/avltree_newnode.c
new file mode 100644
index 0000000..dc972a0
--- /dev/null
+++ b/src/libdatastruct/avltree_newnode.c
@@ -0,0 +1,18 @@
+/* ISC license. */
+
+#include <errno.h>
+#include <skalibs/gensetdyn.h>
+#include <skalibs/avlnode.h>
+#include <skalibs/avltree.h>
+
+int avltree_newnode (avltree_ref t, unsigned int data, unsigned int *i)
+{
+ if (!gensetdyn_new(&t->x, i)) return 0 ;
+ {
+ register avlnode_ref s = avltree_nodes(t) ;
+ s[*i].data = data ;
+ s[*i].child[0] = s[*i].child[1] = (unsigned int)-1 ;
+ s[*i].balance = 0 ;
+ }
+ return 1 ;
+}
diff --git a/src/libdatastruct/avltree_zero.c b/src/libdatastruct/avltree_zero.c
new file mode 100644
index 0000000..400828a
--- /dev/null
+++ b/src/libdatastruct/avltree_zero.c
@@ -0,0 +1,5 @@
+/* ISC license. */
+
+#include <skalibs/avltree.h>
+
+avltree const avltree_zero = AVLTREE_ZERO ;
diff --git a/src/libdatastruct/avltreen_delete.c b/src/libdatastruct/avltreen_delete.c
new file mode 100644
index 0000000..bfe85c5
--- /dev/null
+++ b/src/libdatastruct/avltreen_delete.c
@@ -0,0 +1,16 @@
+/* ISC license. */
+
+#include <errno.h>
+#include <skalibs/genset.h>
+#include <skalibs/avlnode.h>
+#include <skalibs/avltreen.h>
+
+int avltreen_delete (avltreen_ref t, void const *k)
+{
+ unsigned int r = avltreen_root(t) ;
+ unsigned int i = avlnode_delete(avltreen_nodes(t), avltreen_totalsize(t), &r, k, t->dtok, t->kcmp, t->external) ;
+ if (i >= avltreen_totalsize(t)) return (errno = ESRCH, 0) ;
+ avltreen_setroot(t, r) ;
+ if (!genset_delete(&t->x, i)) return 0 ;
+ return 1 ;
+}
diff --git a/src/libdatastruct/avltreen_init.c b/src/libdatastruct/avltreen_init.c
new file mode 100644
index 0000000..5e141b1
--- /dev/null
+++ b/src/libdatastruct/avltreen_init.c
@@ -0,0 +1,15 @@
+/* ISC license. */
+
+#include <skalibs/functypes.h>
+#include <skalibs/genset.h>
+#include <skalibs/avlnode.h>
+#include <skalibs/avltreen.h>
+
+void avltreen_init (avltreen_ref t, avlnode_ref storage, unsigned int *freelist, unsigned int size, dtokfunc_t_ref dtok, cmpfunc_t_ref f, void *p)
+{
+ GENSET_init(&t->x, avlnode, storage, freelist, size) ;
+ t->root = size ;
+ t->dtok = dtok ;
+ t->kcmp = f ;
+ t->external = p ;
+}
diff --git a/src/libdatastruct/avltreen_insert.c b/src/libdatastruct/avltreen_insert.c
new file mode 100644
index 0000000..795216d
--- /dev/null
+++ b/src/libdatastruct/avltreen_insert.c
@@ -0,0 +1,11 @@
+/* ISC license. */
+
+#include <skalibs/avltreen.h>
+
+int avltreen_insert (avltreen_ref t, unsigned int d)
+{
+ unsigned int i = avltreen_newnode(t, d) ;
+ if (i >= avltreen_totalsize(t)) return 0 ;
+ avltreen_insertnode(t, i) ;
+ return 1 ;
+}
diff --git a/src/libdatastruct/avltreen_newnode.c b/src/libdatastruct/avltreen_newnode.c
new file mode 100644
index 0000000..335025c
--- /dev/null
+++ b/src/libdatastruct/avltreen_newnode.c
@@ -0,0 +1,18 @@
+/* ISC license. */
+
+#include <skalibs/genset.h>
+#include <skalibs/avlnode.h>
+#include <skalibs/avltreen.h>
+
+unsigned int avltreen_newnode (avltreen_ref t, unsigned int d)
+{
+ register unsigned int i = genset_new(&t->x) ;
+ if (i < avltreen_totalsize(t))
+ {
+ register avlnode_ref s = avltreen_nodes(t) ;
+ s[i].data = d ;
+ s[i].child[0] = s[i].child[1] = avltreen_totalsize(t) ;
+ s[i].balance = 0 ;
+ }
+ return i ;
+}
diff --git a/src/libdatastruct/genset.c b/src/libdatastruct/genset.c
new file mode 100644
index 0000000..8d750b7
--- /dev/null
+++ b/src/libdatastruct/genset.c
@@ -0,0 +1,27 @@
+/* ISC license. */
+
+#include <errno.h>
+#include <skalibs/genset.h>
+
+void genset_init (genset_ref x, void *storage, unsigned int *freelist, unsigned int esize, unsigned int max)
+{
+ register unsigned int i = 0 ;
+ x->storage = (char *)storage ;
+ x->freelist = freelist ;
+ x->esize = esize ;
+ x->max = max ;
+ x->sp = max ;
+ for (; i < max ; i++) freelist[i] = max - 1 - i ;
+}
+
+unsigned int genset_new (genset_ref x)
+{
+ return x->sp ? x->freelist[--x->sp] : (errno = ENOSPC, x->max) ;
+}
+
+int genset_delete (genset_ref x, unsigned int i)
+{
+ if ((i >= x->max) || (x->sp >= x->max)) return (errno = EINVAL, 0) ;
+ x->freelist[x->sp++] = i ;
+ return 1 ;
+}
diff --git a/src/libdatastruct/genset_iter.c b/src/libdatastruct/genset_iter.c
new file mode 100644
index 0000000..cc6e863
--- /dev/null
+++ b/src/libdatastruct/genset_iter.c
@@ -0,0 +1,19 @@
+/* ISC license. */
+
+#include <skalibs/bitarray.h>
+#include <skalibs/functypes.h>
+#include <skalibs/genset.h>
+
+unsigned int genset_iter (genset_ref g, 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))
+ {
+ j++ ;
+ if ((*f)(g->storage + i * g->esize, stuff)) n++ ;
+ }
+ return n ;
+}
diff --git a/src/libdatastruct/gensetdyn_delete.c b/src/libdatastruct/gensetdyn_delete.c
new file mode 100644
index 0000000..58aec05
--- /dev/null
+++ b/src/libdatastruct/gensetdyn_delete.c
@@ -0,0 +1,11 @@
+/* ISC license. */
+
+#include <errno.h>
+#include <skalibs/genalloc.h>
+#include <skalibs/gensetdyn.h>
+
+int gensetdyn_delete (gensetdyn_ref g, unsigned int i)
+{
+ return (i >= g->storage.len) ? (errno = EINVAL, 0) :
+ genalloc_catb(unsigned int, &g->freelist, &i, 1) ;
+}
diff --git a/src/libdatastruct/gensetdyn_free.c b/src/libdatastruct/gensetdyn_free.c
new file mode 100644
index 0000000..c0a4366
--- /dev/null
+++ b/src/libdatastruct/gensetdyn_free.c
@@ -0,0 +1,12 @@
+/* ISC license. */
+
+#include <skalibs/stralloc.h>
+#include <skalibs/genalloc.h>
+#include <skalibs/gensetdyn.h>
+
+void gensetdyn_free (gensetdyn_ref g)
+{
+ stralloc_free(&g->storage) ;
+ genalloc_free(unsigned int, &g->freelist) ;
+ *g = gensetdyn_zero ;
+}
diff --git a/src/libdatastruct/gensetdyn_init.c b/src/libdatastruct/gensetdyn_init.c
new file mode 100644
index 0000000..cff6ff5
--- /dev/null
+++ b/src/libdatastruct/gensetdyn_init.c
@@ -0,0 +1,15 @@
+/* ISC license. */
+
+#include <skalibs/stralloc.h>
+#include <skalibs/genalloc.h>
+#include <skalibs/gensetdyn.h>
+
+void gensetdyn_init (gensetdyn_ref g, unsigned int esize, unsigned int base, unsigned int fracnum, unsigned int fracden)
+{
+ g->storage = stralloc_zero ;
+ g->freelist = genalloc_zero ;
+ g->esize = esize ;
+ g->base = base ;
+ g->fracnum = fracnum ;
+ g->fracden = fracden ;
+}
diff --git a/src/libdatastruct/gensetdyn_iter.c b/src/libdatastruct/gensetdyn_iter.c
new file mode 100644
index 0000000..216d42b
--- /dev/null
+++ b/src/libdatastruct/gensetdyn_iter.c
@@ -0,0 +1,26 @@
+/* ISC license. */
+
+#include <skalibs/bitarray.h>
+#include <skalibs/functypes.h>
+#include <skalibs/gensetdyn.h>
+
+unsigned int gensetdyn_iter (gensetdyn_ref g, 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) ;
+ 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) ;
+
+ for (; i < sp ; i++) bitarray_clear(bits, fl[i]) ;
+ for (i = 0 ; (i < g->storage.len) && (j < m) ; i++) if (bitarray_peek(bits, i))
+ {
+ j++ ;
+ if ((*f)(gensetdyn_p(g, i), stuff)) n++ ;
+ }
+ return n ;
+}
diff --git a/src/libdatastruct/gensetdyn_new.c b/src/libdatastruct/gensetdyn_new.c
new file mode 100644
index 0000000..6a49189
--- /dev/null
+++ b/src/libdatastruct/gensetdyn_new.c
@@ -0,0 +1,14 @@
+/* ISC license. */
+
+#include <skalibs/genalloc.h>
+#include <skalibs/gensetdyn.h>
+
+int gensetdyn_new (gensetdyn_ref g, unsigned int *i)
+{
+ register unsigned int n ;
+ if (!genalloc_len(unsigned int, &g->freelist) && !gensetdyn_readyplus(g, 1)) return 0 ;
+ n = genalloc_len(unsigned int, &g->freelist) ;
+ *i = genalloc_s(unsigned int, &g->freelist)[n-1] ;
+ genalloc_setlen(unsigned int, &g->freelist, n-1) ;
+ return 1 ;
+}
diff --git a/src/libdatastruct/gensetdyn_ready.c b/src/libdatastruct/gensetdyn_ready.c
new file mode 100644
index 0000000..d1cfd9f
--- /dev/null
+++ b/src/libdatastruct/gensetdyn_ready.c
@@ -0,0 +1,26 @@
+/* ISC license. */
+
+#include <skalibs/stralloc.h>
+#include <skalibs/genalloc.h>
+#include <skalibs/gensetdyn.h>
+
+int gensetdyn_ready (gensetdyn_ref g, unsigned int n)
+{
+ int wasnull = !g->storage.s ;
+ unsigned int i = g->storage.len ;
+ if (n < i) return 1 ;
+ n += g->base + (n * g->fracnum) / g->fracden ;
+ if (!stralloc_ready_tuned(&g->storage, n * g->esize, 0, 0, 1)) return 0 ;
+ if (!genalloc_ready(unsigned int, &g->freelist, n))
+ {
+ if (wasnull) stralloc_free(&g->storage) ;
+ return 0 ;
+ }
+ for (; i < n ; i++)
+ {
+ unsigned int j = n - 1 - i + g->storage.len ;
+ genalloc_catb(unsigned int, &g->freelist, &j, 1) ;
+ }
+ g->storage.len = n ;
+ return 1 ;
+}
diff --git a/src/libdatastruct/gensetdyn_zero.c b/src/libdatastruct/gensetdyn_zero.c
new file mode 100644
index 0000000..e3ab04a
--- /dev/null
+++ b/src/libdatastruct/gensetdyn_zero.c
@@ -0,0 +1,5 @@
+/* ISC license. */
+
+#include <skalibs/gensetdyn.h>
+
+gensetdyn const gensetdyn_zero = GENSETDYN_ZERO ;