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 }