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