--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/cdbmake_add.c	Fri Oct 19 14:06:22 2007 +0200
@@ -0,0 +1,117 @@
+#include "cdbmake.h"
+
+void cdbmake_init(cdbm)
+struct cdbmake *cdbm;
+{
+  cdbm->head = 0;
+  cdbm->split = 0;
+  cdbm->hash = 0;
+  cdbm->numentries = 0;
+}
+
+int cdbmake_add(cdbm,h,p,alloc)
+struct cdbmake *cdbm;
+uint32 h;
+uint32 p;
+char *(*alloc)();
+{
+  struct cdbmake_hplist *head;
+
+  head = cdbm->head;
+  if (!head || (head->num >= CDBMAKE_HPLIST)) {
+    head = (struct cdbmake_hplist *) alloc(sizeof(struct cdbmake_hplist));
+    if (!head) return 0;
+    head->num = 0;
+    head->next = cdbm->head;
+    cdbm->head = head;
+  }
+  head->hp[head->num].h = h;
+  head->hp[head->num].p = p;
+  ++head->num;
+  ++cdbm->numentries;
+  return 1;
+}
+
+int cdbmake_split(cdbm,alloc)
+struct cdbmake *cdbm;
+char *(*alloc)();
+{
+  int i;
+  uint32 u;
+  uint32 memsize;
+  struct cdbmake_hplist *x;
+
+  for (i = 0;i < 256;++i)
+    cdbm->count[i] = 0;
+
+  for (x = cdbm->head;x;x = x->next) {
+    i = x->num;
+    while (i--)
+      ++cdbm->count[255 & x->hp[i].h];
+  }
+
+  memsize = 1;
+  for (i = 0;i < 256;++i) {
+    u = cdbm->count[i] * 2;
+    if (u > memsize)
+      memsize = u;
+  }
+
+  memsize += cdbm->numentries; /* no overflow possible up to now */
+  u = (uint32) 0 - (uint32) 1;
+  u /= sizeof(struct cdbmake_hp);
+  if (memsize > u) return 0;
+
+  cdbm->split = (struct cdbmake_hp *) alloc(memsize * sizeof(struct cdbmake_hp));
+  if (!cdbm->split) return 0;
+
+  cdbm->hash = cdbm->split + cdbm->numentries;
+
+  u = 0;
+  for (i = 0;i < 256;++i) {
+    u += cdbm->count[i]; /* bounded by numentries, so no overflow */
+    cdbm->start[i] = u;
+  }
+
+  for (x = cdbm->head;x;x = x->next) {
+    i = x->num;
+    while (i--)
+      cdbm->split[--cdbm->start[255 & x->hp[i].h]] = x->hp[i];
+  }
+
+  return 1;
+}
+
+uint32 cdbmake_throw(cdbm,pos,b)
+struct cdbmake *cdbm;
+uint32 pos;
+int b;
+{
+  uint32 len;
+  uint32 j;
+  uint32 count;
+  struct cdbmake_hp *hp;
+  uint32 where;
+
+  count = cdbm->count[b];
+
+  len = count + count; /* no overflow possible */
+  cdbmake_pack(cdbm->final + 8 * b,pos);
+  cdbmake_pack(cdbm->final + 8 * b + 4,len);
+
+  if (len) {
+    for (j = 0;j < len;++j)
+      cdbm->hash[j].h = cdbm->hash[j].p = 0;
+
+    hp = cdbm->split + cdbm->start[b];
+    for (j = 0;j < count;++j) {
+      where = (hp->h >> 8) % len;
+      while (cdbm->hash[where].p)
+	if (++where == len)
+	  where = 0;
+      cdbm->hash[where] = *hp++;
+    }
+  }
+
+  return len;
+}