Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
Newer
Older
100644 153 lines (128 sloc) 3.707 kb
3e25c70 import dnscache 1.00
D. J. Bernstein authored
1 /* Public domain. */
2
3 #include "seek.h"
4 #include "error.h"
5 #include "alloc.h"
6 #include "cdb.h"
7 #include "cdb_make.h"
8
9 int cdb_make_start(struct cdb_make *c,int fd)
10 {
11 c->head = 0;
12 c->split = 0;
13 c->hash = 0;
14 c->numentries = 0;
15 c->fd = fd;
16 c->pos = sizeof c->final;
df36440 import djbdns 1.03
D. J. Bernstein authored
17 buffer_init(&c->b,buffer_unixwrite,fd,c->bspace,sizeof c->bspace);
3e25c70 import dnscache 1.00
D. J. Bernstein authored
18 return seek_set(fd,c->pos);
19 }
20
21 static int posplus(struct cdb_make *c,uint32 len)
22 {
23 uint32 newpos = c->pos + len;
24 if (newpos < len) { errno = error_nomem; return -1; }
25 c->pos = newpos;
26 return 0;
27 }
28
29 int cdb_make_addend(struct cdb_make *c,unsigned int keylen,unsigned int datalen,uint32 h)
30 {
31 struct cdb_hplist *head;
32
33 head = c->head;
34 if (!head || (head->num >= CDB_HPLIST)) {
35 head = (struct cdb_hplist *) alloc(sizeof(struct cdb_hplist));
36 if (!head) return -1;
37 head->num = 0;
38 head->next = c->head;
39 c->head = head;
40 }
41 head->hp[head->num].h = h;
42 head->hp[head->num].p = c->pos;
43 ++head->num;
44 ++c->numentries;
45 if (posplus(c,8) == -1) return -1;
46 if (posplus(c,keylen) == -1) return -1;
47 if (posplus(c,datalen) == -1) return -1;
48 return 0;
49 }
50
51 int cdb_make_addbegin(struct cdb_make *c,unsigned int keylen,unsigned int datalen)
52 {
53 char buf[8];
54
55 if (keylen > 0xffffffff) { errno = error_nomem; return -1; }
56 if (datalen > 0xffffffff) { errno = error_nomem; return -1; }
57
58 uint32_pack(buf,keylen);
59 uint32_pack(buf + 4,datalen);
60 if (buffer_putalign(&c->b,buf,8) == -1) return -1;
61 return 0;
62 }
63
df36440 import djbdns 1.03
D. J. Bernstein authored
64 int cdb_make_add(struct cdb_make *c,const char *key,unsigned int keylen,const char *data,unsigned int datalen)
3e25c70 import dnscache 1.00
D. J. Bernstein authored
65 {
66 if (cdb_make_addbegin(c,keylen,datalen) == -1) return -1;
67 if (buffer_putalign(&c->b,key,keylen) == -1) return -1;
68 if (buffer_putalign(&c->b,data,datalen) == -1) return -1;
69 return cdb_make_addend(c,keylen,datalen,cdb_hash(key,keylen));
70 }
71
72 int cdb_make_finish(struct cdb_make *c)
73 {
74 char buf[8];
75 int i;
76 uint32 len;
77 uint32 u;
78 uint32 memsize;
79 uint32 count;
80 uint32 where;
81 struct cdb_hplist *x;
82 struct cdb_hp *hp;
83
84 for (i = 0;i < 256;++i)
85 c->count[i] = 0;
86
87 for (x = c->head;x;x = x->next) {
88 i = x->num;
89 while (i--)
90 ++c->count[255 & x->hp[i].h];
91 }
92
93 memsize = 1;
94 for (i = 0;i < 256;++i) {
95 u = c->count[i] * 2;
96 if (u > memsize)
97 memsize = u;
98 }
99
100 memsize += c->numentries; /* no overflow possible up to now */
101 u = (uint32) 0 - (uint32) 1;
102 u /= sizeof(struct cdb_hp);
103 if (memsize > u) { errno = error_nomem; return -1; }
104
105 c->split = (struct cdb_hp *) alloc(memsize * sizeof(struct cdb_hp));
106 if (!c->split) return -1;
107
108 c->hash = c->split + c->numentries;
109
110 u = 0;
111 for (i = 0;i < 256;++i) {
112 u += c->count[i]; /* bounded by numentries, so no overflow */
113 c->start[i] = u;
114 }
115
116 for (x = c->head;x;x = x->next) {
117 i = x->num;
118 while (i--)
119 c->split[--c->start[255 & x->hp[i].h]] = x->hp[i];
120 }
121
122 for (i = 0;i < 256;++i) {
123 count = c->count[i];
124
125 len = count + count; /* no overflow possible */
126 uint32_pack(c->final + 8 * i,c->pos);
127 uint32_pack(c->final + 8 * i + 4,len);
128
129 for (u = 0;u < len;++u)
130 c->hash[u].h = c->hash[u].p = 0;
131
132 hp = c->split + c->start[i];
133 for (u = 0;u < count;++u) {
134 where = (hp->h >> 8) % len;
135 while (c->hash[where].p)
136 if (++where == len)
137 where = 0;
138 c->hash[where] = *hp++;
139 }
140
141 for (u = 0;u < len;++u) {
142 uint32_pack(buf,c->hash[u].h);
143 uint32_pack(buf + 4,c->hash[u].p);
144 if (buffer_putalign(&c->b,buf,8) == -1) return -1;
145 if (posplus(c,8) == -1) return -1;
146 }
147 }
148
149 if (buffer_flush(&c->b) == -1) return -1;
150 if (seek_begin(c->fd) == -1) return -1;
151 return buffer_putflush(&c->b,c->final,sizeof c->final);
152 }
Something went wrong with that request. Please try again.