1 /*************************************************************************************************
2 * Implementation of Depot
3 * Copyright (C) 2000-2007 Mikio Hirabayashi
4 * This file is part of QDBM, Quick Database Manager.
5 * QDBM is free software; you can redistribute it and/or modify it under the terms of the GNU
6 * Lesser General Public License as published by the Free Software Foundation; either version
7 * 2.1 of the License or any later version. QDBM is distributed in the hope that it will be
8 * useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
9 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more
10 * details.
11 * You should have received a copy of the GNU Lesser General Public License along with QDBM; if
12 * not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
13 * 02111-1307 USA.
14 *************************************************************************************************/
15
16
17 #define QDBM_INTERNAL 1
18
19 #include "depot.h"
20 #include "myconf.h"
21
22 #define DP_FILEMODE 00644 /* permission of a creating file */
23 #define DP_MAGICNUMB "[DEPOT]\n\f" /* magic number on environments of big endian */
24 #define DP_MAGICNUML "[depot]\n\f" /* magic number on environments of little endian */
25 #define DP_HEADSIZ 48 /* size of the reagion of the header */
26 #define DP_LIBVEROFF 12 /* offset of the region for the library version */
27 #define DP_FLAGSOFF 16 /* offset of the region for flags */
28 #define DP_FSIZOFF 24 /* offset of the region for the file size */
29 #define DP_BNUMOFF 32 /* offset of the region for the bucket number */
30 #define DP_RNUMOFF 40 /* offset of the region for the record number */
31 #define DP_DEFBNUM 8191 /* default bucket number */
32 #define DP_FBPOOLSIZ 16 /* size of free block pool */
33 #define DP_ENTBUFSIZ 128 /* size of the entity buffer */
34 #define DP_STKBUFSIZ 256 /* size of the stack key buffer */
35 #define DP_WRTBUFSIZ 8192 /* size of the writing buffer */
36 #define DP_FSBLKSIZ 4096 /* size of a block of the file system */
37 #define DP_TMPFSUF MYEXTSTR "dptmp" /* suffix of a temporary file */
38 #define DP_OPTBLOAD 0.25 /* ratio of bucket loading at optimization */
39 #define DP_OPTRUNIT 256 /* number of records in a process of optimization */
40 #define DP_NUMBUFSIZ 32 /* size of a buffer for a number */
41 #define DP_IOBUFSIZ 8192 /* size of an I/O buffer */
42
43 /* get the first hash value */
44 #define DP_FIRSTHASH(DP_res, DP_kbuf, DP_ksiz) \
45 do { \
46 const unsigned char *_DP_p; \
47 int _DP_ksiz; \
48 _DP_p = (const unsigned char *)(DP_kbuf); \
49 _DP_ksiz = DP_ksiz; \
50 if((_DP_ksiz) == sizeof(int)){ \
51 memcpy(&(DP_res), (DP_kbuf), sizeof(int)); \
52 } else { \
53 (DP_res) = 751; \
54 } \
55 while(_DP_ksiz--){ \
56 (DP_res) = (DP_res) * 31 + *(_DP_p)++; \
57 } \
58 (DP_res) = ((DP_res) * 87767623) & INT_MAX; \
59 } while(FALSE)
60
61 /* get the second hash value */
62 #define DP_SECONDHASH(DP_res, DP_kbuf, DP_ksiz) \
63 do { \
64 const unsigned char *_DP_p; \
65 int _DP_ksiz; \
66 _DP_p = (const unsigned char *)(DP_kbuf) + DP_ksiz - 1; \
67 _DP_ksiz = DP_ksiz; \
68 for((DP_res) = 19780211; _DP_ksiz--;){ \
69 (DP_res) = (DP_res) * 37 + *(_DP_p)--; \
70 } \
71 (DP_res) = ((DP_res) * 43321879) & INT_MAX; \
72 } while(FALSE)
73
74 /* get the third hash value */
75 #define DP_THIRDHASH(DP_res, DP_kbuf, DP_ksiz) \
76 do { \
77 int _DP_i; \
78 (DP_res) = 774831917; \
79 for(_DP_i = (DP_ksiz) - 1; _DP_i >= 0; _DP_i--){ \
80 (DP_res) = (DP_res) * 29 + ((const unsigned char *)(DP_kbuf))[_DP_i]; \
81 } \
82 (DP_res) = ((DP_res) * 5157883) & INT_MAX; \
83 } while(FALSE)
84
85 enum { /* enumeration for a record header */
86 DP_RHIFLAGS, /* offset of flags */
87 DP_RHIHASH, /* offset of value of the second hash function */
88 DP_RHIKSIZ, /* offset of the size of the key */
89 DP_RHIVSIZ, /* offset of the size of the value */
90 DP_RHIPSIZ, /* offset of the size of the padding bytes */
91 DP_RHILEFT, /* offset of the offset of the left child */
92 DP_RHIRIGHT, /* offset of the offset of the right child */
93 DP_RHNUM /* number of elements of a header */
94 };
95
96 enum { /* enumeration for the flag of a record */
97 DP_RECFDEL = 1 << 0, /* deleted */
98 DP_RECFREUSE = 1 << 1 /* reusable */
99 };
100
101
102 /* private function prototypes */
103 static int dpbigendian(void);
104 static char *dpstrdup(const char *str);
105 static int dplock(int fd, int ex, int nb);
106 static int dpwrite(int fd, const void *buf, int size);
107 static int dpseekwrite(int fd, int off, const void *buf, int size);
108 static int dpseekwritenum(int fd, int off, int num);
109 static int dpread(int fd, void *buf, int size);
110 static int dpseekread(int fd, int off, void *buf, int size);
111 static int dpfcopy(int destfd, int destoff, int srcfd, int srcoff);
112 static int dpgetprime(int num);
113 static int dppadsize(DEPOT *depot, int ksiz, int vsiz);
114 static int dprecsize(int *head);
115 static int dprechead(DEPOT *depot, int off, int *head, char *ebuf, int *eep);
116 static char *dpreckey(DEPOT *depot, int off, int *head);
117 static char *dprecval(DEPOT *depot, int off, int *head, int start, int max);
118 static int dprecvalwb(DEPOT *depot, int off, int *head, int start, int max, char *vbuf);
119 static int dpkeycmp(const char *abuf, int asiz, const char *bbuf, int bsiz);
120 static int dprecsearch(DEPOT *depot, const char *kbuf, int ksiz, int hash, int *bip, int *offp,
121 int *entp, int *head, char *ebuf, int *eep, int delhit);
122 static int dprecrewrite(DEPOT *depot, int off, int rsiz, const char *kbuf, int ksiz,
123 const char *vbuf, int vsiz, int hash, int left, int right);
124 static int dprecappend(DEPOT *depot, const char *kbuf, int ksiz, const char *vbuf, int vsiz,
125 int hash, int left, int right);
126 static int dprecover(DEPOT *depot, int off, int *head, const char *vbuf, int vsiz, int cat);
127 static int dprecdelete(DEPOT *depot, int off, int *head, int reusable);
128 static void dpfbpoolcoal(DEPOT *depot);
129 static int dpfbpoolcmp(const void *a, const void *b);
130
131
132
133 /*************************************************************************************************
134 * public objects
135 *************************************************************************************************/
136
137
138 /* String containing the version information. */
139 const char *dpversion = _QDBM_VERSION;
140
141
142 /* Get a message string corresponding to an error code. */
dperrmsg(int ecode)143 const char *dperrmsg(int ecode){
144 switch(ecode){
145 case DP_ENOERR: return "no error";
146 case DP_EFATAL: return "with fatal error";
147 case DP_EMODE: return "invalid mode";
148 case DP_EBROKEN: return "broken database file";
149 case DP_EKEEP: return "existing record";
150 case DP_ENOITEM: return "no item found";
151 case DP_EALLOC: return "memory allocation error";
152 case DP_EMAP: return "memory mapping error";
153 case DP_EOPEN: return "open error";
154 case DP_ECLOSE: return "close error";
155 case DP_ETRUNC: return "trunc error";
156 case DP_ESYNC: return "sync error";
157 case DP_ESTAT: return "stat error";
158 case DP_ESEEK: return "seek error";
159 case DP_EREAD: return "read error";
160 case DP_EWRITE: return "write error";
161 case DP_ELOCK: return "lock error";
162 case DP_EUNLINK: return "unlink error";
163 case DP_EMKDIR: return "mkdir error";
164 case DP_ERMDIR: return "rmdir error";
165 case DP_EMISC: return "miscellaneous error";
166 }
167 return "(invalid ecode)";
168 }
169
170
171 /* Get a database handle. */
dpopen(const char * name,int omode,int bnum)172 DEPOT *dpopen(const char *name, int omode, int bnum){
173 char hbuf[DP_HEADSIZ], *map, c, *tname;
174 int i, mode, fd, inode, fsiz, rnum, msiz, *fbpool;
175 struct stat sbuf;
176 time_t mtime;
177 DEPOT *depot;
178 assert(name);
179 mode = O_RDONLY;
180 if(omode & DP_OWRITER){
181 mode = O_RDWR;
182 if(omode & DP_OCREAT) mode |= O_CREAT;
183 }
184 if((fd = open(name, mode, DP_FILEMODE)) == -1){
185 dpecodeset(DP_EOPEN, __FILE__, __LINE__);
186 return NULL;
187 }
188 if(!(omode & DP_ONOLCK)){
189 if(!dplock(fd, omode & DP_OWRITER, omode & DP_OLCKNB)){
190 close(fd);
191 return NULL;
192 }
193 }
194 if((omode & DP_OWRITER) && (omode & DP_OTRUNC)){
195 if(ftruncate(fd, 0) == -1){
196 close(fd);
197 dpecodeset(DP_ETRUNC, __FILE__, __LINE__);
198 return NULL;
199 }
200 }
201 if(fstat(fd, &sbuf) == -1 || !S_ISREG(sbuf.st_mode) ||
202 (sbuf.st_ino == 0 && lstat(name, &sbuf) == -1)){
203 close(fd);
204 dpecodeset(DP_ESTAT, __FILE__, __LINE__);
205 return NULL;
206 }
207 inode = sbuf.st_ino;
208 mtime = sbuf.st_mtime;
209 fsiz = sbuf.st_size;
210 if((omode & DP_OWRITER) && fsiz == 0){
211 memset(hbuf, 0, DP_HEADSIZ);
212 if(dpbigendian()){
213 memcpy(hbuf, DP_MAGICNUMB, strlen(DP_MAGICNUMB));
214 } else {
215 memcpy(hbuf, DP_MAGICNUML, strlen(DP_MAGICNUML));
216 }
217 sprintf(hbuf + DP_LIBVEROFF, "%d", _QDBM_LIBVER / 100);
218 bnum = bnum < 1 ? DP_DEFBNUM : bnum;
219 bnum = dpgetprime(bnum);
220 memcpy(hbuf + DP_BNUMOFF, &bnum, sizeof(int));
221 rnum = 0;
222 memcpy(hbuf + DP_RNUMOFF, &rnum, sizeof(int));
223 fsiz = DP_HEADSIZ + bnum * sizeof(int);
224 memcpy(hbuf + DP_FSIZOFF, &fsiz, sizeof(int));
225 if(!dpseekwrite(fd, 0, hbuf, DP_HEADSIZ)){
226 close(fd);
227 return NULL;
228 }
229 if(omode & DP_OSPARSE){
230 c = 0;
231 if(!dpseekwrite(fd, fsiz - 1, &c, 1)){
232 close(fd);
233 return NULL;
234 }
235 } else {
236 if(!(map = malloc(bnum * sizeof(int)))){
237 close(fd);
238 dpecodeset(DP_EALLOC, __FILE__, __LINE__);
239 return NULL;
240 }
241 memset(map, 0, bnum * sizeof(int));
242 if(!dpseekwrite(fd, DP_HEADSIZ, map, bnum * sizeof(int))){
243 free(map);
244 close(fd);
245 return NULL;
246 }
247 free(map);
248 }
249 }
250 if(!dpseekread(fd, 0, hbuf, DP_HEADSIZ)){
251 close(fd);
252 dpecodeset(DP_EBROKEN, __FILE__, __LINE__);
253 return NULL;
254 }
255 if(!(omode & DP_ONOLCK) &&
256 ((dpbigendian() ? memcmp(hbuf, DP_MAGICNUMB, strlen(DP_MAGICNUMB)) != 0 :
257 memcmp(hbuf, DP_MAGICNUML, strlen(DP_MAGICNUML)) != 0) ||
258 *((int *)(hbuf + DP_FSIZOFF)) != fsiz)){
259 close(fd);
260 dpecodeset(DP_EBROKEN, __FILE__, __LINE__);
261 return NULL;
262 }
263 bnum = *((int *)(hbuf + DP_BNUMOFF));
264 rnum = *((int *)(hbuf + DP_RNUMOFF));
265 if(bnum < 1 || rnum < 0 || fsiz < DP_HEADSIZ + bnum * sizeof(int)){
266 close(fd);
267 dpecodeset(DP_EBROKEN, __FILE__, __LINE__);
268 return NULL;
269 }
270 msiz = DP_HEADSIZ + bnum * sizeof(int);
271 map = mmap(0, msiz, PROT_READ | ((mode & DP_OWRITER) ? PROT_WRITE : 0), MAP_SHARED, fd, 0);
272 if(map == MAP_FAILED){
273 close(fd);
274 dpecodeset(DP_EMAP, __FILE__, __LINE__);
275 return NULL;
276 }
277 tname = NULL;
278 fbpool = NULL;
279 if(!(depot = malloc(sizeof(DEPOT))) || !(tname = dpstrdup(name)) ||
280 !(fbpool = malloc(DP_FBPOOLSIZ * 2 * sizeof(int)))){
281 free(fbpool);
282 free(tname);
283 free(depot);
284 munmap(map, msiz);
285 close(fd);
286 dpecodeset(DP_EALLOC, __FILE__, __LINE__);
287 return NULL;
288 }
289 depot->name = tname;
290 depot->wmode = (mode & DP_OWRITER);
291 depot->inode = inode;
292 depot->mtime = mtime;
293 depot->fd = fd;
294 depot->fsiz = fsiz;
295 depot->map = map;
296 depot->msiz = msiz;
297 depot->buckets = (int *)(map + DP_HEADSIZ);
298 depot->bnum = bnum;
299 depot->rnum = rnum;
300 depot->fatal = FALSE;
301 depot->ioff = 0;
302 depot->fbpool = fbpool;
303 for(i = 0; i < DP_FBPOOLSIZ * 2; i += 2){
304 depot->fbpool[i] = -1;
305 depot->fbpool[i+1] = -1;
306 }
307 depot->fbpsiz = DP_FBPOOLSIZ * 2;
308 depot->fbpinc = 0;
309 depot->align = 0;
310 return depot;
311 }
312
313
314 /* Close a database handle. */
dpclose(DEPOT * depot)315 int dpclose(DEPOT *depot){
316 int fatal, err;
317 assert(depot);
318 fatal = depot->fatal;
319 err = FALSE;
320 if(depot->wmode){
321 *((int *)(depot->map + DP_FSIZOFF)) = depot->fsiz;
322 *((int *)(depot->map + DP_RNUMOFF)) = depot->rnum;
323 }
324 if(depot->map != MAP_FAILED){
325 if(munmap(depot->map, depot->msiz) == -1){
326 err = TRUE;
327 dpecodeset(DP_EMAP, __FILE__, __LINE__);
328 }
329 }
330 if(close(depot->fd) == -1){
331 err = TRUE;
332 dpecodeset(DP_ECLOSE, __FILE__, __LINE__);
333 }
334 free(depot->fbpool);
335 free(depot->name);
336 free(depot);
337 if(fatal){
338 dpecodeset(DP_EFATAL, __FILE__, __LINE__);
339 return FALSE;
340 }
341 return err ? FALSE : TRUE;
342 }
343
344
345 /* Store a record. */
dpput(DEPOT * depot,const char * kbuf,int ksiz,const char * vbuf,int vsiz,int dmode)346 int dpput(DEPOT *depot, const char *kbuf, int ksiz, const char *vbuf, int vsiz, int dmode){
347 int head[DP_RHNUM], next[DP_RHNUM];
348 int i, hash, bi, off, entoff, ee, newoff, rsiz, nsiz, fdel, mroff, mrsiz, mi, min;
349 char ebuf[DP_ENTBUFSIZ], *tval, *swap;
350 assert(depot && kbuf && vbuf);
351 if(depot->fatal){
352 dpecodeset(DP_EFATAL, __FILE__, __LINE__);
353 return FALSE;
354 }
355 if(!depot->wmode){
356 dpecodeset(DP_EMODE, __FILE__, __LINE__);
357 return FALSE;
358 }
359 if(ksiz < 0) ksiz = strlen(kbuf);
360 if(vsiz < 0) vsiz = strlen(vbuf);
361 newoff = -1;
362 DP_SECONDHASH(hash, kbuf, ksiz);
363 switch(dprecsearch(depot, kbuf, ksiz, hash, &bi, &off, &entoff, head, ebuf, &ee, TRUE)){
364 case -1:
365 depot->fatal = TRUE;
366 return FALSE;
367 case 0:
368 fdel = head[DP_RHIFLAGS] & DP_RECFDEL;
369 if(dmode == DP_DKEEP && !fdel){
370 dpecodeset(DP_EKEEP, __FILE__, __LINE__);
371 return FALSE;
372 }
373 if(fdel){
374 head[DP_RHIPSIZ] += head[DP_RHIVSIZ];
375 head[DP_RHIVSIZ] = 0;
376 }
377 rsiz = dprecsize(head);
378 nsiz = DP_RHNUM * sizeof(int) + ksiz + vsiz;
379 if(dmode == DP_DCAT) nsiz += head[DP_RHIVSIZ];
380 if(off + rsiz >= depot->fsiz){
381 if(rsiz < nsiz){
382 head[DP_RHIPSIZ] += nsiz - rsiz;
383 rsiz = nsiz;
384 depot->fsiz = off + rsiz;
385 }
386 } else {
387 while(nsiz > rsiz && off + rsiz < depot->fsiz){
388 if(!dprechead(depot, off + rsiz, next, NULL, NULL)) return FALSE;
389 if(!(next[DP_RHIFLAGS] & DP_RECFREUSE)) break;
390 head[DP_RHIPSIZ] += dprecsize(next);
391 rsiz += dprecsize(next);
392 }
393 for(i = 0; i < depot->fbpsiz; i += 2){
394 if(depot->fbpool[i] >= off && depot->fbpool[i] < off + rsiz){
395 depot->fbpool[i] = -1;
396 depot->fbpool[i+1] = -1;
397 }
398 }
399 }
400 if(nsiz <= rsiz){
401 if(!dprecover(depot, off, head, vbuf, vsiz, dmode == DP_DCAT)){
402 depot->fatal = TRUE;
403 return FALSE;
404 }
405 } else {
406 tval = NULL;
407 if(dmode == DP_DCAT){
408 if(ee && DP_RHNUM * sizeof(int) + head[DP_RHIKSIZ] + head[DP_RHIVSIZ] <= DP_ENTBUFSIZ){
409 if(!(tval = malloc(head[DP_RHIVSIZ] + vsiz + 1))){
410 dpecodeset(DP_EALLOC, __FILE__, __LINE__);
411 depot->fatal = TRUE;
412 return FALSE;
413 }
414 memcpy(tval, ebuf + (DP_RHNUM * sizeof(int) + head[DP_RHIKSIZ]), head[DP_RHIVSIZ]);
415 } else {
416 if(!(tval = dprecval(depot, off, head, 0, -1))){
417 depot->fatal = TRUE;
418 return FALSE;
419 }
420 if(!(swap = realloc(tval, head[DP_RHIVSIZ] + vsiz + 1))){
421 free(tval);
422 dpecodeset(DP_EALLOC, __FILE__, __LINE__);
423 depot->fatal = TRUE;
424 return FALSE;
425 }
426 tval = swap;
427 }
428 memcpy(tval + head[DP_RHIVSIZ], vbuf, vsiz);
429 vsiz += head[DP_RHIVSIZ];
430 vbuf = tval;
431 }
432 mi = -1;
433 min = -1;
434 for(i = 0; i < depot->fbpsiz; i += 2){
435 if(depot->fbpool[i+1] < nsiz) continue;
436 if(mi == -1 || depot->fbpool[i+1] < min){
437 mi = i;
438 min = depot->fbpool[i+1];
439 }
440 }
441 if(mi >= 0){
442 mroff = depot->fbpool[mi];
443 mrsiz = depot->fbpool[mi+1];
444 depot->fbpool[mi] = -1;
445 depot->fbpool[mi+1] = -1;
446 } else {
447 mroff = -1;
448 mrsiz = -1;
449 }
450 if(!dprecdelete(depot, off, head, TRUE)){
451 free(tval);
452 depot->fatal = TRUE;
453 return FALSE;
454 }
455 if(mroff > 0 && nsiz <= mrsiz){
456 if(!dprecrewrite(depot, mroff, mrsiz, kbuf, ksiz, vbuf, vsiz,
457 hash, head[DP_RHILEFT], head[DP_RHIRIGHT])){
458 free(tval);
459 depot->fatal = TRUE;
460 return FALSE;
461 }
462 newoff = mroff;
463 } else {
464 if((newoff = dprecappend(depot, kbuf, ksiz, vbuf, vsiz,
465 hash, head[DP_RHILEFT], head[DP_RHIRIGHT])) == -1){
466 free(tval);
467 depot->fatal = TRUE;
468 return FALSE;
469 }
470 }
471 free(tval);
472 }
473 if(fdel) depot->rnum++;
474 break;
475 default:
476 if((newoff = dprecappend(depot, kbuf, ksiz, vbuf, vsiz, hash, 0, 0)) == -1){
477 depot->fatal = TRUE;
478 return FALSE;
479 }
480 depot->rnum++;
481 break;
482 }
483 if(newoff > 0){
484 if(entoff > 0){
485 if(!dpseekwritenum(depot->fd, entoff, newoff)){
486 depot->fatal = TRUE;
487 return FALSE;
488 }
489 } else {
490 depot->buckets[bi] = newoff;
491 }
492 }
493 return TRUE;
494 }
495
496
497 /* Delete a record. */
dpout(DEPOT * depot,const char * kbuf,int ksiz)498 int dpout(DEPOT *depot, const char *kbuf, int ksiz){
499 int head[DP_RHNUM], hash, bi, off, entoff, ee;
500 char ebuf[DP_ENTBUFSIZ];
501 assert(depot && kbuf);
502 if(depot->fatal){
503 dpecodeset(DP_EFATAL, __FILE__, __LINE__);
504 return FALSE;
505 }
506 if(!depot->wmode){
507 dpecodeset(DP_EMODE, __FILE__, __LINE__);
508 return FALSE;
509 }
510 if(ksiz < 0) ksiz = strlen(kbuf);
511 DP_SECONDHASH(hash, kbuf, ksiz);
512 switch(dprecsearch(depot, kbuf, ksiz, hash, &bi, &off, &entoff, head, ebuf, &ee, FALSE)){
513 case -1:
514 depot->fatal = TRUE;
515 return FALSE;
516 case 0:
517 break;
518 default:
519 dpecodeset(DP_ENOITEM, __FILE__, __LINE__);
520 return FALSE;
521 }
522 if(!dprecdelete(depot, off, head, FALSE)){
523 depot->fatal = TRUE;
524 return FALSE;
525 }
526 depot->rnum--;
527 return TRUE;
528 }
529
530
531 /* Retrieve a record. */
dpget(DEPOT * depot,const char * kbuf,int ksiz,int start,int max,int * sp)532 char *dpget(DEPOT *depot, const char *kbuf, int ksiz, int start, int max, int *sp){
533 int head[DP_RHNUM], hash, bi, off, entoff, ee, vsiz;
534 char ebuf[DP_ENTBUFSIZ], *vbuf;
535 assert(depot && kbuf && start >= 0);
536 if(depot->fatal){
537 dpecodeset(DP_EFATAL, __FILE__, __LINE__);
538 return NULL;
539 }
540 if(ksiz < 0) ksiz = strlen(kbuf);
541 DP_SECONDHASH(hash, kbuf, ksiz);
542 switch(dprecsearch(depot, kbuf, ksiz, hash, &bi, &off, &entoff, head, ebuf, &ee, FALSE)){
543 case -1:
544 depot->fatal = TRUE;
545 return NULL;
546 case 0:
547 break;
548 default:
549 dpecodeset(DP_ENOITEM, __FILE__, __LINE__);
550 return NULL;
551 }
552 if(start > head[DP_RHIVSIZ]){
553 dpecodeset(DP_ENOITEM, __FILE__, __LINE__);
554 return NULL;
555 }
556 if(ee && DP_RHNUM * sizeof(int) + head[DP_RHIKSIZ] + head[DP_RHIVSIZ] <= DP_ENTBUFSIZ){
557 head[DP_RHIVSIZ] -= start;
558 if(max < 0){
559 vsiz = head[DP_RHIVSIZ];
560 } else {
561 vsiz = max < head[DP_RHIVSIZ] ? max : head[DP_RHIVSIZ];
562 }
563 if(!(vbuf = malloc(vsiz + 1))){
564 dpecodeset(DP_EALLOC, __FILE__, __LINE__);
565 depot->fatal = TRUE;
566 return NULL;
567 }
568 memcpy(vbuf, ebuf + (DP_RHNUM * sizeof(int) + head[DP_RHIKSIZ] + start), vsiz);
569 vbuf[vsiz] = '\0';
570 } else {
571 if(!(vbuf = dprecval(depot, off, head, start, max))){
572 depot->fatal = TRUE;
573 return NULL;
574 }
575 }
576 if(sp){
577 if(max < 0){
578 *sp = head[DP_RHIVSIZ];
579 } else {
580 *sp = max < head[DP_RHIVSIZ] ? max : head[DP_RHIVSIZ];
581 }
582 }
583 return vbuf;
584 }
585
586
587 /* Retrieve a record and write the value into a buffer. */
dpgetwb(DEPOT * depot,const char * kbuf,int ksiz,int start,int max,char * vbuf)588 int dpgetwb(DEPOT *depot, const char *kbuf, int ksiz, int start, int max, char *vbuf){
589 int head[DP_RHNUM], hash, bi, off, entoff, ee, vsiz;
590 char ebuf[DP_ENTBUFSIZ];
591 assert(depot && kbuf && start >= 0 && max >= 0 && vbuf);
592 if(depot->fatal){
593 dpecodeset(DP_EFATAL, __FILE__, __LINE__);
594 return -1;
595 }
596 if(ksiz < 0) ksiz = strlen(kbuf);
597 DP_SECONDHASH(hash, kbuf, ksiz);
598 switch(dprecsearch(depot, kbuf, ksiz, hash, &bi, &off, &entoff, head, ebuf, &ee, FALSE)){
599 case -1:
600 depot->fatal = TRUE;
601 return -1;
602 case 0:
603 break;
604 default:
605 dpecodeset(DP_ENOITEM, __FILE__, __LINE__);
606 return -1;
607 }
608 if(start > head[DP_RHIVSIZ]){
609 dpecodeset(DP_ENOITEM, __FILE__, __LINE__);
610 return -1;
611 }
612 if(ee && DP_RHNUM * sizeof(int) + head[DP_RHIKSIZ] + head[DP_RHIVSIZ] <= DP_ENTBUFSIZ){
613 head[DP_RHIVSIZ] -= start;
614 vsiz = max < head[DP_RHIVSIZ] ? max : head[DP_RHIVSIZ];
615 memcpy(vbuf, ebuf + (DP_RHNUM * sizeof(int) + head[DP_RHIKSIZ] + start), vsiz);
616 } else {
617 if((vsiz = dprecvalwb(depot, off, head, start, max, vbuf)) == -1){
618 depot->fatal = TRUE;
619 return -1;
620 }
621 }
622 return vsiz;
623 }
624
625
626 /* Get the size of the value of a record. */
dpvsiz(DEPOT * depot,const char * kbuf,int ksiz)627 int dpvsiz(DEPOT *depot, const char *kbuf, int ksiz){
628 int head[DP_RHNUM], hash, bi, off, entoff, ee;
629 char ebuf[DP_ENTBUFSIZ];
630 assert(depot && kbuf);
631 if(depot->fatal){
632 dpecodeset(DP_EFATAL, __FILE__, __LINE__);
633 return -1;
634 }
635 if(ksiz < 0) ksiz = strlen(kbuf);
636 DP_SECONDHASH(hash, kbuf, ksiz);
637 switch(dprecsearch(depot, kbuf, ksiz, hash, &bi, &off, &entoff, head, ebuf, &ee, FALSE)){
638 case -1:
639 depot->fatal = TRUE;
640 return -1;
641 case 0:
642 break;
643 default:
644 dpecodeset(DP_ENOITEM, __FILE__, __LINE__);
645 return -1;
646 }
647 return head[DP_RHIVSIZ];
648 }
649
650
651 /* Initialize the iterator of a database handle. */
dpiterinit(DEPOT * depot)652 int dpiterinit(DEPOT *depot){
653 assert(depot);
654 if(depot->fatal){
655 dpecodeset(DP_EFATAL, __FILE__, __LINE__);
656 return FALSE;
657 }
658 depot->ioff = 0;
659 return TRUE;
660 }
661
662
663 /* Get the next key of the iterator. */
dpiternext(DEPOT * depot,int * sp)664 char *dpiternext(DEPOT *depot, int *sp){
665 int off, head[DP_RHNUM], ee;
666 char ebuf[DP_ENTBUFSIZ], *kbuf;
667 assert(depot);
668 if(depot->fatal){
669 dpecodeset(DP_EFATAL, __FILE__, __LINE__);
670 return NULL;
671 }
672 off = DP_HEADSIZ + depot->bnum * sizeof(int);
673 off = off > depot->ioff ? off : depot->ioff;
674 while(off < depot->fsiz){
675 if(!dprechead(depot, off, head, ebuf, &ee)){
676 depot->fatal = TRUE;
677 return NULL;
678 }
679 if(head[DP_RHIFLAGS] & DP_RECFDEL){
680 off += dprecsize(head);
681 } else {
682 if(ee && DP_RHNUM * sizeof(int) + head[DP_RHIKSIZ] <= DP_ENTBUFSIZ){
683 if(!(kbuf = malloc(head[DP_RHIKSIZ] + 1))){
684 dpecodeset(DP_EALLOC, __FILE__, __LINE__);
685 depot->fatal = TRUE;
686 return NULL;
687 }
688 memcpy(kbuf, ebuf + (DP_RHNUM * sizeof(int)), head[DP_RHIKSIZ]);
689 kbuf[head[DP_RHIKSIZ]] = '\0';
690 } else {
691 if(!(kbuf = dpreckey(depot, off, head))){
692 depot->fatal = TRUE;
693 return NULL;
694 }
695 }
696 depot->ioff = off + dprecsize(head);
697 if(sp) *sp = head[DP_RHIKSIZ];
698 return kbuf;
699 }
700 }
701 dpecodeset(DP_ENOITEM, __FILE__, __LINE__);
702 return NULL;
703 }
704
705
706 /* Set alignment of a database handle. */
dpsetalign(DEPOT * depot,int align)707 int dpsetalign(DEPOT *depot, int align){
708 assert(depot);
709 if(depot->fatal){
710 dpecodeset(DP_EFATAL, __FILE__, __LINE__);
711 return FALSE;
712 }
713 if(!depot->wmode){
714 dpecodeset(DP_EMODE, __FILE__, __LINE__);
715 return FALSE;
716 }
717 depot->align = align;
718 return TRUE;
719 }
720
721
722 /* Set the size of the free block pool of a database handle. */
dpsetfbpsiz(DEPOT * depot,int size)723 int dpsetfbpsiz(DEPOT *depot, int size){
724 int *fbpool;
725 int i;
726 assert(depot && size >= 0);
727 if(depot->fatal){
728 dpecodeset(DP_EFATAL, __FILE__, __LINE__);
729 return FALSE;
730 }
731 if(!depot->wmode){
732 dpecodeset(DP_EMODE, __FILE__, __LINE__);
733 return FALSE;
734 }
735 size *= 2;
736 if(!(fbpool = realloc(depot->fbpool, size * sizeof(int) + 1))){
737 dpecodeset(DP_EALLOC, __FILE__, __LINE__);
738 return FALSE;
739 }
740 for(i = 0; i < size; i += 2){
741 fbpool[i] = -1;
742 fbpool[i+1] = -1;
743 }
744 depot->fbpool = fbpool;
745 depot->fbpsiz = size;
746 return TRUE;
747 }
748
749
750
751 /* Synchronize contents of updating a database with the file and the device. */
dpsync(DEPOT * depot)752 int dpsync(DEPOT *depot){
753 assert(depot);
754 if(depot->fatal){
755 dpecodeset(DP_EFATAL, __FILE__, __LINE__);
756 return FALSE;
757 }
758 if(!depot->wmode){
759 dpecodeset(DP_EMODE, __FILE__, __LINE__);
760 return FALSE;
761 }
762 *((int *)(depot->map + DP_FSIZOFF)) = depot->fsiz;
763 *((int *)(depot->map + DP_RNUMOFF)) = depot->rnum;
764 if(msync(depot->map, depot->msiz, MS_SYNC) == -1){
765 dpecodeset(DP_EMAP, __FILE__, __LINE__);
766 depot->fatal = TRUE;
767 return FALSE;
768 }
769 if(fsync(depot->fd) == -1){
770 dpecodeset(DP_ESYNC, __FILE__, __LINE__);
771 depot->fatal = TRUE;
772 return FALSE;
773 }
774 return TRUE;
775 }
776
777
778 /* Optimize a database. */
dpoptimize(DEPOT * depot,int bnum)779 int dpoptimize(DEPOT *depot, int bnum){
780 DEPOT *tdepot;
781 char *name;
782 int i, err, off, head[DP_RHNUM], ee, ksizs[DP_OPTRUNIT], vsizs[DP_OPTRUNIT], unum;
783 char ebuf[DP_ENTBUFSIZ], *kbufs[DP_OPTRUNIT], *vbufs[DP_OPTRUNIT];
784 assert(depot);
785 if(depot->fatal){
786 dpecodeset(DP_EFATAL, __FILE__, __LINE__);
787 return FALSE;
788 }
789 if(!depot->wmode){
790 dpecodeset(DP_EMODE, __FILE__, __LINE__);
791 return FALSE;
792 }
793 if(!(name = malloc(strlen(depot->name) + strlen(DP_TMPFSUF) + 1))){
794 dpecodeset(DP_EALLOC, __FILE__, __LINE__);
795 depot->fatal = FALSE;
796 return FALSE;
797 }
798 sprintf(name, "%s%s", depot->name, DP_TMPFSUF);
799 if(bnum < 0){
800 bnum = (int)(depot->rnum * (1.0 / DP_OPTBLOAD)) + 1;
801 if(bnum < DP_DEFBNUM / 2) bnum = DP_DEFBNUM / 2;
802 }
803 if(!(tdepot = dpopen(name, DP_OWRITER | DP_OCREAT | DP_OTRUNC, bnum))){
804 free(name);
805 depot->fatal = TRUE;
806 return FALSE;
807 }
808 free(name);
809 if(!dpsetflags(tdepot, dpgetflags(depot))){
810 dpclose(tdepot);
811 depot->fatal = TRUE;
812 return FALSE;
813 }
814 tdepot->align = depot->align;
815 err = FALSE;
816 off = DP_HEADSIZ + depot->bnum * sizeof(int);
817 unum = 0;
818 while(off < depot->fsiz){
819 if(!dprechead(depot, off, head, ebuf, &ee)){
820 err = TRUE;
821 break;
822 }
823 if(!(head[DP_RHIFLAGS] & DP_RECFDEL)){
824 if(ee && DP_RHNUM * sizeof(int) + head[DP_RHIKSIZ] <= DP_ENTBUFSIZ){
825 if(!(kbufs[unum] = malloc(head[DP_RHIKSIZ] + 1))){
826 dpecodeset(DP_EALLOC, __FILE__, __LINE__);
827 err = TRUE;
828 break;
829 }
830 memcpy(kbufs[unum], ebuf + (DP_RHNUM * sizeof(int)), head[DP_RHIKSIZ]);
831 if(DP_RHNUM * sizeof(int) + head[DP_RHIKSIZ] + head[DP_RHIVSIZ] <= DP_ENTBUFSIZ){
832 if(!(vbufs[unum] = malloc(head[DP_RHIVSIZ] + 1))){
833 dpecodeset(DP_EALLOC, __FILE__, __LINE__);
834 err = TRUE;
835 break;
836 }
837 memcpy(vbufs[unum], ebuf + (DP_RHNUM * sizeof(int) + head[DP_RHIKSIZ]),
838 head[DP_RHIVSIZ]);
839 } else {
840 vbufs[unum] = dprecval(depot, off, head, 0, -1);
841 }
842 } else {
843 kbufs[unum] = dpreckey(depot, off, head);
844 vbufs[unum] = dprecval(depot, off, head, 0, -1);
845 }
846 ksizs[unum] = head[DP_RHIKSIZ];
847 vsizs[unum] = head[DP_RHIVSIZ];
848 unum++;
849 if(unum >= DP_OPTRUNIT){
850 for(i = 0; i < unum; i++){
851 if(kbufs[i] && vbufs[i]){
852 if(!dpput(tdepot, kbufs[i], ksizs[i], vbufs[i], vsizs[i], DP_DKEEP)) err = TRUE;
853 } else {
854 err = TRUE;
855 }
856 free(kbufs[i]);
857 free(vbufs[i]);
858 if(err) break;
859 }
860 unum = 0;
861 }
862 }
863 off += dprecsize(head);
864 if(err) break;
865 }
866 for(i = 0; i < unum; i++){
867 if(kbufs[i] && vbufs[i]){
868 if(!dpput(tdepot, kbufs[i], ksizs[i], vbufs[i], vsizs[i], DP_DKEEP)) err = TRUE;
869 } else {
870 err = TRUE;
871 }
872 free(kbufs[i]);
873 free(vbufs[i]);
874 if(err) break;
875 }
876 if(!dpsync(tdepot)) err = TRUE;
877 if(err){
878 unlink(tdepot->name);
879 dpclose(tdepot);
880 depot->fatal = TRUE;
881 return FALSE;
882 }
883 if(munmap(depot->map, depot->msiz) == -1){
884 dpclose(tdepot);
885 dpecodeset(DP_EMAP, __FILE__, __LINE__);
886 depot->fatal = TRUE;
887 return FALSE;
888 }
889 depot->map = MAP_FAILED;
890 if(ftruncate(depot->fd, 0) == -1){
891 dpclose(tdepot);
892 unlink(tdepot->name);
893 dpecodeset(DP_ETRUNC, __FILE__, __LINE__);
894 depot->fatal = TRUE;
895 return FALSE;
896 }
897 if(dpfcopy(depot->fd, 0, tdepot->fd, 0) == -1){
898 dpclose(tdepot);
899 unlink(tdepot->name);
900 depot->fatal = TRUE;
901 return FALSE;
902 }
903 depot->fsiz = tdepot->fsiz;
904 depot->bnum = tdepot->bnum;
905 depot->ioff = 0;
906 for(i = 0; i < depot->fbpsiz; i += 2){
907 depot->fbpool[i] = -1;
908 depot->fbpool[i+1] = -1;
909 }
910 depot->msiz = tdepot->msiz;
911 depot->map = mmap(0, depot->msiz, PROT_READ | PROT_WRITE, MAP_SHARED, depot->fd, 0);
912 if(depot->map == MAP_FAILED){
913 dpecodeset(DP_EMAP, __FILE__, __LINE__);
914 depot->fatal = TRUE;
915 return FALSE;
916 }
917 depot->buckets = (int *)(depot->map + DP_HEADSIZ);
918 if(!(name = dpname(tdepot))){
919 dpclose(tdepot);
920 unlink(tdepot->name);
921 depot->fatal = TRUE;
922 return FALSE;
923 }
924 if(!dpclose(tdepot)){
925 free(name);
926 unlink(tdepot->name);
927 depot->fatal = TRUE;
928 return FALSE;
929 }
930 if(unlink(name) == -1){
931 free(name);
932 dpecodeset(DP_EUNLINK, __FILE__, __LINE__);
933 depot->fatal = TRUE;
934 return FALSE;
935 }
936 free(name);
937 return TRUE;
938 }
939
940
941 /* Get the name of a database. */
dpname(DEPOT * depot)942 char *dpname(DEPOT *depot){
943 char *name;
944 assert(depot);
945 if(depot->fatal){
946 dpecodeset(DP_EFATAL, __FILE__, __LINE__);
947 return NULL;
948 }
949 if(!(name = dpstrdup(depot->name))){
950 dpecodeset(DP_EALLOC, __FILE__, __LINE__);
951 depot->fatal = TRUE;
952 return NULL;
953 }
954 return name;
955 }
956
957
958 /* Get the size of a database file. */
dpfsiz(DEPOT * depot)959 int dpfsiz(DEPOT *depot){
960 assert(depot);
961 if(depot->fatal){
962 dpecodeset(DP_EFATAL, __FILE__, __LINE__);
963 return -1;
964 }
965 return depot->fsiz;
966 }
967
968
969 /* Get the number of the elements of the bucket array. */
dpbnum(DEPOT * depot)970 int dpbnum(DEPOT *depot){
971 assert(depot);
972 if(depot->fatal){
973 dpecodeset(DP_EFATAL, __FILE__, __LINE__);
974 return -1;
975 }
976 return depot->bnum;
977 }
978
979
980 /* Get the number of the used elements of the bucket array. */
dpbusenum(DEPOT * depot)981 int dpbusenum(DEPOT *depot){
982 int i, hits;
983 assert(depot);
984 if(depot->fatal){
985 dpecodeset(DP_EFATAL, __FILE__, __LINE__);
986 return -1;
987 }
988 hits = 0;
989 for(i = 0; i < depot->bnum; i++){
990 if(depot->buckets[i]) hits++;
991 }
992 return hits;
993 }
994
995
996 /* Get the number of the records stored in a database. */
dprnum(DEPOT * depot)997 int dprnum(DEPOT *depot){
998 assert(depot);
999 if(depot->fatal){
1000 dpecodeset(DP_EFATAL, __FILE__, __LINE__);
1001 return -1;
1002 }
1003 return depot->rnum;
1004 }
1005
1006
1007 /* Check whether a database handle is a writer or not. */
dpwritable(DEPOT * depot)1008 int dpwritable(DEPOT *depot){
1009 assert(depot);
1010 return depot->wmode;
1011 }
1012
1013
1014 /* Check whether a database has a fatal error or not. */
dpfatalerror(DEPOT * depot)1015 int dpfatalerror(DEPOT *depot){
1016 assert(depot);
1017 return depot->fatal;
1018 }
1019
1020
1021 /* Get the inode number of a database file. */
dpinode(DEPOT * depot)1022 int dpinode(DEPOT *depot){
1023 assert(depot);
1024 return depot->inode;
1025 }
1026
1027
1028 /* Get the last modified time of a database. */
dpmtime(DEPOT * depot)1029 time_t dpmtime(DEPOT *depot){
1030 assert(depot);
1031 return depot->mtime;
1032 }
1033
1034
1035 /* Get the file descriptor of a database file. */
dpfdesc(DEPOT * depot)1036 int dpfdesc(DEPOT *depot){
1037 assert(depot);
1038 return depot->fd;
1039 }
1040
1041
1042 /* Remove a database file. */
dpremove(const char * name)1043 int dpremove(const char *name){
1044 struct stat sbuf;
1045 DEPOT *depot;
1046 assert(name);
1047 if(lstat(name, &sbuf) == -1){
1048 dpecodeset(DP_ESTAT, __FILE__, __LINE__);
1049 return FALSE;
1050 }
1051 if((depot = dpopen(name, DP_OWRITER | DP_OTRUNC, -1)) != NULL) dpclose(depot);
1052 if(unlink(name) == -1){
1053 dpecodeset(DP_EUNLINK, __FILE__, __LINE__);
1054 return FALSE;
1055 }
1056 return TRUE;
1057 }
1058
1059
1060 /* Repair a broken database file. */
dprepair(const char * name)1061 int dprepair(const char *name){
1062 DEPOT *tdepot;
1063 char dbhead[DP_HEADSIZ], *tname, *kbuf, *vbuf;
1064 int fd, fsiz, flags, bnum, tbnum, err, head[DP_RHNUM], off, rsiz, ksiz, vsiz;
1065 struct stat sbuf;
1066 assert(name);
1067 if(lstat(name, &sbuf) == -1){
1068 dpecodeset(DP_ESTAT, __FILE__, __LINE__);
1069 return FALSE;
1070 }
1071 fsiz = sbuf.st_size;
1072 if((fd = open(name, O_RDWR, DP_FILEMODE)) == -1){
1073 dpecodeset(DP_EOPEN, __FILE__, __LINE__);
1074 return FALSE;
1075 }
1076 if(!dpseekread(fd, 0, dbhead, DP_HEADSIZ)){
1077 close(fd);
1078 return FALSE;
1079 }
1080 flags = *(int *)(dbhead + DP_FLAGSOFF);
1081 bnum = *(int *)(dbhead + DP_BNUMOFF);
1082 tbnum = *(int *)(dbhead + DP_RNUMOFF) * 2;
1083 if(tbnum < DP_DEFBNUM) tbnum = DP_DEFBNUM;
1084 if(!(tname = malloc(strlen(name) + strlen(DP_TMPFSUF) + 1))){
1085 dpecodeset(DP_EALLOC, __FILE__, __LINE__);
1086 return FALSE;
1087 }
1088 sprintf(tname, "%s%s", name, DP_TMPFSUF);
1089 if(!(tdepot = dpopen(tname, DP_OWRITER | DP_OCREAT | DP_OTRUNC, tbnum))){
1090 free(tname);
1091 close(fd);
1092 return FALSE;
1093 }
1094 err = FALSE;
1095 off = DP_HEADSIZ + bnum * sizeof(int);
1096 while(off < fsiz){
1097 if(!dpseekread(fd, off, head, DP_RHNUM * sizeof(int))) break;
1098 if(head[DP_RHIFLAGS] & DP_RECFDEL){
1099 if((rsiz = dprecsize(head)) < 0) break;
1100 off += rsiz;
1101 continue;
1102 }
1103 ksiz = head[DP_RHIKSIZ];
1104 vsiz = head[DP_RHIVSIZ];
1105 if(ksiz >= 0 && vsiz >= 0){
1106 kbuf = malloc(ksiz + 1);
1107 vbuf = malloc(vsiz + 1);
1108 if(kbuf && vbuf){
1109 if(dpseekread(fd, off + DP_RHNUM * sizeof(int), kbuf, ksiz) &&
1110 dpseekread(fd, off + DP_RHNUM * sizeof(int) + ksiz, vbuf, vsiz)){
1111 if(!dpput(tdepot, kbuf, ksiz, vbuf, vsiz, DP_DKEEP)) err = TRUE;
1112 } else {
1113 err = TRUE;
1114 }
1115 } else {
1116 if(!err) dpecodeset(DP_EALLOC, __FILE__, __LINE__);
1117 err = TRUE;
1118 }
1119 free(vbuf);
1120 free(kbuf);
1121 } else {
1122 if(!err) dpecodeset(DP_EBROKEN, __FILE__, __LINE__);
1123 err = TRUE;
1124 }
1125 if((rsiz = dprecsize(head)) < 0) break;
1126 off += rsiz;
1127 }
1128 if(!dpsetflags(tdepot, flags)) err = TRUE;
1129 if(!dpsync(tdepot)) err = TRUE;
1130 if(ftruncate(fd, 0) == -1){
1131 if(!err) dpecodeset(DP_ETRUNC, __FILE__, __LINE__);
1132 err = TRUE;
1133 }
1134 if(dpfcopy(fd, 0, tdepot->fd, 0) == -1) err = TRUE;
1135 if(!dpclose(tdepot)) err = TRUE;
1136 if(close(fd) == -1){
1137 if(!err) dpecodeset(DP_ECLOSE, __FILE__, __LINE__);
1138 err = TRUE;
1139 }
1140 if(unlink(tname) == -1){
1141 if(!err) dpecodeset(DP_EUNLINK, __FILE__, __LINE__);
1142 err = TRUE;
1143 }
1144 free(tname);
1145 return err ? FALSE : TRUE;
1146 }
1147
1148
1149 /* Dump all records as endian independent data. */
dpexportdb(DEPOT * depot,const char * name)1150 int dpexportdb(DEPOT *depot, const char *name){
1151 char *kbuf, *vbuf, *pbuf;
1152 int fd, err, ksiz, vsiz, psiz;
1153 assert(depot && name);
1154 if(!(dpiterinit(depot))) return FALSE;
1155 if((fd = open(name, O_RDWR | O_CREAT | O_TRUNC, DP_FILEMODE)) == -1){
1156 dpecodeset(DP_EOPEN, __FILE__, __LINE__);
1157 return FALSE;
1158 }
1159 err = FALSE;
1160 while(!err && (kbuf = dpiternext(depot, &ksiz)) != NULL){
1161 if((vbuf = dpget(depot, kbuf, ksiz, 0, -1, &vsiz)) != NULL){
1162 if((pbuf = malloc(ksiz + vsiz + DP_NUMBUFSIZ * 2)) != NULL){
1163 psiz = 0;
1164 psiz += sprintf(pbuf + psiz, "%X\n%X\n", ksiz, vsiz);
1165 memcpy(pbuf + psiz, kbuf, ksiz);
1166 psiz += ksiz;
1167 pbuf[psiz++] = '\n';
1168 memcpy(pbuf + psiz, vbuf, vsiz);
1169 psiz += vsiz;
1170 pbuf[psiz++] = '\n';
1171 if(!dpwrite(fd, pbuf, psiz)){
1172 dpecodeset(DP_EWRITE, __FILE__, __LINE__);
1173 err = TRUE;
1174 }
1175 free(pbuf);
1176 } else {
1177 dpecodeset(DP_EALLOC, __FILE__, __LINE__);
1178 err = TRUE;
1179 }
1180 free(vbuf);
1181 } else {
1182 err = TRUE;
1183 }
1184 free(kbuf);
1185 }
1186 if(close(fd) == -1){
1187 if(!err) dpecodeset(DP_ECLOSE, __FILE__, __LINE__);
1188 return FALSE;
1189 }
1190 return !err && !dpfatalerror(depot);
1191 }
1192
1193
1194 /* Load all records from endian independent data. */
dpimportdb(DEPOT * depot,const char * name)1195 int dpimportdb(DEPOT *depot, const char *name){
1196 char mbuf[DP_IOBUFSIZ], *rbuf;
1197 int i, j, fd, err, fsiz, off, msiz, ksiz, vsiz, hlen;
1198 struct stat sbuf;
1199 assert(depot && name);
1200 if(!depot->wmode){
1201 dpecodeset(DP_EMODE, __FILE__, __LINE__);
1202 return FALSE;
1203 }
1204 if(dprnum(depot) > 0){
1205 dpecodeset(DP_EMISC, __FILE__, __LINE__);
1206 return FALSE;
1207 }
1208 if((fd = open(name, O_RDONLY, DP_FILEMODE)) == -1){
1209 dpecodeset(DP_EOPEN, __FILE__, __LINE__);
1210 return FALSE;
1211 }
1212 if(fstat(fd, &sbuf) == -1 || !S_ISREG(sbuf.st_mode)){
1213 dpecodeset(DP_ESTAT, __FILE__, __LINE__);
1214 close(fd);
1215 return FALSE;
1216 }
1217 err = FALSE;
1218 fsiz = sbuf.st_size;
1219 off = 0;
1220 while(!err && off < fsiz){
1221 msiz = fsiz - off;
1222 if(msiz > DP_IOBUFSIZ) msiz = DP_IOBUFSIZ;
1223 if(!dpseekread(fd, off, mbuf, msiz)){
1224 err = TRUE;
1225 break;
1226 }
1227 hlen = 0;
1228 ksiz = -1;
1229 vsiz = -1;
1230 for(i = 0; i < msiz; i++){
1231 if(mbuf[i] == '\n'){
1232 mbuf[i] = '\0';
1233 ksiz = strtol(mbuf, NULL, 16);
1234 for(j = i + 1; j < msiz; j++){
1235 if(mbuf[j] == '\n'){
1236 mbuf[j] = '\0';
1237 vsiz = strtol(mbuf + i + 1, NULL, 16);
1238 hlen = j + 1;
1239 break;
1240 }
1241 }
1242 break;
1243 }
1244 }
1245 if(ksiz < 0 || vsiz < 0 || hlen < 4){
1246 dpecodeset(DP_EBROKEN, __FILE__, __LINE__);
1247 err = TRUE;
1248 break;
1249 }
1250 if(hlen + ksiz + vsiz + 2 < DP_IOBUFSIZ){
1251 if(!dpput(depot, mbuf + hlen, ksiz, mbuf + hlen + ksiz + 1, vsiz, DP_DKEEP)) err = TRUE;
1252 } else {
1253 if((rbuf = malloc(ksiz + vsiz + 2)) != NULL){
1254 if(dpseekread(fd, off + hlen, rbuf, ksiz + vsiz + 2)){
1255 if(!dpput(depot, rbuf, ksiz, rbuf + ksiz + 1, vsiz, DP_DKEEP)) err = TRUE;
1256 } else {
1257 err = TRUE;
1258 }
1259 free(rbuf);
1260 } else {
1261 dpecodeset(DP_EALLOC, __FILE__, __LINE__);
1262 err = TRUE;
1263 }
1264 }
1265 off += hlen + ksiz + vsiz + 2;
1266 }
1267 if(close(fd) == -1){
1268 if(!err) dpecodeset(DP_ECLOSE, __FILE__, __LINE__);
1269 return FALSE;
1270 }
1271 return !err && !dpfatalerror(depot);
1272 }
1273
1274
1275 /* Retrieve a record directly from a database file. */
dpsnaffle(const char * name,const char * kbuf,int ksiz,int * sp)1276 char *dpsnaffle(const char *name, const char* kbuf, int ksiz, int *sp){
1277 char hbuf[DP_HEADSIZ], *map, *vbuf, *tkbuf;
1278 int fd, fsiz, bnum, msiz, *buckets, hash, thash, head[DP_RHNUM], err, off, vsiz, tksiz, kcmp;
1279 struct stat sbuf;
1280 assert(name && kbuf);
1281 if(ksiz < 0) ksiz = strlen(kbuf);
1282 if((fd = open(name, O_RDONLY, DP_FILEMODE)) == -1){
1283 dpecodeset(DP_EOPEN, __FILE__, __LINE__);
1284 return NULL;
1285 }
1286 if(fstat(fd, &sbuf) == -1 || !S_ISREG(sbuf.st_mode)){
1287 close(fd);
1288 dpecodeset(DP_ESTAT, __FILE__, __LINE__);
1289 return NULL;
1290 }
1291 fsiz = sbuf.st_size;
1292 if(!dpseekread(fd, 0, hbuf, DP_HEADSIZ)){
1293 close(fd);
1294 dpecodeset(DP_EBROKEN, __FILE__, __LINE__);
1295 return NULL;
1296 }
1297 if(dpbigendian() ? memcmp(hbuf, DP_MAGICNUMB, strlen(DP_MAGICNUMB)) != 0 :
1298 memcmp(hbuf, DP_MAGICNUML, strlen(DP_MAGICNUML)) != 0){
1299 close(fd);
1300 dpecodeset(DP_EBROKEN, __FILE__, __LINE__);
1301 return NULL;
1302 }
1303 bnum = *((int *)(hbuf + DP_BNUMOFF));
1304 if(bnum < 1 || fsiz < DP_HEADSIZ + bnum * sizeof(int)){
1305 close(fd);
1306 dpecodeset(DP_EBROKEN, __FILE__, __LINE__);
1307 return NULL;
1308 }
1309 msiz = DP_HEADSIZ + bnum * sizeof(int);
1310 map = mmap(0, msiz, PROT_READ, MAP_SHARED, fd, 0);
1311 if(map == MAP_FAILED){
1312 close(fd);
1313 dpecodeset(DP_EMAP, __FILE__, __LINE__);
1314 return NULL;
1315 }
1316 buckets = (int *)(map + DP_HEADSIZ);
1317 err = FALSE;
1318 vbuf = NULL;
1319 vsiz = 0;
1320 DP_SECONDHASH(hash, kbuf, ksiz);
1321 DP_FIRSTHASH(thash, kbuf, ksiz);
1322 off = buckets[thash%bnum];
1323 while(off != 0){
1324 if(!dpseekread(fd, off, head, DP_RHNUM * sizeof(int))){
1325 err = TRUE;
1326 break;
1327 }
1328 if(head[DP_RHIKSIZ] < 0 || head[DP_RHIVSIZ] < 0 || head[DP_RHIPSIZ] < 0 ||
1329 head[DP_RHILEFT] < 0 || head[DP_RHIRIGHT] < 0){
1330 dpecodeset(DP_EBROKEN, __FILE__, __LINE__);
1331 err = TRUE;
1332 break;
1333 }
1334 thash = head[DP_RHIHASH];
1335 if(hash > thash){
1336 off = head[DP_RHILEFT];
1337 } else if(hash < thash){
1338 off = head[DP_RHIRIGHT];
1339 } else {
1340 tksiz = head[DP_RHIKSIZ];
1341 if(!(tkbuf = malloc(tksiz + 1))){
1342 dpecodeset(DP_EALLOC, __FILE__, __LINE__);
1343 err = TRUE;
1344 break;
1345 }
1346 if(!dpseekread(fd, off + DP_RHNUM * sizeof(int), tkbuf, tksiz)){
1347 free(tkbuf);
1348 err = TRUE;
1349 break;
1350 }
1351 tkbuf[tksiz] = '\0';
1352 kcmp = dpkeycmp(kbuf, ksiz, tkbuf, tksiz);
1353 free(tkbuf);
1354 if(kcmp > 0){
1355 off = head[DP_RHILEFT];
1356 } else if(kcmp < 0){
1357 off = head[DP_RHIRIGHT];
1358 } else if(head[DP_RHIFLAGS] & DP_RECFDEL){
1359 break;
1360 } else {
1361 vsiz = head[DP_RHIVSIZ];
1362 if(!(vbuf = malloc(vsiz + 1))){
1363 dpecodeset(DP_EALLOC, __FILE__, __LINE__);
1364 err = TRUE;
1365 break;
1366 }
1367 if(!dpseekread(fd, off + DP_RHNUM * sizeof(int) + head[DP_RHIKSIZ], vbuf, vsiz)){
1368 free(vbuf);
1369 vbuf = NULL;
1370 err = TRUE;
1371 break;
1372 }
1373 vbuf[vsiz] = '\0';
1374 break;
1375 }
1376 }
1377 }
1378 if(vbuf){
1379 if(sp) *sp = vsiz;
1380 } else if(!err){
1381 dpecodeset(DP_ENOITEM, __FILE__, __LINE__);
1382 }
1383 munmap(map, msiz);
1384 close(fd);
1385 return vbuf;
1386 }
1387
1388
1389 /* Hash function used inside Depot. */
dpinnerhash(const char * kbuf,int ksiz)1390 int dpinnerhash(const char *kbuf, int ksiz){
1391 int res;
1392 assert(kbuf);
1393 if(ksiz < 0) ksiz = strlen(kbuf);
1394 DP_FIRSTHASH(res, kbuf, ksiz);
1395 return res;
1396 }
1397
1398
1399 /* Hash function which is independent from the hash functions used inside Depot. */
dpouterhash(const char * kbuf,int ksiz)1400 int dpouterhash(const char *kbuf, int ksiz){
1401 int res;
1402 assert(kbuf);
1403 if(ksiz < 0) ksiz = strlen(kbuf);
1404 DP_THIRDHASH(res, kbuf, ksiz);
1405 return res;
1406 }
1407
1408
1409 /* Get a natural prime number not less than a number. */
dpprimenum(int num)1410 int dpprimenum(int num){
1411 assert(num > 0);
1412 return dpgetprime(num);
1413 }
1414
1415
1416
1417 /*************************************************************************************************
1418 * features for experts
1419 *************************************************************************************************/
1420
1421
1422 /* Name of the operating system. */
1423 const char *dpsysname = _QDBM_SYSNAME;
1424
1425
1426 /* File descriptor for debugging output. */
1427 int dpdbgfd = -1;
1428
1429
1430 /* Whether this build is reentrant. */
1431 const int dpisreentrant = _qdbm_ptsafe;
1432
1433
1434 /* Set the last happened error code. */
dpecodeset(int ecode,const char * file,int line)1435 void dpecodeset(int ecode, const char *file, int line){
1436 char iobuf[DP_IOBUFSIZ];
1437 assert(ecode >= DP_ENOERR && file && line >= 0);
1438 dpecode = ecode;
1439 if(dpdbgfd >= 0){
1440 fflush(stdout);
1441 fflush(stderr);
1442 sprintf(iobuf, "* dpecodeset: %s:%d: [%d] %s\n", file, line, ecode, dperrmsg(ecode));
1443 dpwrite(dpdbgfd, iobuf, strlen(iobuf));
1444 }
1445 }
1446
1447
1448 /* Get the pointer of the variable of the last happened error code. */
dpecodeptr(void)1449 int *dpecodeptr(void){
1450 static int defdpecode = DP_ENOERR;
1451 void *ptr;
1452 if(_qdbm_ptsafe){
1453 if(!(ptr = _qdbm_settsd(&defdpecode, sizeof(int), &defdpecode))){
1454 defdpecode = DP_EMISC;
1455 return &defdpecode;
1456 }
1457 return (int *)ptr;
1458 }
1459 return &defdpecode;
1460 }
1461
1462
1463 /* Synchronize updating contents on memory. */
dpmemsync(DEPOT * depot)1464 int dpmemsync(DEPOT *depot){
1465 assert(depot);
1466 if(depot->fatal){
1467 dpecodeset(DP_EFATAL, __FILE__, __LINE__);
1468 return FALSE;
1469 }
1470 if(!depot->wmode){
1471 dpecodeset(DP_EMODE, __FILE__, __LINE__);
1472 return FALSE;
1473 }
1474 *((int *)(depot->map + DP_FSIZOFF)) = depot->fsiz;
1475 *((int *)(depot->map + DP_RNUMOFF)) = depot->rnum;
1476 if(msync(depot->map, depot->msiz, MS_SYNC) == -1){
1477 dpecodeset(DP_EMAP, __FILE__, __LINE__);
1478 depot->fatal = TRUE;
1479 return FALSE;
1480 }
1481 return TRUE;
1482 }
1483
1484
1485 /* Synchronize updating contents on memory, not physically. */
dpmemflush(DEPOT * depot)1486 int dpmemflush(DEPOT *depot){
1487 assert(depot);
1488 if(depot->fatal){
1489 dpecodeset(DP_EFATAL, __FILE__, __LINE__);
1490 return FALSE;
1491 }
1492 if(!depot->wmode){
1493 dpecodeset(DP_EMODE, __FILE__, __LINE__);
1494 return FALSE;
1495 }
1496 *((int *)(depot->map + DP_FSIZOFF)) = depot->fsiz;
1497 *((int *)(depot->map + DP_RNUMOFF)) = depot->rnum;
1498 if(mflush(depot->map, depot->msiz, MS_SYNC) == -1){
1499 dpecodeset(DP_EMAP, __FILE__, __LINE__);
1500 depot->fatal = TRUE;
1501 return FALSE;
1502 }
1503 return TRUE;
1504 }
1505
1506
1507 /* Get flags of a database. */
dpgetflags(DEPOT * depot)1508 int dpgetflags(DEPOT *depot){
1509 int flags;
1510 assert(depot);
1511 memcpy(&flags, depot->map + DP_FLAGSOFF, sizeof(int));
1512 return flags;
1513 }
1514
1515
1516 /* Set flags of a database. */
dpsetflags(DEPOT * depot,int flags)1517 int dpsetflags(DEPOT *depot, int flags){
1518 assert(depot);
1519 if(!depot->wmode){
1520 dpecodeset(DP_EMODE, __FILE__, __LINE__);
1521 return FALSE;
1522 }
1523 memcpy(depot->map + DP_FLAGSOFF, &flags, sizeof(int));
1524 return TRUE;
1525 }
1526
1527
1528
1529 /*************************************************************************************************
1530 * private objects
1531 *************************************************************************************************/
1532
1533
1534 /* Check whether the byte order of the platform is big endian or not.
1535 The return value is true if bigendian, else, it is false. */
dpbigendian(void)1536 static int dpbigendian(void){
1537 char buf[sizeof(int)];
1538 *(int *)buf = 1;
1539 return !buf[0];
1540 }
1541
1542
1543 /* Get a copied string.
1544 `str' specifies an original string.
1545 The return value is a copied string whose region is allocated by `malloc'. */
dpstrdup(const char * str)1546 static char *dpstrdup(const char *str){
1547 int len;
1548 char *buf;
1549 assert(str);
1550 len = strlen(str);
1551 if(!(buf = malloc(len + 1))) return NULL;
1552 memcpy(buf, str, len + 1);
1553 return buf;
1554 }
1555
1556
1557 /* Lock a file descriptor.
1558 `fd' specifies a file descriptor.
1559 `ex' specifies whether an exclusive lock or a shared lock is performed.
1560 `nb' specifies whether to request with non-blocking.
1561 The return value is true if successful, else, it is false. */
dplock(int fd,int ex,int nb)1562 static int dplock(int fd, int ex, int nb){
1563 struct flock lock;
1564 assert(fd >= 0);
1565 memset(&lock, 0, sizeof(struct flock));
1566 lock.l_type = ex ? F_WRLCK : F_RDLCK;
1567 lock.l_whence = SEEK_SET;
1568 lock.l_start = 0;
1569 lock.l_len = 0;
1570 lock.l_pid = 0;
1571 while(fcntl(fd, nb ? F_SETLK : F_SETLKW, &lock) == -1){
1572 if(errno != EINTR){
1573 dpecodeset(DP_ELOCK, __FILE__, __LINE__);
1574 return FALSE;
1575 }
1576 }
1577 return TRUE;
1578 }
1579
1580
1581 /* Write into a file.
1582 `fd' specifies a file descriptor.
1583 `buf' specifies a buffer to write.
1584 `size' specifies the size of the buffer.
1585 The return value is the size of the written buffer, or, -1 on failure. */
dpwrite(int fd,const void * buf,int size)1586 static int dpwrite(int fd, const void *buf, int size){
1587 const char *lbuf;
1588 int rv, wb;
1589 assert(fd >= 0 && buf && size >= 0);
1590 lbuf = buf;
1591 rv = 0;
1592 do {
1593 wb = write(fd, lbuf, size);
1594 switch(wb){
1595 case -1: if(errno != EINTR) return -1;
1596 case 0: break;
1597 default:
1598 lbuf += wb;
1599 size -= wb;
1600 rv += wb;
1601 break;
1602 }
1603 } while(size > 0);
1604 return rv;
1605 }
1606
1607
1608 /* Write into a file at an offset.
1609 `fd' specifies a file descriptor.
1610 `off' specifies an offset of the file.
1611 `buf' specifies a buffer to write.
1612 `size' specifies the size of the buffer.
1613 The return value is true if successful, else, it is false. */
dpseekwrite(int fd,int off,const void * buf,int size)1614 static int dpseekwrite(int fd, int off, const void *buf, int size){
1615 assert(fd >= 0 && buf && size >= 0);
1616 if(size < 1) return TRUE;
1617 if(off < 0){
1618 if(lseek(fd, 0, SEEK_END) == -1){
1619 dpecodeset(DP_ESEEK, __FILE__, __LINE__);
1620 return FALSE;
1621 }
1622 } else {
1623 if(lseek(fd, off, SEEK_SET) != off){
1624 dpecodeset(DP_ESEEK, __FILE__, __LINE__);
1625 return FALSE;
1626 }
1627 }
1628 if(dpwrite(fd, buf, size) != size){
1629 dpecodeset(DP_EWRITE, __FILE__, __LINE__);
1630 return FALSE;
1631 }
1632 return TRUE;
1633 }
1634
1635
1636 /* Write an integer into a file at an offset.
1637 `fd' specifies a file descriptor.
1638 `off' specifies an offset of the file.
1639 `num' specifies an integer.
1640 The return value is true if successful, else, it is false. */
dpseekwritenum(int fd,int off,int num)1641 static int dpseekwritenum(int fd, int off, int num){
1642 assert(fd >= 0);
1643 return dpseekwrite(fd, off, &num, sizeof(int));
1644 }
1645
1646
1647 /* Read from a file and store the data into a buffer.
1648 `fd' specifies a file descriptor.
1649 `buffer' specifies a buffer to store into.
1650 `size' specifies the size to read with.
1651 The return value is the size read with, or, -1 on failure. */
dpread(int fd,void * buf,int size)1652 static int dpread(int fd, void *buf, int size){
1653 char *lbuf;
1654 int i, bs;
1655 assert(fd >= 0 && buf && size >= 0);
1656 lbuf = buf;
1657 for(i = 0; i < size && (bs = read(fd, lbuf + i, size - i)) != 0; i += bs){
1658 if(bs == -1 && errno != EINTR) return -1;
1659 }
1660 return i;
1661 }
1662
1663
1664 /* Read from a file at an offset and store the data into a buffer.
1665 `fd' specifies a file descriptor.
1666 `off' specifies an offset of the file.
1667 `buffer' specifies a buffer to store into.
1668 `size' specifies the size to read with.
1669 The return value is true if successful, else, it is false. */
dpseekread(int fd,int off,void * buf,int size)1670 static int dpseekread(int fd, int off, void *buf, int size){
1671 char *lbuf;
1672 assert(fd >= 0 && off >= 0 && buf && size >= 0);
1673 lbuf = (char *)buf;
1674 if(lseek(fd, off, SEEK_SET) != off){
1675 dpecodeset(DP_ESEEK, __FILE__, __LINE__);
1676 return FALSE;
1677 }
1678 if(dpread(fd, lbuf, size) != size){
1679 dpecodeset(DP_EREAD, __FILE__, __LINE__);
1680 return FALSE;
1681 }
1682 return TRUE;
1683 }
1684
1685
1686 /* Copy data between files.
1687 `destfd' specifies a file descriptor of a destination file.
1688 `destoff' specifies an offset of the destination file.
1689 `srcfd' specifies a file descriptor of a source file.
1690 `srcoff' specifies an offset of the source file.
1691 The return value is the size copied with, or, -1 on failure. */
dpfcopy(int destfd,int destoff,int srcfd,int srcoff)1692 static int dpfcopy(int destfd, int destoff, int srcfd, int srcoff){
1693 char iobuf[DP_IOBUFSIZ];
1694 int sum, iosiz;
1695 if(lseek(srcfd, srcoff, SEEK_SET) == -1 || lseek(destfd, destoff, SEEK_SET) == -1){
1696 dpecodeset(DP_ESEEK, __FILE__, __LINE__);
1697 return -1;
1698 }
1699 sum = 0;
1700 while((iosiz = dpread(srcfd, iobuf, DP_IOBUFSIZ)) > 0){
1701 if(dpwrite(destfd, iobuf, iosiz) == -1){
1702 dpecodeset(DP_EWRITE, __FILE__, __LINE__);
1703 return -1;
1704 }
1705 sum += iosiz;
1706 }
1707 if(iosiz < 0){
1708 dpecodeset(DP_EREAD, __FILE__, __LINE__);
1709 return -1;
1710 }
1711 return sum;
1712 }
1713
1714
1715 /* Get a natural prime number not less than a number.
1716 `num' specified a natural number.
1717 The return value is a prime number not less than the specified number. */
dpgetprime(int num)1718 static int dpgetprime(int num){
1719 int primes[] = {
1720 1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 43, 47, 53, 59, 61, 71, 79, 83,
1721 89, 103, 109, 113, 127, 139, 157, 173, 191, 199, 223, 239, 251, 283, 317, 349,
1722 383, 409, 443, 479, 509, 571, 631, 701, 761, 829, 887, 953, 1021, 1151, 1279,
1723 1399, 1531, 1663, 1789, 1913, 2039, 2297, 2557, 2803, 3067, 3323, 3583, 3833,
1724 4093, 4603, 5119, 5623, 6143, 6653, 7159, 7673, 8191, 9209, 10223, 11261,
1725 12281, 13309, 14327, 15359, 16381, 18427, 20479, 22511, 24571, 26597, 28669,
1726 30713, 32749, 36857, 40949, 45053, 49139, 53239, 57331, 61417, 65521, 73727,
1727 81919, 90107, 98299, 106487, 114679, 122869, 131071, 147451, 163819, 180221,
1728 196597, 212987, 229373, 245759, 262139, 294911, 327673, 360439, 393209, 425977,
1729 458747, 491503, 524287, 589811, 655357, 720887, 786431, 851957, 917503, 982981,
1730 1048573, 1179641, 1310719, 1441771, 1572853, 1703903, 1835003, 1966079,
1731 2097143, 2359267, 2621431, 2883577, 3145721, 3407857, 3670013, 3932153,
1732 4194301, 4718579, 5242877, 5767129, 6291449, 6815741, 7340009, 7864301,
1733 8388593, 9437179, 10485751, 11534329, 12582893, 13631477, 14680063, 15728611,
1734 16777213, 18874367, 20971507, 23068667, 25165813, 27262931, 29360087, 31457269,
1735 33554393, 37748717, 41943023, 46137319, 50331599, 54525917, 58720253, 62914549,
1736 67108859, 75497467, 83886053, 92274671, 100663291, 109051903, 117440509,
1737 125829103, 134217689, 150994939, 167772107, 184549373, 201326557, 218103799,
1738 234881011, 251658227, 268435399, 301989881, 335544301, 369098707, 402653171,
1739 436207613, 469762043, 503316469, 536870909, 603979769, 671088637, 738197503,
1740 805306357, 872415211, 939524087, 1006632947, 1073741789, 1207959503,
1741 1342177237, 1476394991, 1610612711, 1744830457, 1879048183, 2013265907, -1
1742 };
1743 int i;
1744 assert(num > 0);
1745 for(i = 0; primes[i] > 0; i++){
1746 if(num <= primes[i]) return primes[i];
1747 }
1748 return primes[i-1];
1749 }
1750
1751
1752 /* Get the padding size of a record.
1753 `vsiz' specifies the size of the value of a record.
1754 The return value is the padding size of a record. */
dppadsize(DEPOT * depot,int ksiz,int vsiz)1755 static int dppadsize(DEPOT *depot, int ksiz, int vsiz){
1756 int pad;
1757 assert(depot && vsiz >= 0);
1758 if(depot->align > 0){
1759 return depot->align - (depot->fsiz + DP_RHNUM * sizeof(int) + ksiz + vsiz) % depot->align;
1760 } else if(depot->align < 0){
1761 pad = (int)(vsiz * (2.0 / (1 << -(depot->align))));
1762 if(vsiz + pad >= DP_FSBLKSIZ){
1763 if(vsiz <= DP_FSBLKSIZ) pad = 0;
1764 if(depot->fsiz % DP_FSBLKSIZ == 0){
1765 return (pad / DP_FSBLKSIZ) * DP_FSBLKSIZ + DP_FSBLKSIZ -
1766 (depot->fsiz + DP_RHNUM * sizeof(int) + ksiz + vsiz) % DP_FSBLKSIZ;
1767 } else {
1768 return (pad / (DP_FSBLKSIZ / 2)) * (DP_FSBLKSIZ / 2) + (DP_FSBLKSIZ / 2) -
1769 (depot->fsiz + DP_RHNUM * sizeof(int) + ksiz + vsiz) % (DP_FSBLKSIZ / 2);
1770 }
1771 } else {
1772 return pad >= DP_RHNUM * sizeof(int) ? pad : DP_RHNUM * sizeof(int);
1773 }
1774 }
1775 return 0;
1776 }
1777
1778
1779 /* Get the size of a record in a database file.
1780 `head' specifies the header of a record.
1781 The return value is the size of a record in a database file. */
dprecsize(int * head)1782 static int dprecsize(int *head){
1783 assert(head);
1784 return DP_RHNUM * sizeof(int) + head[DP_RHIKSIZ] + head[DP_RHIVSIZ] + head[DP_RHIPSIZ];
1785 }
1786
1787
1788 /* Read the header of a record.
1789 `depot' specifies a database handle.
1790 `off' specifies an offset of the database file.
1791 `head' specifies a buffer for the header.
1792 `ebuf' specifies the pointer to the entity buffer.
1793 `eep' specifies the pointer to a variable to which whether ebuf was used is assigned.
1794 The return value is true if successful, else, it is false. */
dprechead(DEPOT * depot,int off,int * head,char * ebuf,int * eep)1795 static int dprechead(DEPOT *depot, int off, int *head, char *ebuf, int *eep){
1796 assert(depot && off >= 0 && head);
1797 if(off > depot->fsiz){
1798 dpecodeset(DP_EBROKEN, __FILE__, __LINE__);
1799 return FALSE;
1800 }
1801 if(ebuf){
1802 *eep = FALSE;
1803 if(off < depot->fsiz - DP_ENTBUFSIZ){
1804 *eep = TRUE;
1805 if(!dpseekread(depot->fd, off, ebuf, DP_ENTBUFSIZ)) return FALSE;
1806 memcpy(head, ebuf, DP_RHNUM * sizeof(int));
1807 if(head[DP_RHIKSIZ] < 0 || head[DP_RHIVSIZ] < 0 || head[DP_RHIPSIZ] < 0 ||
1808 head[DP_RHILEFT] < 0 || head[DP_RHIRIGHT] < 0){
1809 dpecodeset(DP_EBROKEN, __FILE__, __LINE__);
1810 return FALSE;
1811 }
1812 return TRUE;
1813 }
1814 }
1815 if(!dpseekread(depot->fd, off, head, DP_RHNUM * sizeof(int))) return FALSE;
1816 if(head[DP_RHIKSIZ] < 0 || head[DP_RHIVSIZ] < 0 || head[DP_RHIPSIZ] < 0 ||
1817 head[DP_RHILEFT] < 0 || head[DP_RHIRIGHT] < 0){
1818 dpecodeset(DP_EBROKEN, __FILE__, __LINE__);
1819 return FALSE;
1820 }
1821 return TRUE;
1822 }
1823
1824
1825 /* Read the entitiy of the key of a record.
1826 `depot' specifies a database handle.
1827 `off' specifies an offset of the database file.
1828 `head' specifies the header of a record.
1829 The return value is a key data whose region is allocated by `malloc', or NULL on failure. */
dpreckey(DEPOT * depot,int off,int * head)1830 static char *dpreckey(DEPOT *depot, int off, int *head){
1831 char *kbuf;
1832 int ksiz;
1833 assert(depot && off >= 0);
1834 ksiz = head[DP_RHIKSIZ];
1835 if(!(kbuf = malloc(ksiz + 1))){
1836 dpecodeset(DP_EALLOC, __FILE__, __LINE__);
1837 return NULL;
1838 }
1839 if(!dpseekread(depot->fd, off + DP_RHNUM * sizeof(int), kbuf, ksiz)){
1840 free(kbuf);
1841 return NULL;
1842 }
1843 kbuf[ksiz] = '\0';
1844 return kbuf;
1845 }
1846
1847
1848 /* Read the entitiy of the value of a record.
1849 `depot' specifies a database handle.
1850 `off' specifies an offset of the database file.
1851 `head' specifies the header of a record.
1852 `start' specifies the offset address of the beginning of the region of the value to be read.
1853 `max' specifies the max size to be read. If it is negative, the size to read is unlimited.
1854 The return value is a value data whose region is allocated by `malloc', or NULL on failure. */
dprecval(DEPOT * depot,int off,int * head,int start,int max)1855 static char *dprecval(DEPOT *depot, int off, int *head, int start, int max){
1856 char *vbuf;
1857 int vsiz;
1858 assert(depot && off >= 0 && start >= 0);
1859 head[DP_RHIVSIZ] -= start;
1860 if(max < 0){
1861 vsiz = head[DP_RHIVSIZ];
1862 } else {
1863 vsiz = max < head[DP_RHIVSIZ] ? max : head[DP_RHIVSIZ];
1864 }
1865 if(!(vbuf = malloc(vsiz + 1))){
1866 dpecodeset(DP_EALLOC, __FILE__, __LINE__);
1867 return NULL;
1868 }
1869 if(!dpseekread(depot->fd, off + DP_RHNUM * sizeof(int) + head[DP_RHIKSIZ] + start, vbuf, vsiz)){
1870 free(vbuf);
1871 return NULL;
1872 }
1873 vbuf[vsiz] = '\0';
1874 return vbuf;
1875 }
1876
1877
1878 /* Read the entitiy of the value of a record and write it into a given buffer.
1879 `depot' specifies a database handle.
1880 `off' specifies an offset of the database file.
1881 `head' specifies the header of a record.
1882 `start' specifies the offset address of the beginning of the region of the value to be read.
1883 `max' specifies the max size to be read. It shuld be less than the size of the writing buffer.
1884 If successful, the return value is the size of the written data, else, it is -1. */
dprecvalwb(DEPOT * depot,int off,int * head,int start,int max,char * vbuf)1885 static int dprecvalwb(DEPOT *depot, int off, int *head, int start, int max, char *vbuf){
1886 int vsiz;
1887 assert(depot && off >= 0 && start >= 0 && max >= 0 && vbuf);
1888 head[DP_RHIVSIZ] -= start;
1889 vsiz = max < head[DP_RHIVSIZ] ? max : head[DP_RHIVSIZ];
1890 if(!dpseekread(depot->fd, off + DP_RHNUM * sizeof(int) + head[DP_RHIKSIZ] + start, vbuf, vsiz))
1891 return -1;
1892 return vsiz;
1893 }
1894
1895
1896 /* Compare two keys.
1897 `abuf' specifies the pointer to the region of the former.
1898 `asiz' specifies the size of the region.
1899 `bbuf' specifies the pointer to the region of the latter.
1900 `bsiz' specifies the size of the region.
1901 The return value is 0 if two equals, positive if the formar is big, else, negative. */
dpkeycmp(const char * abuf,int asiz,const char * bbuf,int bsiz)1902 static int dpkeycmp(const char *abuf, int asiz, const char *bbuf, int bsiz){
1903 assert(abuf && asiz >= 0 && bbuf && bsiz >= 0);
1904 if(asiz > bsiz) return 1;
1905 if(asiz < bsiz) return -1;
1906 return memcmp(abuf, bbuf, asiz);
1907 }
1908
1909
1910 /* Search for a record.
1911 `depot' specifies a database handle.
1912 `kbuf' specifies the pointer to the region of a key.
1913 `ksiz' specifies the size of the region.
1914 `hash' specifies the second hash value of the key.
1915 `bip' specifies the pointer to the region to assign the index of the corresponding record.
1916 `offp' specifies the pointer to the region to assign the last visited node in the hash chain,
1917 or, -1 if the hash chain is empty.
1918 `entp' specifies the offset of the last used joint, or, -1 if the hash chain is empty.
1919 `head' specifies the pointer to the region to store the header of the last visited record in.
1920 `ebuf' specifies the pointer to the entity buffer.
1921 `eep' specifies the pointer to a variable to which whether ebuf was used is assigned.
1922 `delhit' specifies whether a deleted record corresponds or not.
1923 The return value is 0 if successful, 1 if there is no corresponding record, -1 on error. */
dprecsearch(DEPOT * depot,const char * kbuf,int ksiz,int hash,int * bip,int * offp,int * entp,int * head,char * ebuf,int * eep,int delhit)1924 static int dprecsearch(DEPOT *depot, const char *kbuf, int ksiz, int hash, int *bip, int *offp,
1925 int *entp, int *head, char *ebuf, int *eep, int delhit){
1926 int off, entoff, thash, kcmp;
1927 char stkey[DP_STKBUFSIZ], *tkey;
1928 assert(depot && kbuf && ksiz >= 0 && hash >= 0 && bip && offp && entp && head && ebuf && eep);
1929 DP_FIRSTHASH(thash, kbuf, ksiz);
1930 *bip = thash % depot->bnum;
1931 off = depot->buckets[*bip];
1932 *offp = -1;
1933 *entp = -1;
1934 entoff = -1;
1935 *eep = FALSE;
1936 while(off != 0){
1937 if(!dprechead(depot, off, head, ebuf, eep)) return -1;
1938 thash = head[DP_RHIHASH];
1939 if(hash > thash){
1940 entoff = off + DP_RHILEFT * sizeof(int);
1941 off = head[DP_RHILEFT];
1942 } else if(hash < thash){
1943 entoff = off + DP_RHIRIGHT * sizeof(int);
1944 off = head[DP_RHIRIGHT];
1945 } else {
1946 if(*eep && DP_RHNUM * sizeof(int) + head[DP_RHIKSIZ] <= DP_ENTBUFSIZ){
1947 kcmp = dpkeycmp(kbuf, ksiz, ebuf + (DP_RHNUM * sizeof(int)), head[DP_RHIKSIZ]);
1948 } else if(head[DP_RHIKSIZ] > DP_STKBUFSIZ){
1949 if(!(tkey = dpreckey(depot, off, head))) return -1;
1950 kcmp = dpkeycmp(kbuf, ksiz, tkey, head[DP_RHIKSIZ]);
1951 free(tkey);
1952 } else {
1953 if(!dpseekread(depot->fd, off + DP_RHNUM * sizeof(int), stkey, head[DP_RHIKSIZ]))
1954 return -1;
1955 kcmp = dpkeycmp(kbuf, ksiz, stkey, head[DP_RHIKSIZ]);
1956 }
1957 if(kcmp > 0){
1958 entoff = off + DP_RHILEFT * sizeof(int);
1959 off = head[DP_RHILEFT];
1960 } else if(kcmp < 0){
1961 entoff = off + DP_RHIRIGHT * sizeof(int);
1962 off = head[DP_RHIRIGHT];
1963 } else {
1964 if(!delhit && (head[DP_RHIFLAGS] & DP_RECFDEL)){
1965 entoff = off + DP_RHILEFT * sizeof(int);
1966 off = head[DP_RHILEFT];
1967 } else {
1968 *offp = off;
1969 *entp = entoff;
1970 return 0;
1971 }
1972 }
1973 }
1974 }
1975 *offp = off;
1976 *entp = entoff;
1977 return 1;
1978 }
1979
1980
1981 /* Overwrite a record.
1982 `depot' specifies a database handle.
1983 `off' specifies the offset of the database file.
1984 `rsiz' specifies the size of the existing record.
1985 `kbuf' specifies the pointer to the region of a key.
1986 `ksiz' specifies the size of the region.
1987 `vbuf' specifies the pointer to the region of a value.
1988 `vsiz' specifies the size of the region.
1989 `hash' specifies the second hash value of the key.
1990 `left' specifies the offset of the left child.
1991 `right' specifies the offset of the right child.
1992 The return value is true if successful, or, false on failure. */
dprecrewrite(DEPOT * depot,int off,int rsiz,const char * kbuf,int ksiz,const char * vbuf,int vsiz,int hash,int left,int right)1993 static int dprecrewrite(DEPOT *depot, int off, int rsiz, const char *kbuf, int ksiz,
1994 const char *vbuf, int vsiz, int hash, int left, int right){
1995 char ebuf[DP_WRTBUFSIZ];
1996 int i, head[DP_RHNUM], asiz, hoff, koff, voff, mi, min, size;
1997 assert(depot && off >= 1 && rsiz > 0 && kbuf && ksiz >= 0 && vbuf && vsiz >= 0);
1998 head[DP_RHIFLAGS] = 0;
1999 head[DP_RHIHASH] = hash;
2000 head[DP_RHIKSIZ] = ksiz;
2001 head[DP_RHIVSIZ] = vsiz;
2002 head[DP_RHIPSIZ] = rsiz - sizeof(head) - ksiz - vsiz;
2003 head[DP_RHILEFT] = left;
2004 head[DP_RHIRIGHT] = right;
2005 asiz = sizeof(head) + ksiz + vsiz;
2006 if(depot->fbpsiz > DP_FBPOOLSIZ * 4 && head[DP_RHIPSIZ] > asiz){
2007 rsiz = (head[DP_RHIPSIZ] - asiz) / 2 + asiz;
2008 head[DP_RHIPSIZ] -= rsiz;
2009 } else {
2010 rsiz = 0;
2011 }
2012 if(asiz <= DP_WRTBUFSIZ){
2013 memcpy(ebuf, head, sizeof(head));
2014 memcpy(ebuf + sizeof(head), kbuf, ksiz);
2015 memcpy(ebuf + sizeof(head) + ksiz, vbuf, vsiz);
2016 if(!dpseekwrite(depot->fd, off, ebuf, asiz)) return FALSE;
2017 } else {
2018 hoff = off;
2019 koff = hoff + sizeof(head);
2020 voff = koff + ksiz;
2021 if(!dpseekwrite(depot->fd, hoff, head, sizeof(head)) ||
2022 !dpseekwrite(depot->fd, koff, kbuf, ksiz) || !dpseekwrite(depot->fd, voff, vbuf, vsiz))
2023 return FALSE;
2024 }
2025 if(rsiz > 0){
2026 off += sizeof(head) + ksiz + vsiz + head[DP_RHIPSIZ];
2027 head[DP_RHIFLAGS] = DP_RECFDEL | DP_RECFREUSE;
2028 head[DP_RHIHASH] = hash;
2029 head[DP_RHIKSIZ] = ksiz;
2030 head[DP_RHIVSIZ] = vsiz;
2031 head[DP_RHIPSIZ] = rsiz - sizeof(head) - ksiz - vsiz;
2032 head[DP_RHILEFT] = 0;
2033 head[DP_RHIRIGHT] = 0;
2034 if(!dpseekwrite(depot->fd, off, head, sizeof(head))) return FALSE;
2035 size = dprecsize(head);
2036 mi = -1;
2037 min = -1;
2038 for(i = 0; i < depot->fbpsiz; i += 2){
2039 if(depot->fbpool[i] == -1){
2040 depot->fbpool[i] = off;
2041 depot->fbpool[i+1] = size;
2042 dpfbpoolcoal(depot);
2043 mi = -1;
2044 break;
2045 }
2046 if(mi == -1 || depot->fbpool[i+1] < min){
2047 mi = i;
2048 min = depot->fbpool[i+1];
2049 }
2050 }
2051 if(mi >= 0 && size > min){
2052 depot->fbpool[mi] = off;
2053 depot->fbpool[mi+1] = size;
2054 dpfbpoolcoal(depot);
2055 }
2056 }
2057 return TRUE;
2058 }
2059
2060
2061 /* Write a record at the end of a database file.
2062 `depot' specifies a database handle.
2063 `kbuf' specifies the pointer to the region of a key.
2064 `ksiz' specifies the size of the region.
2065 `vbuf' specifies the pointer to the region of a value.
2066 `vsiz' specifies the size of the region.
2067 `hash' specifies the second hash value of the key.
2068 `left' specifies the offset of the left child.
2069 `right' specifies the offset of the right child.
2070 The return value is the offset of the record, or, -1 on failure. */
dprecappend(DEPOT * depot,const char * kbuf,int ksiz,const char * vbuf,int vsiz,int hash,int left,int right)2071 static int dprecappend(DEPOT *depot, const char *kbuf, int ksiz, const char *vbuf, int vsiz,
2072 int hash, int left, int right){
2073 char ebuf[DP_WRTBUFSIZ], *hbuf;
2074 int head[DP_RHNUM], asiz, psiz, off;
2075 assert(depot && kbuf && ksiz >= 0 && vbuf && vsiz >= 0);
2076 psiz = dppadsize(depot, ksiz, vsiz);
2077 head[DP_RHIFLAGS] = 0;
2078 head[DP_RHIHASH] = hash;
2079 head[DP_RHIKSIZ] = ksiz;
2080 head[DP_RHIVSIZ] = vsiz;
2081 head[DP_RHIPSIZ] = psiz;
2082 head[DP_RHILEFT] = left;
2083 head[DP_RHIRIGHT] = right;
2084 asiz = sizeof(head) + ksiz + vsiz + psiz;
2085 off = depot->fsiz;
2086 if(asiz <= DP_WRTBUFSIZ){
2087 memcpy(ebuf, head, sizeof(head));
2088 memcpy(ebuf + sizeof(head), kbuf, ksiz);
2089 memcpy(ebuf + sizeof(head) + ksiz, vbuf, vsiz);
2090 memset(ebuf + sizeof(head) + ksiz + vsiz, 0, psiz);
2091 if(!dpseekwrite(depot->fd, off, ebuf, asiz)) return -1;
2092 } else {
2093 if(!(hbuf = malloc(asiz))){
2094 dpecodeset(DP_EALLOC, __FILE__, __LINE__);
2095 return -1;
2096 }
2097 memcpy(hbuf, head, sizeof(head));
2098 memcpy(hbuf + sizeof(head), kbuf, ksiz);
2099 memcpy(hbuf + sizeof(head) + ksiz, vbuf, vsiz);
2100 memset(hbuf + sizeof(head) + ksiz + vsiz, 0, psiz);
2101 if(!dpseekwrite(depot->fd, off, hbuf, asiz)){
2102 free(hbuf);
2103 return -1;
2104 }
2105 free(hbuf);
2106 }
2107 depot->fsiz += asiz;
2108 return off;
2109 }
2110
2111
2112 /* Overwrite the value of a record.
2113 `depot' specifies a database handle.
2114 `off' specifies the offset of the database file.
2115 `head' specifies the header of the record.
2116 `vbuf' specifies the pointer to the region of a value.
2117 `vsiz' specifies the size of the region.
2118 `cat' specifies whether it is concatenate mode or not.
2119 The return value is true if successful, or, false on failure. */
dprecover(DEPOT * depot,int off,int * head,const char * vbuf,int vsiz,int cat)2120 static int dprecover(DEPOT *depot, int off, int *head, const char *vbuf, int vsiz, int cat){
2121 int i, hsiz, hoff, voff;
2122 assert(depot && off >= 0 && head && vbuf && vsiz >= 0);
2123 for(i = 0; i < depot->fbpsiz; i += 2){
2124 if(depot->fbpool[i] == off){
2125 depot->fbpool[i] = -1;
2126 depot->fbpool[i+1] = -1;
2127 break;
2128 }
2129 }
2130 if(cat){
2131 head[DP_RHIFLAGS] = 0;
2132 head[DP_RHIPSIZ] -= vsiz;
2133 head[DP_RHIVSIZ] += vsiz;
2134 hsiz = DP_RHNUM * sizeof(int);
2135 hoff = off;
2136 voff = hoff + DP_RHNUM * sizeof(int) + head[DP_RHIKSIZ] + head[DP_RHIVSIZ] - vsiz;
2137 } else {
2138 head[DP_RHIFLAGS] = 0;
2139 head[DP_RHIPSIZ] += head[DP_RHIVSIZ] - vsiz;
2140 head[DP_RHIVSIZ] = vsiz;
2141 hsiz = DP_RHNUM * sizeof(int);
2142 hoff = off;
2143 voff = hoff + DP_RHNUM * sizeof(int) + head[DP_RHIKSIZ];
2144 }
2145 if(!dpseekwrite(depot->fd, hoff, head, hsiz) ||
2146 !dpseekwrite(depot->fd, voff, vbuf, vsiz)) return FALSE;
2147 return TRUE;
2148 }
2149
2150
2151 /* Delete a record.
2152 `depot' specifies a database handle.
2153 `off' specifies the offset of the database file.
2154 `head' specifies the header of the record.
2155 `reusable' specifies whether the region is reusable or not.
2156 The return value is true if successful, or, false on failure. */
dprecdelete(DEPOT * depot,int off,int * head,int reusable)2157 static int dprecdelete(DEPOT *depot, int off, int *head, int reusable){
2158 int i, mi, min, size;
2159 assert(depot && off >= 0 && head);
2160 if(reusable){
2161 size = dprecsize(head);
2162 mi = -1;
2163 min = -1;
2164 for(i = 0; i < depot->fbpsiz; i += 2){
2165 if(depot->fbpool[i] == -1){
2166 depot->fbpool[i] = off;
2167 depot->fbpool[i+1] = size;
2168 dpfbpoolcoal(depot);
2169 mi = -1;
2170 break;
2171 }
2172 if(mi == -1 || depot->fbpool[i+1] < min){
2173 mi = i;
2174 min = depot->fbpool[i+1];
2175 }
2176 }
2177 if(mi >= 0 && size > min){
2178 depot->fbpool[mi] = off;
2179 depot->fbpool[mi+1] = size;
2180 dpfbpoolcoal(depot);
2181 }
2182 }
2183 return dpseekwritenum(depot->fd, off + DP_RHIFLAGS * sizeof(int),
2184 DP_RECFDEL | (reusable ? DP_RECFREUSE : 0));
2185 }
2186
2187
2188 /* Make contiguous records of the free block pool coalesce.
2189 `depot' specifies a database handle. */
dpfbpoolcoal(DEPOT * depot)2190 static void dpfbpoolcoal(DEPOT *depot){
2191 int i;
2192 assert(depot);
2193 if(depot->fbpinc++ <= depot->fbpsiz / 4) return;
2194 depot->fbpinc = 0;
2195 qsort(depot->fbpool, depot->fbpsiz / 2, sizeof(int) * 2, dpfbpoolcmp);
2196 for(i = 2; i < depot->fbpsiz; i += 2){
2197 if(depot->fbpool[i-2] > 0 &&
2198 depot->fbpool[i-2] + depot->fbpool[i-1] - depot->fbpool[i] == 0){
2199 depot->fbpool[i] = depot->fbpool[i-2];
2200 depot->fbpool[i+1] += depot->fbpool[i-1];
2201 depot->fbpool[i-2] = -1;
2202 depot->fbpool[i-1] = -1;
2203 }
2204 }
2205 }
2206
2207
2208 /* Compare two records of the free block pool.
2209 `a' specifies the pointer to one record.
2210 `b' specifies the pointer to the other record.
2211 The return value is 0 if two equals, positive if the formar is big, else, negative. */
dpfbpoolcmp(const void * a,const void * b)2212 static int dpfbpoolcmp(const void *a, const void *b){
2213 assert(a && b);
2214 return *(int *)a - *(int *)b;
2215 }
2216
2217
2218
2219 /* END OF FILE */
2220