From 0beff2477b55728603127f21a9df604b6fcf840c Mon Sep 17 00:00:00 2001 From: Laurent Bercot Date: Mon, 3 Jul 2023 11:10:09 +0000 Subject: Refactor cdbmake, add cdbmake_addv, cdb_hashv Signed-off-by: Laurent Bercot --- src/libstddjb/cdb-internal.h | 5 ++ src/libstddjb/cdb_hash.c | 8 --- src/libstddjb/cdb_hashadd.c | 9 +++ src/libstddjb/cdb_hashv.c | 14 +++++ src/libstddjb/cdbmake-internal.h | 14 +++++ src/libstddjb/cdbmake.c | 121 ------------------------------------ src/libstddjb/cdbmake_add.c | 22 +++++++ src/libstddjb/cdbmake_addbeginend.c | 24 +++++++ src/libstddjb/cdbmake_addv.c | 30 +++++++++ src/libstddjb/cdbmake_finish.c | 78 +++++++++++++++++++++++ src/libstddjb/cdbmake_posplus.c | 14 +++++ src/libstddjb/cdbmake_start.c | 15 +++++ 12 files changed, 225 insertions(+), 129 deletions(-) create mode 100644 src/libstddjb/cdb_hashadd.c create mode 100644 src/libstddjb/cdb_hashv.c create mode 100644 src/libstddjb/cdbmake-internal.h delete mode 100644 src/libstddjb/cdbmake.c create mode 100644 src/libstddjb/cdbmake_add.c create mode 100644 src/libstddjb/cdbmake_addbeginend.c create mode 100644 src/libstddjb/cdbmake_addv.c create mode 100644 src/libstddjb/cdbmake_finish.c create mode 100644 src/libstddjb/cdbmake_posplus.c create mode 100644 src/libstddjb/cdbmake_start.c (limited to 'src/libstddjb') diff --git a/src/libstddjb/cdb-internal.h b/src/libstddjb/cdb-internal.h index 0db5a5d..d2b7324 100644 --- a/src/libstddjb/cdb-internal.h +++ b/src/libstddjb/cdb-internal.h @@ -4,11 +4,16 @@ #define SKALIBS_CDB_INTERNAL_H #include +#include #include #include +#define CDB_HASHSTART 5381 + +extern uint32_t cdb_hashadd (uint32_t, uint8_t) ; extern uint32_t cdb_hash (char const *, uint32_t) gccattr_pure ; +extern uint32_t cdb_hashv (struct iovec const *, unsigned int) gccattr_pure ; extern char const *cdb_p (cdb const *, uint32_t, uint32_t) gccattr_pure ; #endif diff --git a/src/libstddjb/cdb_hash.c b/src/libstddjb/cdb_hash.c index a7b626b..3849f02 100644 --- a/src/libstddjb/cdb_hash.c +++ b/src/libstddjb/cdb_hash.c @@ -4,14 +4,6 @@ #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, uint32_t len) { uint32_t h = CDB_HASHSTART ; diff --git a/src/libstddjb/cdb_hashadd.c b/src/libstddjb/cdb_hashadd.c new file mode 100644 index 0000000..426fb95 --- /dev/null +++ b/src/libstddjb/cdb_hashadd.c @@ -0,0 +1,9 @@ +/* ISC license. */ + +#include "cdb-internal.h" + +uint32_t cdb_hashadd (uint32_t h, uint8_t c) +{ + h += (h << 5) ; + return h ^ c ; +} diff --git a/src/libstddjb/cdb_hashv.c b/src/libstddjb/cdb_hashv.c new file mode 100644 index 0000000..e2b80d9 --- /dev/null +++ b/src/libstddjb/cdb_hashv.c @@ -0,0 +1,14 @@ +/* ISC license. */ + +#include + +#include "cdb-internal.h" + +uint32_t cdb_hashv (struct iovec const *v, unsigned int n) +{ + uint32_t h = CDB_HASHSTART ; + for (unsigned int i = 0 ; i < n ; i++) + for (size_t j = 0 ; j < v[i].iov_len ; j++) + h = cdb_hashadd(h, ((uint8_t const *)v[i].iov_base)[j]) ; + return h ; +} diff --git a/src/libstddjb/cdbmake-internal.h b/src/libstddjb/cdbmake-internal.h new file mode 100644 index 0000000..1d5bd24 --- /dev/null +++ b/src/libstddjb/cdbmake-internal.h @@ -0,0 +1,14 @@ +/* ISC license. */ + +#ifndef SKALIBS_CDBMAKE_INTERNAL_H +#define SKALIBS_CDBMAKE_INTERNAL_H + +#include + +#include + +extern int cdbmake_posplus (cdbmaker *, uint32_t) ; +extern int cdbmake_addend (cdbmaker *, uint32_t, uint32_t, uint32_t) ; +extern int cdbmake_addbegin (cdbmaker *, uint32_t, uint32_t) ; + +#endif diff --git a/src/libstddjb/cdbmake.c b/src/libstddjb/cdbmake.c deleted file mode 100644 index 4cc4fc8..0000000 --- a/src/libstddjb/cdbmake.c +++ /dev/null @@ -1,121 +0,0 @@ -/* 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 ; -} diff --git a/src/libstddjb/cdbmake_add.c b/src/libstddjb/cdbmake_add.c new file mode 100644 index 0000000..f7fd096 --- /dev/null +++ b/src/libstddjb/cdbmake_add.c @@ -0,0 +1,22 @@ +/* ISC license. */ + +#include +#include +#include +#include +#include +#include "cdb-internal.h" +#include "cdbmake-internal.h" + +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) < keylen + || buffer_put(&c->b, data, datalen) < datalen + || !cdbmake_addend(c, keylen, datalen, cdb_hash(key, keylen))) + { + genalloc_free(diuint32, &c->hplist) ; + return 0 ; + } + return 1 ; +} diff --git a/src/libstddjb/cdbmake_addbeginend.c b/src/libstddjb/cdbmake_addbeginend.c new file mode 100644 index 0000000..37d35c8 --- /dev/null +++ b/src/libstddjb/cdbmake_addbeginend.c @@ -0,0 +1,24 @@ +/* ISC license. */ + +#include +#include + +#include +#include +#include +#include +#include "cdbmake-internal.h" + +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) && cdbmake_posplus(c, 8) && cdbmake_posplus(c, keylen) && cdbmake_posplus(c, datalen) ; +} + +int 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 ; +} diff --git a/src/libstddjb/cdbmake_addv.c b/src/libstddjb/cdbmake_addv.c new file mode 100644 index 0000000..d8719a4 --- /dev/null +++ b/src/libstddjb/cdbmake_addv.c @@ -0,0 +1,30 @@ +/* ISC license. */ + +#include +#include + +#include +#include +#include +#include +#include +#include +#include "cdb-internal.h" +#include "cdbmake-internal.h" + +int cdbmake_addv (cdbmaker *c, struct iovec const *kv, unsigned int kn, struct iovec const *dv, unsigned int dn) +{ + size_t keylen = siovec_len(kv, kn) ; + size_t datalen = siovec_len(dv, dn) ; + if (keylen > UINT32_MAX || datalen > UINT32_MAX) return (errno = EOVERFLOW, 0) ; + + if (!cdbmake_addbegin(c, keylen, datalen) + || buffer_putv(&c->b, kv, kn) < keylen + || buffer_putv(&c->b, dv, dn) < datalen + || !cdbmake_addend(c, keylen, datalen, cdb_hashv(kv, kn))) + { + genalloc_free(diuint32, &c->hplist) ; + return 0 ; + } + return 1 ; +} diff --git a/src/libstddjb/cdbmake_finish.c b/src/libstddjb/cdbmake_finish.c new file mode 100644 index 0000000..fe0b35a --- /dev/null +++ b/src/libstddjb/cdbmake_finish.c @@ -0,0 +1,78 @@ +/* ISC license. */ + +#include +#include +#include + +#include +#include +#include +#include +#include +#include "cdbmake-internal.h" + +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 (!cdbmake_posplus(c, 8)) return 0 ; + } + } + } + + if (!buffer_flush(&c->b) + || lseek(buffer_fd(&c->b), 0, SEEK_SET) == -1 + || buffer_putflush(&c->b, final, 2048) < 2048) return 0 ; + return 1 ; +} diff --git a/src/libstddjb/cdbmake_posplus.c b/src/libstddjb/cdbmake_posplus.c new file mode 100644 index 0000000..a2f4468 --- /dev/null +++ b/src/libstddjb/cdbmake_posplus.c @@ -0,0 +1,14 @@ +/* ISC license. */ + +#include +#include + +#include "cdbmake-internal.h" + +int cdbmake_posplus (cdbmaker *c, uint32_t len) +{ + uint32_t newpos = c->pos + len ; + if (newpos < len) return (errno = ENOMEM, 0) ; + c->pos = newpos ; + return 1 ; +} diff --git a/src/libstddjb/cdbmake_start.c b/src/libstddjb/cdbmake_start.c new file mode 100644 index 0000000..94f1635 --- /dev/null +++ b/src/libstddjb/cdbmake_start.c @@ -0,0 +1,15 @@ +/* ISC license. */ + +#include + +#include +#include +#include + +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 ; +} -- cgit v1.2.3