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
cdb_make_write(struct cdb_make * c,char * buf,uint32 sz)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
cdb_make_start(struct cdb_make * c,FILE * f)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
posplus(struct cdb_make * c,uint32 len)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
cdb_make_addend(struct cdb_make * c,unsigned int keylen,unsigned int datalen,uint32 h)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
cdb_make_addbegin(struct cdb_make * c,unsigned int keylen,unsigned int datalen)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
cdb_make_add(struct cdb_make * c,char * key,unsigned int keylen,char * data,unsigned int datalen)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
cdb_make_finish(struct cdb_make * c)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 }
231