diff options
Diffstat (limited to 'src/libdatastruct')
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 ; |