1 |
root |
1.1 |
/* embeddable/static cdb version by schmorp */ |
2 |
|
|
|
3 |
|
|
/* cdb.h: public cdb include file |
4 |
|
|
* |
5 |
|
|
* This file is a part of tinycdb package by Michael Tokarev, mjt@corpit.ru. |
6 |
|
|
* Public domain. |
7 |
|
|
*/ |
8 |
|
|
|
9 |
|
|
#ifndef TINYCDB_VERSION |
10 |
|
|
#define TINYCDB_VERSION 0.78 |
11 |
|
|
|
12 |
|
|
#ifdef __cplusplus |
13 |
|
|
extern "C" { |
14 |
|
|
#endif |
15 |
|
|
|
16 |
|
|
typedef unsigned int cdbi_t; /* compatibility */ |
17 |
|
|
|
18 |
|
|
/* common routines */ |
19 |
|
|
static unsigned cdb_hash(const void *buf, unsigned len); |
20 |
|
|
static unsigned cdb_unpack(const unsigned char buf[4]); |
21 |
|
|
static void cdb_pack(unsigned num, unsigned char buf[4]); |
22 |
|
|
|
23 |
|
|
struct cdb { |
24 |
|
|
int cdb_fd; /* file descriptor */ |
25 |
|
|
/* private members */ |
26 |
|
|
unsigned cdb_fsize; /* datafile size */ |
27 |
|
|
unsigned cdb_dend; /* end of data ptr */ |
28 |
|
|
const unsigned char *cdb_mem; /* mmap'ed file memory */ |
29 |
|
|
unsigned cdb_vpos, cdb_vlen; /* found data */ |
30 |
|
|
unsigned cdb_kpos, cdb_klen; /* found key */ |
31 |
|
|
}; |
32 |
|
|
|
33 |
|
|
#define CDB_STATIC_INIT {0,0,0,0,0,0,0,0} |
34 |
|
|
|
35 |
|
|
#define cdb_datapos(c) ((c)->cdb_vpos) |
36 |
|
|
#define cdb_datalen(c) ((c)->cdb_vlen) |
37 |
|
|
#define cdb_keypos(c) ((c)->cdb_kpos) |
38 |
|
|
#define cdb_keylen(c) ((c)->cdb_klen) |
39 |
|
|
#define cdb_fileno(c) ((c)->cdb_fd) |
40 |
|
|
|
41 |
|
|
static int cdb_init(struct cdb *cdbp, int fd); |
42 |
|
|
static void cdb_free(struct cdb *cdbp); |
43 |
|
|
|
44 |
|
|
static int cdb_read(const struct cdb *cdbp, |
45 |
|
|
void *buf, unsigned len, unsigned pos); |
46 |
|
|
#define cdb_readdata(cdbp, buf) \ |
47 |
|
|
cdb_read((cdbp), (buf), cdb_datalen(cdbp), cdb_datapos(cdbp)) |
48 |
|
|
#define cdb_readkey(cdbp, buf) \ |
49 |
|
|
cdb_read((cdbp), (buf), cdb_keylen(cdbp), cdb_keypos(cdbp)) |
50 |
|
|
|
51 |
|
|
static const void *cdb_get(const struct cdb *cdbp, unsigned len, unsigned pos); |
52 |
|
|
#define cdb_getdata(cdbp) \ |
53 |
|
|
cdb_get((cdbp), cdb_datalen(cdbp), cdb_datapos(cdbp)) |
54 |
|
|
#define cdb_getkey(cdbp) \ |
55 |
|
|
cdb_get((cdbp), cdb_keylen(cdbp), cdb_keypos(cdbp)) |
56 |
|
|
|
57 |
|
|
static int cdb_find(struct cdb *cdbp, const void *key, unsigned klen); |
58 |
|
|
|
59 |
|
|
struct cdb_find { |
60 |
|
|
struct cdb *cdb_cdbp; |
61 |
|
|
unsigned cdb_hval; |
62 |
|
|
const unsigned char *cdb_htp, *cdb_htab, *cdb_htend; |
63 |
|
|
unsigned cdb_httodo; |
64 |
|
|
const void *cdb_key; |
65 |
|
|
unsigned cdb_klen; |
66 |
|
|
}; |
67 |
|
|
|
68 |
|
|
static int cdb_findinit(struct cdb_find *cdbfp, struct cdb *cdbp, |
69 |
|
|
const void *key, unsigned klen); |
70 |
|
|
static int cdb_findnext(struct cdb_find *cdbfp); |
71 |
|
|
|
72 |
|
|
#define cdb_seqinit(cptr, cdbp) ((*(cptr))=2048) |
73 |
|
|
static int cdb_seqnext(unsigned *cptr, struct cdb *cdbp); |
74 |
|
|
|
75 |
|
|
/* old simple interface */ |
76 |
|
|
/* open file using standard routine, then: */ |
77 |
|
|
static int cdb_seek(int fd, const void *key, unsigned klen, unsigned *dlenp); |
78 |
|
|
static int cdb_bread(int fd, void *buf, int len); |
79 |
|
|
|
80 |
|
|
/* cdb_make */ |
81 |
|
|
|
82 |
|
|
struct cdb_make { |
83 |
|
|
int cdb_fd; /* file descriptor */ |
84 |
|
|
/* private */ |
85 |
|
|
unsigned cdb_dpos; /* data position so far */ |
86 |
|
|
unsigned cdb_rcnt; /* record count so far */ |
87 |
|
|
unsigned char cdb_buf[4096]; /* write buffer */ |
88 |
|
|
unsigned char *cdb_bpos; /* current buf position */ |
89 |
|
|
struct cdb_rl *cdb_rec[256]; /* list of arrays of record infos */ |
90 |
|
|
}; |
91 |
|
|
|
92 |
|
|
enum cdb_put_mode { |
93 |
|
|
CDB_PUT_ADD = 0, /* add unconditionnaly, like cdb_make_add() */ |
94 |
|
|
#define CDB_PUT_ADD CDB_PUT_ADD |
95 |
|
|
CDB_FIND = CDB_PUT_ADD, |
96 |
|
|
CDB_PUT_REPLACE, /* replace: do not place to index OLD record */ |
97 |
|
|
#define CDB_PUT_REPLACE CDB_PUT_REPLACE |
98 |
|
|
CDB_FIND_REMOVE = CDB_PUT_REPLACE, |
99 |
|
|
CDB_PUT_INSERT, /* add only if not already exists */ |
100 |
|
|
#define CDB_PUT_INSERT CDB_PUT_INSERT |
101 |
|
|
CDB_PUT_WARN, /* add unconditionally but ret. 1 if exists */ |
102 |
|
|
#define CDB_PUT_WARN CDB_PUT_WARN |
103 |
|
|
CDB_PUT_REPLACE0, /* if a record exists, fill old one with zeros */ |
104 |
|
|
#define CDB_PUT_REPLACE0 CDB_PUT_REPLACE0 |
105 |
|
|
CDB_FIND_FILL0 = CDB_PUT_REPLACE0 |
106 |
|
|
}; |
107 |
|
|
|
108 |
|
|
static int cdb_make_start(struct cdb_make *cdbmp, int fd); |
109 |
|
|
static int cdb_make_add(struct cdb_make *cdbmp, |
110 |
|
|
const void *key, unsigned klen, |
111 |
|
|
const void *val, unsigned vlen); |
112 |
|
|
static int cdb_make_exists(struct cdb_make *cdbmp, |
113 |
|
|
const void *key, unsigned klen); |
114 |
|
|
static int cdb_make_find(struct cdb_make *cdbmp, |
115 |
|
|
const void *key, unsigned klen, |
116 |
|
|
enum cdb_put_mode mode); |
117 |
|
|
static int cdb_make_put(struct cdb_make *cdbmp, |
118 |
|
|
const void *key, unsigned klen, |
119 |
|
|
const void *val, unsigned vlen, |
120 |
|
|
enum cdb_put_mode mode); |
121 |
|
|
static int cdb_make_finish(struct cdb_make *cdbmp); |
122 |
|
|
|
123 |
|
|
#ifdef __cplusplus |
124 |
|
|
} /* extern "C" */ |
125 |
|
|
#endif |
126 |
|
|
|
127 |
|
|
#endif /* include guard */ |
128 |
|
|
|
129 |
|
|
/* cdb_int.h: internal cdb library declarations |
130 |
|
|
* |
131 |
|
|
* This file is a part of tinycdb package by Michael Tokarev, mjt@corpit.ru. |
132 |
|
|
* Public domain. |
133 |
|
|
*/ |
134 |
|
|
|
135 |
|
|
#include <errno.h> |
136 |
|
|
#include <string.h> |
137 |
|
|
|
138 |
|
|
#ifndef EPROTO |
139 |
|
|
# define EPROTO EINVAL |
140 |
|
|
#endif |
141 |
|
|
|
142 |
|
|
#define internal_function static |
143 |
|
|
|
144 |
|
|
struct cdb_rec { |
145 |
|
|
unsigned hval; |
146 |
|
|
unsigned rpos; |
147 |
|
|
}; |
148 |
|
|
|
149 |
|
|
struct cdb_rl { |
150 |
|
|
struct cdb_rl *next; |
151 |
|
|
unsigned cnt; |
152 |
|
|
struct cdb_rec rec[254]; |
153 |
|
|
}; |
154 |
|
|
|
155 |
|
|
static int _cdb_make_write(struct cdb_make *cdbmp, |
156 |
root |
1.3 |
const void *ptr, unsigned len); |
157 |
root |
1.1 |
static int _cdb_make_fullwrite(int fd, const unsigned char *buf, unsigned len); |
158 |
|
|
static int _cdb_make_flush(struct cdb_make *cdbmp); |
159 |
|
|
static int _cdb_make_add(struct cdb_make *cdbmp, unsigned hval, |
160 |
|
|
const void *key, unsigned klen, |
161 |
|
|
const void *val, unsigned vlen); |
162 |
root |
1.2 |
|
163 |
root |
1.1 |
/* cdb_find.c: cdb_find routine |
164 |
|
|
* |
165 |
|
|
* This file is a part of tinycdb package by Michael Tokarev, mjt@corpit.ru. |
166 |
|
|
* Public domain. |
167 |
|
|
*/ |
168 |
|
|
|
169 |
|
|
static int |
170 |
|
|
cdb_find(struct cdb *cdbp, const void *key, unsigned klen) |
171 |
|
|
{ |
172 |
|
|
const unsigned char *htp; /* hash table pointer */ |
173 |
|
|
const unsigned char *htab; /* hash table */ |
174 |
|
|
const unsigned char *htend; /* end of hash table */ |
175 |
|
|
unsigned httodo; /* ht bytes left to look */ |
176 |
|
|
unsigned pos, n; |
177 |
|
|
|
178 |
|
|
unsigned hval; |
179 |
|
|
|
180 |
|
|
if (klen >= cdbp->cdb_dend) /* if key size is too large */ |
181 |
|
|
return 0; |
182 |
|
|
|
183 |
|
|
hval = cdb_hash(key, klen); |
184 |
|
|
|
185 |
|
|
/* find (pos,n) hash table to use */ |
186 |
|
|
/* first 2048 bytes (toc) are always available */ |
187 |
|
|
/* (hval % 256) * 8 */ |
188 |
|
|
htp = cdbp->cdb_mem + ((hval << 3) & 2047); /* index in toc (256x8) */ |
189 |
|
|
n = cdb_unpack(htp + 4); /* table size */ |
190 |
|
|
if (!n) /* empty table */ |
191 |
|
|
return 0; /* not found */ |
192 |
|
|
httodo = n << 3; /* bytes of htab to lookup */ |
193 |
|
|
pos = cdb_unpack(htp); /* htab position */ |
194 |
|
|
if (n > (cdbp->cdb_fsize >> 3) /* overflow of httodo ? */ |
195 |
|
|
|| pos < cdbp->cdb_dend /* is htab inside data section ? */ |
196 |
|
|
|| pos > cdbp->cdb_fsize /* htab start within file ? */ |
197 |
|
|
|| httodo > cdbp->cdb_fsize - pos) /* entrie htab within file ? */ |
198 |
|
|
return errno = EPROTO, -1; |
199 |
|
|
|
200 |
|
|
htab = cdbp->cdb_mem + pos; /* htab pointer */ |
201 |
|
|
htend = htab + httodo; /* after end of htab */ |
202 |
|
|
/* htab starting position: rest of hval modulo htsize, 8bytes per elt */ |
203 |
|
|
htp = htab + (((hval >> 8) % n) << 3); |
204 |
|
|
|
205 |
|
|
for(;;) { |
206 |
|
|
pos = cdb_unpack(htp + 4); /* record position */ |
207 |
|
|
if (!pos) |
208 |
|
|
return 0; |
209 |
|
|
if (cdb_unpack(htp) == hval) { |
210 |
|
|
if (pos > cdbp->cdb_dend - 8) /* key+val lengths */ |
211 |
|
|
return errno = EPROTO, -1; |
212 |
|
|
if (cdb_unpack(cdbp->cdb_mem + pos) == klen) { |
213 |
|
|
if (cdbp->cdb_dend - klen < pos + 8) |
214 |
|
|
return errno = EPROTO, -1; |
215 |
|
|
if (memcmp(key, cdbp->cdb_mem + pos + 8, klen) == 0) { |
216 |
|
|
n = cdb_unpack(cdbp->cdb_mem + pos + 4); |
217 |
|
|
pos += 8; |
218 |
|
|
if (cdbp->cdb_dend < n || cdbp->cdb_dend - n < pos + klen) |
219 |
|
|
return errno = EPROTO, -1; |
220 |
|
|
cdbp->cdb_kpos = pos; |
221 |
|
|
cdbp->cdb_klen = klen; |
222 |
|
|
cdbp->cdb_vpos = pos + klen; |
223 |
|
|
cdbp->cdb_vlen = n; |
224 |
|
|
return 1; |
225 |
|
|
} |
226 |
|
|
} |
227 |
|
|
} |
228 |
|
|
httodo -= 8; |
229 |
|
|
if (!httodo) |
230 |
|
|
return 0; |
231 |
|
|
if ((htp += 8) >= htend) |
232 |
|
|
htp = htab; |
233 |
|
|
} |
234 |
|
|
|
235 |
|
|
} |
236 |
|
|
|
237 |
|
|
/* cdb_hash.c: cdb hashing routine |
238 |
|
|
* |
239 |
|
|
* This file is a part of tinycdb package by Michael Tokarev, mjt@corpit.ru. |
240 |
|
|
* Public domain. |
241 |
|
|
*/ |
242 |
|
|
|
243 |
|
|
static unsigned |
244 |
|
|
cdb_hash(const void *buf, unsigned len) |
245 |
|
|
{ |
246 |
|
|
register const unsigned char *p = (const unsigned char *)buf; |
247 |
|
|
register const unsigned char *end = p + len; |
248 |
|
|
register unsigned hash = 5381; /* start value */ |
249 |
|
|
while (p < end) |
250 |
|
|
hash = (hash + (hash << 5)) ^ *p++; |
251 |
|
|
return hash; |
252 |
|
|
} |
253 |
|
|
|
254 |
|
|
/* cdb_init.c: cdb_init, cdb_free and cdb_read routines |
255 |
|
|
* |
256 |
|
|
* This file is a part of tinycdb package by Michael Tokarev, mjt@corpit.ru. |
257 |
|
|
* Public domain. |
258 |
|
|
*/ |
259 |
|
|
|
260 |
|
|
#include <sys/types.h> |
261 |
|
|
#ifdef _WIN32 |
262 |
|
|
# include <windows.h> |
263 |
|
|
#else |
264 |
|
|
# include <sys/mman.h> |
265 |
|
|
# ifndef MAP_FAILED |
266 |
|
|
# define MAP_FAILED ((void*)-1) |
267 |
|
|
# endif |
268 |
|
|
#endif |
269 |
|
|
#include <sys/stat.h> |
270 |
|
|
|
271 |
|
|
static int |
272 |
|
|
cdb_init(struct cdb *cdbp, int fd) |
273 |
|
|
{ |
274 |
|
|
struct stat st; |
275 |
|
|
unsigned char *mem; |
276 |
|
|
unsigned fsize, dend; |
277 |
|
|
#ifdef _WIN32 |
278 |
|
|
HANDLE hFile, hMapping; |
279 |
|
|
#endif |
280 |
|
|
|
281 |
|
|
/* get file size */ |
282 |
|
|
if (fstat(fd, &st) < 0) |
283 |
|
|
return -1; |
284 |
|
|
/* trivial sanity check: at least toc should be here */ |
285 |
|
|
if (st.st_size < 2048) |
286 |
|
|
return errno = EPROTO, -1; |
287 |
|
|
fsize = st.st_size < 0xffffffffu ? st.st_size : 0xffffffffu; |
288 |
|
|
/* memory-map file */ |
289 |
|
|
#ifdef _WIN32 |
290 |
|
|
hFile = (HANDLE) _get_osfhandle(fd); |
291 |
|
|
if (hFile == (HANDLE) -1) |
292 |
|
|
return -1; |
293 |
|
|
hMapping = CreateFileMapping(hFile, NULL, PAGE_READONLY, 0, 0, NULL); |
294 |
|
|
if (!hMapping) |
295 |
|
|
return -1; |
296 |
|
|
mem = (unsigned char *)MapViewOfFile(hMapping, FILE_MAP_READ, 0, 0, 0); |
297 |
|
|
CloseHandle(hMapping); |
298 |
|
|
if (!mem) |
299 |
|
|
return -1; |
300 |
|
|
#else |
301 |
|
|
mem = (unsigned char*)mmap(NULL, fsize, PROT_READ, MAP_SHARED, fd, 0); |
302 |
|
|
if (mem == MAP_FAILED) |
303 |
|
|
return -1; |
304 |
|
|
#endif /* _WIN32 */ |
305 |
|
|
|
306 |
|
|
cdbp->cdb_fd = fd; |
307 |
|
|
cdbp->cdb_fsize = fsize; |
308 |
|
|
cdbp->cdb_mem = mem; |
309 |
|
|
|
310 |
|
|
#if 0 |
311 |
|
|
/* XXX don't know well about madvise syscall -- is it legal |
312 |
|
|
to set different options for parts of one mmap() region? |
313 |
|
|
There is also posix_madvise() exist, with POSIX_MADV_RANDOM etc... |
314 |
|
|
*/ |
315 |
|
|
#ifdef MADV_RANDOM |
316 |
|
|
/* set madvise() parameters. Ignore errors for now if system |
317 |
|
|
doesn't support it */ |
318 |
|
|
madvise(mem, 2048, MADV_WILLNEED); |
319 |
|
|
madvise(mem + 2048, cdbp->cdb_fsize - 2048, MADV_RANDOM); |
320 |
|
|
#endif |
321 |
|
|
#endif |
322 |
|
|
|
323 |
|
|
cdbp->cdb_vpos = cdbp->cdb_vlen = 0; |
324 |
|
|
cdbp->cdb_kpos = cdbp->cdb_klen = 0; |
325 |
|
|
dend = cdb_unpack(mem); |
326 |
|
|
if (dend < 2048) dend = 2048; |
327 |
|
|
else if (dend >= fsize) dend = fsize; |
328 |
|
|
cdbp->cdb_dend = dend; |
329 |
|
|
|
330 |
|
|
return 0; |
331 |
|
|
} |
332 |
|
|
|
333 |
|
|
static void |
334 |
|
|
cdb_free(struct cdb *cdbp) |
335 |
|
|
{ |
336 |
|
|
if (cdbp->cdb_mem) { |
337 |
|
|
#ifdef _WIN32 |
338 |
|
|
UnmapViewOfFile((void*) cdbp->cdb_mem); |
339 |
|
|
#else |
340 |
|
|
munmap((void*)cdbp->cdb_mem, cdbp->cdb_fsize); |
341 |
|
|
#endif /* _WIN32 */ |
342 |
|
|
cdbp->cdb_mem = NULL; |
343 |
|
|
} |
344 |
|
|
cdbp->cdb_fsize = 0; |
345 |
|
|
} |
346 |
|
|
|
347 |
|
|
static const void * |
348 |
|
|
cdb_get(const struct cdb *cdbp, unsigned len, unsigned pos) |
349 |
|
|
{ |
350 |
|
|
if (pos > cdbp->cdb_fsize || cdbp->cdb_fsize - pos < len) { |
351 |
|
|
errno = EPROTO; |
352 |
|
|
return NULL; |
353 |
|
|
} |
354 |
|
|
return cdbp->cdb_mem + pos; |
355 |
|
|
} |
356 |
|
|
|
357 |
|
|
static int |
358 |
|
|
cdb_read(const struct cdb *cdbp, void *buf, unsigned len, unsigned pos) |
359 |
|
|
{ |
360 |
|
|
const void *data = cdb_get(cdbp, len, pos); |
361 |
|
|
if (!data) return -1; |
362 |
|
|
memcpy(buf, data, len); |
363 |
|
|
return 0; |
364 |
|
|
} |
365 |
|
|
|
366 |
|
|
/* cdb_make_add.c: basic cdb_make_add routine |
367 |
|
|
* |
368 |
|
|
* This file is a part of tinycdb package by Michael Tokarev, mjt@corpit.ru. |
369 |
|
|
* Public domain. |
370 |
|
|
*/ |
371 |
|
|
|
372 |
|
|
#include <stdlib.h> /* for malloc */ |
373 |
|
|
|
374 |
|
|
int internal_function |
375 |
|
|
_cdb_make_add(struct cdb_make *cdbmp, unsigned hval, |
376 |
|
|
const void *key, unsigned klen, |
377 |
|
|
const void *val, unsigned vlen) |
378 |
|
|
{ |
379 |
|
|
unsigned char rlen[8]; |
380 |
|
|
struct cdb_rl *rl; |
381 |
|
|
unsigned i; |
382 |
|
|
if (klen > 0xffffffff - (cdbmp->cdb_dpos + 8) || |
383 |
|
|
vlen > 0xffffffff - (cdbmp->cdb_dpos + klen + 8)) |
384 |
|
|
return errno = ENOMEM, -1; |
385 |
|
|
i = hval & 255; |
386 |
|
|
rl = cdbmp->cdb_rec[i]; |
387 |
|
|
if (!rl || rl->cnt >= sizeof(rl->rec)/sizeof(rl->rec[0])) { |
388 |
|
|
rl = (struct cdb_rl*)malloc(sizeof(struct cdb_rl)); |
389 |
|
|
if (!rl) |
390 |
|
|
return errno = ENOMEM, -1; |
391 |
|
|
rl->cnt = 0; |
392 |
|
|
rl->next = cdbmp->cdb_rec[i]; |
393 |
|
|
cdbmp->cdb_rec[i] = rl; |
394 |
|
|
} |
395 |
|
|
i = rl->cnt++; |
396 |
|
|
rl->rec[i].hval = hval; |
397 |
|
|
rl->rec[i].rpos = cdbmp->cdb_dpos; |
398 |
|
|
++cdbmp->cdb_rcnt; |
399 |
|
|
cdb_pack(klen, rlen); |
400 |
|
|
cdb_pack(vlen, rlen + 4); |
401 |
|
|
if (_cdb_make_write(cdbmp, rlen, 8) < 0 || |
402 |
|
|
_cdb_make_write(cdbmp, key, klen) < 0 || |
403 |
|
|
_cdb_make_write(cdbmp, val, vlen) < 0) |
404 |
|
|
return -1; |
405 |
|
|
return 0; |
406 |
|
|
} |
407 |
|
|
|
408 |
|
|
static int |
409 |
|
|
cdb_make_add(struct cdb_make *cdbmp, |
410 |
|
|
const void *key, unsigned klen, |
411 |
|
|
const void *val, unsigned vlen) { |
412 |
|
|
return _cdb_make_add(cdbmp, cdb_hash(key, klen), key, klen, val, vlen); |
413 |
|
|
} |
414 |
|
|
|
415 |
|
|
/* cdb_unpack.c: unpack 32bit integer |
416 |
|
|
* |
417 |
|
|
* This file is a part of tinycdb package by Michael Tokarev, mjt@corpit.ru. |
418 |
|
|
* Public domain. |
419 |
|
|
*/ |
420 |
|
|
|
421 |
|
|
static inline unsigned |
422 |
|
|
cdb_unpack(const unsigned char buf[4]) |
423 |
|
|
{ |
424 |
|
|
unsigned n = buf[3]; |
425 |
|
|
n <<= 8; n |= buf[2]; |
426 |
|
|
n <<= 8; n |= buf[1]; |
427 |
|
|
n <<= 8; n |= buf[0]; |
428 |
|
|
return n; |
429 |
|
|
} |
430 |
|
|
|
431 |
|
|
/* cdb_make.c: basic cdb creation routines |
432 |
|
|
* |
433 |
|
|
* This file is a part of tinycdb package by Michael Tokarev, mjt@corpit.ru. |
434 |
|
|
* Public domain. |
435 |
|
|
*/ |
436 |
|
|
|
437 |
|
|
#include <unistd.h> |
438 |
|
|
#include <stdlib.h> |
439 |
|
|
#include <string.h> |
440 |
|
|
|
441 |
|
|
static inline void |
442 |
|
|
cdb_pack(unsigned num, unsigned char buf[4]) |
443 |
|
|
{ |
444 |
|
|
buf[0] = num & 255; num >>= 8; |
445 |
|
|
buf[1] = num & 255; num >>= 8; |
446 |
|
|
buf[2] = num & 255; |
447 |
|
|
buf[3] = num >> 8; |
448 |
|
|
} |
449 |
|
|
|
450 |
|
|
static int |
451 |
|
|
cdb_make_start(struct cdb_make *cdbmp, int fd) |
452 |
|
|
{ |
453 |
|
|
memset(cdbmp, 0, sizeof(*cdbmp)); |
454 |
|
|
cdbmp->cdb_fd = fd; |
455 |
|
|
cdbmp->cdb_dpos = 2048; |
456 |
|
|
cdbmp->cdb_bpos = cdbmp->cdb_buf + 2048; |
457 |
|
|
return 0; |
458 |
|
|
} |
459 |
|
|
|
460 |
|
|
int internal_function |
461 |
|
|
_cdb_make_fullwrite(int fd, const unsigned char *buf, unsigned len) |
462 |
|
|
{ |
463 |
|
|
while(len) { |
464 |
|
|
int l = write(fd, buf, len); |
465 |
|
|
if (l > 0) { |
466 |
|
|
len -= l; |
467 |
|
|
buf += l; |
468 |
|
|
} |
469 |
|
|
else if (l < 0 && errno != EINTR) |
470 |
|
|
return -1; |
471 |
|
|
} |
472 |
|
|
return 0; |
473 |
|
|
} |
474 |
|
|
|
475 |
|
|
int internal_function |
476 |
|
|
_cdb_make_flush(struct cdb_make *cdbmp) { |
477 |
|
|
unsigned len = cdbmp->cdb_bpos - cdbmp->cdb_buf; |
478 |
|
|
if (len) { |
479 |
|
|
if (_cdb_make_fullwrite(cdbmp->cdb_fd, cdbmp->cdb_buf, len) < 0) |
480 |
|
|
return -1; |
481 |
|
|
cdbmp->cdb_bpos = cdbmp->cdb_buf; |
482 |
|
|
} |
483 |
|
|
return 0; |
484 |
|
|
} |
485 |
|
|
|
486 |
|
|
int internal_function |
487 |
root |
1.3 |
_cdb_make_write(struct cdb_make *cdbmp, const void *ptr_, unsigned len) |
488 |
root |
1.1 |
{ |
489 |
root |
1.3 |
const unsigned char *ptr = (const unsigned char *)ptr_; |
490 |
root |
1.1 |
unsigned l = sizeof(cdbmp->cdb_buf) - (cdbmp->cdb_bpos - cdbmp->cdb_buf); |
491 |
|
|
cdbmp->cdb_dpos += len; |
492 |
|
|
if (len > l) { |
493 |
|
|
memcpy(cdbmp->cdb_bpos, ptr, l); |
494 |
|
|
cdbmp->cdb_bpos += l; |
495 |
|
|
if (_cdb_make_flush(cdbmp) < 0) |
496 |
|
|
return -1; |
497 |
|
|
ptr += l; len -= l; |
498 |
|
|
l = len / sizeof(cdbmp->cdb_buf); |
499 |
|
|
if (l) { |
500 |
|
|
l *= sizeof(cdbmp->cdb_buf); |
501 |
|
|
if (_cdb_make_fullwrite(cdbmp->cdb_fd, ptr, l) < 0) |
502 |
|
|
return -1; |
503 |
|
|
ptr += l; len -= l; |
504 |
|
|
} |
505 |
|
|
} |
506 |
|
|
if (len) { |
507 |
|
|
memcpy(cdbmp->cdb_bpos, ptr, len); |
508 |
|
|
cdbmp->cdb_bpos += len; |
509 |
|
|
} |
510 |
|
|
return 0; |
511 |
|
|
} |
512 |
|
|
|
513 |
|
|
static int |
514 |
|
|
cdb_make_finish_internal(struct cdb_make *cdbmp) |
515 |
|
|
{ |
516 |
|
|
unsigned hcnt[256]; /* hash table counts */ |
517 |
|
|
unsigned hpos[256]; /* hash table positions */ |
518 |
|
|
struct cdb_rec *htab; |
519 |
|
|
unsigned char *p; |
520 |
|
|
struct cdb_rl *rl; |
521 |
|
|
unsigned hsize; |
522 |
|
|
unsigned t, i; |
523 |
|
|
|
524 |
|
|
if (((0xffffffff - cdbmp->cdb_dpos) >> 3) < cdbmp->cdb_rcnt) |
525 |
|
|
return errno = ENOMEM, -1; |
526 |
|
|
|
527 |
|
|
/* count htab sizes and reorder reclists */ |
528 |
|
|
hsize = 0; |
529 |
|
|
for (t = 0; t < 256; ++t) { |
530 |
|
|
struct cdb_rl *rlt = NULL; |
531 |
|
|
i = 0; |
532 |
|
|
rl = cdbmp->cdb_rec[t]; |
533 |
|
|
while(rl) { |
534 |
|
|
struct cdb_rl *rln = rl->next; |
535 |
|
|
rl->next = rlt; |
536 |
|
|
rlt = rl; |
537 |
|
|
i += rl->cnt; |
538 |
|
|
rl = rln; |
539 |
|
|
} |
540 |
|
|
cdbmp->cdb_rec[t] = rlt; |
541 |
|
|
if (hsize < (hcnt[t] = i << 1)) |
542 |
|
|
hsize = hcnt[t]; |
543 |
|
|
} |
544 |
|
|
|
545 |
|
|
/* allocate memory to hold max htable */ |
546 |
|
|
htab = (struct cdb_rec*)malloc((hsize + 2) * sizeof(struct cdb_rec)); |
547 |
|
|
if (!htab) |
548 |
|
|
return errno = ENOENT, -1; |
549 |
|
|
p = (unsigned char *)htab; |
550 |
|
|
htab += 2; |
551 |
|
|
|
552 |
|
|
/* build hash tables */ |
553 |
|
|
for (t = 0; t < 256; ++t) { |
554 |
|
|
unsigned len, hi; |
555 |
|
|
hpos[t] = cdbmp->cdb_dpos; |
556 |
|
|
if ((len = hcnt[t]) == 0) |
557 |
|
|
continue; |
558 |
|
|
for (i = 0; i < len; ++i) |
559 |
|
|
htab[i].hval = htab[i].rpos = 0; |
560 |
|
|
for (rl = cdbmp->cdb_rec[t]; rl; rl = rl->next) |
561 |
|
|
for (i = 0; i < rl->cnt; ++i) { |
562 |
|
|
hi = (rl->rec[i].hval >> 8) % len; |
563 |
|
|
while(htab[hi].rpos) |
564 |
|
|
if (++hi == len) |
565 |
|
|
hi = 0; |
566 |
|
|
htab[hi] = rl->rec[i]; |
567 |
|
|
} |
568 |
|
|
for (i = 0; i < len; ++i) { |
569 |
|
|
cdb_pack(htab[i].hval, p + (i << 3)); |
570 |
|
|
cdb_pack(htab[i].rpos, p + (i << 3) + 4); |
571 |
|
|
} |
572 |
|
|
if (_cdb_make_write(cdbmp, p, len << 3) < 0) { |
573 |
|
|
free(p); |
574 |
|
|
return -1; |
575 |
|
|
} |
576 |
|
|
} |
577 |
|
|
free(p); |
578 |
|
|
if (_cdb_make_flush(cdbmp) < 0) |
579 |
|
|
return -1; |
580 |
|
|
p = cdbmp->cdb_buf; |
581 |
|
|
for (t = 0; t < 256; ++t) { |
582 |
|
|
cdb_pack(hpos[t], p + (t << 3)); |
583 |
|
|
cdb_pack(hcnt[t], p + (t << 3) + 4); |
584 |
|
|
} |
585 |
|
|
if (lseek(cdbmp->cdb_fd, 0, 0) != 0 || |
586 |
|
|
_cdb_make_fullwrite(cdbmp->cdb_fd, p, 2048) != 0) |
587 |
|
|
return -1; |
588 |
|
|
|
589 |
|
|
return 0; |
590 |
|
|
} |
591 |
|
|
|
592 |
|
|
static void |
593 |
|
|
cdb_make_free(struct cdb_make *cdbmp) |
594 |
|
|
{ |
595 |
|
|
unsigned t; |
596 |
|
|
for(t = 0; t < 256; ++t) { |
597 |
|
|
struct cdb_rl *rl = cdbmp->cdb_rec[t]; |
598 |
|
|
while(rl) { |
599 |
|
|
struct cdb_rl *tm = rl; |
600 |
|
|
rl = rl->next; |
601 |
|
|
free(tm); |
602 |
|
|
} |
603 |
|
|
} |
604 |
|
|
} |
605 |
|
|
|
606 |
|
|
static int |
607 |
|
|
cdb_make_finish(struct cdb_make *cdbmp) |
608 |
|
|
{ |
609 |
|
|
int r = cdb_make_finish_internal(cdbmp); |
610 |
|
|
cdb_make_free(cdbmp); |
611 |
|
|
return r; |
612 |
|
|
} |
613 |
|
|
|