diff options
Diffstat (limited to 'qdbm/depot.c')
-rw-r--r-- | qdbm/depot.c | 2219 |
1 files changed, 0 insertions, 2219 deletions
diff --git a/qdbm/depot.c b/qdbm/depot.c deleted file mode 100644 index 717335b8..00000000 --- a/qdbm/depot.c +++ /dev/null @@ -1,2219 +0,0 @@ -/************************************************************************************************* - * Implementation of Depot - * Copyright (C) 2000-2007 Mikio Hirabayashi - * This file is part of QDBM, Quick Database Manager. - * QDBM is free software; you can redistribute it and/or modify it under the terms of the GNU - * Lesser General Public License as published by the Free Software Foundation; either version - * 2.1 of the License or any later version. QDBM is distributed in the hope that it will be - * useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or - * FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more - * details. - * You should have received a copy of the GNU Lesser General Public License along with QDBM; if - * not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA - * 02111-1307 USA. - *************************************************************************************************/ - - -#define QDBM_INTERNAL 1 - -#include "depot.h" -#include "myconf.h" - -#define DP_FILEMODE 00644 /* permission of a creating file */ -#define DP_MAGICNUMB "[DEPOT]\n\f" /* magic number on environments of big endian */ -#define DP_MAGICNUML "[depot]\n\f" /* magic number on environments of little endian */ -#define DP_HEADSIZ 48 /* size of the reagion of the header */ -#define DP_LIBVEROFF 12 /* offset of the region for the library version */ -#define DP_FLAGSOFF 16 /* offset of the region for flags */ -#define DP_FSIZOFF 24 /* offset of the region for the file size */ -#define DP_BNUMOFF 32 /* offset of the region for the bucket number */ -#define DP_RNUMOFF 40 /* offset of the region for the record number */ -#define DP_DEFBNUM 8191 /* default bucket number */ -#define DP_FBPOOLSIZ 16 /* size of free block pool */ -#define DP_ENTBUFSIZ 128 /* size of the entity buffer */ -#define DP_STKBUFSIZ 256 /* size of the stack key buffer */ -#define DP_WRTBUFSIZ 8192 /* size of the writing buffer */ -#define DP_FSBLKSIZ 4096 /* size of a block of the file system */ -#define DP_TMPFSUF MYEXTSTR "dptmp" /* suffix of a temporary file */ -#define DP_OPTBLOAD 0.25 /* ratio of bucket loading at optimization */ -#define DP_OPTRUNIT 256 /* number of records in a process of optimization */ -#define DP_NUMBUFSIZ 32 /* size of a buffer for a number */ -#define DP_IOBUFSIZ 8192 /* size of an I/O buffer */ - -/* get the first hash value */ -#define DP_FIRSTHASH(DP_res, DP_kbuf, DP_ksiz) \ - do { \ - const unsigned char *_DP_p; \ - int _DP_ksiz; \ - _DP_p = (const unsigned char *)(DP_kbuf); \ - _DP_ksiz = DP_ksiz; \ - if((_DP_ksiz) == sizeof(int)){ \ - memcpy(&(DP_res), (DP_kbuf), sizeof(int)); \ - } else { \ - (DP_res) = 751; \ - } \ - while(_DP_ksiz--){ \ - (DP_res) = (DP_res) * 31 + *(_DP_p)++; \ - } \ - (DP_res) = ((DP_res) * 87767623) & INT_MAX; \ - } while(FALSE) - -/* get the second hash value */ -#define DP_SECONDHASH(DP_res, DP_kbuf, DP_ksiz) \ - do { \ - const unsigned char *_DP_p; \ - int _DP_ksiz; \ - _DP_p = (const unsigned char *)(DP_kbuf) + DP_ksiz - 1; \ - _DP_ksiz = DP_ksiz; \ - for((DP_res) = 19780211; _DP_ksiz--;){ \ - (DP_res) = (DP_res) * 37 + *(_DP_p)--; \ - } \ - (DP_res) = ((DP_res) * 43321879) & INT_MAX; \ - } while(FALSE) - -/* get the third hash value */ -#define DP_THIRDHASH(DP_res, DP_kbuf, DP_ksiz) \ - do { \ - int _DP_i; \ - (DP_res) = 774831917; \ - for(_DP_i = (DP_ksiz) - 1; _DP_i >= 0; _DP_i--){ \ - (DP_res) = (DP_res) * 29 + ((const unsigned char *)(DP_kbuf))[_DP_i]; \ - } \ - (DP_res) = ((DP_res) * 5157883) & INT_MAX; \ - } while(FALSE) - -enum { /* enumeration for a record header */ - DP_RHIFLAGS, /* offset of flags */ - DP_RHIHASH, /* offset of value of the second hash function */ - DP_RHIKSIZ, /* offset of the size of the key */ - DP_RHIVSIZ, /* offset of the size of the value */ - DP_RHIPSIZ, /* offset of the size of the padding bytes */ - DP_RHILEFT, /* offset of the offset of the left child */ - DP_RHIRIGHT, /* offset of the offset of the right child */ - DP_RHNUM /* number of elements of a header */ -}; - -enum { /* enumeration for the flag of a record */ - DP_RECFDEL = 1 << 0, /* deleted */ - DP_RECFREUSE = 1 << 1 /* reusable */ -}; - - -/* private function prototypes */ -static int dpbigendian(void); -static char *dpstrdup(const char *str); -static int dplock(int fd, int ex, int nb); -static int dpwrite(int fd, const void *buf, int size); -static int dpseekwrite(int fd, int off, const void *buf, int size); -static int dpseekwritenum(int fd, int off, int num); -static int dpread(int fd, void *buf, int size); -static int dpseekread(int fd, int off, void *buf, int size); -static int dpfcopy(int destfd, int destoff, int srcfd, int srcoff); -static int dpgetprime(int num); -static int dppadsize(DEPOT *depot, int ksiz, int vsiz); -static int dprecsize(int *head); -static int dprechead(DEPOT *depot, int off, int *head, char *ebuf, int *eep); -static char *dpreckey(DEPOT *depot, int off, int *head); -static char *dprecval(DEPOT *depot, int off, int *head, int start, int max); -static int dprecvalwb(DEPOT *depot, int off, int *head, int start, int max, char *vbuf); -static int dpkeycmp(const char *abuf, int asiz, const char *bbuf, int bsiz); -static int dprecsearch(DEPOT *depot, const char *kbuf, int ksiz, int hash, int *bip, int *offp, - int *entp, int *head, char *ebuf, int *eep, int delhit); -static int dprecrewrite(DEPOT *depot, int off, int rsiz, const char *kbuf, int ksiz, - const char *vbuf, int vsiz, int hash, int left, int right); -static int dprecappend(DEPOT *depot, const char *kbuf, int ksiz, const char *vbuf, int vsiz, - int hash, int left, int right); -static int dprecover(DEPOT *depot, int off, int *head, const char *vbuf, int vsiz, int cat); -static int dprecdelete(DEPOT *depot, int off, int *head, int reusable); -static void dpfbpoolcoal(DEPOT *depot); -static int dpfbpoolcmp(const void *a, const void *b); - - - -/************************************************************************************************* - * public objects - *************************************************************************************************/ - - -/* String containing the version information. */ -const char *dpversion = _QDBM_VERSION; - - -/* Get a message string corresponding to an error code. */ -const char *dperrmsg(int ecode){ - switch(ecode){ - case DP_ENOERR: return "no error"; - case DP_EFATAL: return "with fatal error"; - case DP_EMODE: return "invalid mode"; - case DP_EBROKEN: return "broken database file"; - case DP_EKEEP: return "existing record"; - case DP_ENOITEM: return "no item found"; - case DP_EALLOC: return "memory allocation error"; - case DP_EMAP: return "memory mapping error"; - case DP_EOPEN: return "open error"; - case DP_ECLOSE: return "close error"; - case DP_ETRUNC: return "trunc error"; - case DP_ESYNC: return "sync error"; - case DP_ESTAT: return "stat error"; - case DP_ESEEK: return "seek error"; - case DP_EREAD: return "read error"; - case DP_EWRITE: return "write error"; - case DP_ELOCK: return "lock error"; - case DP_EUNLINK: return "unlink error"; - case DP_EMKDIR: return "mkdir error"; - case DP_ERMDIR: return "rmdir error"; - case DP_EMISC: return "miscellaneous error"; - } - return "(invalid ecode)"; -} - - -/* Get a database handle. */ -DEPOT *dpopen(const char *name, int omode, int bnum){ - char hbuf[DP_HEADSIZ], *map, c, *tname; - int i, mode, fd, inode, fsiz, rnum, msiz, *fbpool; - struct stat sbuf; - time_t mtime; - DEPOT *depot; - assert(name); - mode = O_RDONLY; - if(omode & DP_OWRITER){ - mode = O_RDWR; - if(omode & DP_OCREAT) mode |= O_CREAT; - } - if((fd = open(name, mode, DP_FILEMODE)) == -1){ - dpecodeset(DP_EOPEN, __FILE__, __LINE__); - return NULL; - } - if(!(omode & DP_ONOLCK)){ - if(!dplock(fd, omode & DP_OWRITER, omode & DP_OLCKNB)){ - close(fd); - return NULL; - } - } - if((omode & DP_OWRITER) && (omode & DP_OTRUNC)){ - if(ftruncate(fd, 0) == -1){ - close(fd); - dpecodeset(DP_ETRUNC, __FILE__, __LINE__); - return NULL; - } - } - if(fstat(fd, &sbuf) == -1 || !S_ISREG(sbuf.st_mode) || - (sbuf.st_ino == 0 && lstat(name, &sbuf) == -1)){ - close(fd); - dpecodeset(DP_ESTAT, __FILE__, __LINE__); - return NULL; - } - inode = sbuf.st_ino; - mtime = sbuf.st_mtime; - fsiz = sbuf.st_size; - if((omode & DP_OWRITER) && fsiz == 0){ - memset(hbuf, 0, DP_HEADSIZ); - if(dpbigendian()){ - memcpy(hbuf, DP_MAGICNUMB, strlen(DP_MAGICNUMB)); - } else { - memcpy(hbuf, DP_MAGICNUML, strlen(DP_MAGICNUML)); - } - sprintf(hbuf + DP_LIBVEROFF, "%d", _QDBM_LIBVER / 100); - bnum = bnum < 1 ? DP_DEFBNUM : bnum; - bnum = dpgetprime(bnum); - memcpy(hbuf + DP_BNUMOFF, &bnum, sizeof(int)); - rnum = 0; - memcpy(hbuf + DP_RNUMOFF, &rnum, sizeof(int)); - fsiz = DP_HEADSIZ + bnum * sizeof(int); - memcpy(hbuf + DP_FSIZOFF, &fsiz, sizeof(int)); - if(!dpseekwrite(fd, 0, hbuf, DP_HEADSIZ)){ - close(fd); - return NULL; - } - if(omode & DP_OSPARSE){ - c = 0; - if(!dpseekwrite(fd, fsiz - 1, &c, 1)){ - close(fd); - return NULL; - } - } else { - if(!(map = malloc(bnum * sizeof(int)))){ - close(fd); - dpecodeset(DP_EALLOC, __FILE__, __LINE__); - return NULL; - } - memset(map, 0, bnum * sizeof(int)); - if(!dpseekwrite(fd, DP_HEADSIZ, map, bnum * sizeof(int))){ - free(map); - close(fd); - return NULL; - } - free(map); - } - } - if(!dpseekread(fd, 0, hbuf, DP_HEADSIZ)){ - close(fd); - dpecodeset(DP_EBROKEN, __FILE__, __LINE__); - return NULL; - } - if(!(omode & DP_ONOLCK) && - ((dpbigendian() ? memcmp(hbuf, DP_MAGICNUMB, strlen(DP_MAGICNUMB)) != 0 : - memcmp(hbuf, DP_MAGICNUML, strlen(DP_MAGICNUML)) != 0) || - *((int *)(hbuf + DP_FSIZOFF)) != fsiz)){ - close(fd); - dpecodeset(DP_EBROKEN, __FILE__, __LINE__); - return NULL; - } - bnum = *((int *)(hbuf + DP_BNUMOFF)); - rnum = *((int *)(hbuf + DP_RNUMOFF)); - if(bnum < 1 || rnum < 0 || fsiz < DP_HEADSIZ + bnum * sizeof(int)){ - close(fd); - dpecodeset(DP_EBROKEN, __FILE__, __LINE__); - return NULL; - } - msiz = DP_HEADSIZ + bnum * sizeof(int); - map = mmap(0, msiz, PROT_READ | ((mode & DP_OWRITER) ? PROT_WRITE : 0), MAP_SHARED, fd, 0); - if(map == MAP_FAILED){ - close(fd); - dpecodeset(DP_EMAP, __FILE__, __LINE__); - return NULL; - } - tname = NULL; - fbpool = NULL; - if(!(depot = malloc(sizeof(DEPOT))) || !(tname = dpstrdup(name)) || - !(fbpool = malloc(DP_FBPOOLSIZ * 2 * sizeof(int)))){ - free(fbpool); - free(tname); - free(depot); - munmap(map, msiz); - close(fd); - dpecodeset(DP_EALLOC, __FILE__, __LINE__); - return NULL; - } - depot->name = tname; - depot->wmode = (mode & DP_OWRITER); - depot->inode = inode; - depot->mtime = mtime; - depot->fd = fd; - depot->fsiz = fsiz; - depot->map = map; - depot->msiz = msiz; - depot->buckets = (int *)(map + DP_HEADSIZ); - depot->bnum = bnum; - depot->rnum = rnum; - depot->fatal = FALSE; - depot->ioff = 0; - depot->fbpool = fbpool; - for(i = 0; i < DP_FBPOOLSIZ * 2; i += 2){ - depot->fbpool[i] = -1; - depot->fbpool[i+1] = -1; - } - depot->fbpsiz = DP_FBPOOLSIZ * 2; - depot->fbpinc = 0; - depot->align = 0; - return depot; -} - - -/* Close a database handle. */ -int dpclose(DEPOT *depot){ - int fatal, err; - assert(depot); - fatal = depot->fatal; - err = FALSE; - if(depot->wmode){ - *((int *)(depot->map + DP_FSIZOFF)) = depot->fsiz; - *((int *)(depot->map + DP_RNUMOFF)) = depot->rnum; - } - if(depot->map != MAP_FAILED){ - if(munmap(depot->map, depot->msiz) == -1){ - err = TRUE; - dpecodeset(DP_EMAP, __FILE__, __LINE__); - } - } - if(close(depot->fd) == -1){ - err = TRUE; - dpecodeset(DP_ECLOSE, __FILE__, __LINE__); - } - free(depot->fbpool); - free(depot->name); - free(depot); - if(fatal){ - dpecodeset(DP_EFATAL, __FILE__, __LINE__); - return FALSE; - } - return err ? FALSE : TRUE; -} - - -/* Store a record. */ -int dpput(DEPOT *depot, const char *kbuf, int ksiz, const char *vbuf, int vsiz, int dmode){ - int head[DP_RHNUM], next[DP_RHNUM]; - int i, hash, bi, off, entoff, ee, newoff, rsiz, nsiz, fdel, mroff, mrsiz, mi, min; - char ebuf[DP_ENTBUFSIZ], *tval, *swap; - assert(depot && kbuf && vbuf); - if(depot->fatal){ - dpecodeset(DP_EFATAL, __FILE__, __LINE__); - return FALSE; - } - if(!depot->wmode){ - dpecodeset(DP_EMODE, __FILE__, __LINE__); - return FALSE; - } - if(ksiz < 0) ksiz = strlen(kbuf); - if(vsiz < 0) vsiz = strlen(vbuf); - newoff = -1; - DP_SECONDHASH(hash, kbuf, ksiz); - switch(dprecsearch(depot, kbuf, ksiz, hash, &bi, &off, &entoff, head, ebuf, &ee, TRUE)){ - case -1: - depot->fatal = TRUE; - return FALSE; - case 0: - fdel = head[DP_RHIFLAGS] & DP_RECFDEL; - if(dmode == DP_DKEEP && !fdel){ - dpecodeset(DP_EKEEP, __FILE__, __LINE__); - return FALSE; - } - if(fdel){ - head[DP_RHIPSIZ] += head[DP_RHIVSIZ]; - head[DP_RHIVSIZ] = 0; - } - rsiz = dprecsize(head); - nsiz = DP_RHNUM * sizeof(int) + ksiz + vsiz; - if(dmode == DP_DCAT) nsiz += head[DP_RHIVSIZ]; - if(off + rsiz >= depot->fsiz){ - if(rsiz < nsiz){ - head[DP_RHIPSIZ] += nsiz - rsiz; - rsiz = nsiz; - depot->fsiz = off + rsiz; - } - } else { - while(nsiz > rsiz && off + rsiz < depot->fsiz){ - if(!dprechead(depot, off + rsiz, next, NULL, NULL)) return FALSE; - if(!(next[DP_RHIFLAGS] & DP_RECFREUSE)) break; - head[DP_RHIPSIZ] += dprecsize(next); - rsiz += dprecsize(next); - } - for(i = 0; i < depot->fbpsiz; i += 2){ - if(depot->fbpool[i] >= off && depot->fbpool[i] < off + rsiz){ - depot->fbpool[i] = -1; - depot->fbpool[i+1] = -1; - } - } - } - if(nsiz <= rsiz){ - if(!dprecover(depot, off, head, vbuf, vsiz, dmode == DP_DCAT)){ - depot->fatal = TRUE; - return FALSE; - } - } else { - tval = NULL; - if(dmode == DP_DCAT){ - if(ee && DP_RHNUM * sizeof(int) + head[DP_RHIKSIZ] + head[DP_RHIVSIZ] <= DP_ENTBUFSIZ){ - if(!(tval = malloc(head[DP_RHIVSIZ] + vsiz + 1))){ - dpecodeset(DP_EALLOC, __FILE__, __LINE__); - depot->fatal = TRUE; - return FALSE; - } - memcpy(tval, ebuf + (DP_RHNUM * sizeof(int) + head[DP_RHIKSIZ]), head[DP_RHIVSIZ]); - } else { - if(!(tval = dprecval(depot, off, head, 0, -1))){ - depot->fatal = TRUE; - return FALSE; - } - if(!(swap = realloc(tval, head[DP_RHIVSIZ] + vsiz + 1))){ - free(tval); - dpecodeset(DP_EALLOC, __FILE__, __LINE__); - depot->fatal = TRUE; - return FALSE; - } - tval = swap; - } - memcpy(tval + head[DP_RHIVSIZ], vbuf, vsiz); - vsiz += head[DP_RHIVSIZ]; - vbuf = tval; - } - mi = -1; - min = -1; - for(i = 0; i < depot->fbpsiz; i += 2){ - if(depot->fbpool[i+1] < nsiz) continue; - if(mi == -1 || depot->fbpool[i+1] < min){ - mi = i; - min = depot->fbpool[i+1]; - } - } - if(mi >= 0){ - mroff = depot->fbpool[mi]; - mrsiz = depot->fbpool[mi+1]; - depot->fbpool[mi] = -1; - depot->fbpool[mi+1] = -1; - } else { - mroff = -1; - mrsiz = -1; - } - if(!dprecdelete(depot, off, head, TRUE)){ - free(tval); - depot->fatal = TRUE; - return FALSE; - } - if(mroff > 0 && nsiz <= mrsiz){ - if(!dprecrewrite(depot, mroff, mrsiz, kbuf, ksiz, vbuf, vsiz, - hash, head[DP_RHILEFT], head[DP_RHIRIGHT])){ - free(tval); - depot->fatal = TRUE; - return FALSE; - } - newoff = mroff; - } else { - if((newoff = dprecappend(depot, kbuf, ksiz, vbuf, vsiz, - hash, head[DP_RHILEFT], head[DP_RHIRIGHT])) == -1){ - free(tval); - depot->fatal = TRUE; - return FALSE; - } - } - free(tval); - } - if(fdel) depot->rnum++; - break; - default: - if((newoff = dprecappend(depot, kbuf, ksiz, vbuf, vsiz, hash, 0, 0)) == -1){ - depot->fatal = TRUE; - return FALSE; - } - depot->rnum++; - break; - } - if(newoff > 0){ - if(entoff > 0){ - if(!dpseekwritenum(depot->fd, entoff, newoff)){ - depot->fatal = TRUE; - return FALSE; - } - } else { - depot->buckets[bi] = newoff; - } - } - return TRUE; -} - - -/* Delete a record. */ -int dpout(DEPOT *depot, const char *kbuf, int ksiz){ - int head[DP_RHNUM], hash, bi, off, entoff, ee; - char ebuf[DP_ENTBUFSIZ]; - assert(depot && kbuf); - if(depot->fatal){ - dpecodeset(DP_EFATAL, __FILE__, __LINE__); - return FALSE; - } - if(!depot->wmode){ - dpecodeset(DP_EMODE, __FILE__, __LINE__); - return FALSE; - } - if(ksiz < 0) ksiz = strlen(kbuf); - DP_SECONDHASH(hash, kbuf, ksiz); - switch(dprecsearch(depot, kbuf, ksiz, hash, &bi, &off, &entoff, head, ebuf, &ee, FALSE)){ - case -1: - depot->fatal = TRUE; - return FALSE; - case 0: - break; - default: - dpecodeset(DP_ENOITEM, __FILE__, __LINE__); - return FALSE; - } - if(!dprecdelete(depot, off, head, FALSE)){ - depot->fatal = TRUE; - return FALSE; - } - depot->rnum--; - return TRUE; -} - - -/* Retrieve a record. */ -char *dpget(DEPOT *depot, const char *kbuf, int ksiz, int start, int max, int *sp){ - int head[DP_RHNUM], hash, bi, off, entoff, ee, vsiz; - char ebuf[DP_ENTBUFSIZ], *vbuf; - assert(depot && kbuf && start >= 0); - if(depot->fatal){ - dpecodeset(DP_EFATAL, __FILE__, __LINE__); - return NULL; - } - if(ksiz < 0) ksiz = strlen(kbuf); - DP_SECONDHASH(hash, kbuf, ksiz); - switch(dprecsearch(depot, kbuf, ksiz, hash, &bi, &off, &entoff, head, ebuf, &ee, FALSE)){ - case -1: - depot->fatal = TRUE; - return NULL; - case 0: - break; - default: - dpecodeset(DP_ENOITEM, __FILE__, __LINE__); - return NULL; - } - if(start > head[DP_RHIVSIZ]){ - dpecodeset(DP_ENOITEM, __FILE__, __LINE__); - return NULL; - } - if(ee && DP_RHNUM * sizeof(int) + head[DP_RHIKSIZ] + head[DP_RHIVSIZ] <= DP_ENTBUFSIZ){ - head[DP_RHIVSIZ] -= start; - if(max < 0){ - vsiz = head[DP_RHIVSIZ]; - } else { - vsiz = max < head[DP_RHIVSIZ] ? max : head[DP_RHIVSIZ]; - } - if(!(vbuf = malloc(vsiz + 1))){ - dpecodeset(DP_EALLOC, __FILE__, __LINE__); - depot->fatal = TRUE; - return NULL; - } - memcpy(vbuf, ebuf + (DP_RHNUM * sizeof(int) + head[DP_RHIKSIZ] + start), vsiz); - vbuf[vsiz] = '\0'; - } else { - if(!(vbuf = dprecval(depot, off, head, start, max))){ - depot->fatal = TRUE; - return NULL; - } - } - if(sp){ - if(max < 0){ - *sp = head[DP_RHIVSIZ]; - } else { - *sp = max < head[DP_RHIVSIZ] ? max : head[DP_RHIVSIZ]; - } - } - return vbuf; -} - - -/* Retrieve a record and write the value into a buffer. */ -int dpgetwb(DEPOT *depot, const char *kbuf, int ksiz, int start, int max, char *vbuf){ - int head[DP_RHNUM], hash, bi, off, entoff, ee, vsiz; - char ebuf[DP_ENTBUFSIZ]; - assert(depot && kbuf && start >= 0 && max >= 0 && vbuf); - if(depot->fatal){ - dpecodeset(DP_EFATAL, __FILE__, __LINE__); - return -1; - } - if(ksiz < 0) ksiz = strlen(kbuf); - DP_SECONDHASH(hash, kbuf, ksiz); - switch(dprecsearch(depot, kbuf, ksiz, hash, &bi, &off, &entoff, head, ebuf, &ee, FALSE)){ - case -1: - depot->fatal = TRUE; - return -1; - case 0: - break; - default: - dpecodeset(DP_ENOITEM, __FILE__, __LINE__); - return -1; - } - if(start > head[DP_RHIVSIZ]){ - dpecodeset(DP_ENOITEM, __FILE__, __LINE__); - return -1; - } - if(ee && DP_RHNUM * sizeof(int) + head[DP_RHIKSIZ] + head[DP_RHIVSIZ] <= DP_ENTBUFSIZ){ - head[DP_RHIVSIZ] -= start; - vsiz = max < head[DP_RHIVSIZ] ? max : head[DP_RHIVSIZ]; - memcpy(vbuf, ebuf + (DP_RHNUM * sizeof(int) + head[DP_RHIKSIZ] + start), vsiz); - } else { - if((vsiz = dprecvalwb(depot, off, head, start, max, vbuf)) == -1){ - depot->fatal = TRUE; - return -1; - } - } - return vsiz; -} - - -/* Get the size of the value of a record. */ -int dpvsiz(DEPOT *depot, const char *kbuf, int ksiz){ - int head[DP_RHNUM], hash, bi, off, entoff, ee; - char ebuf[DP_ENTBUFSIZ]; - assert(depot && kbuf); - if(depot->fatal){ - dpecodeset(DP_EFATAL, __FILE__, __LINE__); - return -1; - } - if(ksiz < 0) ksiz = strlen(kbuf); - DP_SECONDHASH(hash, kbuf, ksiz); - switch(dprecsearch(depot, kbuf, ksiz, hash, &bi, &off, &entoff, head, ebuf, &ee, FALSE)){ - case -1: - depot->fatal = TRUE; - return -1; - case 0: - break; - default: - dpecodeset(DP_ENOITEM, __FILE__, __LINE__); - return -1; - } - return head[DP_RHIVSIZ]; -} - - -/* Initialize the iterator of a database handle. */ -int dpiterinit(DEPOT *depot){ - assert(depot); - if(depot->fatal){ - dpecodeset(DP_EFATAL, __FILE__, __LINE__); - return FALSE; - } - depot->ioff = 0; - return TRUE; -} - - -/* Get the next key of the iterator. */ -char *dpiternext(DEPOT *depot, int *sp){ - int off, head[DP_RHNUM], ee; - char ebuf[DP_ENTBUFSIZ], *kbuf; - assert(depot); - if(depot->fatal){ - dpecodeset(DP_EFATAL, __FILE__, __LINE__); - return NULL; - } - off = DP_HEADSIZ + depot->bnum * sizeof(int); - off = off > depot->ioff ? off : depot->ioff; - while(off < depot->fsiz){ - if(!dprechead(depot, off, head, ebuf, &ee)){ - depot->fatal = TRUE; - return NULL; - } - if(head[DP_RHIFLAGS] & DP_RECFDEL){ - off += dprecsize(head); - } else { - if(ee && DP_RHNUM * sizeof(int) + head[DP_RHIKSIZ] <= DP_ENTBUFSIZ){ - if(!(kbuf = malloc(head[DP_RHIKSIZ] + 1))){ - dpecodeset(DP_EALLOC, __FILE__, __LINE__); - depot->fatal = TRUE; - return NULL; - } - memcpy(kbuf, ebuf + (DP_RHNUM * sizeof(int)), head[DP_RHIKSIZ]); - kbuf[head[DP_RHIKSIZ]] = '\0'; - } else { - if(!(kbuf = dpreckey(depot, off, head))){ - depot->fatal = TRUE; - return NULL; - } - } - depot->ioff = off + dprecsize(head); - if(sp) *sp = head[DP_RHIKSIZ]; - return kbuf; - } - } - dpecodeset(DP_ENOITEM, __FILE__, __LINE__); - return NULL; -} - - -/* Set alignment of a database handle. */ -int dpsetalign(DEPOT *depot, int align){ - assert(depot); - if(depot->fatal){ - dpecodeset(DP_EFATAL, __FILE__, __LINE__); - return FALSE; - } - if(!depot->wmode){ - dpecodeset(DP_EMODE, __FILE__, __LINE__); - return FALSE; - } - depot->align = align; - return TRUE; -} - - -/* Set the size of the free block pool of a database handle. */ -int dpsetfbpsiz(DEPOT *depot, int size){ - int *fbpool; - int i; - assert(depot && size >= 0); - if(depot->fatal){ - dpecodeset(DP_EFATAL, __FILE__, __LINE__); - return FALSE; - } - if(!depot->wmode){ - dpecodeset(DP_EMODE, __FILE__, __LINE__); - return FALSE; - } - size *= 2; - if(!(fbpool = realloc(depot->fbpool, size * sizeof(int) + 1))){ - dpecodeset(DP_EALLOC, __FILE__, __LINE__); - return FALSE; - } - for(i = 0; i < size; i += 2){ - fbpool[i] = -1; - fbpool[i+1] = -1; - } - depot->fbpool = fbpool; - depot->fbpsiz = size; - return TRUE; -} - - - -/* Synchronize contents of updating a database with the file and the device. */ -int dpsync(DEPOT *depot){ - assert(depot); - if(depot->fatal){ - dpecodeset(DP_EFATAL, __FILE__, __LINE__); - return FALSE; - } - if(!depot->wmode){ - dpecodeset(DP_EMODE, __FILE__, __LINE__); - return FALSE; - } - *((int *)(depot->map + DP_FSIZOFF)) = depot->fsiz; - *((int *)(depot->map + DP_RNUMOFF)) = depot->rnum; - if(msync(depot->map, depot->msiz, MS_SYNC) == -1){ - dpecodeset(DP_EMAP, __FILE__, __LINE__); - depot->fatal = TRUE; - return FALSE; - } - if(fsync(depot->fd) == -1){ - dpecodeset(DP_ESYNC, __FILE__, __LINE__); - depot->fatal = TRUE; - return FALSE; - } - return TRUE; -} - - -/* Optimize a database. */ -int dpoptimize(DEPOT *depot, int bnum){ - DEPOT *tdepot; - char *name; - int i, err, off, head[DP_RHNUM], ee, ksizs[DP_OPTRUNIT], vsizs[DP_OPTRUNIT], unum; - char ebuf[DP_ENTBUFSIZ], *kbufs[DP_OPTRUNIT], *vbufs[DP_OPTRUNIT]; - assert(depot); - if(depot->fatal){ - dpecodeset(DP_EFATAL, __FILE__, __LINE__); - return FALSE; - } - if(!depot->wmode){ - dpecodeset(DP_EMODE, __FILE__, __LINE__); - return FALSE; - } - if(!(name = malloc(strlen(depot->name) + strlen(DP_TMPFSUF) + 1))){ - dpecodeset(DP_EALLOC, __FILE__, __LINE__); - depot->fatal = FALSE; - return FALSE; - } - sprintf(name, "%s%s", depot->name, DP_TMPFSUF); - if(bnum < 0){ - bnum = (int)(depot->rnum * (1.0 / DP_OPTBLOAD)) + 1; - if(bnum < DP_DEFBNUM / 2) bnum = DP_DEFBNUM / 2; - } - if(!(tdepot = dpopen(name, DP_OWRITER | DP_OCREAT | DP_OTRUNC, bnum))){ - free(name); - depot->fatal = TRUE; - return FALSE; - } - free(name); - if(!dpsetflags(tdepot, dpgetflags(depot))){ - dpclose(tdepot); - depot->fatal = TRUE; - return FALSE; - } - tdepot->align = depot->align; - err = FALSE; - off = DP_HEADSIZ + depot->bnum * sizeof(int); - unum = 0; - while(off < depot->fsiz){ - if(!dprechead(depot, off, head, ebuf, &ee)){ - err = TRUE; - break; - } - if(!(head[DP_RHIFLAGS] & DP_RECFDEL)){ - if(ee && DP_RHNUM * sizeof(int) + head[DP_RHIKSIZ] <= DP_ENTBUFSIZ){ - if(!(kbufs[unum] = malloc(head[DP_RHIKSIZ] + 1))){ - dpecodeset(DP_EALLOC, __FILE__, __LINE__); - err = TRUE; - break; - } - memcpy(kbufs[unum], ebuf + (DP_RHNUM * sizeof(int)), head[DP_RHIKSIZ]); - if(DP_RHNUM * sizeof(int) + head[DP_RHIKSIZ] + head[DP_RHIVSIZ] <= DP_ENTBUFSIZ){ - if(!(vbufs[unum] = malloc(head[DP_RHIVSIZ] + 1))){ - dpecodeset(DP_EALLOC, __FILE__, __LINE__); - err = TRUE; - break; - } - memcpy(vbufs[unum], ebuf + (DP_RHNUM * sizeof(int) + head[DP_RHIKSIZ]), - head[DP_RHIVSIZ]); - } else { - vbufs[unum] = dprecval(depot, off, head, 0, -1); - } - } else { - kbufs[unum] = dpreckey(depot, off, head); - vbufs[unum] = dprecval(depot, off, head, 0, -1); - } - ksizs[unum] = head[DP_RHIKSIZ]; - vsizs[unum] = head[DP_RHIVSIZ]; - unum++; - if(unum >= DP_OPTRUNIT){ - for(i = 0; i < unum; i++){ - if(kbufs[i] && vbufs[i]){ - if(!dpput(tdepot, kbufs[i], ksizs[i], vbufs[i], vsizs[i], DP_DKEEP)) err = TRUE; - } else { - err = TRUE; - } - free(kbufs[i]); - free(vbufs[i]); - if(err) break; - } - unum = 0; - } - } - off += dprecsize(head); - if(err) break; - } - for(i = 0; i < unum; i++){ - if(kbufs[i] && vbufs[i]){ - if(!dpput(tdepot, kbufs[i], ksizs[i], vbufs[i], vsizs[i], DP_DKEEP)) err = TRUE; - } else { - err = TRUE; - } - free(kbufs[i]); - free(vbufs[i]); - if(err) break; - } - if(!dpsync(tdepot)) err = TRUE; - if(err){ - unlink(tdepot->name); - dpclose(tdepot); - depot->fatal = TRUE; - return FALSE; - } - if(munmap(depot->map, depot->msiz) == -1){ - dpclose(tdepot); - dpecodeset(DP_EMAP, __FILE__, __LINE__); - depot->fatal = TRUE; - return FALSE; - } - depot->map = MAP_FAILED; - if(ftruncate(depot->fd, 0) == -1){ - dpclose(tdepot); - unlink(tdepot->name); - dpecodeset(DP_ETRUNC, __FILE__, __LINE__); - depot->fatal = TRUE; - return FALSE; - } - if(dpfcopy(depot->fd, 0, tdepot->fd, 0) == -1){ - dpclose(tdepot); - unlink(tdepot->name); - depot->fatal = TRUE; - return FALSE; - } - depot->fsiz = tdepot->fsiz; - depot->bnum = tdepot->bnum; - depot->ioff = 0; - for(i = 0; i < depot->fbpsiz; i += 2){ - depot->fbpool[i] = -1; - depot->fbpool[i+1] = -1; - } - depot->msiz = tdepot->msiz; - depot->map = mmap(0, depot->msiz, PROT_READ | PROT_WRITE, MAP_SHARED, depot->fd, 0); - if(depot->map == MAP_FAILED){ - dpecodeset(DP_EMAP, __FILE__, __LINE__); - depot->fatal = TRUE; - return FALSE; - } - depot->buckets = (int *)(depot->map + DP_HEADSIZ); - if(!(name = dpname(tdepot))){ - dpclose(tdepot); - unlink(tdepot->name); - depot->fatal = TRUE; - return FALSE; - } - if(!dpclose(tdepot)){ - free(name); - unlink(tdepot->name); - depot->fatal = TRUE; - return FALSE; - } - if(unlink(name) == -1){ - free(name); - dpecodeset(DP_EUNLINK, __FILE__, __LINE__); - depot->fatal = TRUE; - return FALSE; - } - free(name); - return TRUE; -} - - -/* Get the name of a database. */ -char *dpname(DEPOT *depot){ - char *name; - assert(depot); - if(depot->fatal){ - dpecodeset(DP_EFATAL, __FILE__, __LINE__); - return NULL; - } - if(!(name = dpstrdup(depot->name))){ - dpecodeset(DP_EALLOC, __FILE__, __LINE__); - depot->fatal = TRUE; - return NULL; - } - return name; -} - - -/* Get the size of a database file. */ -int dpfsiz(DEPOT *depot){ - assert(depot); - if(depot->fatal){ - dpecodeset(DP_EFATAL, __FILE__, __LINE__); - return -1; - } - return depot->fsiz; -} - - -/* Get the number of the elements of the bucket array. */ -int dpbnum(DEPOT *depot){ - assert(depot); - if(depot->fatal){ - dpecodeset(DP_EFATAL, __FILE__, __LINE__); - return -1; - } - return depot->bnum; -} - - -/* Get the number of the used elements of the bucket array. */ -int dpbusenum(DEPOT *depot){ - int i, hits; - assert(depot); - if(depot->fatal){ - dpecodeset(DP_EFATAL, __FILE__, __LINE__); - return -1; - } - hits = 0; - for(i = 0; i < depot->bnum; i++){ - if(depot->buckets[i]) hits++; - } - return hits; -} - - -/* Get the number of the records stored in a database. */ -int dprnum(DEPOT *depot){ - assert(depot); - if(depot->fatal){ - dpecodeset(DP_EFATAL, __FILE__, __LINE__); - return -1; - } - return depot->rnum; -} - - -/* Check whether a database handle is a writer or not. */ -int dpwritable(DEPOT *depot){ - assert(depot); - return depot->wmode; -} - - -/* Check whether a database has a fatal error or not. */ -int dpfatalerror(DEPOT *depot){ - assert(depot); - return depot->fatal; -} - - -/* Get the inode number of a database file. */ -int dpinode(DEPOT *depot){ - assert(depot); - return depot->inode; -} - - -/* Get the last modified time of a database. */ -time_t dpmtime(DEPOT *depot){ - assert(depot); - return depot->mtime; -} - - -/* Get the file descriptor of a database file. */ -int dpfdesc(DEPOT *depot){ - assert(depot); - return depot->fd; -} - - -/* Remove a database file. */ -int dpremove(const char *name){ - struct stat sbuf; - DEPOT *depot; - assert(name); - if(lstat(name, &sbuf) == -1){ - dpecodeset(DP_ESTAT, __FILE__, __LINE__); - return FALSE; - } - if((depot = dpopen(name, DP_OWRITER | DP_OTRUNC, -1)) != NULL) dpclose(depot); - if(unlink(name) == -1){ - dpecodeset(DP_EUNLINK, __FILE__, __LINE__); - return FALSE; - } - return TRUE; -} - - -/* Repair a broken database file. */ -int dprepair(const char *name){ - DEPOT *tdepot; - char dbhead[DP_HEADSIZ], *tname, *kbuf, *vbuf; - int fd, fsiz, flags, bnum, tbnum, err, head[DP_RHNUM], off, rsiz, ksiz, vsiz; - struct stat sbuf; - assert(name); - if(lstat(name, &sbuf) == -1){ - dpecodeset(DP_ESTAT, __FILE__, __LINE__); - return FALSE; - } - fsiz = sbuf.st_size; - if((fd = open(name, O_RDWR, DP_FILEMODE)) == -1){ - dpecodeset(DP_EOPEN, __FILE__, __LINE__); - return FALSE; - } - if(!dpseekread(fd, 0, dbhead, DP_HEADSIZ)){ - close(fd); - return FALSE; - } - flags = *(int *)(dbhead + DP_FLAGSOFF); - bnum = *(int *)(dbhead + DP_BNUMOFF); - tbnum = *(int *)(dbhead + DP_RNUMOFF) * 2; - if(tbnum < DP_DEFBNUM) tbnum = DP_DEFBNUM; - if(!(tname = malloc(strlen(name) + strlen(DP_TMPFSUF) + 1))){ - dpecodeset(DP_EALLOC, __FILE__, __LINE__); - return FALSE; - } - sprintf(tname, "%s%s", name, DP_TMPFSUF); - if(!(tdepot = dpopen(tname, DP_OWRITER | DP_OCREAT | DP_OTRUNC, tbnum))){ - free(tname); - close(fd); - return FALSE; - } - err = FALSE; - off = DP_HEADSIZ + bnum * sizeof(int); - while(off < fsiz){ - if(!dpseekread(fd, off, head, DP_RHNUM * sizeof(int))) break; - if(head[DP_RHIFLAGS] & DP_RECFDEL){ - if((rsiz = dprecsize(head)) < 0) break; - off += rsiz; - continue; - } - ksiz = head[DP_RHIKSIZ]; - vsiz = head[DP_RHIVSIZ]; - if(ksiz >= 0 && vsiz >= 0){ - kbuf = malloc(ksiz + 1); - vbuf = malloc(vsiz + 1); - if(kbuf && vbuf){ - if(dpseekread(fd, off + DP_RHNUM * sizeof(int), kbuf, ksiz) && - dpseekread(fd, off + DP_RHNUM * sizeof(int) + ksiz, vbuf, vsiz)){ - if(!dpput(tdepot, kbuf, ksiz, vbuf, vsiz, DP_DKEEP)) err = TRUE; - } else { - err = TRUE; - } - } else { - if(!err) dpecodeset(DP_EALLOC, __FILE__, __LINE__); - err = TRUE; - } - free(vbuf); - free(kbuf); - } else { - if(!err) dpecodeset(DP_EBROKEN, __FILE__, __LINE__); - err = TRUE; - } - if((rsiz = dprecsize(head)) < 0) break; - off += rsiz; - } - if(!dpsetflags(tdepot, flags)) err = TRUE; - if(!dpsync(tdepot)) err = TRUE; - if(ftruncate(fd, 0) == -1){ - if(!err) dpecodeset(DP_ETRUNC, __FILE__, __LINE__); - err = TRUE; - } - if(dpfcopy(fd, 0, tdepot->fd, 0) == -1) err = TRUE; - if(!dpclose(tdepot)) err = TRUE; - if(close(fd) == -1){ - if(!err) dpecodeset(DP_ECLOSE, __FILE__, __LINE__); - err = TRUE; - } - if(unlink(tname) == -1){ - if(!err) dpecodeset(DP_EUNLINK, __FILE__, __LINE__); - err = TRUE; - } - free(tname); - return err ? FALSE : TRUE; -} - - -/* Dump all records as endian independent data. */ -int dpexportdb(DEPOT *depot, const char *name){ - char *kbuf, *vbuf, *pbuf; - int fd, err, ksiz, vsiz, psiz; - assert(depot && name); - if(!(dpiterinit(depot))) return FALSE; - if((fd = open(name, O_RDWR | O_CREAT | O_TRUNC, DP_FILEMODE)) == -1){ - dpecodeset(DP_EOPEN, __FILE__, __LINE__); - return FALSE; - } - err = FALSE; - while(!err && (kbuf = dpiternext(depot, &ksiz)) != NULL){ - if((vbuf = dpget(depot, kbuf, ksiz, 0, -1, &vsiz)) != NULL){ - if((pbuf = malloc(ksiz + vsiz + DP_NUMBUFSIZ * 2)) != NULL){ - psiz = 0; - psiz += sprintf(pbuf + psiz, "%X\n%X\n", ksiz, vsiz); - memcpy(pbuf + psiz, kbuf, ksiz); - psiz += ksiz; - pbuf[psiz++] = '\n'; - memcpy(pbuf + psiz, vbuf, vsiz); - psiz += vsiz; - pbuf[psiz++] = '\n'; - if(!dpwrite(fd, pbuf, psiz)){ - dpecodeset(DP_EWRITE, __FILE__, __LINE__); - err = TRUE; - } - free(pbuf); - } else { - dpecodeset(DP_EALLOC, __FILE__, __LINE__); - err = TRUE; - } - free(vbuf); - } else { - err = TRUE; - } - free(kbuf); - } - if(close(fd) == -1){ - if(!err) dpecodeset(DP_ECLOSE, __FILE__, __LINE__); - return FALSE; - } - return !err && !dpfatalerror(depot); -} - - -/* Load all records from endian independent data. */ -int dpimportdb(DEPOT *depot, const char *name){ - char mbuf[DP_IOBUFSIZ], *rbuf; - int i, j, fd, err, fsiz, off, msiz, ksiz, vsiz, hlen; - struct stat sbuf; - assert(depot && name); - if(!depot->wmode){ - dpecodeset(DP_EMODE, __FILE__, __LINE__); - return FALSE; - } - if(dprnum(depot) > 0){ - dpecodeset(DP_EMISC, __FILE__, __LINE__); - return FALSE; - } - if((fd = open(name, O_RDONLY, DP_FILEMODE)) == -1){ - dpecodeset(DP_EOPEN, __FILE__, __LINE__); - return FALSE; - } - if(fstat(fd, &sbuf) == -1 || !S_ISREG(sbuf.st_mode)){ - dpecodeset(DP_ESTAT, __FILE__, __LINE__); - close(fd); - return FALSE; - } - err = FALSE; - fsiz = sbuf.st_size; - off = 0; - while(!err && off < fsiz){ - msiz = fsiz - off; - if(msiz > DP_IOBUFSIZ) msiz = DP_IOBUFSIZ; - if(!dpseekread(fd, off, mbuf, msiz)){ - err = TRUE; - break; - } - hlen = 0; - ksiz = -1; - vsiz = -1; - for(i = 0; i < msiz; i++){ - if(mbuf[i] == '\n'){ - mbuf[i] = '\0'; - ksiz = strtol(mbuf, NULL, 16); - for(j = i + 1; j < msiz; j++){ - if(mbuf[j] == '\n'){ - mbuf[j] = '\0'; - vsiz = strtol(mbuf + i + 1, NULL, 16); - hlen = j + 1; - break; - } - } - break; - } - } - if(ksiz < 0 || vsiz < 0 || hlen < 4){ - dpecodeset(DP_EBROKEN, __FILE__, __LINE__); - err = TRUE; - break; - } - if(hlen + ksiz + vsiz + 2 < DP_IOBUFSIZ){ - if(!dpput(depot, mbuf + hlen, ksiz, mbuf + hlen + ksiz + 1, vsiz, DP_DKEEP)) err = TRUE; - } else { - if((rbuf = malloc(ksiz + vsiz + 2)) != NULL){ - if(dpseekread(fd, off + hlen, rbuf, ksiz + vsiz + 2)){ - if(!dpput(depot, rbuf, ksiz, rbuf + ksiz + 1, vsiz, DP_DKEEP)) err = TRUE; - } else { - err = TRUE; - } - free(rbuf); - } else { - dpecodeset(DP_EALLOC, __FILE__, __LINE__); - err = TRUE; - } - } - off += hlen + ksiz + vsiz + 2; - } - if(close(fd) == -1){ - if(!err) dpecodeset(DP_ECLOSE, __FILE__, __LINE__); - return FALSE; - } - return !err && !dpfatalerror(depot); -} - - -/* Retrieve a record directly from a database file. */ -char *dpsnaffle(const char *name, const char* kbuf, int ksiz, int *sp){ - char hbuf[DP_HEADSIZ], *map, *vbuf, *tkbuf; - int fd, fsiz, bnum, msiz, *buckets, hash, thash, head[DP_RHNUM], err, off, vsiz, tksiz, kcmp; - struct stat sbuf; - assert(name && kbuf); - if(ksiz < 0) ksiz = strlen(kbuf); - if((fd = open(name, O_RDONLY, DP_FILEMODE)) == -1){ - dpecodeset(DP_EOPEN, __FILE__, __LINE__); - return NULL; - } - if(fstat(fd, &sbuf) == -1 || !S_ISREG(sbuf.st_mode)){ - close(fd); - dpecodeset(DP_ESTAT, __FILE__, __LINE__); - return NULL; - } - fsiz = sbuf.st_size; - if(!dpseekread(fd, 0, hbuf, DP_HEADSIZ)){ - close(fd); - dpecodeset(DP_EBROKEN, __FILE__, __LINE__); - return NULL; - } - if(dpbigendian() ? memcmp(hbuf, DP_MAGICNUMB, strlen(DP_MAGICNUMB)) != 0 : - memcmp(hbuf, DP_MAGICNUML, strlen(DP_MAGICNUML)) != 0){ - close(fd); - dpecodeset(DP_EBROKEN, __FILE__, __LINE__); - return NULL; - } - bnum = *((int *)(hbuf + DP_BNUMOFF)); - if(bnum < 1 || fsiz < DP_HEADSIZ + bnum * sizeof(int)){ - close(fd); - dpecodeset(DP_EBROKEN, __FILE__, __LINE__); - return NULL; - } - msiz = DP_HEADSIZ + bnum * sizeof(int); - map = mmap(0, msiz, PROT_READ, MAP_SHARED, fd, 0); - if(map == MAP_FAILED){ - close(fd); - dpecodeset(DP_EMAP, __FILE__, __LINE__); - return NULL; - } - buckets = (int *)(map + DP_HEADSIZ); - err = FALSE; - vbuf = NULL; - vsiz = 0; - DP_SECONDHASH(hash, kbuf, ksiz); - DP_FIRSTHASH(thash, kbuf, ksiz); - off = buckets[thash%bnum]; - while(off != 0){ - if(!dpseekread(fd, off, head, DP_RHNUM * sizeof(int))){ - err = TRUE; - break; - } - if(head[DP_RHIKSIZ] < 0 || head[DP_RHIVSIZ] < 0 || head[DP_RHIPSIZ] < 0 || - head[DP_RHILEFT] < 0 || head[DP_RHIRIGHT] < 0){ - dpecodeset(DP_EBROKEN, __FILE__, __LINE__); - err = TRUE; - break; - } - thash = head[DP_RHIHASH]; - if(hash > thash){ - off = head[DP_RHILEFT]; - } else if(hash < thash){ - off = head[DP_RHIRIGHT]; - } else { - tksiz = head[DP_RHIKSIZ]; - if(!(tkbuf = malloc(tksiz + 1))){ - dpecodeset(DP_EALLOC, __FILE__, __LINE__); - err = TRUE; - break; - } - if(!dpseekread(fd, off + DP_RHNUM * sizeof(int), tkbuf, tksiz)){ - free(tkbuf); - err = TRUE; - break; - } - tkbuf[tksiz] = '\0'; - kcmp = dpkeycmp(kbuf, ksiz, tkbuf, tksiz); - free(tkbuf); - if(kcmp > 0){ - off = head[DP_RHILEFT]; - } else if(kcmp < 0){ - off = head[DP_RHIRIGHT]; - } else if(head[DP_RHIFLAGS] & DP_RECFDEL){ - break; - } else { - vsiz = head[DP_RHIVSIZ]; - if(!(vbuf = malloc(vsiz + 1))){ - dpecodeset(DP_EALLOC, __FILE__, __LINE__); - err = TRUE; - break; - } - if(!dpseekread(fd, off + DP_RHNUM * sizeof(int) + head[DP_RHIKSIZ], vbuf, vsiz)){ - free(vbuf); - vbuf = NULL; - err = TRUE; - break; - } - vbuf[vsiz] = '\0'; - break; - } - } - } - if(vbuf){ - if(sp) *sp = vsiz; - } else if(!err){ - dpecodeset(DP_ENOITEM, __FILE__, __LINE__); - } - munmap(map, msiz); - close(fd); - return vbuf; -} - - -/* Hash function used inside Depot. */ -int dpinnerhash(const char *kbuf, int ksiz){ - int res; - assert(kbuf); - if(ksiz < 0) ksiz = strlen(kbuf); - DP_FIRSTHASH(res, kbuf, ksiz); - return res; -} - - -/* Hash function which is independent from the hash functions used inside Depot. */ -int dpouterhash(const char *kbuf, int ksiz){ - int res; - assert(kbuf); - if(ksiz < 0) ksiz = strlen(kbuf); - DP_THIRDHASH(res, kbuf, ksiz); - return res; -} - - -/* Get a natural prime number not less than a number. */ -int dpprimenum(int num){ - assert(num > 0); - return dpgetprime(num); -} - - - -/************************************************************************************************* - * features for experts - *************************************************************************************************/ - - -/* Name of the operating system. */ -const char *dpsysname = _QDBM_SYSNAME; - - -/* File descriptor for debugging output. */ -int dpdbgfd = -1; - - -/* Whether this build is reentrant. */ -const int dpisreentrant = _qdbm_ptsafe; - - -/* Set the last happened error code. */ -void dpecodeset(int ecode, const char *file, int line){ - char iobuf[DP_IOBUFSIZ]; - assert(ecode >= DP_ENOERR && file && line >= 0); - dpecode = ecode; - if(dpdbgfd >= 0){ - fflush(stdout); - fflush(stderr); - sprintf(iobuf, "* dpecodeset: %s:%d: [%d] %s\n", file, line, ecode, dperrmsg(ecode)); - dpwrite(dpdbgfd, iobuf, strlen(iobuf)); - } -} - - -/* Get the pointer of the variable of the last happened error code. */ -int *dpecodeptr(void){ - static int defdpecode = DP_ENOERR; - void *ptr; - if(_qdbm_ptsafe){ - if(!(ptr = _qdbm_settsd(&defdpecode, sizeof(int), &defdpecode))){ - defdpecode = DP_EMISC; - return &defdpecode; - } - return (int *)ptr; - } - return &defdpecode; -} - - -/* Synchronize updating contents on memory. */ -int dpmemsync(DEPOT *depot){ - assert(depot); - if(depot->fatal){ - dpecodeset(DP_EFATAL, __FILE__, __LINE__); - return FALSE; - } - if(!depot->wmode){ - dpecodeset(DP_EMODE, __FILE__, __LINE__); - return FALSE; - } - *((int *)(depot->map + DP_FSIZOFF)) = depot->fsiz; - *((int *)(depot->map + DP_RNUMOFF)) = depot->rnum; - if(msync(depot->map, depot->msiz, MS_SYNC) == -1){ - dpecodeset(DP_EMAP, __FILE__, __LINE__); - depot->fatal = TRUE; - return FALSE; - } - return TRUE; -} - - -/* Synchronize updating contents on memory, not physically. */ -int dpmemflush(DEPOT *depot){ - assert(depot); - if(depot->fatal){ - dpecodeset(DP_EFATAL, __FILE__, __LINE__); - return FALSE; - } - if(!depot->wmode){ - dpecodeset(DP_EMODE, __FILE__, __LINE__); - return FALSE; - } - *((int *)(depot->map + DP_FSIZOFF)) = depot->fsiz; - *((int *)(depot->map + DP_RNUMOFF)) = depot->rnum; - if(mflush(depot->map, depot->msiz, MS_SYNC) == -1){ - dpecodeset(DP_EMAP, __FILE__, __LINE__); - depot->fatal = TRUE; - return FALSE; - } - return TRUE; -} - - -/* Get flags of a database. */ -int dpgetflags(DEPOT *depot){ - int flags; - assert(depot); - memcpy(&flags, depot->map + DP_FLAGSOFF, sizeof(int)); - return flags; -} - - -/* Set flags of a database. */ -int dpsetflags(DEPOT *depot, int flags){ - assert(depot); - if(!depot->wmode){ - dpecodeset(DP_EMODE, __FILE__, __LINE__); - return FALSE; - } - memcpy(depot->map + DP_FLAGSOFF, &flags, sizeof(int)); - return TRUE; -} - - - -/************************************************************************************************* - * private objects - *************************************************************************************************/ - - -/* Check whether the byte order of the platform is big endian or not. - The return value is true if bigendian, else, it is false. */ -static int dpbigendian(void){ - char buf[sizeof(int)]; - *(int *)buf = 1; - return !buf[0]; -} - - -/* Get a copied string. - `str' specifies an original string. - The return value is a copied string whose region is allocated by `malloc'. */ -static char *dpstrdup(const char *str){ - int len; - char *buf; - assert(str); - len = strlen(str); - if(!(buf = malloc(len + 1))) return NULL; - memcpy(buf, str, len + 1); - return buf; -} - - -/* Lock a file descriptor. - `fd' specifies a file descriptor. - `ex' specifies whether an exclusive lock or a shared lock is performed. - `nb' specifies whether to request with non-blocking. - The return value is true if successful, else, it is false. */ -static int dplock(int fd, int ex, int nb){ - struct flock lock; - assert(fd >= 0); - memset(&lock, 0, sizeof(struct flock)); - lock.l_type = ex ? F_WRLCK : F_RDLCK; - lock.l_whence = SEEK_SET; - lock.l_start = 0; - lock.l_len = 0; - lock.l_pid = 0; - while(fcntl(fd, nb ? F_SETLK : F_SETLKW, &lock) == -1){ - if(errno != EINTR){ - dpecodeset(DP_ELOCK, __FILE__, __LINE__); - return FALSE; - } - } - return TRUE; -} - - -/* Write into a file. - `fd' specifies a file descriptor. - `buf' specifies a buffer to write. - `size' specifies the size of the buffer. - The return value is the size of the written buffer, or, -1 on failure. */ -static int dpwrite(int fd, const void *buf, int size){ - const char *lbuf; - int rv, wb; - assert(fd >= 0 && buf && size >= 0); - lbuf = buf; - rv = 0; - do { - wb = write(fd, lbuf, size); - switch(wb){ - case -1: if(errno != EINTR) return -1; - case 0: break; - default: - lbuf += wb; - size -= wb; - rv += wb; - break; - } - } while(size > 0); - return rv; -} - - -/* Write into a file at an offset. - `fd' specifies a file descriptor. - `off' specifies an offset of the file. - `buf' specifies a buffer to write. - `size' specifies the size of the buffer. - The return value is true if successful, else, it is false. */ -static int dpseekwrite(int fd, int off, const void *buf, int size){ - assert(fd >= 0 && buf && size >= 0); - if(size < 1) return TRUE; - if(off < 0){ - if(lseek(fd, 0, SEEK_END) == -1){ - dpecodeset(DP_ESEEK, __FILE__, __LINE__); - return FALSE; - } - } else { - if(lseek(fd, off, SEEK_SET) != off){ - dpecodeset(DP_ESEEK, __FILE__, __LINE__); - return FALSE; - } - } - if(dpwrite(fd, buf, size) != size){ - dpecodeset(DP_EWRITE, __FILE__, __LINE__); - return FALSE; - } - return TRUE; -} - - -/* Write an integer into a file at an offset. - `fd' specifies a file descriptor. - `off' specifies an offset of the file. - `num' specifies an integer. - The return value is true if successful, else, it is false. */ -static int dpseekwritenum(int fd, int off, int num){ - assert(fd >= 0); - return dpseekwrite(fd, off, &num, sizeof(int)); -} - - -/* Read from a file and store the data into a buffer. - `fd' specifies a file descriptor. - `buffer' specifies a buffer to store into. - `size' specifies the size to read with. - The return value is the size read with, or, -1 on failure. */ -static int dpread(int fd, void *buf, int size){ - char *lbuf; - int i, bs; - assert(fd >= 0 && buf && size >= 0); - lbuf = buf; - for(i = 0; i < size && (bs = read(fd, lbuf + i, size - i)) != 0; i += bs){ - if(bs == -1 && errno != EINTR) return -1; - } - return i; -} - - -/* Read from a file at an offset and store the data into a buffer. - `fd' specifies a file descriptor. - `off' specifies an offset of the file. - `buffer' specifies a buffer to store into. - `size' specifies the size to read with. - The return value is true if successful, else, it is false. */ -static int dpseekread(int fd, int off, void *buf, int size){ - char *lbuf; - assert(fd >= 0 && off >= 0 && buf && size >= 0); - lbuf = (char *)buf; - if(lseek(fd, off, SEEK_SET) != off){ - dpecodeset(DP_ESEEK, __FILE__, __LINE__); - return FALSE; - } - if(dpread(fd, lbuf, size) != size){ - dpecodeset(DP_EREAD, __FILE__, __LINE__); - return FALSE; - } - return TRUE; -} - - -/* Copy data between files. - `destfd' specifies a file descriptor of a destination file. - `destoff' specifies an offset of the destination file. - `srcfd' specifies a file descriptor of a source file. - `srcoff' specifies an offset of the source file. - The return value is the size copied with, or, -1 on failure. */ -static int dpfcopy(int destfd, int destoff, int srcfd, int srcoff){ - char iobuf[DP_IOBUFSIZ]; - int sum, iosiz; - if(lseek(srcfd, srcoff, SEEK_SET) == -1 || lseek(destfd, destoff, SEEK_SET) == -1){ - dpecodeset(DP_ESEEK, __FILE__, __LINE__); - return -1; - } - sum = 0; - while((iosiz = dpread(srcfd, iobuf, DP_IOBUFSIZ)) > 0){ - if(dpwrite(destfd, iobuf, iosiz) == -1){ - dpecodeset(DP_EWRITE, __FILE__, __LINE__); - return -1; - } - sum += iosiz; - } - if(iosiz < 0){ - dpecodeset(DP_EREAD, __FILE__, __LINE__); - return -1; - } - return sum; -} - - -/* Get a natural prime number not less than a number. - `num' specified a natural number. - The return value is a prime number not less than the specified number. */ -static int dpgetprime(int num){ - int primes[] = { - 1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 43, 47, 53, 59, 61, 71, 79, 83, - 89, 103, 109, 113, 127, 139, 157, 173, 191, 199, 223, 239, 251, 283, 317, 349, - 383, 409, 443, 479, 509, 571, 631, 701, 761, 829, 887, 953, 1021, 1151, 1279, - 1399, 1531, 1663, 1789, 1913, 2039, 2297, 2557, 2803, 3067, 3323, 3583, 3833, - 4093, 4603, 5119, 5623, 6143, 6653, 7159, 7673, 8191, 9209, 10223, 11261, - 12281, 13309, 14327, 15359, 16381, 18427, 20479, 22511, 24571, 26597, 28669, - 30713, 32749, 36857, 40949, 45053, 49139, 53239, 57331, 61417, 65521, 73727, - 81919, 90107, 98299, 106487, 114679, 122869, 131071, 147451, 163819, 180221, - 196597, 212987, 229373, 245759, 262139, 294911, 327673, 360439, 393209, 425977, - 458747, 491503, 524287, 589811, 655357, 720887, 786431, 851957, 917503, 982981, - 1048573, 1179641, 1310719, 1441771, 1572853, 1703903, 1835003, 1966079, - 2097143, 2359267, 2621431, 2883577, 3145721, 3407857, 3670013, 3932153, - 4194301, 4718579, 5242877, 5767129, 6291449, 6815741, 7340009, 7864301, - 8388593, 9437179, 10485751, 11534329, 12582893, 13631477, 14680063, 15728611, - 16777213, 18874367, 20971507, 23068667, 25165813, 27262931, 29360087, 31457269, - 33554393, 37748717, 41943023, 46137319, 50331599, 54525917, 58720253, 62914549, - 67108859, 75497467, 83886053, 92274671, 100663291, 109051903, 117440509, - 125829103, 134217689, 150994939, 167772107, 184549373, 201326557, 218103799, - 234881011, 251658227, 268435399, 301989881, 335544301, 369098707, 402653171, - 436207613, 469762043, 503316469, 536870909, 603979769, 671088637, 738197503, - 805306357, 872415211, 939524087, 1006632947, 1073741789, 1207959503, - 1342177237, 1476394991, 1610612711, 1744830457, 1879048183, 2013265907, -1 - }; - int i; - assert(num > 0); - for(i = 0; primes[i] > 0; i++){ - if(num <= primes[i]) return primes[i]; - } - return primes[i-1]; -} - - -/* Get the padding size of a record. - `vsiz' specifies the size of the value of a record. - The return value is the padding size of a record. */ -static int dppadsize(DEPOT *depot, int ksiz, int vsiz){ - int pad; - assert(depot && vsiz >= 0); - if(depot->align > 0){ - return depot->align - (depot->fsiz + DP_RHNUM * sizeof(int) + ksiz + vsiz) % depot->align; - } else if(depot->align < 0){ - pad = (int)(vsiz * (2.0 / (1 << -(depot->align)))); - if(vsiz + pad >= DP_FSBLKSIZ){ - if(vsiz <= DP_FSBLKSIZ) pad = 0; - if(depot->fsiz % DP_FSBLKSIZ == 0){ - return (pad / DP_FSBLKSIZ) * DP_FSBLKSIZ + DP_FSBLKSIZ - - (depot->fsiz + DP_RHNUM * sizeof(int) + ksiz + vsiz) % DP_FSBLKSIZ; - } else { - return (pad / (DP_FSBLKSIZ / 2)) * (DP_FSBLKSIZ / 2) + (DP_FSBLKSIZ / 2) - - (depot->fsiz + DP_RHNUM * sizeof(int) + ksiz + vsiz) % (DP_FSBLKSIZ / 2); - } - } else { - return pad >= DP_RHNUM * sizeof(int) ? pad : DP_RHNUM * sizeof(int); - } - } - return 0; -} - - -/* Get the size of a record in a database file. - `head' specifies the header of a record. - The return value is the size of a record in a database file. */ -static int dprecsize(int *head){ - assert(head); - return DP_RHNUM * sizeof(int) + head[DP_RHIKSIZ] + head[DP_RHIVSIZ] + head[DP_RHIPSIZ]; -} - - -/* Read the header of a record. - `depot' specifies a database handle. - `off' specifies an offset of the database file. - `head' specifies a buffer for the header. - `ebuf' specifies the pointer to the entity buffer. - `eep' specifies the pointer to a variable to which whether ebuf was used is assigned. - The return value is true if successful, else, it is false. */ -static int dprechead(DEPOT *depot, int off, int *head, char *ebuf, int *eep){ - assert(depot && off >= 0 && head); - if(off > depot->fsiz){ - dpecodeset(DP_EBROKEN, __FILE__, __LINE__); - return FALSE; - } - if(ebuf){ - *eep = FALSE; - if(off < depot->fsiz - DP_ENTBUFSIZ){ - *eep = TRUE; - if(!dpseekread(depot->fd, off, ebuf, DP_ENTBUFSIZ)) return FALSE; - memcpy(head, ebuf, DP_RHNUM * sizeof(int)); - if(head[DP_RHIKSIZ] < 0 || head[DP_RHIVSIZ] < 0 || head[DP_RHIPSIZ] < 0 || - head[DP_RHILEFT] < 0 || head[DP_RHIRIGHT] < 0){ - dpecodeset(DP_EBROKEN, __FILE__, __LINE__); - return FALSE; - } - return TRUE; - } - } - if(!dpseekread(depot->fd, off, head, DP_RHNUM * sizeof(int))) return FALSE; - if(head[DP_RHIKSIZ] < 0 || head[DP_RHIVSIZ] < 0 || head[DP_RHIPSIZ] < 0 || - head[DP_RHILEFT] < 0 || head[DP_RHIRIGHT] < 0){ - dpecodeset(DP_EBROKEN, __FILE__, __LINE__); - return FALSE; - } - return TRUE; -} - - -/* Read the entitiy of the key of a record. - `depot' specifies a database handle. - `off' specifies an offset of the database file. - `head' specifies the header of a record. - The return value is a key data whose region is allocated by `malloc', or NULL on failure. */ -static char *dpreckey(DEPOT *depot, int off, int *head){ - char *kbuf; - int ksiz; - assert(depot && off >= 0); - ksiz = head[DP_RHIKSIZ]; - if(!(kbuf = malloc(ksiz + 1))){ - dpecodeset(DP_EALLOC, __FILE__, __LINE__); - return NULL; - } - if(!dpseekread(depot->fd, off + DP_RHNUM * sizeof(int), kbuf, ksiz)){ - free(kbuf); - return NULL; - } - kbuf[ksiz] = '\0'; - return kbuf; -} - - -/* Read the entitiy of the value of a record. - `depot' specifies a database handle. - `off' specifies an offset of the database file. - `head' specifies the header of a record. - `start' specifies the offset address of the beginning of the region of the value to be read. - `max' specifies the max size to be read. If it is negative, the size to read is unlimited. - The return value is a value data whose region is allocated by `malloc', or NULL on failure. */ -static char *dprecval(DEPOT *depot, int off, int *head, int start, int max){ - char *vbuf; - int vsiz; - assert(depot && off >= 0 && start >= 0); - head[DP_RHIVSIZ] -= start; - if(max < 0){ - vsiz = head[DP_RHIVSIZ]; - } else { - vsiz = max < head[DP_RHIVSIZ] ? max : head[DP_RHIVSIZ]; - } - if(!(vbuf = malloc(vsiz + 1))){ - dpecodeset(DP_EALLOC, __FILE__, __LINE__); - return NULL; - } - if(!dpseekread(depot->fd, off + DP_RHNUM * sizeof(int) + head[DP_RHIKSIZ] + start, vbuf, vsiz)){ - free(vbuf); - return NULL; - } - vbuf[vsiz] = '\0'; - return vbuf; -} - - -/* Read the entitiy of the value of a record and write it into a given buffer. - `depot' specifies a database handle. - `off' specifies an offset of the database file. - `head' specifies the header of a record. - `start' specifies the offset address of the beginning of the region of the value to be read. - `max' specifies the max size to be read. It shuld be less than the size of the writing buffer. - If successful, the return value is the size of the written data, else, it is -1. */ -static int dprecvalwb(DEPOT *depot, int off, int *head, int start, int max, char *vbuf){ - int vsiz; - assert(depot && off >= 0 && start >= 0 && max >= 0 && vbuf); - head[DP_RHIVSIZ] -= start; - vsiz = max < head[DP_RHIVSIZ] ? max : head[DP_RHIVSIZ]; - if(!dpseekread(depot->fd, off + DP_RHNUM * sizeof(int) + head[DP_RHIKSIZ] + start, vbuf, vsiz)) - return -1; - return vsiz; -} - - -/* Compare two keys. - `abuf' specifies the pointer to the region of the former. - `asiz' specifies the size of the region. - `bbuf' specifies the pointer to the region of the latter. - `bsiz' specifies the size of the region. - The return value is 0 if two equals, positive if the formar is big, else, negative. */ -static int dpkeycmp(const char *abuf, int asiz, const char *bbuf, int bsiz){ - assert(abuf && asiz >= 0 && bbuf && bsiz >= 0); - if(asiz > bsiz) return 1; - if(asiz < bsiz) return -1; - return memcmp(abuf, bbuf, asiz); -} - - -/* Search for a record. - `depot' specifies a database handle. - `kbuf' specifies the pointer to the region of a key. - `ksiz' specifies the size of the region. - `hash' specifies the second hash value of the key. - `bip' specifies the pointer to the region to assign the index of the corresponding record. - `offp' specifies the pointer to the region to assign the last visited node in the hash chain, - or, -1 if the hash chain is empty. - `entp' specifies the offset of the last used joint, or, -1 if the hash chain is empty. - `head' specifies the pointer to the region to store the header of the last visited record in. - `ebuf' specifies the pointer to the entity buffer. - `eep' specifies the pointer to a variable to which whether ebuf was used is assigned. - `delhit' specifies whether a deleted record corresponds or not. - The return value is 0 if successful, 1 if there is no corresponding record, -1 on error. */ -static int dprecsearch(DEPOT *depot, const char *kbuf, int ksiz, int hash, int *bip, int *offp, - int *entp, int *head, char *ebuf, int *eep, int delhit){ - int off, entoff, thash, kcmp; - char stkey[DP_STKBUFSIZ], *tkey; - assert(depot && kbuf && ksiz >= 0 && hash >= 0 && bip && offp && entp && head && ebuf && eep); - DP_FIRSTHASH(thash, kbuf, ksiz); - *bip = thash % depot->bnum; - off = depot->buckets[*bip]; - *offp = -1; - *entp = -1; - entoff = -1; - *eep = FALSE; - while(off != 0){ - if(!dprechead(depot, off, head, ebuf, eep)) return -1; - thash = head[DP_RHIHASH]; - if(hash > thash){ - entoff = off + DP_RHILEFT * sizeof(int); - off = head[DP_RHILEFT]; - } else if(hash < thash){ - entoff = off + DP_RHIRIGHT * sizeof(int); - off = head[DP_RHIRIGHT]; - } else { - if(*eep && DP_RHNUM * sizeof(int) + head[DP_RHIKSIZ] <= DP_ENTBUFSIZ){ - kcmp = dpkeycmp(kbuf, ksiz, ebuf + (DP_RHNUM * sizeof(int)), head[DP_RHIKSIZ]); - } else if(head[DP_RHIKSIZ] > DP_STKBUFSIZ){ - if(!(tkey = dpreckey(depot, off, head))) return -1; - kcmp = dpkeycmp(kbuf, ksiz, tkey, head[DP_RHIKSIZ]); - free(tkey); - } else { - if(!dpseekread(depot->fd, off + DP_RHNUM * sizeof(int), stkey, head[DP_RHIKSIZ])) - return -1; - kcmp = dpkeycmp(kbuf, ksiz, stkey, head[DP_RHIKSIZ]); - } - if(kcmp > 0){ - entoff = off + DP_RHILEFT * sizeof(int); - off = head[DP_RHILEFT]; - } else if(kcmp < 0){ - entoff = off + DP_RHIRIGHT * sizeof(int); - off = head[DP_RHIRIGHT]; - } else { - if(!delhit && (head[DP_RHIFLAGS] & DP_RECFDEL)){ - entoff = off + DP_RHILEFT * sizeof(int); - off = head[DP_RHILEFT]; - } else { - *offp = off; - *entp = entoff; - return 0; - } - } - } - } - *offp = off; - *entp = entoff; - return 1; -} - - -/* Overwrite a record. - `depot' specifies a database handle. - `off' specifies the offset of the database file. - `rsiz' specifies the size of the existing record. - `kbuf' specifies the pointer to the region of a key. - `ksiz' specifies the size of the region. - `vbuf' specifies the pointer to the region of a value. - `vsiz' specifies the size of the region. - `hash' specifies the second hash value of the key. - `left' specifies the offset of the left child. - `right' specifies the offset of the right child. - The return value is true if successful, or, false on failure. */ -static int dprecrewrite(DEPOT *depot, int off, int rsiz, const char *kbuf, int ksiz, - const char *vbuf, int vsiz, int hash, int left, int right){ - char ebuf[DP_WRTBUFSIZ]; - int i, head[DP_RHNUM], asiz, hoff, koff, voff, mi, min, size; - assert(depot && off >= 1 && rsiz > 0 && kbuf && ksiz >= 0 && vbuf && vsiz >= 0); - head[DP_RHIFLAGS] = 0; - head[DP_RHIHASH] = hash; - head[DP_RHIKSIZ] = ksiz; - head[DP_RHIVSIZ] = vsiz; - head[DP_RHIPSIZ] = rsiz - sizeof(head) - ksiz - vsiz; - head[DP_RHILEFT] = left; - head[DP_RHIRIGHT] = right; - asiz = sizeof(head) + ksiz + vsiz; - if(depot->fbpsiz > DP_FBPOOLSIZ * 4 && head[DP_RHIPSIZ] > asiz){ - rsiz = (head[DP_RHIPSIZ] - asiz) / 2 + asiz; - head[DP_RHIPSIZ] -= rsiz; - } else { - rsiz = 0; - } - if(asiz <= DP_WRTBUFSIZ){ - memcpy(ebuf, head, sizeof(head)); - memcpy(ebuf + sizeof(head), kbuf, ksiz); - memcpy(ebuf + sizeof(head) + ksiz, vbuf, vsiz); - if(!dpseekwrite(depot->fd, off, ebuf, asiz)) return FALSE; - } else { - hoff = off; - koff = hoff + sizeof(head); - voff = koff + ksiz; - if(!dpseekwrite(depot->fd, hoff, head, sizeof(head)) || - !dpseekwrite(depot->fd, koff, kbuf, ksiz) || !dpseekwrite(depot->fd, voff, vbuf, vsiz)) - return FALSE; - } - if(rsiz > 0){ - off += sizeof(head) + ksiz + vsiz + head[DP_RHIPSIZ]; - head[DP_RHIFLAGS] = DP_RECFDEL | DP_RECFREUSE; - head[DP_RHIHASH] = hash; - head[DP_RHIKSIZ] = ksiz; - head[DP_RHIVSIZ] = vsiz; - head[DP_RHIPSIZ] = rsiz - sizeof(head) - ksiz - vsiz; - head[DP_RHILEFT] = 0; - head[DP_RHIRIGHT] = 0; - if(!dpseekwrite(depot->fd, off, head, sizeof(head))) return FALSE; - size = dprecsize(head); - mi = -1; - min = -1; - for(i = 0; i < depot->fbpsiz; i += 2){ - if(depot->fbpool[i] == -1){ - depot->fbpool[i] = off; - depot->fbpool[i+1] = size; - dpfbpoolcoal(depot); - mi = -1; - break; - } - if(mi == -1 || depot->fbpool[i+1] < min){ - mi = i; - min = depot->fbpool[i+1]; - } - } - if(mi >= 0 && size > min){ - depot->fbpool[mi] = off; - depot->fbpool[mi+1] = size; - dpfbpoolcoal(depot); - } - } - return TRUE; -} - - -/* Write a record at the end of a database file. - `depot' specifies a database handle. - `kbuf' specifies the pointer to the region of a key. - `ksiz' specifies the size of the region. - `vbuf' specifies the pointer to the region of a value. - `vsiz' specifies the size of the region. - `hash' specifies the second hash value of the key. - `left' specifies the offset of the left child. - `right' specifies the offset of the right child. - The return value is the offset of the record, or, -1 on failure. */ -static int dprecappend(DEPOT *depot, const char *kbuf, int ksiz, const char *vbuf, int vsiz, - int hash, int left, int right){ - char ebuf[DP_WRTBUFSIZ], *hbuf; - int head[DP_RHNUM], asiz, psiz, off; - assert(depot && kbuf && ksiz >= 0 && vbuf && vsiz >= 0); - psiz = dppadsize(depot, ksiz, vsiz); - head[DP_RHIFLAGS] = 0; - head[DP_RHIHASH] = hash; - head[DP_RHIKSIZ] = ksiz; - head[DP_RHIVSIZ] = vsiz; - head[DP_RHIPSIZ] = psiz; - head[DP_RHILEFT] = left; - head[DP_RHIRIGHT] = right; - asiz = sizeof(head) + ksiz + vsiz + psiz; - off = depot->fsiz; - if(asiz <= DP_WRTBUFSIZ){ - memcpy(ebuf, head, sizeof(head)); - memcpy(ebuf + sizeof(head), kbuf, ksiz); - memcpy(ebuf + sizeof(head) + ksiz, vbuf, vsiz); - memset(ebuf + sizeof(head) + ksiz + vsiz, 0, psiz); - if(!dpseekwrite(depot->fd, off, ebuf, asiz)) return -1; - } else { - if(!(hbuf = malloc(asiz))){ - dpecodeset(DP_EALLOC, __FILE__, __LINE__); - return -1; - } - memcpy(hbuf, head, sizeof(head)); - memcpy(hbuf + sizeof(head), kbuf, ksiz); - memcpy(hbuf + sizeof(head) + ksiz, vbuf, vsiz); - memset(hbuf + sizeof(head) + ksiz + vsiz, 0, psiz); - if(!dpseekwrite(depot->fd, off, hbuf, asiz)){ - free(hbuf); - return -1; - } - free(hbuf); - } - depot->fsiz += asiz; - return off; -} - - -/* Overwrite the value of a record. - `depot' specifies a database handle. - `off' specifies the offset of the database file. - `head' specifies the header of the record. - `vbuf' specifies the pointer to the region of a value. - `vsiz' specifies the size of the region. - `cat' specifies whether it is concatenate mode or not. - The return value is true if successful, or, false on failure. */ -static int dprecover(DEPOT *depot, int off, int *head, const char *vbuf, int vsiz, int cat){ - int i, hsiz, hoff, voff; - assert(depot && off >= 0 && head && vbuf && vsiz >= 0); - for(i = 0; i < depot->fbpsiz; i += 2){ - if(depot->fbpool[i] == off){ - depot->fbpool[i] = -1; - depot->fbpool[i+1] = -1; - break; - } - } - if(cat){ - head[DP_RHIFLAGS] = 0; - head[DP_RHIPSIZ] -= vsiz; - head[DP_RHIVSIZ] += vsiz; - hsiz = DP_RHNUM * sizeof(int); - hoff = off; - voff = hoff + DP_RHNUM * sizeof(int) + head[DP_RHIKSIZ] + head[DP_RHIVSIZ] - vsiz; - } else { - head[DP_RHIFLAGS] = 0; - head[DP_RHIPSIZ] += head[DP_RHIVSIZ] - vsiz; - head[DP_RHIVSIZ] = vsiz; - hsiz = DP_RHNUM * sizeof(int); - hoff = off; - voff = hoff + DP_RHNUM * sizeof(int) + head[DP_RHIKSIZ]; - } - if(!dpseekwrite(depot->fd, hoff, head, hsiz) || - !dpseekwrite(depot->fd, voff, vbuf, vsiz)) return FALSE; - return TRUE; -} - - -/* Delete a record. - `depot' specifies a database handle. - `off' specifies the offset of the database file. - `head' specifies the header of the record. - `reusable' specifies whether the region is reusable or not. - The return value is true if successful, or, false on failure. */ -static int dprecdelete(DEPOT *depot, int off, int *head, int reusable){ - int i, mi, min, size; - assert(depot && off >= 0 && head); - if(reusable){ - size = dprecsize(head); - mi = -1; - min = -1; - for(i = 0; i < depot->fbpsiz; i += 2){ - if(depot->fbpool[i] == -1){ - depot->fbpool[i] = off; - depot->fbpool[i+1] = size; - dpfbpoolcoal(depot); - mi = -1; - break; - } - if(mi == -1 || depot->fbpool[i+1] < min){ - mi = i; - min = depot->fbpool[i+1]; - } - } - if(mi >= 0 && size > min){ - depot->fbpool[mi] = off; - depot->fbpool[mi+1] = size; - dpfbpoolcoal(depot); - } - } - return dpseekwritenum(depot->fd, off + DP_RHIFLAGS * sizeof(int), - DP_RECFDEL | (reusable ? DP_RECFREUSE : 0)); -} - - -/* Make contiguous records of the free block pool coalesce. - `depot' specifies a database handle. */ -static void dpfbpoolcoal(DEPOT *depot){ - int i; - assert(depot); - if(depot->fbpinc++ <= depot->fbpsiz / 4) return; - depot->fbpinc = 0; - qsort(depot->fbpool, depot->fbpsiz / 2, sizeof(int) * 2, dpfbpoolcmp); - for(i = 2; i < depot->fbpsiz; i += 2){ - if(depot->fbpool[i-2] > 0 && - depot->fbpool[i-2] + depot->fbpool[i-1] - depot->fbpool[i] == 0){ - depot->fbpool[i] = depot->fbpool[i-2]; - depot->fbpool[i+1] += depot->fbpool[i-1]; - depot->fbpool[i-2] = -1; - depot->fbpool[i-1] = -1; - } - } -} - - -/* Compare two records of the free block pool. - `a' specifies the pointer to one record. - `b' specifies the pointer to the other record. - The return value is 0 if two equals, positive if the formar is big, else, negative. */ -static int dpfbpoolcmp(const void *a, const void *b){ - assert(a && b); - return *(int *)a - *(int *)b; -} - - - -/* END OF FILE */ |