initial commit with rc for skalibs-2.0.0.0

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 ;