xref: /titanic_44/usr/src/ucblib/libdbm/dbm.c (revision 5bbb4db2c3f208d12bf0fd11769728f9e5ba66a2)

/*
 * 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);
}