[unix-history] / usr / src / old / libndbm / ndbm.c

/*
 * Copyright (c) 1983 Regents of the University of California.
 * All rights reserved.  The Berkeley software License Agreement
 * specifies the terms and conditions for redistribution.
 */

#if defined(LIBC_SCCS) && !defined(lint)
static char sccsid[] = "@(#)ndbm.c	5.4 (Berkeley) %G%";
#endif LIBC_SCCS and not lint

#include <sys/types.h>
#include <sys/stat.h>
#include <sys/file.h>
#include <stdio.h>
#include <errno.h>
#include <ndbm.h>

#define BYTESIZ 8
#undef setbit

static  datum makdatum();
static  long hashinc();
static  long dcalchash();
extern  int errno;

DBM *
dbm_open(file, flags, mode)
	char *file;
	int flags, mode;
{
	struct stat statb;
	register DBM *db;

	if ((db = (DBM *)malloc(sizeof *db)) == 0) {
		errno = ENOMEM;
		return ((DBM *)0);
	}
	db->dbm_flags = (flags & 03) == O_RDONLY ? _DBM_RDONLY : 0;
	if ((flags & 03) == O_WRONLY)
		flags = (flags & ~03) | O_RDWR;
	strcpy(db->dbm_pagbuf, file);
	strcat(db->dbm_pagbuf, ".pag");
	db->dbm_pagf = open(db->dbm_pagbuf, flags, mode);
	if (db->dbm_pagf < 0)
		goto bad;
	strcpy(db->dbm_pagbuf, file);
	strcat(db->dbm_pagbuf, ".dir");
	db->dbm_dirf = open(db->dbm_pagbuf, flags, mode);
	if (db->dbm_dirf < 0)
		goto bad1;
	fstat(db->dbm_dirf, &statb);
	db->dbm_maxbno = statb.st_size*BYTESIZ-1;
	db->dbm_pagbno = db->dbm_dirbno = -1;
	return (db);
bad1:
	(void) close(db->dbm_pagf);
bad:
	free((char *)db);
	return ((DBM *)0);
}

void
dbm_close(db)
	DBM *db;
{

	(void) close(db->dbm_dirf);
	(void) close(db->dbm_pagf);
	free((char *)db);
}

long
dbm_forder(db, key)
	register DBM *db;
	datum key;
{
	long hash;

	hash = dcalchash(key);
	for (db->dbm_hmask=0;; db->dbm_hmask=(db->dbm_hmask<<1)+1) {
		db->dbm_blkno = hash & db->dbm_hmask;
		db->dbm_bitno = db->dbm_blkno + db->dbm_hmask;
		if (getbit(db) == 0)
			break;
	}
	return (db->dbm_blkno);
}

datum
dbm_fetch(db, key)
	register DBM *db;
	datum key;
{
	register i;
	datum item;

	if (dbm_error(db))
		goto err;
	dbm_access(db, dcalchash(key));
	if ((i = finddatum(db->dbm_pagbuf, key)) >= 0) {
		item = makdatum(db->dbm_pagbuf, i+1);
		if (item.dptr != NULL)
			return (item);
	}
err:
	item.dptr = NULL;
	item.dsize = 0;
	return (item);
}

dbm_delete(db, key)
	register DBM *db;
	datum key;
{
	register i;
	datum item;

	if (dbm_error(db))
		return (-1);
	if (dbm_rdonly(db)) {
		errno = EPERM;
		return (-1);
	}
	dbm_access(db, dcalchash(key));
	if ((i = finddatum(db->dbm_pagbuf, key)) < 0)
		return (-1);
	if (!delitem(db->dbm_pagbuf, i))
		goto err;
	db->dbm_pagbno = db->dbm_blkno;
	(void) lseek(db->dbm_pagf, db->dbm_blkno*PBLKSIZ, L_SET);
	if (write(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) != PBLKSIZ) {
	err:
		db->dbm_flags |= _DBM_IOERR;
		return (-1);
	}
	return (0);
}

dbm_store(db, key, dat, replace)
	register DBM *db;
	datum key, dat;
	int replace;
{
	register i;
	datum item, item1;
	char ovfbuf[PBLKSIZ];

	if (dbm_error(db))
		return (-1);
	if (dbm_rdonly(db)) {
		errno = EPERM;
		return (-1);
	}
loop:
	dbm_access(db, dcalchash(key));
	if ((i = finddatum(db->dbm_pagbuf, key)) >= 0) {
		if (!replace)
			return (1);
		if (!delitem(db->dbm_pagbuf, i)) {
			db->dbm_flags |= _DBM_IOERR;
			return (-1);
		}
	}
	if (!additem(db->dbm_pagbuf, key, dat))
		goto split;
	db->dbm_pagbno = db->dbm_blkno;
	(void) lseek(db->dbm_pagf, db->dbm_blkno*PBLKSIZ, L_SET);
	if (write(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) != PBLKSIZ) {
		db->dbm_flags |= _DBM_IOERR;
		return (-1);
	}
	return (0);

split:
	if (key.dsize+dat.dsize+3*sizeof(short) >= PBLKSIZ) {
		db->dbm_flags |= _DBM_IOERR;
		errno = ENOSPC;
		return (-1);
	}
	bzero(ovfbuf, PBLKSIZ);
	for (i=0;;) {
		item = makdatum(db->dbm_pagbuf, i);
		if (item.dptr == NULL)
			break;
		if (dcalchash(item) & (db->dbm_hmask+1)) {
			item1 = makdatum(db->dbm_pagbuf, i+1);
			if (item1.dptr == NULL) {
				fprintf(stderr, "ndbm: split not paired\n");
				db->dbm_flags |= _DBM_IOERR;
				break;
			}
			if (!additem(ovfbuf, item, item1) ||
			    !delitem(db->dbm_pagbuf, i)) {
				db->dbm_flags |= _DBM_IOERR;
				return (-1);
			}
			continue;
		}
		i += 2;
	}
	db->dbm_pagbno = db->dbm_blkno;
	(void) lseek(db->dbm_pagf, db->dbm_blkno*PBLKSIZ, L_SET);
	if (write(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) != PBLKSIZ) {
		db->dbm_flags |= _DBM_IOERR;
		return (-1);
	}
	(void) lseek(db->dbm_pagf, (db->dbm_blkno+db->dbm_hmask+1)*PBLKSIZ, L_SET);
	if (write(db->dbm_pagf, ovfbuf, PBLKSIZ) != PBLKSIZ) {
		db->dbm_flags |= _DBM_IOERR;
		return (-1);
	}
	setbit(db);
	goto loop;
}

datum
dbm_firstkey(db)
	DBM *db;
{

	db->dbm_blkptr = 0L;
	db->dbm_keyptr = 0;
	return (dbm_nextkey(db));
}

datum
dbm_nextkey(db)
	register DBM *db;
{
	struct stat statb;
	datum item;

	if (dbm_error(db) || fstat(db->dbm_pagf, &statb) < 0)
		goto err;
	statb.st_size /= PBLKSIZ;
	for (;;) {
		if (db->dbm_blkptr != db->dbm_pagbno) {
			db->dbm_pagbno = db->dbm_blkptr;
			(void) lseek(db->dbm_pagf, db->dbm_blkptr*PBLKSIZ, L_SET);
			if (read(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) != PBLKSIZ)
				bzero(db->dbm_pagbuf, PBLKSIZ);
#ifdef DEBUG
			else if (chkblk(db->dbm_pagbuf) < 0)
				db->dbm_flags |= _DBM_IOERR;
#endif
		}
		if (((short *)db->dbm_pagbuf)[0] != 0) {
			item = makdatum(db->dbm_pagbuf, db->dbm_keyptr);
			if (item.dptr != NULL) {
				db->dbm_keyptr += 2;
				return (item);
			}
			db->dbm_keyptr = 0;
		}
		if (++db->dbm_blkptr >= statb.st_size)
			break;
	}
err:
	item.dptr = NULL;
	item.dsize = 0;
	return (item);
}

static
dbm_access(db, hash)
	register DBM *db;
	long hash;
{

	for (db->dbm_hmask=0;; db->dbm_hmask=(db->dbm_hmask<<1)+1) {
		db->dbm_blkno = hash & db->dbm_hmask;
		db->dbm_bitno = db->dbm_blkno + db->dbm_hmask;
		if (getbit(db) == 0)
			break;
	}
	if (db->dbm_blkno != db->dbm_pagbno) {
		db->dbm_pagbno = db->dbm_blkno;
		(void) lseek(db->dbm_pagf, db->dbm_blkno*PBLKSIZ, L_SET);
		if (read(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) != PBLKSIZ)
			bzero(db->dbm_pagbuf, PBLKSIZ);
#ifdef DEBUG
		else if (chkblk(db->dbm_pagbuf) < 0)
			db->dbm_flags |= _DBM_IOERR;
#endif
	}
}

static
getbit(db)
	register DBM *db;
{
	long bn;
	register b, i, n;
	

	if (db->dbm_bitno > db->dbm_maxbno)
		return (0);
	n = db->dbm_bitno % BYTESIZ;
	bn = db->dbm_bitno / BYTESIZ;
	i = bn % DBLKSIZ;
	b = bn / DBLKSIZ;
	if (b != db->dbm_dirbno) {
		db->dbm_dirbno = b;
		(void) lseek(db->dbm_dirf, (long)b*DBLKSIZ, L_SET);
		if (read(db->dbm_dirf, db->dbm_dirbuf, DBLKSIZ) != DBLKSIZ)
			bzero(db->dbm_dirbuf, DBLKSIZ);
	}
	return (db->dbm_dirbuf[i] & (1<<n));
}

static
setbit(db)
	register DBM *db;
{
	long bn;
	register i, n, b;

	if (db->dbm_bitno > db->dbm_maxbno)
		db->dbm_maxbno = db->dbm_bitno;
	n = db->dbm_bitno % BYTESIZ;
	bn = db->dbm_bitno / BYTESIZ;
	i = bn % DBLKSIZ;
	b = bn / DBLKSIZ;
	if (b != db->dbm_dirbno) {
		db->dbm_dirbno = b;
		(void) lseek(db->dbm_dirf, (long)b*DBLKSIZ, L_SET);
		if (read(db->dbm_dirf, db->dbm_dirbuf, DBLKSIZ) != DBLKSIZ)
			bzero(db->dbm_dirbuf, DBLKSIZ);
	}
	db->dbm_dirbuf[i] |= 1<<n;
	db->dbm_dirbno = b;
	(void) lseek(db->dbm_dirf, (long)b*DBLKSIZ, L_SET);
	if (write(db->dbm_dirf, db->dbm_dirbuf, DBLKSIZ) != DBLKSIZ)
		db->dbm_flags |= _DBM_IOERR;
}

static datum
makdatum(buf, n)
	char buf[PBLKSIZ];
{
	register short *sp;
	register t;
	datum item;

	sp = (short *)buf;
	if ((unsigned)n >= sp[0]) {
		item.dptr = NULL;
		item.dsize = 0;
		return (item);
	}
	t = PBLKSIZ;
	if (n > 0)
		t = sp[n];
	item.dptr = buf+sp[n+1];
	item.dsize = t - sp[n+1];
	return (item);
}

static
finddatum(buf, item)
	char buf[PBLKSIZ];
	datum item;
{
	register short *sp;
	register int i, n, j;

	sp = (short *)buf;
	n = PBLKSIZ;
	for (i=0, j=sp[0]; i<j; i+=2, n = sp[i]) {
		n -= sp[i+1];
		if (n != item.dsize)
			continue;
		if (n == 0 || bcmp(&buf[sp[i+1]], item.dptr, n) == 0)
			return (i);
	}
	return (-1);
}

static  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,
};
static  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,
};

static long
hashinc(db, hash)
	register DBM *db;
	long hash;
{
	long bit;

	hash &= db->dbm_hmask;
	bit = db->dbm_hmask+1;
	for (;;) {
		bit >>= 1;
		if (bit == 0)
			return (0L);
		if ((hash & bit) == 0)
			return (hash | bit);
		hash &= ~bit;
	}
}

static long
dcalchash(item)
	datum item;
{
	register int s, c, j;
	register char *cp;
	register long hashl;
	register int hashi;

	hashl = 0;
	hashi = 0;
	for (cp = item.dptr, s=item.dsize; --s >= 0; ) {
		c = *cp++;
		for (j=0; j<BYTESIZ; j+=4) {
			hashi += hitab[c&017];
			hashl += hltab[hashi&63];
			c >>= 4;
		}
	}
	return (hashl);
}

/*
 * Delete pairs of items (n & n+1).
 */
static
delitem(buf, n)
	char buf[PBLKSIZ];
{
	register short *sp, *sp1;
	register i1, i2;

	sp = (short *)buf;
	i2 = sp[0];
	if ((unsigned)n >= i2 || (n & 1))
		return (0);
	if (n == i2-2) {
		sp[0] -= 2;
		return (1);
	}
	i1 = PBLKSIZ;
	if (n > 0)
		i1 = sp[n];
	i1 -= sp[n+2];
	if (i1 > 0) {
		i2 = sp[i2];
		bcopy(&buf[i2], &buf[i2 + i1], sp[n+2] - i2);
	}
	sp[0] -= 2;
	for (sp1 = sp + sp[0], sp += n+1; sp <= sp1; sp++)
		sp[0] = sp[2] + i1;
	return (1);
}

/*
 * Add pairs of items (item & item1).
 */
static
additem(buf, item, item1)
	char buf[PBLKSIZ];
	datum item, item1;
{
	register short *sp;
	register i1, i2;

	sp = (short *)buf;
	i1 = PBLKSIZ;
	i2 = sp[0];
	if (i2 > 0)
		i1 = sp[i2];
	i1 -= item.dsize + item1.dsize;
	if (i1 <= (i2+3) * (int)sizeof(short))
		return (0);
	sp[0] += 2;
	sp[++i2] = i1 + item1.dsize;
	bcopy(item.dptr, &buf[i1 + item1.dsize], item.dsize);
	sp[++i2] = i1;
	bcopy(item1.dptr, &buf[i1], item1.dsize);
	return (1);
}

#ifdef DEBUG
static
chkblk(buf)
	char buf[PBLKSIZ];
{
	register short *sp;
	register t, i;

	sp = (short *)buf;
	t = PBLKSIZ;
	for (i=0; i<sp[0]; i++) {
		if (sp[i+1] > t)
			return (-1);
		t = sp[i+1];
	}
	if (t < (sp[0]+1)*sizeof(short))
		return (-1);
	return (0);
}
#endif
Commit	Line	Data
bb0cfa24 DF	1	/*
	2	* Copyright (c) 1983 Regents of the University of California.
	3	* All rights reserved. The Berkeley software License Agreement
	4	* specifies the terms and conditions for redistribution.
	5	*/
	6
2ce81398	7	#if defined(LIBC_SCCS) && !defined(lint)
a5e1e880	8	static char sccsid[] = "@(#)ndbm.c 5.4 (Berkeley) %G%";
2ce81398	9	#endif LIBC_SCCS and not lint
1e2c9ae9 RC	10
	11	#include <sys/types.h>
	12	#include <sys/stat.h>
	13	#include <sys/file.h>
b5f04745	14	#include <stdio.h>
1e2c9ae9 RC	15	#include <errno.h>
	16	#include <ndbm.h>
	17
1e2c9ae9	18	#define BYTESIZ 8
bc04a781	19	#undef setbit
1e2c9ae9	20
1e2c9ae9	21	static datum makdatum();
1e2c9ae9 RC	22	static long hashinc();
1e2c9ae9 RC	23	static long dcalchash();
1e2c9ae9 RC	24	extern int errno;
	25
	26	DBM *
b5f04745	27	dbm_open(file, flags, mode)
1e2c9ae9 RC	28	char *file;
	29	int flags, mode;
	30	{
	31	struct stat statb;
	32	register DBM *db;
	33
	34	if ((db = (DBM )malloc(sizeof db)) == 0) {
	35	errno = ENOMEM;
	36	return ((DBM *)0);
	37	}
b5f04745	38	db->dbm_flags = (flags & 03) == O_RDONLY ? _DBM_RDONLY : 0;
1e2c9ae9 RC	39	if ((flags & 03) == O_WRONLY)
1e2c9ae9 RC	40	flags = (flags & ~03) \| O_RDWR;
b5f04745 RC	41	strcpy(db->dbm_pagbuf, file);
	42	strcat(db->dbm_pagbuf, ".pag");
	43	db->dbm_pagf = open(db->dbm_pagbuf, flags, mode);
	44	if (db->dbm_pagf < 0)
1e2c9ae9	45	goto bad;
b5f04745 RC	46	strcpy(db->dbm_pagbuf, file);
	47	strcat(db->dbm_pagbuf, ".dir");
	48	db->dbm_dirf = open(db->dbm_pagbuf, flags, mode);
	49	if (db->dbm_dirf < 0)
1e2c9ae9	50	goto bad1;
b5f04745 RC	51	fstat(db->dbm_dirf, &statb);
	52	db->dbm_maxbno = statb.st_size*BYTESIZ-1;
	53	db->dbm_pagbno = db->dbm_dirbno = -1;
1e2c9ae9 RC	54	return (db);
1e2c9ae9 RC	55	bad1:
b5f04745	56	(void) close(db->dbm_pagf);
1e2c9ae9 RC	57	bad:
	58	free((char *)db);
	59	return ((DBM *)0);
	60	}
	61
	62	void
b5f04745	63	dbm_close(db)
1e2c9ae9 RC	64	DBM *db;
	65	{
	66
b5f04745 RC	67	(void) close(db->dbm_dirf);
b5f04745 RC	68	(void) close(db->dbm_pagf);
1e2c9ae9 RC	69	free((char *)db);
	70	}
	71
	72	long
b5f04745	73	dbm_forder(db, key)
1e2c9ae9 RC	74	register DBM *db;
	75	datum key;
	76	{
	77	long hash;
	78
	79	hash = dcalchash(key);
b5f04745 RC	80	for (db->dbm_hmask=0;; db->dbm_hmask=(db->dbm_hmask<<1)+1) {
	81	db->dbm_blkno = hash & db->dbm_hmask;
	82	db->dbm_bitno = db->dbm_blkno + db->dbm_hmask;
1e2c9ae9 RC	83	if (getbit(db) == 0)
	84	break;
	85	}
b5f04745	86	return (db->dbm_blkno);
1e2c9ae9 RC	87	}
	88
	89	datum
b5f04745	90	dbm_fetch(db, key)
1e2c9ae9 RC	91	register DBM *db;
	92	datum key;
	93	{
	94	register i;
	95	datum item;
	96
b5f04745 RC	97	if (dbm_error(db))
b5f04745 RC	98	goto err;
1e2c9ae9	99	dbm_access(db, dcalchash(key));
130081c8 RC	100	if ((i = finddatum(db->dbm_pagbuf, key)) >= 0) {
	101	item = makdatum(db->dbm_pagbuf, i+1);
	102	if (item.dptr != NULL)
1e2c9ae9	103	return (item);
1e2c9ae9	104	}
b5f04745 RC	105	err:
	106	item.dptr = NULL;
	107	item.dsize = 0;
	108	return (item);
1e2c9ae9 RC	109	}
1e2c9ae9 RC	110
b5f04745	111	dbm_delete(db, key)
1e2c9ae9 RC	112	register DBM *db;
	113	datum key;
	114	{
	115	register i;
	116	datum item;
	117
b5f04745 RC	118	if (dbm_error(db))
	119	return (-1);
	120	if (dbm_rdonly(db)) {
1e2c9ae9 RC	121	errno = EPERM;
	122	return (-1);
	123	}
	124	dbm_access(db, dcalchash(key));
130081c8	125	if ((i = finddatum(db->dbm_pagbuf, key)) < 0)
b5f04745	126	return (-1);
130081c8 RC	127	if (!delitem(db->dbm_pagbuf, i))
130081c8 RC	128	goto err;
b5f04745 RC	129	db->dbm_pagbno = db->dbm_blkno;
	130	(void) lseek(db->dbm_pagf, db->dbm_blkno*PBLKSIZ, L_SET);
	131	if (write(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) != PBLKSIZ) {
130081c8	132	err:
b5f04745 RC	133	db->dbm_flags \|= _DBM_IOERR;
	134	return (-1);
	135	}
1e2c9ae9 RC	136	return (0);
	137	}
	138
b5f04745	139	dbm_store(db, key, dat, replace)
1e2c9ae9 RC	140	register DBM *db;
1e2c9ae9 RC	141	datum key, dat;
b7fcb3c9	142	int replace;
1e2c9ae9 RC	143	{
1e2c9ae9 RC	144	register i;
130081c8	145	datum item, item1;
1e2c9ae9 RC	146	char ovfbuf[PBLKSIZ];
1e2c9ae9 RC	147
b5f04745 RC	148	if (dbm_error(db))
	149	return (-1);
	150	if (dbm_rdonly(db)) {
1e2c9ae9 RC	151	errno = EPERM;
	152	return (-1);
	153	}
	154	loop:
	155	dbm_access(db, dcalchash(key));
130081c8 RC	156	if ((i = finddatum(db->dbm_pagbuf, key)) >= 0) {
	157	if (!replace)
	158	return (1);
	159	if (!delitem(db->dbm_pagbuf, i)) {
	160	db->dbm_flags \|= _DBM_IOERR;
	161	return (-1);
1e2c9ae9 RC	162	}
1e2c9ae9 RC	163	}
130081c8	164	if (!additem(db->dbm_pagbuf, key, dat))
1e2c9ae9	165	goto split;
b5f04745 RC	166	db->dbm_pagbno = db->dbm_blkno;
	167	(void) lseek(db->dbm_pagf, db->dbm_blkno*PBLKSIZ, L_SET);
	168	if (write(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) != PBLKSIZ) {
	169	db->dbm_flags \|= _DBM_IOERR;
	170	return (-1);
	171	}
1e2c9ae9 RC	172	return (0);
	173
	174	split:
130081c8	175	if (key.dsize+dat.dsize+3*sizeof(short) >= PBLKSIZ) {
b5f04745	176	db->dbm_flags \|= _DBM_IOERR;
1e2c9ae9 RC	177	errno = ENOSPC;
	178	return (-1);
	179	}
	180	bzero(ovfbuf, PBLKSIZ);
	181	for (i=0;;) {
b5f04745	182	item = makdatum(db->dbm_pagbuf, i);
1e2c9ae9 RC	183	if (item.dptr == NULL)
1e2c9ae9 RC	184	break;
b5f04745	185	if (dcalchash(item) & (db->dbm_hmask+1)) {
130081c8 RC	186	item1 = makdatum(db->dbm_pagbuf, i+1);
130081c8 RC	187	if (item1.dptr == NULL) {
b5f04745 RC	188	fprintf(stderr, "ndbm: split not paired\n");
b5f04745 RC	189	db->dbm_flags \|= _DBM_IOERR;
1e2c9ae9 RC	190	break;
1e2c9ae9 RC	191	}
130081c8	192	if (!additem(ovfbuf, item, item1) \|\|
b5f04745 RC	193	!delitem(db->dbm_pagbuf, i)) {
	194	db->dbm_flags \|= _DBM_IOERR;
	195	return (-1);
	196	}
1e2c9ae9 RC	197	continue;
	198	}
	199	i += 2;
	200	}
b5f04745 RC	201	db->dbm_pagbno = db->dbm_blkno;
	202	(void) lseek(db->dbm_pagf, db->dbm_blkno*PBLKSIZ, L_SET);
	203	if (write(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) != PBLKSIZ) {
	204	db->dbm_flags \|= _DBM_IOERR;
	205	return (-1);
	206	}
	207	(void) lseek(db->dbm_pagf, (db->dbm_blkno+db->dbm_hmask+1)*PBLKSIZ, L_SET);
	208	if (write(db->dbm_pagf, ovfbuf, PBLKSIZ) != PBLKSIZ) {
	209	db->dbm_flags \|= _DBM_IOERR;
	210	return (-1);
	211	}
1e2c9ae9 RC	212	setbit(db);
	213	goto loop;
	214	}
	215
	216	datum
b5f04745	217	dbm_firstkey(db)
1e2c9ae9 RC	218	DBM *db;
	219	{
	220
130081c8 RC	221	db->dbm_blkptr = 0L;
	222	db->dbm_keyptr = 0;
	223	return (dbm_nextkey(db));
1e2c9ae9 RC	224	}
	225
	226	datum
130081c8	227	dbm_nextkey(db)
1e2c9ae9	228	register DBM *db;
1e2c9ae9	229	{
130081c8 RC	230	struct stat statb;
130081c8 RC	231	datum item;
1e2c9ae9	232
130081c8	233	if (dbm_error(db) \|\| fstat(db->dbm_pagf, &statb) < 0)
b5f04745	234	goto err;
130081c8 RC	235	statb.st_size /= PBLKSIZ;
	236	for (;;) {
	237	if (db->dbm_blkptr != db->dbm_pagbno) {
	238	db->dbm_pagbno = db->dbm_blkptr;
	239	(void) lseek(db->dbm_pagf, db->dbm_blkptr*PBLKSIZ, L_SET);
	240	if (read(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) != PBLKSIZ)
	241	bzero(db->dbm_pagbuf, PBLKSIZ);
	242	#ifdef DEBUG
	243	else if (chkblk(db->dbm_pagbuf) < 0)
	244	db->dbm_flags \|= _DBM_IOERR;
	245	#endif
	246	}
	247	if (((short *)db->dbm_pagbuf)[0] != 0) {
	248	item = makdatum(db->dbm_pagbuf, db->dbm_keyptr);
	249	if (item.dptr != NULL) {
	250	db->dbm_keyptr += 2;
	251	return (item);
	252	}
	253	db->dbm_keyptr = 0;
1e2c9ae9	254	}
130081c8 RC	255	if (++db->dbm_blkptr >= statb.st_size)
130081c8 RC	256	break;
1e2c9ae9	257	}
b5f04745 RC	258	err:
	259	item.dptr = NULL;
	260	item.dsize = 0;
	261	return (item);
1e2c9ae9 RC	262	}
1e2c9ae9 RC	263
1e2c9ae9 RC	264	static
	265	dbm_access(db, hash)
	266	register DBM *db;
	267	long hash;
	268	{
130081c8	269
b5f04745 RC	270	for (db->dbm_hmask=0;; db->dbm_hmask=(db->dbm_hmask<<1)+1) {
	271	db->dbm_blkno = hash & db->dbm_hmask;
	272	db->dbm_bitno = db->dbm_blkno + db->dbm_hmask;
1e2c9ae9 RC	273	if (getbit(db) == 0)
	274	break;
	275	}
b5f04745 RC	276	if (db->dbm_blkno != db->dbm_pagbno) {
	277	db->dbm_pagbno = db->dbm_blkno;
	278	(void) lseek(db->dbm_pagf, db->dbm_blkno*PBLKSIZ, L_SET);
	279	if (read(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) != PBLKSIZ)
	280	bzero(db->dbm_pagbuf, PBLKSIZ);
130081c8	281	#ifdef DEBUG
b5f04745 RC	282	else if (chkblk(db->dbm_pagbuf) < 0)
b5f04745 RC	283	db->dbm_flags \|= _DBM_IOERR;
130081c8	284	#endif
1e2c9ae9 RC	285	}
	286	}
	287
	288	static
	289	getbit(db)
	290	register DBM *db;
	291	{
	292	long bn;
	293	register b, i, n;
	294
	295
b5f04745	296	if (db->dbm_bitno > db->dbm_maxbno)
1e2c9ae9	297	return (0);
b5f04745 RC	298	n = db->dbm_bitno % BYTESIZ;
b5f04745 RC	299	bn = db->dbm_bitno / BYTESIZ;
1e2c9ae9 RC	300	i = bn % DBLKSIZ;
1e2c9ae9 RC	301	b = bn / DBLKSIZ;
b5f04745 RC	302	if (b != db->dbm_dirbno) {
	303	db->dbm_dirbno = b;
	304	(void) lseek(db->dbm_dirf, (long)b*DBLKSIZ, L_SET);
	305	if (read(db->dbm_dirf, db->dbm_dirbuf, DBLKSIZ) != DBLKSIZ)
	306	bzero(db->dbm_dirbuf, DBLKSIZ);
1e2c9ae9	307	}
130081c8	308	return (db->dbm_dirbuf[i] & (1<<n));
1e2c9ae9 RC	309	}
	310
	311	static
	312	setbit(db)
	313	register DBM *db;
	314	{
	315	long bn;
	316	register i, n, b;
	317
130081c8	318	if (db->dbm_bitno > db->dbm_maxbno)
b5f04745	319	db->dbm_maxbno = db->dbm_bitno;
b5f04745 RC	320	n = db->dbm_bitno % BYTESIZ;
b5f04745 RC	321	bn = db->dbm_bitno / BYTESIZ;
1e2c9ae9 RC	322	i = bn % DBLKSIZ;
1e2c9ae9 RC	323	b = bn / DBLKSIZ;
130081c8 RC	324	if (b != db->dbm_dirbno) {
	325	db->dbm_dirbno = b;
	326	(void) lseek(db->dbm_dirf, (long)b*DBLKSIZ, L_SET);
	327	if (read(db->dbm_dirf, db->dbm_dirbuf, DBLKSIZ) != DBLKSIZ)
	328	bzero(db->dbm_dirbuf, DBLKSIZ);
	329	}
b5f04745 RC	330	db->dbm_dirbuf[i] \|= 1<<n;
	331	db->dbm_dirbno = b;
	332	(void) lseek(db->dbm_dirf, (long)b*DBLKSIZ, L_SET);
130081c8	333	if (write(db->dbm_dirf, db->dbm_dirbuf, DBLKSIZ) != DBLKSIZ)
b5f04745	334	db->dbm_flags \|= _DBM_IOERR;
1e2c9ae9 RC	335	}
	336
	337	static datum
	338	makdatum(buf, n)
	339	char buf[PBLKSIZ];
	340	{
	341	register short *sp;
	342	register t;
	343	datum item;
	344
	345	sp = (short *)buf;
130081c8	346	if ((unsigned)n >= sp[0]) {
b5f04745 RC	347	item.dptr = NULL;
	348	item.dsize = 0;
	349	return (item);
	350	}
1e2c9ae9 RC	351	t = PBLKSIZ;
1e2c9ae9 RC	352	if (n > 0)
b5f04745	353	t = sp[n];
1e2c9ae9 RC	354	item.dptr = buf+sp[n+1];
	355	item.dsize = t - sp[n+1];
	356	return (item);
1e2c9ae9 RC	357	}
	358
	359	static
130081c8 RC	360	finddatum(buf, item)
	361	char buf[PBLKSIZ];
	362	datum item;
1e2c9ae9	363	{
130081c8 RC	364	register short *sp;
130081c8 RC	365	register int i, n, j;
1e2c9ae9	366
130081c8 RC	367	sp = (short *)buf;
	368	n = PBLKSIZ;
	369	for (i=0, j=sp[0]; i<j; i+=2, n = sp[i]) {
	370	n -= sp[i+1];
	371	if (n != item.dsize)
	372	continue;
	373	if (n == 0 \|\| bcmp(&buf[sp[i+1]], item.dptr, n) == 0)
	374	return (i);
	375	}
	376	return (-1);
1e2c9ae9 RC	377	}
	378
	379	static int hitab[16]
	380	/* ken's
	381	{
	382	055,043,036,054,063,014,004,005,
	383	010,064,077,000,035,027,025,071,
	384	};
	385	*/
	386	= { 61, 57, 53, 49, 45, 41, 37, 33,
	387	29, 25, 21, 17, 13, 9, 5, 1,
	388	};
	389	static long hltab[64]
	390	= {
	391	06100151277L,06106161736L,06452611562L,05001724107L,
	392	02614772546L,04120731531L,04665262210L,07347467531L,
	393	06735253126L,06042345173L,03072226605L,01464164730L,
	394	03247435524L,07652510057L,01546775256L,05714532133L,
	395	06173260402L,07517101630L,02431460343L,01743245566L,
	396	00261675137L,02433103631L,03421772437L,04447707466L,
	397	04435620103L,03757017115L,03641531772L,06767633246L,
	398	02673230344L,00260612216L,04133454451L,00615531516L,
	399	06137717526L,02574116560L,02304023373L,07061702261L,
	400	05153031405L,05322056705L,07401116734L,06552375715L,
	401	06165233473L,05311063631L,01212221723L,01052267235L,
	402	06000615237L,01075222665L,06330216006L,04402355630L,
	403	01451177262L,02000133436L,06025467062L,07121076461L,
	404	03123433522L,01010635225L,01716177066L,05161746527L,
	405	01736635071L,06243505026L,03637211610L,01756474365L,
	406	04723077174L,03642763134L,05750130273L,03655541561L,
	407	};
	408
	409	static long
	410	hashinc(db, hash)
	411	register DBM *db;
	412	long hash;
	413	{
	414	long bit;
	415
b5f04745 RC	416	hash &= db->dbm_hmask;
b5f04745 RC	417	bit = db->dbm_hmask+1;
1e2c9ae9 RC	418	for (;;) {
	419	bit >>= 1;
	420	if (bit == 0)
	421	return (0L);
b5f04745 RC	422	if ((hash & bit) == 0)
b5f04745 RC	423	return (hash \| bit);
1e2c9ae9 RC	424	hash &= ~bit;
	425	}
	426	}
	427
	428	static long
	429	dcalchash(item)
	430	datum item;
	431	{
b5f04745 RC	432	register int s, c, j;
	433	register char *cp;
	434	register long hashl;
	435	register int hashi;
1e2c9ae9 RC	436
	437	hashl = 0;
	438	hashi = 0;
b5f04745 RC	439	for (cp = item.dptr, s=item.dsize; --s >= 0; ) {
b5f04745 RC	440	c = *cp++;
1e2c9ae9	441	for (j=0; j<BYTESIZ; j+=4) {
b5f04745	442	hashi += hitab[c&017];
1e2c9ae9	443	hashl += hltab[hashi&63];
b5f04745	444	c >>= 4;
1e2c9ae9 RC	445	}
	446	}
	447	return (hashl);
	448	}
	449
130081c8 RC	450	/*
	451	* Delete pairs of items (n & n+1).
	452	*/
1e2c9ae9 RC	453	static
	454	delitem(buf, n)
	455	char buf[PBLKSIZ];
	456	{
b5f04745 RC	457	register short sp, sp1;
b5f04745 RC	458	register i1, i2;
1e2c9ae9 RC	459
1e2c9ae9 RC	460	sp = (short *)buf;
b5f04745	461	i2 = sp[0];
130081c8	462	if ((unsigned)n >= i2 \|\| (n & 1))
b5f04745	463	return (0);
130081c8 RC	464	if (n == i2-2) {
130081c8 RC	465	sp[0] -= 2;
b5f04745 RC	466	return (1);
	467	}
	468	i1 = PBLKSIZ;
1e2c9ae9	469	if (n > 0)
b5f04745	470	i1 = sp[n];
130081c8	471	i1 -= sp[n+2];
b5f04745 RC	472	if (i1 > 0) {
b5f04745 RC	473	i2 = sp[i2];
130081c8	474	bcopy(&buf[i2], &buf[i2 + i1], sp[n+2] - i2);
1e2c9ae9	475	}
130081c8 RC	476	sp[0] -= 2;
	477	for (sp1 = sp + sp[0], sp += n+1; sp <= sp1; sp++)
	478	sp[0] = sp[2] + i1;
b5f04745	479	return (1);
1e2c9ae9 RC	480	}
1e2c9ae9 RC	481
130081c8 RC	482	/*
	483	* Add pairs of items (item & item1).
	484	*/
1e2c9ae9	485	static
130081c8	486	additem(buf, item, item1)
1e2c9ae9	487	char buf[PBLKSIZ];
130081c8	488	datum item, item1;
1e2c9ae9 RC	489	{
	490	register short *sp;
	491	register i1, i2;
	492
	493	sp = (short *)buf;
	494	i1 = PBLKSIZ;
b5f04745 RC	495	i2 = sp[0];
	496	if (i2 > 0)
	497	i1 = sp[i2];
130081c8	498	i1 -= item.dsize + item1.dsize;
a5e1e880	499	if (i1 <= (i2+3) * (int)sizeof(short))
b5f04745	500	return (0);
130081c8 RC	501	sp[0] += 2;
	502	sp[++i2] = i1 + item1.dsize;
	503	bcopy(item.dptr, &buf[i1 + item1.dsize], item.dsize);
	504	sp[++i2] = i1;
	505	bcopy(item1.dptr, &buf[i1], item1.dsize);
b5f04745	506	return (1);
1e2c9ae9 RC	507	}
1e2c9ae9 RC	508
130081c8	509	#ifdef DEBUG
1e2c9ae9 RC	510	static
	511	chkblk(buf)
	512	char buf[PBLKSIZ];
	513	{
	514	register short *sp;
	515	register t, i;
	516
	517	sp = (short *)buf;
	518	t = PBLKSIZ;
	519	for (i=0; i<sp[0]; i++) {
	520	if (sp[i+1] > t)
b5f04745	521	return (-1);
1e2c9ae9 RC	522	t = sp[i+1];
	523	}
	524	if (t < (sp[0]+1)*sizeof(short))
b5f04745 RC	525	return (-1);
b5f04745 RC	526	return (0);
1e2c9ae9	527	}
130081c8	528	#endif