src/analysisd/cdb/cdb_make.c

   1 /* Public domain. */
   2 /* Adapted from DJB's original cdb-0.75 package */
   3
   4 #include <sys/types.h>
   5 #include <unistd.h>
   6 #include <stdlib.h>
   7 #include <stdio.h>
   8 #include <errno.h>
   9 #include "cdb.h"
  10 #include "cdb_make.h"
  11 #include "uint32.h"
  12
  13 static int cdb_make_write(struct cdb_make *c, char *buf, uint32 sz) {
  14   fwrite(buf, sz, 1, c->fp);
  15   return ferror(c->fp);
  16 }
  17
  18 int cdb_make_start(struct cdb_make *c, FILE * f)
  19 {
  20   c->head = 0;
  21   c->split = 0;
  22   c->hash = 0;
  23   c->numentries = 0;
  24   c->fp = f;
  25   c->pos = sizeof c->final;
  26   if (fseek(f,c->pos,SEEK_SET) == -1) {
  27     perror("fseek failed");
  28     return -1;
  29   }
  30   return ftell(c->fp);
  31 }
  32
  33 static int posplus(struct cdb_make *c,uint32 len)
  34 {
  35   uint32 newpos = c->pos + len;
  36   if (newpos < len) { errno = ENOMEM; return -1; }
  37   c->pos = newpos;
  38   return 0;
  39 }
  40
  41 int cdb_make_addend(struct cdb_make *c,unsigned int keylen,unsigned int datalen,uint32 h)
  42 {
  43   struct cdb_hplist *head;
  44
  45   head = c->head;
  46   if (!head || (head->num >= CDB_HPLIST)) {
  47     head = (struct cdb_hplist *) malloc(sizeof(struct cdb_hplist));
  48     if (!head) return -1;
  49     head->num = 0;
  50     head->next = c->head;
  51     c->head = head;
  52   }
  53   head->hp[head->num].h = h;
  54   head->hp[head->num].p = c->pos;
  55   ++head->num;
  56   ++c->numentries;
  57   if (posplus(c,8) == -1) return -1;
  58   if (posplus(c,keylen) == -1) return -1;
  59   if (posplus(c,datalen) == -1) return -1;
  60   return 0;
  61 }
  62
  63 int cdb_make_addbegin(struct cdb_make *c,unsigned int keylen,unsigned int datalen)
  64 {
  65   char buf[8];
  66
  67   if (keylen > 0xffffffff) { errno = ENOMEM; return -1; }
  68   if (datalen > 0xffffffff) { errno = ENOMEM; return -1; }
  69
  70   uint32_pack(buf,keylen);
  71   uint32_pack(buf + 4,datalen);
  72   if (cdb_make_write(c,buf,8) != 0) return -1;
  73   /* if (buffer_putalign(&c->b,buf,8) == -1) return -1; */
  74   return 0;
  75 }
  76
  77 int cdb_make_add(struct cdb_make *c,char *key,unsigned int keylen,char *data,unsigned int datalen)
  78 {
  79   if (cdb_make_addbegin(c,keylen,datalen) == -1) return -1;
  80   if (cdb_make_write(c,key,keylen) != 0) return -1;
  81   if (cdb_make_write(c,data,datalen) != 0) return -1;
  82   /* if (buffer_putalign(&c->b,key,keylen) == -1) return -1; */
  83   /* if (buffer_putalign(&c->b,data,datalen) == -1) return -1; */
  84   return cdb_make_addend(c,keylen,datalen,cdb_hash(key,keylen));
  85 }
  86
  87 int cdb_make_finish(struct cdb_make *c)
  88 {
  89   char buf[8];
  90   int i;
  91   uint32 len;
  92   uint32 u;
  93   uint32 memsize;
  94   uint32 count;
  95   uint32 where;
  96   struct cdb_hplist *x;
  97   struct cdb_hp *hp;
  98
  99   for (i = 0;i < 256;++i)
 100     c->count[i] = 0;
 101
 102   for (x = c->head;x;x = x->next) {
 103     i = x->num;
 104     while (i--)
 105       ++c->count[255 & x->hp[i].h];
 106   }
 107
 108   memsize = 1;
 109   for (i = 0;i < 256;++i) {
 110     u = c->count[i] * 2;
 111     if (u > memsize)
 112       memsize = u;
 113   }
 114
 115   memsize += c->numentries; /* no overflow possible up to now */
 116   u = (uint32) 0 - (uint32) 1;
 117   u /= sizeof(struct cdb_hp);
 118   if (memsize > u) { errno = ENOMEM; return -1; }
 119
 120   c->split = (struct cdb_hp *) malloc(memsize * sizeof(struct cdb_hp));
 121   if (!c->split) return -1;
 122
 123   c->hash = c->split + c->numentries;
 124
 125   u = 0;
 126   for (i = 0;i < 256;++i) {
 127     u += c->count[i]; /* bounded by numentries, so no overflow */
 128     c->start[i] = u;
 129   }
 130
 131   for (x = c->head;x;x = x->next) {
 132     i = x->num;
 133     while (i--)
 134       c->split[--c->start[255 & x->hp[i].h]] = x->hp[i];
 135   }
 136
 137   for (i = 0;i < 256;++i) {
 138     count = c->count[i];
 139
 140     len = count + count; /* no overflow possible */
 141     uint32_pack(c->final + 8 * i,c->pos);
 142     uint32_pack(c->final + 8 * i + 4,len);
 143
 144     for (u = 0;u < len;++u)
 145       c->hash[u].h = c->hash[u].p = 0;
 146
 147     hp = c->split + c->start[i];
 148     for (u = 0;u < count;++u) {
 149       where = (hp->h >> 8) % len;
 150       while (c->hash[where].p)
 151         if (++where == len)
 152           where = 0;
 153       c->hash[where] = *hp++;
 154     }
 155
 156     for (u = 0;u < len;++u) {
 157       uint32_pack(buf,c->hash[u].h);
 158       uint32_pack(buf + 4,c->hash[u].p);
 159       if (cdb_make_write(c,buf,8) != 0) return -1;
 160       /* if (buffer_putalign(&c->b,buf,8) == -1) return -1; */
 161       if (posplus(c,8) == -1) return -1;
 162     }
 163   }
 164
 165   if (c->split) free(c->split);
 166
 167   for (x = c->head;x;c->head = x) {
 168     x = x->next;
 169     free(c->head);
 170   }
 171
 172   if (fflush(c->fp) != 0) return -1;
 173   /* if (buffer_flush(&c->b) == -1) return -1; */
 174   rewind(c->fp);
 175   if (ftell(c->fp) != 0) return -1;
 176   /* if (seek_begin(c->fd) == -1) return -1; */
 177   if (cdb_make_write(c,c->final,sizeof c->final) != 0) return -1;
 178   return fflush(c->fp);
 179   /* return buffer_putflush(&c->b,c->final,sizeof c->final); */
 180 }