chiark - git - mdw - qmail/blob - cdbmake_add.c

   1 #include "cdbmake.h"
   2
   3 void cdbmake_init(cdbm)
   4 struct cdbmake *cdbm;
   5 {
   6   cdbm->head = 0;
   7   cdbm->split = 0;
   8   cdbm->hash = 0;
   9   cdbm->numentries = 0;
  10 }
  11
  12 int cdbmake_add(cdbm,h,p,alloc)
  13 struct cdbmake *cdbm;
  14 uint32 h;
  15 uint32 p;
  16 char *(*alloc)();
  17 {
  18   struct cdbmake_hplist *head;
  19
  20   head = cdbm->head;
  21   if (!head || (head->num >= CDBMAKE_HPLIST)) {
  22     head = (struct cdbmake_hplist *) alloc(sizeof(struct cdbmake_hplist));
  23     if (!head) return 0;
  24     head->num = 0;
  25     head->next = cdbm->head;
  26     cdbm->head = head;
  27   }
  28   head->hp[head->num].h = h;
  29   head->hp[head->num].p = p;
  30   ++head->num;
  31   ++cdbm->numentries;
  32   return 1;
  33 }
  34
  35 int cdbmake_split(cdbm,alloc)
  36 struct cdbmake *cdbm;
  37 char *(*alloc)();
  38 {
  39   int i;
  40   uint32 u;
  41   uint32 memsize;
  42   struct cdbmake_hplist *x;
  43
  44   for (i = 0;i < 256;++i)
  45     cdbm->count[i] = 0;
  46
  47   for (x = cdbm->head;x;x = x->next) {
  48     i = x->num;
  49     while (i--)
  50       ++cdbm->count[255 & x->hp[i].h];
  51   }
  52
  53   memsize = 1;
  54   for (i = 0;i < 256;++i) {
  55     u = cdbm->count[i] * 2;
  56     if (u > memsize)
  57       memsize = u;
  58   }
  59
  60   memsize += cdbm->numentries; /* no overflow possible up to now */
  61   u = (uint32) 0 - (uint32) 1;
  62   u /= sizeof(struct cdbmake_hp);
  63   if (memsize > u) return 0;
  64
  65   cdbm->split = (struct cdbmake_hp *) alloc(memsize * sizeof(struct cdbmake_hp));
  66   if (!cdbm->split) return 0;
  67
  68   cdbm->hash = cdbm->split + cdbm->numentries;
  69
  70   u = 0;
  71   for (i = 0;i < 256;++i) {
  72     u += cdbm->count[i]; /* bounded by numentries, so no overflow */
  73     cdbm->start[i] = u;
  74   }
  75
  76   for (x = cdbm->head;x;x = x->next) {
  77     i = x->num;
  78     while (i--)
  79       cdbm->split[--cdbm->start[255 & x->hp[i].h]] = x->hp[i];
  80   }
  81
  82   return 1;
  83 }
  84
  85 uint32 cdbmake_throw(cdbm,pos,b)
  86 struct cdbmake *cdbm;
  87 uint32 pos;
  88 int b;
  89 {
  90   uint32 len;
  91   uint32 j;
  92   uint32 count;
  93   struct cdbmake_hp *hp;
  94   uint32 where;
  95
  96   count = cdbm->count[b];
  97
  98   len = count + count; /* no overflow possible */
  99   cdbmake_pack(cdbm->final + 8 * b,pos);
 100   cdbmake_pack(cdbm->final + 8 * b + 4,len);
 101
 102   if (len) {
 103     for (j = 0;j < len;++j)
 104       cdbm->hash[j].h = cdbm->hash[j].p = 0;
 105
 106     hp = cdbm->split + cdbm->start[b];
 107     for (j = 0;j < count;++j) {
 108       where = (hp->h >> 8) % len;
 109       while (cdbm->hash[where].p)
 110         if (++where == len)
 111           where = 0;
 112       cdbm->hash[where] = *hp++;
 113     }
 114   }
 115
 116   return len;
 117 }