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
  14 static int cdb_make_write(struct cdb_make *c, char *buf, uint32 sz)
  15 {
  16     fwrite(buf, sz, 1, c->fp);
  17     return ferror(c->fp);
  18 }
  19
  20 int cdb_make_start(struct cdb_make *c, FILE *f)
  21 {
  22     c->head = 0;
  23     c->split = 0;
  24     c->hash = 0;
  25     c->numentries = 0;
  26     c->fp = f;
  27     c->pos = sizeof c->final;
  28     if (fseek(f, c->pos, SEEK_SET) == -1) {
  29         perror("fseek failed");
  30         return -1;
  31     }
  32     return ftell(c->fp);
  33 }
  34
  35 static int posplus(struct cdb_make *c, uint32 len)
  36 {
  37     uint32 newpos = c->pos + len;
  38     if (newpos < len) {
  39         errno = ENOMEM;
  40         return -1;
  41     }
  42     c->pos = newpos;
  43     return 0;
  44 }
  45
  46 int cdb_make_addend(struct cdb_make *c, unsigned int keylen, unsigned int datalen, uint32 h)
  47 {
  48     struct cdb_hplist *head;
  49
  50     head = c->head;
  51     if (!head || (head->num >= CDB_HPLIST)) {
  52         head = (struct cdb_hplist *) malloc(sizeof(struct cdb_hplist));
  53         if (!head) {
  54             return -1;
  55         }
  56         head->num = 0;
  57         head->next = c->head;
  58         c->head = head;
  59     }
  60     head->hp[head->num].h = h;
  61     head->hp[head->num].p = c->pos;
  62     ++head->num;
  63     ++c->numentries;
  64     if (posplus(c, 8) == -1) {
  65         return -1;
  66     }
  67     if (posplus(c, keylen) == -1) {
  68         return -1;
  69     }
  70     if (posplus(c, datalen) == -1) {
  71         return -1;
  72     }
  73     return 0;
  74 }
  75
  76 int cdb_make_addbegin(struct cdb_make *c, unsigned int keylen, unsigned int datalen)
  77 {
  78     char buf[8];
  79
  80     /*if (keylen > 0xffffffff) {
  81         errno = ENOMEM;
  82         return -1;
  83     }
  84     if (datalen > 0xffffffff) {
  85         errno = ENOMEM;
  86         return -1;
  87     }*/
  88
  89     uint32_pack(buf, keylen);
  90     uint32_pack(buf + 4, datalen);
  91     if (cdb_make_write(c, buf, 8) != 0) {
  92         return -1;
  93     }
  94     /* if (buffer_putalign(&c->b,buf,8) == -1) return -1; */
  95     return 0;
  96 }
  97
  98 int cdb_make_add(struct cdb_make *c, char *key, unsigned int keylen, char *data, unsigned int datalen)
  99 {
 100     if (cdb_make_addbegin(c, keylen, datalen) == -1) {
 101         return -1;
 102     }
 103     if (cdb_make_write(c, key, keylen) != 0) {
 104         return -1;
 105     }
 106     if (cdb_make_write(c, data, datalen) != 0) {
 107         return -1;
 108     }
 109     /* if (buffer_putalign(&c->b,key,keylen) == -1) return -1; */
 110     /* if (buffer_putalign(&c->b,data,datalen) == -1) return -1; */
 111     return cdb_make_addend(c, keylen, datalen, cdb_hash(key, keylen));
 112 }
 113
 114 int cdb_make_finish(struct cdb_make *c)
 115 {
 116     char buf[8];
 117     int i;
 118     uint32 len;
 119     uint32 u;
 120     uint32 memsize;
 121     uint32 count;
 122     uint32 where;
 123     struct cdb_hplist *x;
 124     struct cdb_hp *hp;
 125
 126     for (i = 0; i < 256; ++i) {
 127         c->count[i] = 0;
 128     }
 129
 130     for (x = c->head; x; x = x->next) {
 131         i = x->num;
 132         while (i--) {
 133             ++c->count[255 & x->hp[i].h];
 134         }
 135     }
 136
 137     memsize = 1;
 138     for (i = 0; i < 256; ++i) {
 139         u = c->count[i] * 2;
 140         if (u > memsize) {
 141             memsize = u;
 142         }
 143     }
 144
 145     memsize += c->numentries; /* no overflow possible up to now */
 146     u = (uint32) 0 - (uint32) 1;
 147     u /= sizeof(struct cdb_hp);
 148     if (memsize > u) {
 149         errno = ENOMEM;
 150         return -1;
 151     }
 152
 153     c->split = (struct cdb_hp *) malloc(memsize * sizeof(struct cdb_hp));
 154     if (!c->split) {
 155         return -1;
 156     }
 157
 158     c->hash = c->split + c->numentries;
 159
 160     u = 0;
 161     for (i = 0; i < 256; ++i) {
 162         u += c->count[i]; /* bounded by numentries, so no overflow */
 163         c->start[i] = u;
 164     }
 165
 166     for (x = c->head; x; x = x->next) {
 167         i = x->num;
 168         while (i--) {
 169             c->split[--c->start[255 & x->hp[i].h]] = x->hp[i];
 170         }
 171     }
 172
 173     for (i = 0; i < 256; ++i) {
 174         count = c->count[i];
 175
 176         len = count + count; /* no overflow possible */
 177         uint32_pack(c->final + 8 * i, c->pos);
 178         uint32_pack(c->final + 8 * i + 4, len);
 179
 180         for (u = 0; u < len; ++u) {
 181             c->hash[u].h = c->hash[u].p = 0;
 182         }
 183
 184         hp = c->split + c->start[i];
 185         for (u = 0; u < count; ++u) {
 186             where = (hp->h >> 8) % len;
 187             while (c->hash[where].p)
 188                 if (++where == len) {
 189                     where = 0;
 190                 }
 191             c->hash[where] = *hp++;
 192         }
 193
 194         for (u = 0; u < len; ++u) {
 195             uint32_pack(buf, c->hash[u].h);
 196             uint32_pack(buf + 4, c->hash[u].p);
 197             if (cdb_make_write(c, buf, 8) != 0) {
 198                 return -1;
 199             }
 200             /* if (buffer_putalign(&c->b,buf,8) == -1) return -1; */
 201             if (posplus(c, 8) == -1) {
 202                 return -1;
 203             }
 204         }
 205     }
 206
 207     if (c->split) {
 208         free(c->split);
 209     }
 210
 211     for (x = c->head; x; c->head = x) {
 212         x = x->next;
 213         free(c->head);
 214     }
 215
 216     if (fflush(c->fp) != 0) {
 217         return -1;
 218     }
 219     /* if (buffer_flush(&c->b) == -1) return -1; */
 220     rewind(c->fp);
 221     if (ftell(c->fp) != 0) {
 222         return -1;
 223     }
 224     /* if (seek_begin(c->fd) == -1) return -1; */
 225     if (cdb_make_write(c, c->final, sizeof c->final) != 0) {
 226         return -1;
 227     }
 228     return fflush(c->fp);
 229     /* return buffer_putflush(&c->b,c->final,sizeof c->final); */
 230 }