/* * sdbm - ndbm work-alike hashed database library * based on Per-Aake Larson's Dynamic Hashing algorithms. BIT 18 (1978). * author: oz@nexus.yorku.ca * status: public domain. * * core routines */ #include "INTERN.h" #include "config.h" #ifdef WIN32 #include "io.h" #endif #include "sdbm.h" #include "tune.h" #include "pair.h" #ifdef I_FCNTL # include #endif #ifdef I_SYS_FILE # include #endif #ifdef I_STRING # ifndef __ultrix__ # include # endif #else # include #endif /* * externals */ #include /* See notes in perl.h about avoiding extern int errno; */ extern Malloc_t malloc proto((MEM_SIZE)); extern Free_t free proto((Malloc_t)); /* * forward */ static int getdbit proto((DBM *, long)); static int setdbit proto((DBM *, long)); static int getpage proto((DBM *, long)); static datum getnext proto((DBM *)); static int makroom proto((DBM *, long, int)); /* * useful macros */ #define bad(x) ((x).dptr == NULL || (x).dsize < 0) #define exhash(item) sdbm_hash((item).dptr, (item).dsize) #define ioerr(db) ((db)->flags |= DBM_IOERR) #define OFF_PAG(off) (long) (off) * PBLKSIZ #define OFF_DIR(off) (long) (off) * DBLKSIZ static const long masks[] = { 000000000000, 000000000001, 000000000003, 000000000007, 000000000017, 000000000037, 000000000077, 000000000177, 000000000377, 000000000777, 000000001777, 000000003777, 000000007777, 000000017777, 000000037777, 000000077777, 000000177777, 000000377777, 000000777777, 000001777777, 000003777777, 000007777777, 000017777777, 000037777777, 000077777777, 000177777777, 000377777777, 000777777777, 001777777777, 003777777777, 007777777777, 017777777777 }; DBM * sdbm_open(register char *file, register int flags, register int mode) 54 { 54 register DBM *db; 54 register char *dirname; 54 register char *pagname; 54 register int n; 54 if (file == NULL || !*file) ###### return errno = EINVAL, (DBM *) NULL; /* * need space for two seperate filenames */ 54 n = strlen(file) * 2 + strlen(DIRFEXT) + strlen(PAGFEXT) + 2; 54 if ((dirname = (char *) malloc((unsigned) n)) == NULL) ###### return errno = ENOMEM, (DBM *) NULL; /* * build the file names */ 54 dirname = strcat(strcpy(dirname, file), DIRFEXT); 54 pagname = strcpy(dirname + strlen(dirname) + 1, file); 54 pagname = strcat(pagname, PAGFEXT); 54 db = sdbm_prep(dirname, pagname, flags, mode); 54 free((char *) dirname); 54 return db; } DBM * sdbm_prep(char *dirname, char *pagname, int flags, int mode) 54 { 54 register DBM *db; 54 struct stat dstat; 54 if ((db = (DBM *) malloc(sizeof(DBM))) == NULL) ###### return errno = ENOMEM, (DBM *) NULL; 54 db->flags = 0; 54 db->hmask = 0; 54 db->blkptr = 0; 54 db->keyptr = 0; /* * adjust user flags so that WRONLY becomes RDWR, * as required by this package. Also set our internal * flag for RDONLY if needed. */ 54 if (flags & O_WRONLY) ###### flags = (flags & ~O_WRONLY) | O_RDWR; 54 else if ((flags & 03) == O_RDONLY) ###### db->flags = DBM_RDONLY; /* * open the files in sequence, and stat the dirfile. * If we fail anywhere, undo everything, return NULL. */ #if defined(OS2) || defined(MSDOS) || defined(WIN32) || defined(__CYGWIN__) flags |= O_BINARY; # endif 54 if ((db->pagf = open(pagname, flags, mode)) > -1) { 54 if ((db->dirf = open(dirname, flags, mode)) > -1) { /* * need the dirfile size to establish max bit number. */ 54 if (fstat(db->dirf, &dstat) == 0) { /* * zero size: either a fresh database, or one with a single, * unsplit data page: dirpage is all zeros. */ 54 db->dirbno = (!dstat.st_size) ? 0 : -1; 54 db->pagbno = -1; 54 db->maxbno = dstat.st_size * BYTESIZ; 54 (void) memset(db->pagbuf, 0, PBLKSIZ); 54 (void) memset(db->dirbuf, 0, DBLKSIZ); /* * success */ 54 return db; } ###### (void) close(db->dirf); } ###### (void) close(db->pagf); } ###### free((char *) db); ###### return (DBM *) NULL; } void sdbm_close(register DBM *db) 54 { 54 if (db == NULL) ###### errno = EINVAL; else { 54 (void) close(db->dirf); 54 (void) close(db->pagf); 54 free((char *) db); } } datum sdbm_fetch(register DBM *db, datum key) 1154 { 1154 if (db == NULL || bad(key)) ###### return errno = EINVAL, nullitem; 1154 if (getpage(db, exhash(key))) 1154 return getpair(db->pagbuf, key); ###### return ioerr(db), nullitem; } int sdbm_exists(register DBM *db, datum key) 2 { 2 if (db == NULL || bad(key)) ###### return errno = EINVAL, -1; 2 if (getpage(db, exhash(key))) 2 return exipair(db->pagbuf, key); ###### return ioerr(db), -1; } int sdbm_delete(register DBM *db, datum key) 6 { 6 if (db == NULL || bad(key)) ###### return errno = EINVAL, -1; 6 if (sdbm_rdonly(db)) ###### return errno = EPERM, -1; 6 if (getpage(db, exhash(key))) { 6 if (!delpair(db->pagbuf, key)) ###### return -1; /* * update the page file */ 6 if (lseek(db->pagf, OFF_PAG(db->pagbno), SEEK_SET) < 0 || write(db->pagf, db->pagbuf, PBLKSIZ) < 0) ###### return ioerr(db), -1; 6 return 0; } ###### return ioerr(db), -1; } int sdbm_store(register DBM *db, datum key, datum val, int flags) 991 { 991 int need; 991 register long hash; 991 if (db == NULL || bad(key)) ###### return errno = EINVAL, -1; 991 if (sdbm_rdonly(db)) ###### return errno = EPERM, -1; 991 need = key.dsize + val.dsize; /* * is the pair too big (or too small) for this database ?? */ 991 if (need < 0 || need > PAIRMAX) ###### return errno = EINVAL, -1; 991 if (getpage(db, (hash = exhash(key)))) { /* * if we need to replace, delete the key/data pair * first. If it is not there, ignore. */ 991 if (flags == DBM_REPLACE) 991 (void) delpair(db->pagbuf, key); #ifdef SEEDUPS ###### else if (duppair(db->pagbuf, key)) ###### return 1; #endif /* * if we do not have enough room, we have to split. */ 991 if (!fitpair(db->pagbuf, need)) 6 if (!makroom(db, hash, need)) ###### return ioerr(db), -1; /* * we have enough room or split is successful. insert the key, * and update the page file. */ 991 (void) putpair(db->pagbuf, key, val); 991 if (lseek(db->pagf, OFF_PAG(db->pagbno), SEEK_SET) < 0 || write(db->pagf, db->pagbuf, PBLKSIZ) < 0) ###### return ioerr(db), -1; /* * success */ 991 return 0; } ###### return ioerr(db), -1; } /* * makroom - make room by splitting the overfull page * this routine will attempt to make room for SPLTMAX times before * giving up. */ static int makroom(register DBM *db, long int hash, int need) 6 { 6 long newp; 6 char twin[PBLKSIZ]; #if defined(DOSISH) || defined(WIN32) char zer[PBLKSIZ]; long oldtail; #endif 6 char *pag = db->pagbuf; 6 char *New = twin; 6 register int smax = SPLTMAX; 6 do { /* * split the current page */ 6 (void) splpage(pag, New, db->hmask + 1); /* * address of the new page */ 6 newp = (hash & db->hmask) | (db->hmask + 1); /* * write delay, read avoidence/cache shuffle: * select the page for incoming pair: if key is to go to the new page, * write out the previous one, and copy the new one over, thus making * it the current page. If not, simply write the new page, and we are * still looking at the page of interest. current page is not updated * here, as sdbm_store will do so, after it inserts the incoming pair. */ #if defined(DOSISH) || defined(WIN32) /* * Fill hole with 0 if made it. * (hole is NOT read as 0) */ oldtail = lseek(db->pagf, 0L, SEEK_END); memset(zer, 0, PBLKSIZ); while (OFF_PAG(newp) > oldtail) { if (lseek(db->pagf, 0L, SEEK_END) < 0 || write(db->pagf, zer, PBLKSIZ) < 0) { return 0; } oldtail += PBLKSIZ; } #endif 6 if (hash & (db->hmask + 1)) { ###### if (lseek(db->pagf, OFF_PAG(db->pagbno), SEEK_SET) < 0 || write(db->pagf, db->pagbuf, PBLKSIZ) < 0) ###### return 0; ###### db->pagbno = newp; ###### (void) memcpy(pag, New, PBLKSIZ); } 6 else if (lseek(db->pagf, OFF_PAG(newp), SEEK_SET) < 0 || write(db->pagf, New, PBLKSIZ) < 0) ###### return 0; 6 if (!setdbit(db, db->curbit)) ###### return 0; /* * see if we have enough room now */ 6 if (fitpair(pag, need)) 6 return 1; /* * try again... update curbit and hmask as getpage would have * done. because of our update of the current page, we do not * need to read in anything. BUT we have to write the current * [deferred] page out, as the window of failure is too great. */ ###### db->curbit = 2 * db->curbit + ((hash & (db->hmask + 1)) ? 2 : 1); ###### db->hmask |= db->hmask + 1; ###### if (lseek(db->pagf, OFF_PAG(db->pagbno), SEEK_SET) < 0 || write(db->pagf, db->pagbuf, PBLKSIZ) < 0) ###### return 0; ###### } while (--smax); /* * if we are here, this is real bad news. After SPLTMAX splits, * we still cannot fit the key. say goodnight. */ #ifdef BADMESS ###### (void) write(2, "sdbm: cannot insert after SPLTMAX attempts.\n", 44); #endif ###### return 0; } /* * the following two routines will break if * deletions aren't taken into account. (ndbm bug) */ datum sdbm_firstkey(register DBM *db) 47 { 47 if (db == NULL) ###### return errno = EINVAL, nullitem; /* * start at page 0 */ 47 if (lseek(db->pagf, OFF_PAG(0), SEEK_SET) < 0 || read(db->pagf, db->pagbuf, PBLKSIZ) < 0) ###### return ioerr(db), nullitem; 47 db->pagbno = 0; 47 db->blkptr = 0; 47 db->keyptr = 0; 47 return getnext(db); } datum sdbm_nextkey(register DBM *db) 378 { 378 if (db == NULL) ###### return errno = EINVAL, nullitem; 378 return getnext(db); } /* * all important binary trie traversal */ static int getpage(register DBM *db, register long int hash) 2153 { 2153 register int hbit; 2153 register long dbit; 2153 register long pagb; 2153 dbit = 0; 2153 hbit = 0; 4309 while (dbit < db->maxbno && getdbit(db, dbit)) 2156 dbit = 2 * dbit + ((hash & (1 << hbit++)) ? 2 : 1); debug(("dbit: %d...", dbit)); 2153 db->curbit = dbit; 2153 db->hmask = masks[hbit]; 2153 pagb = hash & db->hmask; /* * see if the block we need is already in memory. * note: this lookaside cache has about 10% hit rate. */ 2153 if (pagb != db->pagbno) { /* * note: here, we assume a "hole" is read as 0s. * if not, must zero pagbuf first. */ 1380 if (lseek(db->pagf, OFF_PAG(pagb), SEEK_SET) < 0 || read(db->pagf, db->pagbuf, PBLKSIZ) < 0) ###### return 0; 1380 if (!chkpage(db->pagbuf)) ###### return 0; 1380 db->pagbno = pagb; debug(("pag read: %d\n", pagb)); } 2153 return 1; } static int getdbit(register DBM *db, register long int dbit) 3560 { 3560 register long c; 3560 register long dirb; 3560 c = dbit / BYTESIZ; 3560 dirb = c / DBLKSIZ; 3560 if (dirb != db->dirbno) { ###### int got; ###### if (lseek(db->dirf, OFF_DIR(dirb), SEEK_SET) < 0 || (got=read(db->dirf, db->dirbuf, DBLKSIZ)) < 0) ###### return 0; ###### if (got==0) ###### memset(db->dirbuf,0,DBLKSIZ); ###### db->dirbno = dirb; debug(("dir read: %d\n", dirb)); } 3560 return db->dirbuf[c % DBLKSIZ] & (1 << dbit % BYTESIZ); } static int setdbit(register DBM *db, register long int dbit) 6 { 6 register long c; 6 register long dirb; 6 c = dbit / BYTESIZ; 6 dirb = c / DBLKSIZ; 6 if (dirb != db->dirbno) { ###### int got; ###### if (lseek(db->dirf, OFF_DIR(dirb), SEEK_SET) < 0 || (got=read(db->dirf, db->dirbuf, DBLKSIZ)) < 0) ###### return 0; ###### if (got==0) ###### memset(db->dirbuf,0,DBLKSIZ); ###### db->dirbno = dirb; debug(("dir read: %d\n", dirb)); } 6 db->dirbuf[c % DBLKSIZ] |= (1 << dbit % BYTESIZ); #if 0 if (dbit >= db->maxbno) db->maxbno += DBLKSIZ * BYTESIZ; #else 6 if (OFF_DIR((dirb+1))*BYTESIZ > db->maxbno) 2 db->maxbno=OFF_DIR((dirb+1))*BYTESIZ; #endif 6 if (lseek(db->dirf, OFF_DIR(dirb), SEEK_SET) < 0 || write(db->dirf, db->dirbuf, DBLKSIZ) < 0) ###### return 0; 6 return 1; } /* * getnext - get the next key in the page, and if done with * the page, try the next page in sequence */ static datum getnext(register DBM *db) 425 { 425 datum key; 466 for (;;) { 425 db->keyptr++; 425 key = getnkey(db->pagbuf, db->keyptr); 425 if (key.dptr != NULL) 384 return key; /* * we either run out, or there is nothing on this page.. * try the next one... If we lost our position on the * file, we will have to seek. */ 41 db->keyptr = 0; 41 if (db->pagbno != db->blkptr++) ###### if (lseek(db->pagf, OFF_PAG(db->blkptr), SEEK_SET) < 0) ###### break; 41 db->pagbno = db->blkptr; 41 if (read(db->pagf, db->pagbuf, PBLKSIZ) <= 0) 41 break; ###### if (!chkpage(db->pagbuf)) 41 break; } 41 return ioerr(db), nullitem; }