OpenSolaris_b135/ucblib/libdbm/dbm.c
/*
* CDDL HEADER START
*
* The contents of this file are subject to the terms of the
* Common Development and Distribution License (the "License").
* You may not use this file except in compliance with the License.
*
* You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
* or http://www.opensolaris.org/os/licensing.
* See the License for the specific language governing permissions
* and limitations under the License.
*
* When distributing Covered Code, include this CDDL HEADER in each
* file and include the License file at usr/src/OPENSOLARIS.LICENSE.
* If applicable, add the following below this CDDL HEADER, with the
* fields enclosed by brackets "[]" replaced with your own identifying
* information: Portions Copyright [yyyy] [name of copyright owner]
*
* CDDL HEADER END
*/
/*
* Copyright 2009 Sun Microsystems, Inc. All rights reserved.
* Use is subject to license terms.
*/
/* Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T */
/* All Rights Reserved */
/*
* Portions of this source code were derived from Berkeley 4.3 BSD
* under license from the Regents of the University of California.
*/
/*LINTLIBRARY*/
#include <sys/types.h>
#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <strings.h>
#include <malloc.h>
#include <sys/stat.h>
#include <sys/fcntl.h>
#include <dbm.h>
#include <errno.h>
/* forward declarations */
/* could be all static if not were for older *.a releases */
void chkblk(char buf[PBLKSIZ]);
void delitem(char buf[PBLKSIZ], int n);
void dbm_access(long hash);
int getbit(void);
int setbit(void);
int additem(char buf[PBLKSIZ], datum item);
int cmpdatum(datum d1, datum d2);
int
dbminit(char *file)
{
struct stat64 statb;
dbrdonly = 0;
if (strlcpy(pagbuf, file, sizeof (pagbuf)) >= sizeof (pagbuf) ||
strlcat(pagbuf, ".pag", sizeof (pagbuf)) >= sizeof (pagbuf)) {
/*
* file.pag does not fit into pagbuf.
* fails with ENAMETOOLONG.
*/
errno = ENAMETOOLONG;
return (-1);
}
pagf = open(pagbuf, 2);
if (pagf < 0) {
pagf = open(pagbuf, 0);
dbrdonly = 1;
}
/*
* We know this won't overflow so it is safe to ignore the
* return value; we use strl* to prevent false hits in
* code sweeps.
*/
(void) strlcpy(pagbuf, file, sizeof (pagbuf));
(void) strlcat(pagbuf, ".dir", sizeof (pagbuf));
dirf = open(pagbuf, 2);
if (dirf < 0) {
dirf = open(pagbuf, 0);
dbrdonly = 1;
}
if (pagf < 0 || dirf < 0) {
(void) printf("cannot open database %s\n", file);
return (-1);
}
/* Guards against large inodes */
(void) fstat64(dirf, &statb);
maxbno = (off_t)statb.st_size * BYTESIZ - 1;
return (0);
}
static long oldb1 = -1L;
static long oldb2 = -1L;
/* Avoid using cached data for subsequent accesses. */
int
dbmflush(void)
{
oldb1 = -1L;
oldb2 = -1L;
return (0);
}
/* Clean up after ourself. */
int
dbmclose(void)
{
(void) close(pagf);
(void) close(dirf);
bitno = 0;
maxbno = 0;
blkno = 0;
hmask = 0;
oldb1 = -1L;
oldb2 = -1L;
return (0);
}
long
forder(datum key)
{
long hash;
hash = calchash(key);
for (hmask = 0; ; hmask = (hmask<<1)+1) {
blkno = hash & hmask;
bitno = blkno + hmask;
if (getbit() == 0)
break;
}
return (blkno);
}
datum
fetch(datum key)
{
int i;
datum item;
dbm_access(calchash(key));
for (i = 0; ; i += 2) {
item = makdatum(pagbuf, i);
if (item.dptr == NULL)
return (item);
if (cmpdatum(key, item) == 0) {
item = makdatum(pagbuf, i+1);
if (item.dptr == NULL)
(void) printf("items not in pairs\n");
return (item);
}
}
}
int
delete(datum key)
{
int i;
datum item;
if (dbrdonly)
return (-1);
dbm_access(calchash(key));
for (i = 0; ; i += 2) {
item = makdatum(pagbuf, i);
if (item.dptr == NULL)
return (-1);
if (cmpdatum(key, item) == 0) {
delitem(pagbuf, i);
delitem(pagbuf, i);
break;
}
}
(void) lseek(pagf, blkno*PBLKSIZ, 0);
(void) write(pagf, pagbuf, PBLKSIZ);
return (0);
}
int
store(datum key, datum dat)
{
int i;
datum item;
char ovfbuf[PBLKSIZ];
datum Sentry;
int Oneflag;
Sentry.dsize = 0;
Sentry.dptr = NULL;
if (dbrdonly)
return (-1);
loop:
dbm_access(calchash(key));
for (i = 0; ; i += 2) {
item = makdatum(pagbuf, i);
if (item.dptr == NULL)
break;
if (cmpdatum(key, item) == 0) {
delitem(pagbuf, i);
delitem(pagbuf, i);
break;
}
}
i = additem(pagbuf, key);
if (i < 0)
goto split;
if (additem(pagbuf, dat) < 0) {
delitem(pagbuf, i);
goto split;
}
(void) lseek(pagf, blkno*PBLKSIZ, 0);
(void) write(pagf, pagbuf, PBLKSIZ);
return (0);
split:
if (key.dsize+dat.dsize+3*sizeof (short) >= PBLKSIZ) {
(void) printf("entry too big\n");
return (-1);
}
bzero(ovfbuf, PBLKSIZ);
Oneflag = 0;
for (i = 0; ; ) {
item = makdatum(pagbuf, i);
Oneflag++;
if (item.dptr == NULL) {
if ((Sentry.dsize == key.dsize) &&
(strncmp(Sentry.dptr, key.dptr, key.dsize) == 0))
return (-1);
if (Oneflag == 2) {
Sentry.dsize = key.dsize;
Sentry.dptr = malloc(strlen(key.dptr)+1);
(void) strncpy(Sentry.dptr, key.dptr,
key.dsize);
}
break;
}
if (calchash(item) & (hmask+1)) {
(void) additem(ovfbuf, item);
delitem(pagbuf, i);
item = makdatum(pagbuf, i);
if (item.dptr == NULL) {
(void) printf("split not paired\n");
break;
}
(void) additem(ovfbuf, item);
delitem(pagbuf, i);
continue;
}
i += 2;
}
(void) lseek(pagf, blkno*PBLKSIZ, 0);
if (write(pagf, pagbuf, PBLKSIZ) < 0)
return (-1);
(void) lseek(pagf, (blkno+hmask+1)*PBLKSIZ, 0);
if (write(pagf, ovfbuf, PBLKSIZ) < 0)
return (-1);
if (setbit() < 0)
return (-1);
goto loop;
}
datum
firstkey(void)
{
return (firsthash(0L));
}
datum
nextkey(datum key)
{
int i;
datum item, bitem;
long hash;
int f;
hash = calchash(key);
dbm_access(hash);
f = 1;
for (i = 0; ; i += 2) {
item = makdatum(pagbuf, i);
if (item.dptr == NULL)
break;
if (cmpdatum(key, item) <= 0)
continue;
if (f || cmpdatum(bitem, item) < 0) {
bitem = item;
f = 0;
}
}
if (f == 0)
return (bitem);
hash = hashinc(hash);
if (hash == 0)
return (item);
return (firsthash(hash));
}
datum
firsthash(long hash)
{
int i;
datum item, bitem;
loop:
dbm_access(hash);
bitem = makdatum(pagbuf, 0);
for (i = 2; ; i += 2) {
item = makdatum(pagbuf, i);
if (item.dptr == NULL)
break;
if (cmpdatum(bitem, item) < 0)
bitem = item;
}
if (bitem.dptr != NULL)
return (bitem);
hash = hashinc(hash);
if (hash == 0)
return (item);
goto loop;
}
void
dbm_access(long hash)
{
ssize_t readsize;
for (hmask = 0; ; hmask = (hmask<<1)+1) {
blkno = hash & hmask;
bitno = blkno + hmask;
if (getbit() == 0)
break;
}
if (blkno != oldb1) {
(void) lseek(pagf, blkno*PBLKSIZ, 0);
readsize = read(pagf, pagbuf, PBLKSIZ);
if (readsize != PBLKSIZ) {
if (readsize < 0) readsize = 0;
bzero(pagbuf+readsize, PBLKSIZ-readsize);
}
chkblk(pagbuf);
oldb1 = blkno;
}
}
int
getbit(void)
{
long bn;
ssize_t readsize;
long b, i, n;
if (bitno > maxbno)
return (0);
n = bitno % BYTESIZ;
bn = bitno / BYTESIZ;
i = bn % DBLKSIZ;
b = bn / DBLKSIZ;
if (b != oldb2) {
(void) lseek(dirf, (long)b*DBLKSIZ, 0);
readsize = read(dirf, dirbuf, DBLKSIZ);
if (readsize != DBLKSIZ) {
if (readsize < 0) readsize = 0;
bzero(dirbuf+readsize, DBLKSIZ-readsize);
}
oldb2 = b;
}
if (dirbuf[i] & (1<<n))
return (1);
return (0);
}
int
setbit(void)
{
long bn;
long i, n, b;
if (dbrdonly)
return (-1);
if (bitno > maxbno) {
maxbno = bitno;
(void) getbit();
}
n = bitno % BYTESIZ;
bn = bitno / BYTESIZ;
i = bn % DBLKSIZ;
b = bn / DBLKSIZ;
dirbuf[i] |= 1<<n;
(void) lseek(dirf, (long)b*DBLKSIZ, 0);
if (write(dirf, dirbuf, DBLKSIZ) < 0)
return (-1);
return (0);
}
datum
makdatum(char buf[PBLKSIZ], int n)
{
short *sp;
int t;
datum item;
sp = (short *)buf;
if (n < 0 || n >= sp[0])
goto null;
t = PBLKSIZ;
if (n > 0)
t = sp[n+1-1];
item.dptr = buf+sp[n+1];
item.dsize = t - sp[n+1];
return (item);
null:
item.dptr = NULL;
item.dsize = 0;
return (item);
}
int
cmpdatum(datum d1, datum d2)
{
int n;
char *p1, *p2;
n = d1.dsize;
if (n != d2.dsize)
return (n - d2.dsize);
if (n == 0)
return (0);
p1 = d1.dptr;
p2 = d2.dptr;
do
if (*p1++ != *p2++)
return (*--p1 - *--p2);
while (--n);
return (0);
}
int hitab[16]
/*
* ken's
* {
* 055,043,036,054,063,014,004,005,
* 010,064,077,000,035,027,025,071,
* };
*/
= { 61, 57, 53, 49, 45, 41, 37, 33,
29, 25, 21, 17, 13, 9, 5, 1,
};
long hltab[64] = {
06100151277L, 06106161736L, 06452611562L, 05001724107L,
02614772546L, 04120731531L, 04665262210L, 07347467531L,
06735253126L, 06042345173L, 03072226605L, 01464164730L,
03247435524L, 07652510057L, 01546775256L, 05714532133L,
06173260402L, 07517101630L, 02431460343L, 01743245566L,
00261675137L, 02433103631L, 03421772437L, 04447707466L,
04435620103L, 03757017115L, 03641531772L, 06767633246L,
02673230344L, 00260612216L, 04133454451L, 00615531516L,
06137717526L, 02574116560L, 02304023373L, 07061702261L,
05153031405L, 05322056705L, 07401116734L, 06552375715L,
06165233473L, 05311063631L, 01212221723L, 01052267235L,
06000615237L, 01075222665L, 06330216006L, 04402355630L,
01451177262L, 02000133436L, 06025467062L, 07121076461L,
03123433522L, 01010635225L, 01716177066L, 05161746527L,
01736635071L, 06243505026L, 03637211610L, 01756474365L,
04723077174L, 03642763134L, 05750130273L, 03655541561L,
};
long
hashinc(long hash)
{
long bit;
hash &= hmask;
bit = hmask+1;
for (;;) {
bit >>= 1;
if (bit == 0)
return (0L);
if ((hash&bit) == 0)
return (hash|bit);
hash &= ~bit;
}
}
long
calchash(datum item)
{
int i, j, f;
long hashl;
int hashi;
hashl = 0;
hashi = 0;
for (i = 0; i < item.dsize; i++) {
f = item.dptr[i];
for (j = 0; j < BYTESIZ; j += 4) {
hashi += hitab[f&017];
hashl += hltab[hashi&63];
f >>= 4;
}
}
return (hashl);
}
void
delitem(char buf[PBLKSIZ], int n)
{
short *sp;
int i1, i2, i3;
sp = (short *)buf;
if (n < 0 || n >= sp[0])
goto bad;
i1 = sp[n+1];
i2 = PBLKSIZ;
if (n > 0)
i2 = sp[n+1-1];
i3 = sp[sp[0]+1-1];
if (i2 > i1)
while (i1 > i3) {
i1--;
i2--;
buf[i2] = buf[i1];
buf[i1] = 0;
}
i2 -= i1;
for (i1 = n+1; i1 < sp[0]; i1++)
sp[i1+1-1] = sp[i1+1] + i2;
sp[0]--;
sp[sp[0]+1] = 0;
return;
bad:
(void) printf("bad delitem\n");
abort();
}
int
additem(char buf[PBLKSIZ], datum item)
{
short *sp;
int i1, i2;
sp = (short *)buf;
i1 = PBLKSIZ;
if (sp[0] > 0)
i1 = sp[sp[0]+1-1];
i1 -= item.dsize;
i2 = (int)((sp[0]+2) * sizeof (short));
if (i1 <= i2)
return (-1);
sp[sp[0]+1] = (short)i1;
for (i2 = 0; i2 < item.dsize; i2++) {
buf[i1] = item.dptr[i2];
i1++;
}
sp[0]++;
return (sp[0]-1);
}
void
chkblk(char buf[PBLKSIZ])
{
short *sp;
int t, i;
sp = (short *)buf;
t = PBLKSIZ;
for (i = 0; i < sp[0]; i++) {
if (sp[i+1] > t)
goto bad;
t = sp[i+1];
}
if (t < (sp[0]+1)*sizeof (short))
goto bad;
return;
bad:
(void) printf("bad block\n");
abort();
bzero(buf, PBLKSIZ);
}