| 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 | } |