From dd6bb6c6b8298ebeff2d1882becb36580b969d6f Mon Sep 17 00:00:00 2001
From: Laurent Bercot <ska-skaware@skarnet.org>
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 <ska@appnovation.com>
---
 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 +++++++++++++++++++++++++++++++++++++
 16 files changed, 258 insertions(+), 280 deletions(-)
 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/libstddjb')

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 <stdint.h>
+
+#include <skalibs/gccattributes.h>
+#include <skalibs/cdb.h>
+
+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 <stdint.h>
+#include <string.h>
+
+#include <skalibs/uint32.h>
+#include <skalibs/cdb.h>
+#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 <stdint.h>
-#include <string.h>
-#include <skalibs/uint32.h>
-#include <skalibs/cdb.h>
-
-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 <sys/mman.h>
-#include <errno.h>
-
+#include <skalibs/posixplz.h>
 #include <skalibs/cdb.h>
 
-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 <skalibs/cdb.h>
+#include <stdint.h>
 
-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 <skalibs/bsdsnowflake.h>
-
 #include <sys/stat.h>
 #include <sys/mman.h>
 #include <stdint.h>
 #include <errno.h>
 
+#include <skalibs/djbunix.h>
 #include <skalibs/cdb.h>
 
-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 <unistd.h>
-#include <stdint.h>
-#include <errno.h>
-#include <skalibs/uint32.h>
-#include <skalibs/diuint32.h>
-#include <skalibs/buffer.h>
-#include <skalibs/genalloc.h>
-#include <skalibs/cdb.h>
-#include <skalibs/cdb_make.h>
-
-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 <skalibs/djbunix.h>
-#include <skalibs/cdb.h>
-
-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 <skalibs/uint32.h>
-#include <skalibs/cdb.h>
-
-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 <skalibs/cdb.h>
+#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 <string.h>
-#include <errno.h>
-
-#include <skalibs/cdb.h>
-#include <skalibs/posixishard.h>
-
-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 <skalibs/cdb.h>
+
+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 <stdint.h>
-#include <skalibs/cdb.h>
-
-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 <stdint.h>
+
+#include <skalibs/uint32.h>
+#include <skalibs/cdb.h>
+#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 <skalibs/cdb.h>
 
-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 <unistd.h>
+#include <stdint.h>
+#include <errno.h>
+
+#include <skalibs/uint32.h>
+#include <skalibs/diuint32.h>
+#include <skalibs/buffer.h>
+#include <skalibs/genalloc.h>
+#include <skalibs/cdbmake.h>
+#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