1 /* Public domain. */

     2 

     3 #include "readwrite.h"

     4 #include "seek.h"

     5 #include "error.h"

     6 #include "alloc.h"

     7 #include "cdb.h"

     8 #include "cdb_make.h"

     9 

    10 int cdb_make_start(struct cdb_make *c,int fd)

    11 {

    12   c->head = 0;

    13   c->split = 0;

    14   c->hash = 0;

    15   c->numentries = 0;

    16   c->fd = fd;

    17   c->pos = sizeof c->final;

    18   buffer_init(&c->b,write,fd,c->bspace,sizeof c->bspace);

    19   return seek_set(fd,c->pos);

    20 }

    21 

    22 static int posplus(struct cdb_make *c,uint32 len)

    23 {

    24   uint32 newpos = c->pos + len;

    25   if (newpos < len) { errno = error_nomem; return -1; }

    26   c->pos = newpos;

    27   return 0;

    28 }

    29 

    30 int cdb_make_addend(struct cdb_make *c,unsigned int keylen,unsigned int datalen,uint32 h)

    31 {

    32   struct cdb_hplist *head;

    33 

    34   head = c->head;

    35   if (!head || (head->num >= CDB_HPLIST)) {

    36     head = (struct cdb_hplist *) alloc(sizeof(struct cdb_hplist));

    37     if (!head) return -1;

    38     head->num = 0;

    39     head->next = c->head;

    40     c->head = head;

    41   }

    42   head->hp[head->num].h = h;

    43   head->hp[head->num].p = c->pos;

    44   ++head->num;

    45   ++c->numentries;

    46   if (posplus(c,8) == -1) return -1;

    47   if (posplus(c,keylen) == -1) return -1;

    48   if (posplus(c,datalen) == -1) return -1;

    49   return 0;

    50 }

    51 

    52 int cdb_make_addbegin(struct cdb_make *c,unsigned int keylen,unsigned int datalen)

    53 {

    54   char buf[8];

    55 

    56   if (keylen > 0xffffffff) { errno = error_nomem; return -1; }

    57   if (datalen > 0xffffffff) { errno = error_nomem; return -1; }

    58 

    59   uint32_pack(buf,keylen);

    60   uint32_pack(buf + 4,datalen);

    61   if (buffer_putalign(&c->b,buf,8) == -1) return -1;

    62   return 0;

    63 }

    64 

    65 int cdb_make_add(struct cdb_make *c,char *key,unsigned int keylen,char *data,unsigned int datalen)

    66 {

    67   if (cdb_make_addbegin(c,keylen,datalen) == -1) return -1;

    68   if (buffer_putalign(&c->b,key,keylen) == -1) return -1;

    69   if (buffer_putalign(&c->b,data,datalen) == -1) return -1;

    70   return cdb_make_addend(c,keylen,datalen,cdb_hash(key,keylen));

    71 }

    72 

    73 int cdb_make_finish(struct cdb_make *c)

    74 {

    75   char buf[8];

    76   int i;

    77   uint32 len;

    78   uint32 u;

    79   uint32 memsize;

    80   uint32 count;

    81   uint32 where;

    82   struct cdb_hplist *x;

    83   struct cdb_hp *hp;

    84 

    85   for (i = 0;i < 256;++i)

    86     c->count[i] = 0;

    87 

    88   for (x = c->head;x;x = x->next) {

    89     i = x->num;

    90     while (i--)

    91       ++c->count[255 & x->hp[i].h];

    92   }

    93 

    94   memsize = 1;

    95   for (i = 0;i < 256;++i) {

    96     u = c->count[i] * 2;

    97     if (u > memsize)

    98       memsize = u;

    99   }

   100 

   101   memsize += c->numentries; /* no overflow possible up to now */

   102   u = (uint32) 0 - (uint32) 1;

   103   u /= sizeof(struct cdb_hp);

   104   if (memsize > u) { errno = error_nomem; return -1; }

   105 

   106   c->split = (struct cdb_hp *) alloc(memsize * sizeof(struct cdb_hp));

   107   if (!c->split) return -1;

   108 

   109   c->hash = c->split + c->numentries;

   110 

   111   u = 0;

   112   for (i = 0;i < 256;++i) {

   113     u += c->count[i]; /* bounded by numentries, so no overflow */

   114     c->start[i] = u;

   115   }

   116 

   117   for (x = c->head;x;x = x->next) {

   118     i = x->num;

   119     while (i--)

   120       c->split[--c->start[255 & x->hp[i].h]] = x->hp[i];

   121   }

   122 

   123   for (i = 0;i < 256;++i) {

   124     count = c->count[i];

   125 

   126     len = count + count; /* no overflow possible */

   127     uint32_pack(c->final + 8 * i,c->pos);

   128     uint32_pack(c->final + 8 * i + 4,len);

   129 

   130     for (u = 0;u < len;++u)

   131       c->hash[u].h = c->hash[u].p = 0;

   132 

   133     hp = c->split + c->start[i];

   134     for (u = 0;u < count;++u) {

   135       where = (hp->h >> 8) % len;

   136       while (c->hash[where].p)

   137 	if (++where == len)

   138 	  where = 0;

   139       c->hash[where] = *hp++;

   140     }

   141 

   142     for (u = 0;u < len;++u) {

   143       uint32_pack(buf,c->hash[u].h);

   144       uint32_pack(buf + 4,c->hash[u].p);

   145       if (buffer_putalign(&c->b,buf,8) == -1) return -1;

   146       if (posplus(c,8) == -1) return -1;

   147     }

   148   }

   149 

   150   if (buffer_flush(&c->b) == -1) return -1;

   151   if (seek_begin(c->fd) == -1) return -1;

   152   return buffer_putflush(&c->b,c->final,sizeof c->final);

   153 }