nightmaremail

Unnamed repository; edit this file 'description' to name the repository.
Log | Files | Refs

cdbmake_add.c (2267B)

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