| 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 |
const unsigned char *ptr, unsigned len); |
| 157 |
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 |
/* cdb_find.c: cdb_find routine |
| 163 |
* |
| 164 |
* This file is a part of tinycdb package by Michael Tokarev, mjt@corpit.ru. |
| 165 |
* Public domain. |
| 166 |
*/ |
| 167 |
|
| 168 |
static int |
| 169 |
cdb_find(struct cdb *cdbp, const void *key, unsigned klen) |
| 170 |
{ |
| 171 |
const unsigned char *htp; /* hash table pointer */ |
| 172 |
const unsigned char *htab; /* hash table */ |
| 173 |
const unsigned char *htend; /* end of hash table */ |
| 174 |
unsigned httodo; /* ht bytes left to look */ |
| 175 |
unsigned pos, n; |
| 176 |
|
| 177 |
unsigned hval; |
| 178 |
|
| 179 |
if (klen >= cdbp->cdb_dend) /* if key size is too large */ |
| 180 |
return 0; |
| 181 |
|
| 182 |
hval = cdb_hash(key, klen); |
| 183 |
|
| 184 |
/* find (pos,n) hash table to use */ |
| 185 |
/* first 2048 bytes (toc) are always available */ |
| 186 |
/* (hval % 256) * 8 */ |
| 187 |
htp = cdbp->cdb_mem + ((hval << 3) & 2047); /* index in toc (256x8) */ |
| 188 |
n = cdb_unpack(htp + 4); /* table size */ |
| 189 |
if (!n) /* empty table */ |
| 190 |
return 0; /* not found */ |
| 191 |
httodo = n << 3; /* bytes of htab to lookup */ |
| 192 |
pos = cdb_unpack(htp); /* htab position */ |
| 193 |
if (n > (cdbp->cdb_fsize >> 3) /* overflow of httodo ? */ |
| 194 |
|| pos < cdbp->cdb_dend /* is htab inside data section ? */ |
| 195 |
|| pos > cdbp->cdb_fsize /* htab start within file ? */ |
| 196 |
|| httodo > cdbp->cdb_fsize - pos) /* entrie htab within file ? */ |
| 197 |
return errno = EPROTO, -1; |
| 198 |
|
| 199 |
htab = cdbp->cdb_mem + pos; /* htab pointer */ |
| 200 |
htend = htab + httodo; /* after end of htab */ |
| 201 |
/* htab starting position: rest of hval modulo htsize, 8bytes per elt */ |
| 202 |
htp = htab + (((hval >> 8) % n) << 3); |
| 203 |
|
| 204 |
for(;;) { |
| 205 |
pos = cdb_unpack(htp + 4); /* record position */ |
| 206 |
if (!pos) |
| 207 |
return 0; |
| 208 |
if (cdb_unpack(htp) == hval) { |
| 209 |
if (pos > cdbp->cdb_dend - 8) /* key+val lengths */ |
| 210 |
return errno = EPROTO, -1; |
| 211 |
if (cdb_unpack(cdbp->cdb_mem + pos) == klen) { |
| 212 |
if (cdbp->cdb_dend - klen < pos + 8) |
| 213 |
return errno = EPROTO, -1; |
| 214 |
if (memcmp(key, cdbp->cdb_mem + pos + 8, klen) == 0) { |
| 215 |
n = cdb_unpack(cdbp->cdb_mem + pos + 4); |
| 216 |
pos += 8; |
| 217 |
if (cdbp->cdb_dend < n || cdbp->cdb_dend - n < pos + klen) |
| 218 |
return errno = EPROTO, -1; |
| 219 |
cdbp->cdb_kpos = pos; |
| 220 |
cdbp->cdb_klen = klen; |
| 221 |
cdbp->cdb_vpos = pos + klen; |
| 222 |
cdbp->cdb_vlen = n; |
| 223 |
return 1; |
| 224 |
} |
| 225 |
} |
| 226 |
} |
| 227 |
httodo -= 8; |
| 228 |
if (!httodo) |
| 229 |
return 0; |
| 230 |
if ((htp += 8) >= htend) |
| 231 |
htp = htab; |
| 232 |
} |
| 233 |
|
| 234 |
} |
| 235 |
|
| 236 |
/* cdb_hash.c: cdb hashing routine |
| 237 |
* |
| 238 |
* This file is a part of tinycdb package by Michael Tokarev, mjt@corpit.ru. |
| 239 |
* Public domain. |
| 240 |
*/ |
| 241 |
|
| 242 |
static unsigned |
| 243 |
cdb_hash(const void *buf, unsigned len) |
| 244 |
{ |
| 245 |
register const unsigned char *p = (const unsigned char *)buf; |
| 246 |
register const unsigned char *end = p + len; |
| 247 |
register unsigned hash = 5381; /* start value */ |
| 248 |
while (p < end) |
| 249 |
hash = (hash + (hash << 5)) ^ *p++; |
| 250 |
return hash; |
| 251 |
} |
| 252 |
|
| 253 |
/* cdb_init.c: cdb_init, cdb_free and cdb_read routines |
| 254 |
* |
| 255 |
* This file is a part of tinycdb package by Michael Tokarev, mjt@corpit.ru. |
| 256 |
* Public domain. |
| 257 |
*/ |
| 258 |
|
| 259 |
#include <sys/types.h> |
| 260 |
#ifdef _WIN32 |
| 261 |
# include <windows.h> |
| 262 |
#else |
| 263 |
# include <sys/mman.h> |
| 264 |
# ifndef MAP_FAILED |
| 265 |
# define MAP_FAILED ((void*)-1) |
| 266 |
# endif |
| 267 |
#endif |
| 268 |
#include <sys/stat.h> |
| 269 |
|
| 270 |
static int |
| 271 |
cdb_init(struct cdb *cdbp, int fd) |
| 272 |
{ |
| 273 |
struct stat st; |
| 274 |
unsigned char *mem; |
| 275 |
unsigned fsize, dend; |
| 276 |
#ifdef _WIN32 |
| 277 |
HANDLE hFile, hMapping; |
| 278 |
#endif |
| 279 |
|
| 280 |
/* get file size */ |
| 281 |
if (fstat(fd, &st) < 0) |
| 282 |
return -1; |
| 283 |
/* trivial sanity check: at least toc should be here */ |
| 284 |
if (st.st_size < 2048) |
| 285 |
return errno = EPROTO, -1; |
| 286 |
fsize = st.st_size < 0xffffffffu ? st.st_size : 0xffffffffu; |
| 287 |
/* memory-map file */ |
| 288 |
#ifdef _WIN32 |
| 289 |
hFile = (HANDLE) _get_osfhandle(fd); |
| 290 |
if (hFile == (HANDLE) -1) |
| 291 |
return -1; |
| 292 |
hMapping = CreateFileMapping(hFile, NULL, PAGE_READONLY, 0, 0, NULL); |
| 293 |
if (!hMapping) |
| 294 |
return -1; |
| 295 |
mem = (unsigned char *)MapViewOfFile(hMapping, FILE_MAP_READ, 0, 0, 0); |
| 296 |
CloseHandle(hMapping); |
| 297 |
if (!mem) |
| 298 |
return -1; |
| 299 |
#else |
| 300 |
mem = (unsigned char*)mmap(NULL, fsize, PROT_READ, MAP_SHARED, fd, 0); |
| 301 |
if (mem == MAP_FAILED) |
| 302 |
return -1; |
| 303 |
#endif /* _WIN32 */ |
| 304 |
|
| 305 |
cdbp->cdb_fd = fd; |
| 306 |
cdbp->cdb_fsize = fsize; |
| 307 |
cdbp->cdb_mem = mem; |
| 308 |
|
| 309 |
#if 0 |
| 310 |
/* XXX don't know well about madvise syscall -- is it legal |
| 311 |
to set different options for parts of one mmap() region? |
| 312 |
There is also posix_madvise() exist, with POSIX_MADV_RANDOM etc... |
| 313 |
*/ |
| 314 |
#ifdef MADV_RANDOM |
| 315 |
/* set madvise() parameters. Ignore errors for now if system |
| 316 |
doesn't support it */ |
| 317 |
madvise(mem, 2048, MADV_WILLNEED); |
| 318 |
madvise(mem + 2048, cdbp->cdb_fsize - 2048, MADV_RANDOM); |
| 319 |
#endif |
| 320 |
#endif |
| 321 |
|
| 322 |
cdbp->cdb_vpos = cdbp->cdb_vlen = 0; |
| 323 |
cdbp->cdb_kpos = cdbp->cdb_klen = 0; |
| 324 |
dend = cdb_unpack(mem); |
| 325 |
if (dend < 2048) dend = 2048; |
| 326 |
else if (dend >= fsize) dend = fsize; |
| 327 |
cdbp->cdb_dend = dend; |
| 328 |
|
| 329 |
return 0; |
| 330 |
} |
| 331 |
|
| 332 |
static void |
| 333 |
cdb_free(struct cdb *cdbp) |
| 334 |
{ |
| 335 |
if (cdbp->cdb_mem) { |
| 336 |
#ifdef _WIN32 |
| 337 |
UnmapViewOfFile((void*) cdbp->cdb_mem); |
| 338 |
#else |
| 339 |
munmap((void*)cdbp->cdb_mem, cdbp->cdb_fsize); |
| 340 |
#endif /* _WIN32 */ |
| 341 |
cdbp->cdb_mem = NULL; |
| 342 |
} |
| 343 |
cdbp->cdb_fsize = 0; |
| 344 |
} |
| 345 |
|
| 346 |
static const void * |
| 347 |
cdb_get(const struct cdb *cdbp, unsigned len, unsigned pos) |
| 348 |
{ |
| 349 |
if (pos > cdbp->cdb_fsize || cdbp->cdb_fsize - pos < len) { |
| 350 |
errno = EPROTO; |
| 351 |
return NULL; |
| 352 |
} |
| 353 |
return cdbp->cdb_mem + pos; |
| 354 |
} |
| 355 |
|
| 356 |
static int |
| 357 |
cdb_read(const struct cdb *cdbp, void *buf, unsigned len, unsigned pos) |
| 358 |
{ |
| 359 |
const void *data = cdb_get(cdbp, len, pos); |
| 360 |
if (!data) return -1; |
| 361 |
memcpy(buf, data, len); |
| 362 |
return 0; |
| 363 |
} |
| 364 |
|
| 365 |
/* cdb_make_add.c: basic cdb_make_add routine |
| 366 |
* |
| 367 |
* This file is a part of tinycdb package by Michael Tokarev, mjt@corpit.ru. |
| 368 |
* Public domain. |
| 369 |
*/ |
| 370 |
|
| 371 |
#include <stdlib.h> /* for malloc */ |
| 372 |
|
| 373 |
int internal_function |
| 374 |
_cdb_make_add(struct cdb_make *cdbmp, unsigned hval, |
| 375 |
const void *key, unsigned klen, |
| 376 |
const void *val, unsigned vlen) |
| 377 |
{ |
| 378 |
unsigned char rlen[8]; |
| 379 |
struct cdb_rl *rl; |
| 380 |
unsigned i; |
| 381 |
if (klen > 0xffffffff - (cdbmp->cdb_dpos + 8) || |
| 382 |
vlen > 0xffffffff - (cdbmp->cdb_dpos + klen + 8)) |
| 383 |
return errno = ENOMEM, -1; |
| 384 |
i = hval & 255; |
| 385 |
rl = cdbmp->cdb_rec[i]; |
| 386 |
if (!rl || rl->cnt >= sizeof(rl->rec)/sizeof(rl->rec[0])) { |
| 387 |
rl = (struct cdb_rl*)malloc(sizeof(struct cdb_rl)); |
| 388 |
if (!rl) |
| 389 |
return errno = ENOMEM, -1; |
| 390 |
rl->cnt = 0; |
| 391 |
rl->next = cdbmp->cdb_rec[i]; |
| 392 |
cdbmp->cdb_rec[i] = rl; |
| 393 |
} |
| 394 |
i = rl->cnt++; |
| 395 |
rl->rec[i].hval = hval; |
| 396 |
rl->rec[i].rpos = cdbmp->cdb_dpos; |
| 397 |
++cdbmp->cdb_rcnt; |
| 398 |
cdb_pack(klen, rlen); |
| 399 |
cdb_pack(vlen, rlen + 4); |
| 400 |
if (_cdb_make_write(cdbmp, rlen, 8) < 0 || |
| 401 |
_cdb_make_write(cdbmp, key, klen) < 0 || |
| 402 |
_cdb_make_write(cdbmp, val, vlen) < 0) |
| 403 |
return -1; |
| 404 |
return 0; |
| 405 |
} |
| 406 |
|
| 407 |
static int |
| 408 |
cdb_make_add(struct cdb_make *cdbmp, |
| 409 |
const void *key, unsigned klen, |
| 410 |
const void *val, unsigned vlen) { |
| 411 |
return _cdb_make_add(cdbmp, cdb_hash(key, klen), key, klen, val, vlen); |
| 412 |
} |
| 413 |
|
| 414 |
/* cdb_unpack.c: unpack 32bit integer |
| 415 |
* |
| 416 |
* This file is a part of tinycdb package by Michael Tokarev, mjt@corpit.ru. |
| 417 |
* Public domain. |
| 418 |
*/ |
| 419 |
|
| 420 |
static inline unsigned |
| 421 |
cdb_unpack(const unsigned char buf[4]) |
| 422 |
{ |
| 423 |
unsigned n = buf[3]; |
| 424 |
n <<= 8; n |= buf[2]; |
| 425 |
n <<= 8; n |= buf[1]; |
| 426 |
n <<= 8; n |= buf[0]; |
| 427 |
return n; |
| 428 |
} |
| 429 |
|
| 430 |
/* cdb_make.c: basic cdb creation routines |
| 431 |
* |
| 432 |
* This file is a part of tinycdb package by Michael Tokarev, mjt@corpit.ru. |
| 433 |
* Public domain. |
| 434 |
*/ |
| 435 |
|
| 436 |
#include <unistd.h> |
| 437 |
#include <stdlib.h> |
| 438 |
#include <string.h> |
| 439 |
|
| 440 |
static inline void |
| 441 |
cdb_pack(unsigned num, unsigned char buf[4]) |
| 442 |
{ |
| 443 |
buf[0] = num & 255; num >>= 8; |
| 444 |
buf[1] = num & 255; num >>= 8; |
| 445 |
buf[2] = num & 255; |
| 446 |
buf[3] = num >> 8; |
| 447 |
} |
| 448 |
|
| 449 |
static int |
| 450 |
cdb_make_start(struct cdb_make *cdbmp, int fd) |
| 451 |
{ |
| 452 |
memset(cdbmp, 0, sizeof(*cdbmp)); |
| 453 |
cdbmp->cdb_fd = fd; |
| 454 |
cdbmp->cdb_dpos = 2048; |
| 455 |
cdbmp->cdb_bpos = cdbmp->cdb_buf + 2048; |
| 456 |
return 0; |
| 457 |
} |
| 458 |
|
| 459 |
int internal_function |
| 460 |
_cdb_make_fullwrite(int fd, const unsigned char *buf, unsigned len) |
| 461 |
{ |
| 462 |
while(len) { |
| 463 |
int l = write(fd, buf, len); |
| 464 |
if (l > 0) { |
| 465 |
len -= l; |
| 466 |
buf += l; |
| 467 |
} |
| 468 |
else if (l < 0 && errno != EINTR) |
| 469 |
return -1; |
| 470 |
} |
| 471 |
return 0; |
| 472 |
} |
| 473 |
|
| 474 |
int internal_function |
| 475 |
_cdb_make_flush(struct cdb_make *cdbmp) { |
| 476 |
unsigned len = cdbmp->cdb_bpos - cdbmp->cdb_buf; |
| 477 |
if (len) { |
| 478 |
if (_cdb_make_fullwrite(cdbmp->cdb_fd, cdbmp->cdb_buf, len) < 0) |
| 479 |
return -1; |
| 480 |
cdbmp->cdb_bpos = cdbmp->cdb_buf; |
| 481 |
} |
| 482 |
return 0; |
| 483 |
} |
| 484 |
|
| 485 |
int internal_function |
| 486 |
_cdb_make_write(struct cdb_make *cdbmp, const unsigned char *ptr, unsigned len) |
| 487 |
{ |
| 488 |
unsigned l = sizeof(cdbmp->cdb_buf) - (cdbmp->cdb_bpos - cdbmp->cdb_buf); |
| 489 |
cdbmp->cdb_dpos += len; |
| 490 |
if (len > l) { |
| 491 |
memcpy(cdbmp->cdb_bpos, ptr, l); |
| 492 |
cdbmp->cdb_bpos += l; |
| 493 |
if (_cdb_make_flush(cdbmp) < 0) |
| 494 |
return -1; |
| 495 |
ptr += l; len -= l; |
| 496 |
l = len / sizeof(cdbmp->cdb_buf); |
| 497 |
if (l) { |
| 498 |
l *= sizeof(cdbmp->cdb_buf); |
| 499 |
if (_cdb_make_fullwrite(cdbmp->cdb_fd, ptr, l) < 0) |
| 500 |
return -1; |
| 501 |
ptr += l; len -= l; |
| 502 |
} |
| 503 |
} |
| 504 |
if (len) { |
| 505 |
memcpy(cdbmp->cdb_bpos, ptr, len); |
| 506 |
cdbmp->cdb_bpos += len; |
| 507 |
} |
| 508 |
return 0; |
| 509 |
} |
| 510 |
|
| 511 |
static int |
| 512 |
cdb_make_finish_internal(struct cdb_make *cdbmp) |
| 513 |
{ |
| 514 |
unsigned hcnt[256]; /* hash table counts */ |
| 515 |
unsigned hpos[256]; /* hash table positions */ |
| 516 |
struct cdb_rec *htab; |
| 517 |
unsigned char *p; |
| 518 |
struct cdb_rl *rl; |
| 519 |
unsigned hsize; |
| 520 |
unsigned t, i; |
| 521 |
|
| 522 |
if (((0xffffffff - cdbmp->cdb_dpos) >> 3) < cdbmp->cdb_rcnt) |
| 523 |
return errno = ENOMEM, -1; |
| 524 |
|
| 525 |
/* count htab sizes and reorder reclists */ |
| 526 |
hsize = 0; |
| 527 |
for (t = 0; t < 256; ++t) { |
| 528 |
struct cdb_rl *rlt = NULL; |
| 529 |
i = 0; |
| 530 |
rl = cdbmp->cdb_rec[t]; |
| 531 |
while(rl) { |
| 532 |
struct cdb_rl *rln = rl->next; |
| 533 |
rl->next = rlt; |
| 534 |
rlt = rl; |
| 535 |
i += rl->cnt; |
| 536 |
rl = rln; |
| 537 |
} |
| 538 |
cdbmp->cdb_rec[t] = rlt; |
| 539 |
if (hsize < (hcnt[t] = i << 1)) |
| 540 |
hsize = hcnt[t]; |
| 541 |
} |
| 542 |
|
| 543 |
/* allocate memory to hold max htable */ |
| 544 |
htab = (struct cdb_rec*)malloc((hsize + 2) * sizeof(struct cdb_rec)); |
| 545 |
if (!htab) |
| 546 |
return errno = ENOENT, -1; |
| 547 |
p = (unsigned char *)htab; |
| 548 |
htab += 2; |
| 549 |
|
| 550 |
/* build hash tables */ |
| 551 |
for (t = 0; t < 256; ++t) { |
| 552 |
unsigned len, hi; |
| 553 |
hpos[t] = cdbmp->cdb_dpos; |
| 554 |
if ((len = hcnt[t]) == 0) |
| 555 |
continue; |
| 556 |
for (i = 0; i < len; ++i) |
| 557 |
htab[i].hval = htab[i].rpos = 0; |
| 558 |
for (rl = cdbmp->cdb_rec[t]; rl; rl = rl->next) |
| 559 |
for (i = 0; i < rl->cnt; ++i) { |
| 560 |
hi = (rl->rec[i].hval >> 8) % len; |
| 561 |
while(htab[hi].rpos) |
| 562 |
if (++hi == len) |
| 563 |
hi = 0; |
| 564 |
htab[hi] = rl->rec[i]; |
| 565 |
} |
| 566 |
for (i = 0; i < len; ++i) { |
| 567 |
cdb_pack(htab[i].hval, p + (i << 3)); |
| 568 |
cdb_pack(htab[i].rpos, p + (i << 3) + 4); |
| 569 |
} |
| 570 |
if (_cdb_make_write(cdbmp, p, len << 3) < 0) { |
| 571 |
free(p); |
| 572 |
return -1; |
| 573 |
} |
| 574 |
} |
| 575 |
free(p); |
| 576 |
if (_cdb_make_flush(cdbmp) < 0) |
| 577 |
return -1; |
| 578 |
p = cdbmp->cdb_buf; |
| 579 |
for (t = 0; t < 256; ++t) { |
| 580 |
cdb_pack(hpos[t], p + (t << 3)); |
| 581 |
cdb_pack(hcnt[t], p + (t << 3) + 4); |
| 582 |
} |
| 583 |
if (lseek(cdbmp->cdb_fd, 0, 0) != 0 || |
| 584 |
_cdb_make_fullwrite(cdbmp->cdb_fd, p, 2048) != 0) |
| 585 |
return -1; |
| 586 |
|
| 587 |
return 0; |
| 588 |
} |
| 589 |
|
| 590 |
static void |
| 591 |
cdb_make_free(struct cdb_make *cdbmp) |
| 592 |
{ |
| 593 |
unsigned t; |
| 594 |
for(t = 0; t < 256; ++t) { |
| 595 |
struct cdb_rl *rl = cdbmp->cdb_rec[t]; |
| 596 |
while(rl) { |
| 597 |
struct cdb_rl *tm = rl; |
| 598 |
rl = rl->next; |
| 599 |
free(tm); |
| 600 |
} |
| 601 |
} |
| 602 |
} |
| 603 |
|
| 604 |
static int |
| 605 |
cdb_make_finish(struct cdb_make *cdbmp) |
| 606 |
{ |
| 607 |
int r = cdb_make_finish_internal(cdbmp); |
| 608 |
cdb_make_free(cdbmp); |
| 609 |
return r; |
| 610 |
} |
| 611 |
|
