summaryrefslogtreecommitdiff
path: root/cdbmake_add.c
diff options
context:
space:
mode:
authorJohn Denker <jsd@av8n.com>2012-06-02 01:58:45 (GMT)
committerJohn Denker <jsd@av8n.com>2012-06-02 01:58:45 (GMT)
commitb732a73bc773789894466b0e5320b2f1fe42c7e9 (patch)
tree385358983f064a1f10a5080b33a3ba13010886db /cdbmake_add.c
parent634d365a03cb0581a062cd3cf4db9ae69f1cde26 (diff)
original, as downloaded from http://www.qmail.org/netqmail-1.06.tar.gz
Diffstat (limited to 'cdbmake_add.c')
-rw-r--r--cdbmake_add.c118
1 files changed, 118 insertions, 0 deletions
diff --git a/cdbmake_add.c b/cdbmake_add.c
new file mode 100644
index 0000000..83a03ff
--- /dev/null
+++ b/cdbmake_add.c
@@ -0,0 +1,118 @@
+#include "alloc.h"
+#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;
+}