From dd6bb6c6b8298ebeff2d1882becb36580b969d6f Mon Sep 17 00:00:00 2001 From: Laurent Bercot Date: Fri, 23 Jul 2021 16:43:57 +0000 Subject: New 2.11.0.0 branch with several modifications - libbiguint removed - cdb_make changed to cdbmake (because different ui) - cdb redesigned Signed-off-by: Laurent Bercot --- src/include/skalibs/cdb.h | 68 ++++++++++---------- src/include/skalibs/cdb_make.h | 27 -------- src/include/skalibs/cdbmake.h | 27 ++++++++ src/include/skalibs/posixplz.h | 1 + src/include/skalibs/stddjb.h | 2 +- src/libbiguint/bu_addc.c | 19 ------ src/libbiguint/bu_addmod.c | 10 --- src/libbiguint/bu_cmp.c | 17 ----- src/libbiguint/bu_copy.c | 18 ------ src/libbiguint/bu_copy_internal.c | 8 --- src/libbiguint/bu_div.c | 22 ------- src/libbiguint/bu_div_internal.c | 44 ------------- src/libbiguint/bu_divmod.c | 31 --------- src/libbiguint/bu_divmod_internal.c | 36 ----------- src/libbiguint/bu_fmt.c | 19 ------ src/libbiguint/bu_gcd.c | 32 ---------- src/libbiguint/bu_invmod.c | 11 ---- src/libbiguint/bu_len.c | 9 --- src/libbiguint/bu_mod.c | 9 --- src/libbiguint/bu_mul.c | 32 ---------- src/libbiguint/bu_mulmod.c | 15 ----- src/libbiguint/bu_pack.c | 9 --- src/libbiguint/bu_pack_big.c | 10 --- src/libbiguint/bu_scan.c | 15 ----- src/libbiguint/bu_scan_internal.c | 21 ------- src/libbiguint/bu_scanlen.c | 12 ---- src/libbiguint/bu_slbc.c | 16 ----- src/libbiguint/bu_srbc.c | 14 ----- src/libbiguint/bu_subc.c | 19 ------ src/libbiguint/bu_submod.c | 11 ---- src/libbiguint/bu_unpack.c | 9 --- src/libbiguint/bu_unpack_big.c | 10 --- src/libbiguint/bu_zero.c | 8 --- src/libposixplz/munmap_void.c | 13 ++++ src/libstddjb/cdb-internal.h | 14 +++++ src/libstddjb/cdb_find.c | 57 +++++++++++++++++ src/libstddjb/cdb_findnext.c | 68 -------------------- src/libstddjb/cdb_free.c | 12 ++-- src/libstddjb/cdb_hash.c | 10 ++- src/libstddjb/cdb_init.c | 22 ++++--- src/libstddjb/cdb_make.c | 122 ------------------------------------ src/libstddjb/cdb_mapfile.c | 17 ----- src/libstddjb/cdb_nextkey.c | 23 ------- src/libstddjb/cdb_p.c | 9 +++ src/libstddjb/cdb_read.c | 14 ----- src/libstddjb/cdb_reader_zero.c | 5 ++ src/libstddjb/cdb_successor.c | 17 ----- src/libstddjb/cdb_traverse_next.c | 25 ++++++++ src/libstddjb/cdb_zero.c | 2 +- src/libstddjb/cdbmake.c | 121 +++++++++++++++++++++++++++++++++++ 50 files changed, 333 insertions(+), 829 deletions(-) delete mode 100644 src/include/skalibs/cdb_make.h create mode 100644 src/include/skalibs/cdbmake.h delete mode 100644 src/libbiguint/bu_addc.c delete mode 100644 src/libbiguint/bu_addmod.c delete mode 100644 src/libbiguint/bu_cmp.c delete mode 100644 src/libbiguint/bu_copy.c delete mode 100644 src/libbiguint/bu_copy_internal.c delete mode 100644 src/libbiguint/bu_div.c delete mode 100644 src/libbiguint/bu_div_internal.c delete mode 100644 src/libbiguint/bu_divmod.c delete mode 100644 src/libbiguint/bu_divmod_internal.c delete mode 100644 src/libbiguint/bu_fmt.c delete mode 100644 src/libbiguint/bu_gcd.c delete mode 100644 src/libbiguint/bu_invmod.c delete mode 100644 src/libbiguint/bu_len.c delete mode 100644 src/libbiguint/bu_mod.c delete mode 100644 src/libbiguint/bu_mul.c delete mode 100644 src/libbiguint/bu_mulmod.c delete mode 100644 src/libbiguint/bu_pack.c delete mode 100644 src/libbiguint/bu_pack_big.c delete mode 100644 src/libbiguint/bu_scan.c delete mode 100644 src/libbiguint/bu_scan_internal.c delete mode 100644 src/libbiguint/bu_scanlen.c delete mode 100644 src/libbiguint/bu_slbc.c delete mode 100644 src/libbiguint/bu_srbc.c delete mode 100644 src/libbiguint/bu_subc.c delete mode 100644 src/libbiguint/bu_submod.c delete mode 100644 src/libbiguint/bu_unpack.c delete mode 100644 src/libbiguint/bu_unpack_big.c delete mode 100644 src/libbiguint/bu_zero.c create mode 100644 src/libposixplz/munmap_void.c create mode 100644 src/libstddjb/cdb-internal.h create mode 100644 src/libstddjb/cdb_find.c delete mode 100644 src/libstddjb/cdb_findnext.c delete mode 100644 src/libstddjb/cdb_make.c delete mode 100644 src/libstddjb/cdb_mapfile.c delete mode 100644 src/libstddjb/cdb_nextkey.c create mode 100644 src/libstddjb/cdb_p.c delete mode 100644 src/libstddjb/cdb_read.c create mode 100644 src/libstddjb/cdb_reader_zero.c delete mode 100644 src/libstddjb/cdb_successor.c create mode 100644 src/libstddjb/cdb_traverse_next.c create mode 100644 src/libstddjb/cdbmake.c (limited to 'src') diff --git a/src/include/skalibs/cdb.h b/src/include/skalibs/cdb.h index 20d3903..9b05b22 100644 --- a/src/include/skalibs/cdb.h +++ b/src/include/skalibs/cdb.h @@ -1,50 +1,48 @@ /* ISC license. */ -#ifndef CDB_H -#define CDB_H +#ifndef SKALIBS_CDB_H +#define SKALIBS_CDB_H #include -#include -#define CDB_HASHSTART 5381 -extern uint32_t cdb_hashadd (uint32_t, unsigned char) gccattr_const ; -extern uint32_t cdb_hash (char const *, unsigned int) gccattr_pure ; +#include -typedef struct cdb cdb_t, *cdb_t_ref ; -struct cdb +typedef struct cdb_s cdb, *cdb_ref ; +struct cdb_s { - char *map ; - uint32_t size ; /* initialized if map is nonzero */ - uint32_t loop ; /* number of hash slots searched under this key */ - uint32_t khash ; /* initialized if loop is nonzero */ - uint32_t kpos ; /* initialized if loop is nonzero */ - uint32_t hpos ; /* initialized if loop is nonzero */ - uint32_t hslots ; /* initialized if loop is nonzero */ - uint32_t dpos ; /* initialized if cdb_findnext() returns 1 */ - uint32_t dlen ; /* initialized if cdb_findnext() returns 1 */ + char const *map ; + uint32_t size ; } ; +#define CDB_ZERO { .map = 0, .size = 0 } +extern cdb const cdb_zero ; -#define CDB_ZERO { .map = 0, .size = 0, .loop = 0, .khash = 0, .kpos = 0, .hpos = 0, .hslots = 0, .dpos = 0, .dlen = 0 } -extern struct cdb const cdb_zero ; +typedef struct cdb_reader_s cdb_reader, *cdb_reader_ref ; +struct cdb_reader_s +{ + uint32_t loop ; + uint32_t khash ; + uint32_t kpos ; + uint32_t hpos ; + uint32_t hslots ; +} ; +#define CDB_READER_ZERO { .loop = 0, .khash = 0, .kpos = 0, .hpos = 0, .hslots = 0 } +extern cdb_reader const cdb_reader_zero ; -extern void cdb_free (struct cdb *) ; +typedef struct cdb_data_s cdb_data, *cdb_data_ref ; +struct cdb_data_s +{ + char const *s ; + uint32_t len ; +} ; -#define cdb_init_map(c, fd, domap) (!cdb_init(c, fd)) -extern int cdb_init (struct cdb *, int fd) ; -extern int cdb_mapfile (struct cdb *, char const *) ; -extern int cdb_read (struct cdb *, char *, unsigned int, uint32_t) ; -#define cdb_findstart(c) ((c)->loop = 0) -extern int cdb_findnext (struct cdb *, char const *, unsigned int) ; -#define cdb_find(c, s, len) (cdb_findstart(c), cdb_findnext(c, s, len)) +extern void cdb_free (cdb *) ; +extern int cdb_init (cdb *, char const *) ; -#define cdb_datapos(c) ((c)->dpos) -#define cdb_datalen(c) ((c)->dlen) -#define cdb_keypos(c) ((c)->kpos) -#define cdb_keylen(c) ((c)->dpos - (c)->kpos) +#define cdb_findstart(d) ((d)->loop = 0) +extern int cdb_find (cdb const *, cdb_reader *, cdb_data *, char const *, uint32_t) ; -#define cdb_traverse_init(c, kpos) (*(kpos) = 2048) -#define cdb_firstkey(c, kpos) (cdb_traverse_init(c, kpos), cdb_nextkey(c, kpos)) -extern int cdb_nextkey (struct cdb *, uint32_t *) ; -extern int cdb_successor (struct cdb *, char const *, unsigned int) ; +#define CDB_TRAVERSE_INIT() 2048 +#define cdb_traverse_init(pos) (*pos = 2048) +extern int cdb_traverse_next (cdb const *, cdb_data *, cdb_data *, uint32_t *) ; #endif diff --git a/src/include/skalibs/cdb_make.h b/src/include/skalibs/cdb_make.h deleted file mode 100644 index 69e1c68..0000000 --- a/src/include/skalibs/cdb_make.h +++ /dev/null @@ -1,27 +0,0 @@ -/* ISC license. */ - -#ifndef CDB_MAKE_H -#define CDB_MAKE_H - -#include -#include -#include -#include -#include - -typedef struct cdb_make cdb_make, *cdb_make_ref ; -struct cdb_make -{ - genalloc hplist ; /* array of diuint32 */ - uint32_t pos ; - buffer b ; - char buf[BUFFER_OUTSIZE] ; -} ; - -#define CDB_MAKE_ZERO { .hplist = GENALLOC_ZERO, .pos = 2048, .b = BUFFER_INIT(&fd_writev, -1, 0, 0) } - -extern int cdb_make_start (struct cdb_make *, int) ; -extern int cdb_make_add (struct cdb_make *, char const *, unsigned int, char const *, unsigned int) ; -extern int cdb_make_finish (struct cdb_make *) ; - -#endif diff --git a/src/include/skalibs/cdbmake.h b/src/include/skalibs/cdbmake.h new file mode 100644 index 0000000..bf03ad6 --- /dev/null +++ b/src/include/skalibs/cdbmake.h @@ -0,0 +1,27 @@ +/* ISC license. */ + +#ifndef SKALIBS_CDBMAKE_H +#define SKALIBS_CDBMAKE_H + +#include +#include +#include +#include +#include + +typedef struct cdbmaker_s cdbmaker, *cdbmaker_ref ; +struct cdbmaker_s +{ + genalloc hplist ; /* array of diuint32 */ + uint32_t pos ; + buffer b ; + char buf[BUFFER_OUTSIZE] ; +} ; + +#define CDBMAKER_ZERO { .hplist = GENALLOC_ZERO, .pos = 2048, .b = BUFFER_INIT(&fd_writev, -1, 0, 0) } + +extern int cdbmake_start (cdbmaker *, int) ; +extern int cdbmake_add (cdbmaker *, char const *, unsigned int, char const *, unsigned int) ; +extern int cdbmake_finish (cdbmaker *) ; + +#endif diff --git a/src/include/skalibs/posixplz.h b/src/include/skalibs/posixplz.h index 55e03fc..2c972c8 100644 --- a/src/include/skalibs/posixplz.h +++ b/src/include/skalibs/posixplz.h @@ -34,6 +34,7 @@ extern int getpeereid (int, uid_t *, gid_t *) ; extern void execvep (char const *, char const *const *, char const *const *, char const *) ; extern void execvep_loose (char const *, char const *const *, char const *const *, char const *) ; extern void unlink_void (char const *) ; +extern void munmap_void (void *, size_t) ; extern pid_t doublefork (void) ; extern int touch (char const *) ; diff --git a/src/include/skalibs/stddjb.h b/src/include/skalibs/stddjb.h index b15bff3..b2b1d32 100644 --- a/src/include/skalibs/stddjb.h +++ b/src/include/skalibs/stddjb.h @@ -19,7 +19,7 @@ #include #include #include -#include +#include #include #include #include diff --git a/src/libbiguint/bu_addc.c b/src/libbiguint/bu_addc.c deleted file mode 100644 index b6d1ccb..0000000 --- a/src/libbiguint/bu_addc.c +++ /dev/null @@ -1,19 +0,0 @@ -/* ISC license. */ - -#include -#include -#include - -int bu_addc (uint32_t *c, unsigned int cn, uint32_t const *a, unsigned int an, uint32_t const *b, unsigned int bn, int carry) -{ - unsigned int i = 0 ; - for (; i < cn ; i++) - { - uint32_t ai = (i < an) ? a[i] : 0 ; - uint32_t bi = (i < bn) ? b[i] : 0 ; - uint32_t ci = ai + bi + carry ; - carry = (carry || bi) && (ci < ai) ; - c[i] = ci ; - } - return carry ? (errno = EOVERFLOW, 0) : 1 ; -} diff --git a/src/libbiguint/bu_addmod.c b/src/libbiguint/bu_addmod.c deleted file mode 100644 index 4ebe2f7..0000000 --- a/src/libbiguint/bu_addmod.c +++ /dev/null @@ -1,10 +0,0 @@ -/* ISC license. */ - -#include - -int bu_addmod (uint32_t *c, unsigned int cn, uint32_t const *a, unsigned int an, uint32_t const *b, unsigned int bn, uint32_t const *m, unsigned int mn) -{ - if (!bu_add(c, cn, a, an, b, bn)) return 0 ; - if (bu_cmp(c, cn, m, mn) >= 0) bu_sub(c, cn, c, cn, m, mn) ; - return 1 ; -} diff --git a/src/libbiguint/bu_cmp.c b/src/libbiguint/bu_cmp.c deleted file mode 100644 index 0c87e92..0000000 --- a/src/libbiguint/bu_cmp.c +++ /dev/null @@ -1,17 +0,0 @@ -/* ISC license. */ - -#include - -int bu_cmp (uint32_t const *a, unsigned int an, uint32_t const *b, unsigned int bn) -{ - an = bu_len(a, an) ; - bn = bu_len(b, bn) ; - if (an < bn) return -1 ; - if (an > bn) return 1 ; - while (bn--) - { - if (a[bn] < b[bn]) return -1 ; - if (a[bn] > b[bn]) return 1 ; - } - return 0 ; -} diff --git a/src/libbiguint/bu_copy.c b/src/libbiguint/bu_copy.c deleted file mode 100644 index 0c64417..0000000 --- a/src/libbiguint/bu_copy.c +++ /dev/null @@ -1,18 +0,0 @@ -/* ISC license. */ - -#include -#include -#include - -int bu_copy (uint32_t *b, unsigned int bn, uint32_t const *a, unsigned int an) -{ - unsigned int alen = bu_len(a, an) ; - if (bn < alen) - { - bu_copy_internal(b, a, bn) ; - return (errno = EOVERFLOW, 0) ; - } - bu_copy_internal(b, a, alen) ; - bu_zero(b + alen, bn - alen) ; - return 1 ; -} diff --git a/src/libbiguint/bu_copy_internal.c b/src/libbiguint/bu_copy_internal.c deleted file mode 100644 index 8de4d5e..0000000 --- a/src/libbiguint/bu_copy_internal.c +++ /dev/null @@ -1,8 +0,0 @@ -/* ISC license. */ - -#include - -void bu_copy_internal (uint32_t *b, uint32_t const *a, unsigned int n) -{ - while (n--) b[n] = a[n] ; -} diff --git a/src/libbiguint/bu_div.c b/src/libbiguint/bu_div.c deleted file mode 100644 index a5b6986..0000000 --- a/src/libbiguint/bu_div.c +++ /dev/null @@ -1,22 +0,0 @@ -/* ISC license. */ - -#include -#include - -int bu_div (uint32_t const *a, unsigned int an, uint32_t const *b, unsigned int bn, uint32_t *q, unsigned int qn, uint32_t *r, unsigned int rn) -{ - unsigned int alen = bu_len(a, an) ; - unsigned int blen = bu_len(b, bn) ; - if (!blen) return (errno = EDOM, 0) ; - else - { - uint32_t qq[alen] ; - uint32_t rr[alen] ; - int qh, rh ; - bu_copy_internal(rr, a, alen) ; - bu_div_internal(rr, alen, b, blen, qq, alen) ; - qh = bu_copy(q, qn, qq, alen) ; - rh = bu_copy(r, rn, rr, alen) ; - return qh && rh ; - } -} diff --git a/src/libbiguint/bu_div_internal.c b/src/libbiguint/bu_div_internal.c deleted file mode 100644 index 0765a99..0000000 --- a/src/libbiguint/bu_div_internal.c +++ /dev/null @@ -1,44 +0,0 @@ -/* ISC license. */ - -#include - -/* - q = a/b, a = a mod b. Assumes b != 0 and qn >= alen - blen + 1. -*/ - -void bu_div_internal (uint32_t *a, unsigned int an, uint32_t const *b, unsigned int bn, uint32_t *q, unsigned int qn) -{ - unsigned int alen = bu_len(a, an) ; - unsigned int blen = bu_len(b, bn) ; - bu_zero(q, qn) ; - if (alen < blen) return ; - { - uint32_t bb[alen + 1] ; - unsigned int i = 1 + ((alen - blen) << 5) ; - bu_zero(bb, alen - blen) ; - bu_copy_internal(bb + alen - blen, b, blen) ; - bb[alen] = 0 ; - - while (bu_cmp(a, alen, bb, alen+1) >= 0) - { - bu_slb(bb + alen - blen, blen + 1) ; - i++ ; - } - while (i && (bu_cmp(a, alen, bb, alen+1) < 0)) - { - bu_srb(bb, alen + 1) ; - i-- ; - } - - while (i--) - { - bu_slb(q, alen - blen + 1) ; - if (bu_cmp(a, alen, bb, alen) >= 0) - { - bu_sub(a, alen, a, alen, bb, alen) ; - q[0] |= 1 ; - } - bu_srb(bb, alen) ; - } - } -} diff --git a/src/libbiguint/bu_divmod.c b/src/libbiguint/bu_divmod.c deleted file mode 100644 index 17b6b7b..0000000 --- a/src/libbiguint/bu_divmod.c +++ /dev/null @@ -1,31 +0,0 @@ -/* ISC license. */ - -#include -#include - -/* - q = y/x mod m. -*/ - -int bu_divmod (uint32_t *q, unsigned int qn, uint32_t const *y, unsigned int yn, uint32_t const *x, unsigned int xn, uint32_t const *m, unsigned int mn) -{ - unsigned int ylen = bu_len(y, yn) ; - unsigned int xlen = bu_len(x, xn) ; - unsigned int mlen = bu_len(m, mn) ; - unsigned int n = ylen ; - if (n < xlen) n = xlen ; - if (n < mlen) n = mlen ; - if (!n) return (errno = EDOM, 0) ; - { - uint32_t yy[n] ; - uint32_t xx[n] ; - uint32_t mm[n] ; - bu_gcd(xx, n, x, xlen, m, mlen) ; - if ((xx[0] != 1) || (bu_len(xx, n) != 1)) return (errno = EDOM, 0) ; - bu_copy_internal(yy, y, ylen) ; bu_zero(yy+ylen, n-ylen) ; - bu_copy_internal(xx, x, xlen) ; bu_zero(xx+xlen, n-xlen) ; - bu_copy_internal(mm, m, mlen) ; bu_zero(mm+mlen, n-mlen) ; - bu_divmod_internal(yy, xx, mm, n) ; - return bu_copy(q, qn, yy, n) ; - } -} diff --git a/src/libbiguint/bu_divmod_internal.c b/src/libbiguint/bu_divmod_internal.c deleted file mode 100644 index afb8ccc..0000000 --- a/src/libbiguint/bu_divmod_internal.c +++ /dev/null @@ -1,36 +0,0 @@ -/* ISC license. */ - -#include - -/* - u = u/a mod m. a and m must be relatively prime - otherwise, infinite loop. - a is not immutable. - Original idea by Sheueling Chang Shantz of Sun Research. -*/ - -void bu_divmod_internal (uint32_t *u, uint32_t *a, uint32_t const *m, unsigned int n) -{ - uint32_t bb[n] ; uint32_t *b = bb ; - uint32_t vv[n] ; uint32_t *v = vv ; - bu_copy_internal(b, m, n) ; - bu_zero(v, n) ; - - /*** XXX: this iterates like mad, should probably be optimized more */ - for (;;) - { - while (!(a[0] & 1)) - { - bu_srb(a, n) ; - if (u[0] & 1) bu_add(u, n, u, n, m, n) ; - bu_srb(u, n) ; - } - if ((a[0] == 1) && (bu_len(a, n) == 1)) break ; - if (bu_cmp(a, n, b, n) < 0) - { - uint32_t *t = a ; a = b ; b = t ; - t = u ; u = v ; v = t ; - } - bu_add(a, n, a, n, b, n) ; - bu_add(u, n, u, n, v, n) ; - } -} diff --git a/src/libbiguint/bu_fmt.c b/src/libbiguint/bu_fmt.c deleted file mode 100644 index 9402621..0000000 --- a/src/libbiguint/bu_fmt.c +++ /dev/null @@ -1,19 +0,0 @@ -/* ISC license. */ - -#include -#include -#include - -size_t bu_fmt (char *s, uint32_t const *x, unsigned int n) -{ - size_t len = 0 ; - while (n--) - { - char fmt[8] ; - size_t i = uint32_xfmt(fmt, x[n]) ; - memcpy(s+len, "00000000", 8-i) ; - memcpy(s+len+8-i, fmt, i) ; - len += 8 ; - } - return len ; -} diff --git a/src/libbiguint/bu_gcd.c b/src/libbiguint/bu_gcd.c deleted file mode 100644 index 738091e..0000000 --- a/src/libbiguint/bu_gcd.c +++ /dev/null @@ -1,32 +0,0 @@ -/* ISC license. */ - -#include - -int bu_gcd (uint32_t *r, unsigned int rn, uint32_t const *a, unsigned int an, uint32_t const *b, unsigned int bn) -{ - if (bu_cmp(a, an, b, bn) < 0) - { - uint32_t const *t = a ; - unsigned int tn = an ; - a = b ; an = bn ; - b = t ; bn = tn ; - } - { - uint32_t trash[an] ; - uint32_t aa[an] ; - uint32_t bb[an] ; - uint32_t *aaa = aa, *bbb = bb ; - bu_copy_internal(aa, a, an) ; - bu_copy_internal(bb, b, bn) ; - bu_zero(bb+bn, an-bn) ; - - while (bu_len(bbb, an)) - { - uint32_t *ttt = aaa ; - bu_div_internal(aaa, an, bbb, an, trash, an) ; - aaa = bbb ; - bbb = ttt ; - } - return bu_copy(r, rn, aaa, an) ; - } -} diff --git a/src/libbiguint/bu_invmod.c b/src/libbiguint/bu_invmod.c deleted file mode 100644 index f9ae9e2..0000000 --- a/src/libbiguint/bu_invmod.c +++ /dev/null @@ -1,11 +0,0 @@ -/* ISC license. */ - -#include - -/* x^-1 mod m. */ - -int bu_invmod (uint32_t *x, unsigned int xn, uint32_t const *m, unsigned int mn) -{ - uint32_t const one = 1 ; - return bu_divmod(x, xn, &one, 1, x, xn, m, mn) ; -} diff --git a/src/libbiguint/bu_len.c b/src/libbiguint/bu_len.c deleted file mode 100644 index 6e66b17..0000000 --- a/src/libbiguint/bu_len.c +++ /dev/null @@ -1,9 +0,0 @@ -/* ISC license. */ - -#include - -unsigned int bu_len (uint32_t const *a, unsigned int n) -{ - while (n--) if (a[n]) return n+1 ; - return 0 ; -} diff --git a/src/libbiguint/bu_mod.c b/src/libbiguint/bu_mod.c deleted file mode 100644 index ca16af0..0000000 --- a/src/libbiguint/bu_mod.c +++ /dev/null @@ -1,9 +0,0 @@ -/* ISC license. */ - -#include - -int bu_mod (uint32_t *a, unsigned int an, uint32_t const *b, unsigned int bn) -{ - uint32_t q[an] ; - return bu_div(a, an, b, bn, q, an, a, an) ; -} diff --git a/src/libbiguint/bu_mul.c b/src/libbiguint/bu_mul.c deleted file mode 100644 index 16043fd..0000000 --- a/src/libbiguint/bu_mul.c +++ /dev/null @@ -1,32 +0,0 @@ -/* ISC license. */ - -#include -#include -#include - - /* No Karatsuba. Keep it simple, stupid. */ - -int bu_mul (uint32_t *x, unsigned int xn, uint32_t const *a, unsigned int an, uint32_t const *b, unsigned int bn) -{ - unsigned int alen = bu_len(a, an) ; - unsigned int blen = bu_len(b, bn) ; - uint32_t c[alen + blen] ; - unsigned int i = 0 ; - bu_zero(c, alen + blen) ; - for (; i < alen ; i++) - { - uint32_t carry = 0 ; - unsigned int j = 0 ; - for (; j < blen ; j++) - { - uint64_t t = a[i] ; - t *= b[j] ; - t += c[i+j] ; - t += carry ; - c[i+j] = (uint32_t)t ; - carry = (uint32_t)(t >> 32) ; - } - c[i+j] += carry ; - } - return bu_copy(x, xn, c, alen+blen) ; -} diff --git a/src/libbiguint/bu_mulmod.c b/src/libbiguint/bu_mulmod.c deleted file mode 100644 index 59ed3fc..0000000 --- a/src/libbiguint/bu_mulmod.c +++ /dev/null @@ -1,15 +0,0 @@ -/* ISC license. */ - -#include - - /* Nope, no Montgomery either. */ - -int bu_mulmod (uint32_t *c, unsigned int cn, uint32_t const *a, unsigned int an, uint32_t const *b, unsigned int bn, uint32_t const *m, unsigned int mn) -{ - unsigned int alen = bu_len(a, an) ; - unsigned int blen = bu_len(b, bn) ; - uint32_t x[alen+blen] ; - if (!bu_mul(x, alen+blen, a, alen, b, blen)) return 0 ; - if (!bu_mod(x, alen+blen, m, mn)) return 0 ; - return bu_copy(c, cn, x, mn) ; -} diff --git a/src/libbiguint/bu_pack.c b/src/libbiguint/bu_pack.c deleted file mode 100644 index b43ab04..0000000 --- a/src/libbiguint/bu_pack.c +++ /dev/null @@ -1,9 +0,0 @@ -/* ISC license. */ - -#include -#include - -void bu_pack (char *s, uint32_t const *a, unsigned int n) -{ - while (n--) uint32_pack(s + (n<<2), a[n]) ; -} diff --git a/src/libbiguint/bu_pack_big.c b/src/libbiguint/bu_pack_big.c deleted file mode 100644 index caca082..0000000 --- a/src/libbiguint/bu_pack_big.c +++ /dev/null @@ -1,10 +0,0 @@ -/* ISC license. */ - -#include -#include - -void bu_pack_big (char *s, uint32_t const *a, unsigned int n) -{ - unsigned int i = 0 ; - for (; i < n ; i++) uint32_pack_big(s + (i<<2), a[n-1-i]) ; -} diff --git a/src/libbiguint/bu_scan.c b/src/libbiguint/bu_scan.c deleted file mode 100644 index 8d4ecd0..0000000 --- a/src/libbiguint/bu_scan.c +++ /dev/null @@ -1,15 +0,0 @@ -/* ISC license. */ - -#include -#include -#include -#include - -int bu_scan (char const *s, size_t len, uint32_t *x, unsigned int xn, size_t zeron) -{ - size_t n = bitarray_div8(zeron) ; - if (xn < n) return (errno = EOVERFLOW, 0) ; - bu_scan_internal(s, len, x) ; - bu_zero(x + n, xn - n) ; - return 1 ; -} diff --git a/src/libbiguint/bu_scan_internal.c b/src/libbiguint/bu_scan_internal.c deleted file mode 100644 index d7a75b6..0000000 --- a/src/libbiguint/bu_scan_internal.c +++ /dev/null @@ -1,21 +0,0 @@ -/* ISC license. */ - -#include -#include -#include - -void bu_scan_internal (char const *s, size_t len, uint32_t *x) -{ - char fmt[9] = "\0\0\0\0\0\0\0\0" ; - size_t i = 0 ; - if (len & 7) - { - memcpy(fmt, s, len & 7) ; - uint32_xscan(fmt, x + (len >> 3)) ; - } - for (; i < (len >> 3) ; i++) - { - memcpy(fmt, s + len - 8 - (i << 3), 8) ; - uint32_xscan(fmt, x + i) ; - } -} diff --git a/src/libbiguint/bu_scanlen.c b/src/libbiguint/bu_scanlen.c deleted file mode 100644 index ed93fa3..0000000 --- a/src/libbiguint/bu_scanlen.c +++ /dev/null @@ -1,12 +0,0 @@ -/* ISC license. */ - -#include -#include - -size_t bu_scanlen (char const *s, size_t *zeron) -{ - size_t n = ucharn_findlen(s) ; - *zeron = n ; - while (*s == '0') { s++ ; (*zeron)-- ; } - return n ; -} diff --git a/src/libbiguint/bu_slbc.c b/src/libbiguint/bu_slbc.c deleted file mode 100644 index 13d9b6d..0000000 --- a/src/libbiguint/bu_slbc.c +++ /dev/null @@ -1,16 +0,0 @@ -/* ISC license. */ - -#include - -int bu_slbc (uint32_t *a, unsigned int n, int carry) -{ - unsigned int i = 0 ; - carry = !!carry ; - for (; i < n ; i++) - { - int c = a[i] >> 31 ; - a[i] = (a[i] << 1) | carry ; - carry = c ; - } - return carry ; -} diff --git a/src/libbiguint/bu_srbc.c b/src/libbiguint/bu_srbc.c deleted file mode 100644 index b23186b..0000000 --- a/src/libbiguint/bu_srbc.c +++ /dev/null @@ -1,14 +0,0 @@ -/* ISC license. */ - -#include - -int bu_srbc (uint32_t *a, unsigned int n, int carry) -{ - while (n--) - { - int c = a[n] & 1 ; - a[n] = (a[n] >> 1) | (carry ? 0x80000000U : 0) ; - carry = c ; - } - return carry ; -} diff --git a/src/libbiguint/bu_subc.c b/src/libbiguint/bu_subc.c deleted file mode 100644 index 63147b0..0000000 --- a/src/libbiguint/bu_subc.c +++ /dev/null @@ -1,19 +0,0 @@ -/* ISC license. */ - -#include -#include -#include - -int bu_subc (uint32_t *c, unsigned int cn, uint32_t const *a, unsigned int an, uint32_t const *b, unsigned int bn, int carry) -{ - unsigned int i = 0 ; - for (; i < cn ; i++) - { - uint32_t ai = (i < an) ? a[i] : 0 ; - uint32_t bi = (i < bn) ? b[i] : 0 ; - uint32_t ci = ai - bi - carry ; - carry = (carry || bi) && (ci > ai) ; - c[i] = ci ; - } - return carry ? (errno = EOVERFLOW, 0) : 1 ; -} diff --git a/src/libbiguint/bu_submod.c b/src/libbiguint/bu_submod.c deleted file mode 100644 index 98048e1..0000000 --- a/src/libbiguint/bu_submod.c +++ /dev/null @@ -1,11 +0,0 @@ -/* ISC license. */ - -#include -#include - -int bu_submod (uint32_t *c, unsigned int cn, uint32_t const *a, unsigned int an, uint32_t const *b, unsigned int bn, uint32_t const *m, unsigned int mn) -{ - if (!bu_sub(c, cn, a, an, b, bn) && bu_add(c, cn, c, cn, m, mn)) - return (errno = EDOM, 0) ; - return 1 ; -} diff --git a/src/libbiguint/bu_unpack.c b/src/libbiguint/bu_unpack.c deleted file mode 100644 index 0c93277..0000000 --- a/src/libbiguint/bu_unpack.c +++ /dev/null @@ -1,9 +0,0 @@ -/* ISC license. */ - -#include -#include - -void bu_unpack (char const *s, uint32_t *a, unsigned int n) -{ - while (n--) uint32_unpack(s + (n<<2), a + n) ; -} diff --git a/src/libbiguint/bu_unpack_big.c b/src/libbiguint/bu_unpack_big.c deleted file mode 100644 index 97f37cf..0000000 --- a/src/libbiguint/bu_unpack_big.c +++ /dev/null @@ -1,10 +0,0 @@ -/* ISC license. */ - -#include -#include - -void bu_unpack_big (char const *s, uint32_t *a, unsigned int n) -{ - unsigned int i = 0 ; - for (; i < n ; i++) uint32_unpack_big(s + (i<<2), a + n - 1 - i) ; -} diff --git a/src/libbiguint/bu_zero.c b/src/libbiguint/bu_zero.c deleted file mode 100644 index ab87752..0000000 --- a/src/libbiguint/bu_zero.c +++ /dev/null @@ -1,8 +0,0 @@ -/* ISC license. */ - -#include - -void bu_zero (uint32_t *z, unsigned int n) -{ - while (n--) z[n] = 0 ; -} diff --git a/src/libposixplz/munmap_void.c b/src/libposixplz/munmap_void.c new file mode 100644 index 0000000..bbc6e10 --- /dev/null +++ b/src/libposixplz/munmap_void.c @@ -0,0 +1,13 @@ +/* ISC license. */ + +#include +#include + +#include + +void munmap_void (void *addr, size_t len) +{ + int e = errno ; + munmap(addr, len) ; + errno = e ; +} diff --git a/src/libstddjb/cdb-internal.h b/src/libstddjb/cdb-internal.h new file mode 100644 index 0000000..0db5a5d --- /dev/null +++ b/src/libstddjb/cdb-internal.h @@ -0,0 +1,14 @@ +/* ISC license. */ + +#ifndef SKALIBS_CDB_INTERNAL_H +#define SKALIBS_CDB_INTERNAL_H + +#include + +#include +#include + +extern uint32_t cdb_hash (char const *, uint32_t) gccattr_pure ; +extern char const *cdb_p (cdb const *, uint32_t, uint32_t) gccattr_pure ; + +#endif diff --git a/src/libstddjb/cdb_find.c b/src/libstddjb/cdb_find.c new file mode 100644 index 0000000..a9c66e3 --- /dev/null +++ b/src/libstddjb/cdb_find.c @@ -0,0 +1,57 @@ +/* ISC license. */ + +#include +#include + +#include +#include +#include "cdb-internal.h" + +int cdb_find (cdb const *c, cdb_reader *d, cdb_data *out, char const *key, uint32_t len) +{ + if (!d->loop) + { + uint32_t u = cdb_hash(key, len) ; + char const *p = cdb_p(c, 8, (u << 3) & 2047) ; + if (!p) return -1 ; + uint32_unpack(p + 4, &d->hslots) ; + if (!d->hslots) return 0 ; + uint32_unpack(p, &d->hpos) ; + d->khash = u ; + u >>= 8 ; + u %= d->hslots ; + u <<= 3 ; + d->kpos = d->hpos + u ; + } + + while (d->loop < d->hslots) + { + uint32_t pos, u ; + char const *p = cdb_p(c, 8, d->kpos) ; + if (!p) return -1 ; + uint32_unpack(p + 4, &pos) ; + if (!pos) return 0 ; + d->loop++ ; + d->kpos += 8 ; + if (d->kpos == d->hpos + (d->hslots << 3)) d->kpos = d->hpos ; + uint32_unpack(p, &u) ; + if (u == d->khash) + { + p = cdb_p(c, 8, pos) ; + if (!p) return -1 ; + uint32_unpack(p, &u) ; + if (u == len) + { + char const *k = cdb_p(c, len, pos + 8) ; + if (!k) return -1 ; + if (!memcmp(key, k, len)) + { + uint32_unpack(p + 4, &out->len) ; + out->s = c->map + pos + 8 + len ; + return 1 ; + } + } + } + } + return 0 ; +} diff --git a/src/libstddjb/cdb_findnext.c b/src/libstddjb/cdb_findnext.c deleted file mode 100644 index 536013b..0000000 --- a/src/libstddjb/cdb_findnext.c +++ /dev/null @@ -1,68 +0,0 @@ -/* ISC license. */ - -#include -#include -#include -#include - -static int match (struct cdb *c, char const *key, unsigned int len, uint32_t pos) -{ - char buf[1024] ; - while (len > 0) - { - unsigned int n = 1024 ; - if (n > len) n = len ; - if (cdb_read(c, buf, n, pos) < 0) return -1 ; - if (memcmp(buf, key, n)) return 0 ; - pos += n ; key += n ; len -= n ; - } - return 1 ; -} - -int cdb_findnext (struct cdb *c, char const *key, unsigned int len) -{ - char buf[8] ; - uint32_t pos ; - uint32_t u ; - - if (!c->loop) - { - u = cdb_hash(key, len) ; - if (cdb_read(c, buf, 8, (u << 3) & 2047) < 0) return -1 ; - uint32_unpack(buf + 4, &c->hslots) ; - if (!c->hslots) return 0 ; - uint32_unpack(buf, &c->hpos) ; - c->khash = u ; - u >>= 8 ; - u %= c->hslots ; - u <<= 3 ; - c->kpos = c->hpos + u ; - } - - while (c->loop < c->hslots) - { - if (cdb_read(c, buf, 8, c->kpos) < 0) return -1 ; - uint32_unpack(buf + 4, &pos) ; - if (!pos) return 0 ; - c->loop++ ; - c->kpos += 8 ; - if (c->kpos == c->hpos + (c->hslots << 3)) c->kpos = c->hpos ; - uint32_unpack(buf, &u) ; - if (u == c->khash) - { - if (cdb_read(c, buf, 8, pos) < 0) return -1 ; - uint32_unpack(buf, &u) ; - if (u == len) - switch (match(c, key, len, pos + 8)) - { - case -1: - return -1 ; - case 1: - uint32_unpack(buf + 4, &c->dlen) ; - c->dpos = pos + 8 + len ; - return 1 ; - } - } - } - return 0 ; -} diff --git a/src/libstddjb/cdb_free.c b/src/libstddjb/cdb_free.c index d4250ec..a59e961 100644 --- a/src/libstddjb/cdb_free.c +++ b/src/libstddjb/cdb_free.c @@ -1,17 +1,13 @@ /* ISC license. */ -#include -#include - +#include #include -extern void cdb_free (struct cdb *c) +extern void cdb_free (cdb *c) { if (c->map) { - int e = errno ; - munmap(c->map, c->size) ; - errno = e ; + munmap_void((void *)c->map, c->size) ; + c->map = 0 ; } - *c = cdb_zero ; } diff --git a/src/libstddjb/cdb_hash.c b/src/libstddjb/cdb_hash.c index 82dcfbc..a7b626b 100644 --- a/src/libstddjb/cdb_hash.c +++ b/src/libstddjb/cdb_hash.c @@ -1,14 +1,18 @@ /* ISC license. */ -#include +#include -uint32_t cdb_hashadd (uint32_t h, unsigned char c) +#include "cdb-internal.h" + +#define CDB_HASHSTART 5381 + +static inline uint32_t cdb_hashadd (uint32_t h, unsigned char c) { h += (h << 5) ; return h ^ c ; } -uint32_t cdb_hash (char const *buf, unsigned int len) +uint32_t cdb_hash (char const *buf, uint32_t len) { uint32_t h = CDB_HASHSTART ; while (len--) h = cdb_hashadd(h, *buf++) ; diff --git a/src/libstddjb/cdb_init.c b/src/libstddjb/cdb_init.c index 8b56c1a..7a6c2f6 100644 --- a/src/libstddjb/cdb_init.c +++ b/src/libstddjb/cdb_init.c @@ -1,23 +1,31 @@ /* ISC license. */ -#include - #include #include #include #include +#include #include -int cdb_init (struct cdb *c, int fd) +int cdb_init (cdb *c, char const *file) { - struct stat st ; char *map ; - if (fstat(fd, &st) < 0) return -1 ; - if (st.st_size > UINT32_MAX) return (errno = EOVERFLOW, -1) ; + struct stat st ; + int fd = openc_read(file) ; + if (fd < 0) return 0 ; + if (fstat(fd, &st) < 0) goto err ; + if (st.st_size > UINT32_MAX) goto eoverf ; map = mmap(0, st.st_size, PROT_READ, MAP_SHARED, fd, 0) ; - if (map == MAP_FAILED) return -1 ; + if (map == MAP_FAILED) goto err ; c->map = map ; c->size = st.st_size ; + fd_close(fd) ; + return 1 ; + + eoverf: + errno = EOVERFLOW ; + err: + fd_close(fd) ; return 0 ; } diff --git a/src/libstddjb/cdb_make.c b/src/libstddjb/cdb_make.c deleted file mode 100644 index 53e64b1..0000000 --- a/src/libstddjb/cdb_make.c +++ /dev/null @@ -1,122 +0,0 @@ -/* ISC license. */ - -#include -#include -#include -#include -#include -#include -#include -#include -#include - -int cdb_make_start (struct cdb_make *c, int fd) -{ - c->hplist = genalloc_zero ; - c->pos = 2048 ; - buffer_init(&c->b, &buffer_write, fd, c->buf, BUFFER_OUTSIZE) ; - if (lseek(fd, c->pos, SEEK_SET) < 0) return -1 ; - return 0 ; -} - -static int posplus (struct cdb_make *c, uint32_t len) -{ - uint32_t newpos = c->pos + len ; - if (newpos < len) return (errno = ENOMEM, 0) ; - c->pos = newpos ; - return 1 ; -} - -static inline int cdb_make_addend (struct cdb_make *c, unsigned int keylen, unsigned int datalen, uint32_t h) -{ - diuint32 blah = { .left = h, .right = c->pos } ; - return genalloc_append(diuint32, &c->hplist, &blah) && posplus(c, 8) && posplus(c, keylen) && posplus(c, datalen) ; -} - -static inline ssize_t cdb_make_addbegin (struct cdb_make *c, unsigned int keylen, unsigned int datalen) -{ - char buf[8] ; - uint32_pack(buf, (uint32_t)keylen) ; - uint32_pack(buf + 4, (uint32_t)datalen) ; - return buffer_put(&c->b, buf, 8) ; -} - -int cdb_make_add (struct cdb_make *c, char const *key, unsigned int keylen, char const *data, unsigned int datalen) -{ - if (cdb_make_addbegin(c, keylen, datalen) < 0 - || buffer_put(&c->b, key, keylen) < 0 - || buffer_put(&c->b, data, datalen) < 0 - || !cdb_make_addend(c, keylen, datalen, cdb_hash(key, keylen))) - { - genalloc_free(diuint32, &c->hplist) ; - return -1 ; - } - return 0 ; -} - -int cdb_make_finish (struct cdb_make *c) -{ - uint32_t count[256] ; - uint32_t start[256] ; - char final[2048] ; - unsigned int size = 1 ; - unsigned int n = genalloc_len(diuint32, &c->hplist) ; - unsigned int i = 0 ; - diuint32 *hp = genalloc_s(diuint32, &c->hplist) ; - - for (; i < 256 ; i++) count[i] = 0 ; - for (i = 0 ; i < n ; i++) ++count[hp[i].left & 255] ; - - { - uint32_t u = 0 ; - for (i = 0 ; i < 256 ; i++) start[i] = u += count[i] ; /* bounded by n */ - for (i = 0 ; i < 256 ; i++) - { - u = count[i] << 1 ; - if (u > size) size = u ; - } - size += n ; /* no overflow possible up to now */ - u = 0xffffffffUL ; u /= sizeof(diuint32) ; - if (size > u) return (errno = ENOMEM, -1) ; - } - i = n ; - { - diuint32 split[size] ; - while (i--) split[--start[hp[i].left & 255]] = hp[i] ; - genalloc_free(diuint32, &c->hplist) ; - hp = split + n ; - - for (i = 0 ; i < 256 ; ++i) - { - char buf[8] ; - uint32_t k = count[i] ; - uint32_t len = k << 1 ; /* no overflow possible */ - diuint32 *p = split + start[i] ; - unsigned int j = 0 ; - - uint32_pack(final + (i << 3), c->pos) ; - uint32_pack(final + (i << 3) + 4, len) ; - - for (; j < len ; j++) hp[j].left = hp[j].right = 0 ; - for (j = 0 ; j < k ; j++) - { - uint32_t where = (p->left >> 8) % len ; - while (hp[where].right) if (++where == len) where = 0 ; - hp[where] = *p++ ; - } - - for (j = 0 ; j < len ; j++) - { - uint32_pack(buf, hp[j].left) ; - uint32_pack(buf + 4, hp[j].right) ; - if (buffer_put(&c->b, buf, 8) < 0) return -1 ; - if (!posplus(c, 8)) return -1 ; - } - } - } - - if (!buffer_flush(&c->b)) return -1 ; - if (lseek(buffer_fd(&c->b), 0, SEEK_SET) < 0) return -1 ; - if (buffer_putflush(&c->b, final, 2048) < 0) return -1 ; - return 0 ; -} diff --git a/src/libstddjb/cdb_mapfile.c b/src/libstddjb/cdb_mapfile.c deleted file mode 100644 index b31f1e6..0000000 --- a/src/libstddjb/cdb_mapfile.c +++ /dev/null @@ -1,17 +0,0 @@ -/* ISC license. */ - -#include -#include - -int cdb_mapfile (struct cdb *c, char const *file) -{ - int fd = openc_read(file) ; - if (fd < 0) return 0 ; - if (cdb_init(c, fd) == -1) - { - fd_close(fd) ; - return 0 ; - } - fd_close(fd) ; - return 1 ; -} diff --git a/src/libstddjb/cdb_nextkey.c b/src/libstddjb/cdb_nextkey.c deleted file mode 100644 index 6de3b24..0000000 --- a/src/libstddjb/cdb_nextkey.c +++ /dev/null @@ -1,23 +0,0 @@ -/* ISC license. */ - -#include -#include - -int cdb_nextkey (struct cdb *c, uint32_t *kpos) -{ - char buf[8] ; - uint32_t eod, klen ; - if (cdb_read(c, buf, 4, 0) < 0) return -1 ; - uint32_unpack(buf, &eod) ; - if (eod < 8 || eod - 8 < *kpos) return 0 ; - c->kpos = *kpos + 8 ; - if (c->kpos < *kpos) return -1 ; /* wraparound */ - cdb_findstart(c) ; - c->hslots = 1 ; - if (cdb_read(c, buf, 8, *kpos) < 0) return -1 ; - uint32_unpack(buf, &klen) ; - uint32_unpack(buf + 4, &c->dlen) ; - c->dpos = c->kpos + klen ; - *kpos += 8 + klen + c->dlen ; - return 1 ; -} diff --git a/src/libstddjb/cdb_p.c b/src/libstddjb/cdb_p.c new file mode 100644 index 0000000..9e46292 --- /dev/null +++ b/src/libstddjb/cdb_p.c @@ -0,0 +1,9 @@ +/* ISC license. */ + +#include +#include "cdb-internal.h" + +char const *cdb_p (cdb const *c, uint32_t len, uint32_t pos) +{ + return pos <= c->size && len <= c->size - pos ? c->map + pos : 0 ; +} diff --git a/src/libstddjb/cdb_read.c b/src/libstddjb/cdb_read.c deleted file mode 100644 index 1fb15da..0000000 --- a/src/libstddjb/cdb_read.c +++ /dev/null @@ -1,14 +0,0 @@ -/* ISC license. */ - -#include -#include - -#include -#include - -int cdb_read (struct cdb *c, char *buf, unsigned int len, uint32_t pos) -{ - if ((pos > c->size) || (c->size - pos < len)) return (errno = EPROTO, -1) ; - memcpy(buf, c->map + pos, len) ; - return 0 ; -} diff --git a/src/libstddjb/cdb_reader_zero.c b/src/libstddjb/cdb_reader_zero.c new file mode 100644 index 0000000..1dbb275 --- /dev/null +++ b/src/libstddjb/cdb_reader_zero.c @@ -0,0 +1,5 @@ +/* ISC license. */ + +#include + +cdb_reader const cdb_reader_zero = CDB_READER_ZERO ; diff --git a/src/libstddjb/cdb_successor.c b/src/libstddjb/cdb_successor.c deleted file mode 100644 index 51956bf..0000000 --- a/src/libstddjb/cdb_successor.c +++ /dev/null @@ -1,17 +0,0 @@ -/* ISC license. */ - -#include -#include - -int cdb_successor (struct cdb *c, char const *key, unsigned int klen) -{ - uint32_t kpos ; - if (key) - { - int r = cdb_find(c, key, klen) ; - if (r < 1) return r ; - kpos = c->dpos + c->dlen ; - } - else cdb_traverse_init(c, &kpos) ; - return cdb_nextkey(c, &kpos) ; -} diff --git a/src/libstddjb/cdb_traverse_next.c b/src/libstddjb/cdb_traverse_next.c new file mode 100644 index 0000000..887574b --- /dev/null +++ b/src/libstddjb/cdb_traverse_next.c @@ -0,0 +1,25 @@ +/* ISC license. */ + +#include + +#include +#include +#include "cdb-internal.h" + +int cdb_traverse_next (cdb const *c, cdb_data *key, cdb_data *data, uint32_t *pos) +{ + uint32_t eod ; + char const *p = cdb_p(c, 4, 0) ; + if (!p) return -1 ; + uint32_unpack(p, &eod) ; + if (eod < 8 || eod - 8 < *pos) return 0 ; + if (*pos + 8 < *pos) return -1 ; + p = cdb_p(c, 8, *pos) ; + if (!p) return -1 ; + uint32_unpack(p, &key->len) ; + uint32_unpack(p + 4, &data->len) ; + key->s = c->map + *pos + 8 ; + data->s = key->s + key->len ; + *pos += 8 + key->len + data->len ; + return 1 ; +} diff --git a/src/libstddjb/cdb_zero.c b/src/libstddjb/cdb_zero.c index ce70444..164a192 100644 --- a/src/libstddjb/cdb_zero.c +++ b/src/libstddjb/cdb_zero.c @@ -2,4 +2,4 @@ #include -struct cdb const cdb_zero = CDB_ZERO ; +cdb const cdb_zero = CDB_ZERO ; diff --git a/src/libstddjb/cdbmake.c b/src/libstddjb/cdbmake.c new file mode 100644 index 0000000..4cc4fc8 --- /dev/null +++ b/src/libstddjb/cdbmake.c @@ -0,0 +1,121 @@ +/* ISC license. */ + +#include +#include +#include + +#include +#include +#include +#include +#include +#include "cdb-internal.h" + +int cdbmake_start (cdbmaker *c, int fd) +{ + c->hplist = genalloc_zero ; + c->pos = 2048 ; + buffer_init(&c->b, &buffer_write, fd, c->buf, BUFFER_OUTSIZE) ; + return lseek(fd, c->pos, SEEK_SET) >= 0 ; +} + +static int posplus (cdbmaker *c, uint32_t len) +{ + uint32_t newpos = c->pos + len ; + if (newpos < len) return (errno = ENOMEM, 0) ; + c->pos = newpos ; + return 1 ; +} + +static inline int cdbmake_addend (cdbmaker *c, uint32_t keylen, uint32_t datalen, uint32_t h) +{ + diuint32 blah = { .left = h, .right = c->pos } ; + return genalloc_append(diuint32, &c->hplist, &blah) && posplus(c, 8) && posplus(c, keylen) && posplus(c, datalen) ; +} + +static inline ssize_t cdbmake_addbegin (cdbmaker *c, uint32_t keylen, uint32_t datalen) +{ + char buf[8] ; + uint32_pack(buf, keylen) ; + uint32_pack(buf + 4, datalen) ; + return buffer_put(&c->b, buf, 8) == 8 ; +} + +int cdbmake_add (cdbmaker *c, char const *key, uint32_t keylen, char const *data, uint32_t datalen) +{ + if (!cdbmake_addbegin(c, keylen, datalen) + || buffer_put(&c->b, key, keylen) < 0 + || buffer_put(&c->b, data, datalen) < 0 + || !cdbmake_addend(c, keylen, datalen, cdb_hash(key, keylen))) + { + genalloc_free(diuint32, &c->hplist) ; + return 0 ; + } + return 1 ; +} + +int cdbmake_finish (cdbmaker *c) +{ + uint32_t count[256] ; + uint32_t start[256] ; + char final[2048] ; + unsigned int size = 1 ; + unsigned int n = genalloc_len(diuint32, &c->hplist) ; + unsigned int i = 0 ; + diuint32 *hp = genalloc_s(diuint32, &c->hplist) ; + + for (; i < 256 ; i++) count[i] = 0 ; + for (i = 0 ; i < n ; i++) ++count[hp[i].left & 255] ; + + { + uint32_t u = 0 ; + for (i = 0 ; i < 256 ; i++) start[i] = u += count[i] ; /* bounded by n */ + for (i = 0 ; i < 256 ; i++) + { + u = count[i] << 1 ; + if (u > size) size = u ; + } + size += n ; /* no overflow possible up to now */ + u = 0xffffffffUL ; u /= sizeof(diuint32) ; + if (size > u) return (errno = ENOMEM, 0) ; + } + i = n ; + { + diuint32 split[size] ; + while (i--) split[--start[hp[i].left & 255]] = hp[i] ; + genalloc_free(diuint32, &c->hplist) ; + hp = split + n ; + + for (i = 0 ; i < 256 ; ++i) + { + char buf[8] ; + uint32_t k = count[i] ; + uint32_t len = k << 1 ; /* no overflow possible */ + diuint32 *p = split + start[i] ; + + uint32_pack(final + (i << 3), c->pos) ; + uint32_pack(final + (i << 3) + 4, len) ; + + for (uint32_t j = 0 ; j < len ; j++) hp[j].left = hp[j].right = 0 ; + for (uint32_t j = 0 ; j < k ; j++) + { + uint32_t where = (p->left >> 8) % len ; + while (hp[where].right) if (++where == len) where = 0 ; + hp[where] = *p++ ; + } + + for (uint32_t j = 0 ; j < len ; j++) + { + uint32_pack(buf, hp[j].left) ; + uint32_pack(buf + 4, hp[j].right) ; + if (buffer_put(&c->b, buf, 8) < 0) return 0 ; + if (!posplus(c, 8)) return 0 ; + } + } + } + + if (!buffer_flush(&c->b) + || lseek(buffer_fd(&c->b), 0, SEEK_SET) < 0 + || buffer_putflush(&c->b, final, 2048) < 0) return 0 ; + return 1 ; +} -- cgit v1.2.3