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