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

#ifndef lint
static char sccsid[] = "@(#)ndbm.c	4.2 (Berkeley) %G%";
#endif

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

#define NULL    (char *)0
#define BYTESIZ 8

static  datum firsthash();
static  dbm_access();
static  getbit();
static  setbit();
static  datum makdatum();
static  cmpdatum();
static  long hashinc();
static  long dcalchash();
static  delitem();
static  additem();
static  chkblk();
extern  int errno;

DBM *
ndbmopen(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);
	}
	if ((flags & 03) == O_WRONLY)
		flags = (flags & ~03) | O_RDWR;
	db->db_flags = 0;
	strcpy(db->db_pagbuf, file);
	strcat(db->db_pagbuf, ".pag");
	db->db_pagf = open(db->db_pagbuf, flags, mode);
	if (db->db_pagf < 0)
		goto bad;
	strcpy(db->db_pagbuf, file);
	strcat(db->db_pagbuf, ".dir");
	db->db_dirf = open(db->db_pagbuf, flags, mode);
	if (db->db_dirf < 0)
		goto bad1;
	fstat(db->db_dirf, &statb);
	db->db_maxbno = statb.st_size*BYTESIZ-1;
	db->db_pagbno = db->db_dirbno = -1;
	return (db);
bad1:
	(void) close(db->db_pagf);
bad:
	free((char *)db);
	return ((DBM *)0);
}

void
ndbmclose(db)
	DBM *db;
{

	(void) close(db->db_dirf);
	(void) close(db->db_pagf);
	free((char *)db);
}

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

	hash = dcalchash(key);
	for (db->db_hmask=0;; db->db_hmask=(db->db_hmask<<1)+1) {
		db->db_blkno = hash & db->db_hmask;
		db->db_bitno = db->db_blkno + db->db_hmask;
		if (getbit(db) == 0)
			break;
	}
	return (db->db_blkno);
}

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

	dbm_access(db, dcalchash(key));
	for (i=0;; i+=2) {
		item = makdatum(db->db_pagbuf, i);
		if (item.dptr == NULL)
			return (item);
		if (cmpdatum(key, item) == 0) {
			item = makdatum(db->db_pagbuf, i+1);
			if (item.dptr == NULL)
				printf("items not in pairs\n");
			return (item);
		}
	}
}

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

	if (dbrdonly(db)) {
		errno = EPERM;
		return (-1);
	}
	dbm_access(db, dcalchash(key));
	for (i=0;; i+=2) {
		item = makdatum(db->db_pagbuf, i);
		if (item.dptr == NULL)
			return (-1);
		if (cmpdatum(key, item) == 0) {
			delitem(db->db_pagbuf, i);
			delitem(db->db_pagbuf, i);
			break;
		}
	}
	(void) lseek(db->db_pagf, db->db_blkno*PBLKSIZ, L_SET);
	(void) write(db->db_pagf, db->db_pagbuf, PBLKSIZ);
	db->db_pagbno = db->db_blkno;
	return (0);
}

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

	if (dbrdonly(db)) {
		errno = EPERM;
		return (-1);
	}
loop:
	dbm_access(db, dcalchash(key));
	for (i=0;; i+=2) {
		item = makdatum(db->db_pagbuf, i);
		if (item.dptr == NULL)
			break;
		if (cmpdatum(key, item) == 0) {
			if (!replace)
				return (1);
			delitem(db->db_pagbuf, i);
			delitem(db->db_pagbuf, i);
			break;
		}
	}
	i = additem(db->db_pagbuf, key);
	if (i < 0)
		goto split;
	if (additem(db->db_pagbuf, dat) < 0) {
		delitem(db->db_pagbuf, i);
		goto split;
	}
	(void) lseek(db->db_pagf, db->db_blkno*PBLKSIZ, L_SET);
	(void) write(db->db_pagf, db->db_pagbuf, PBLKSIZ);
	db->db_pagbno = db->db_blkno;
	return (0);

split:
	if (key.dsize+dat.dsize+2*sizeof(short) >= PBLKSIZ) {
		errno = ENOSPC;
		return (-1);
	}
	bzero(ovfbuf, PBLKSIZ);
	for (i=0;;) {
		item = makdatum(db->db_pagbuf, i);
		if (item.dptr == NULL)
			break;
		if (dcalchash(item) & (db->db_hmask+1)) {
			additem(ovfbuf, item);
			delitem(db->db_pagbuf, i);
			item = makdatum(db->db_pagbuf, i);
			if (item.dptr == NULL) {
				printf("ndbm: split not paired\n");
				break;
			}
			additem(ovfbuf, item);
			delitem(db->db_pagbuf, i);
			continue;
		}
		i += 2;
	}
	(void) lseek(db->db_pagf, db->db_blkno*PBLKSIZ, L_SET);
	(void) write(db->db_pagf, db->db_pagbuf, PBLKSIZ);
	db->db_pagbno = db->db_blkno;
	(void) lseek(db->db_pagf, (db->db_blkno+db->db_hmask+1)*PBLKSIZ, L_SET);
	(void) write(db->db_pagf, ovfbuf, PBLKSIZ);
	setbit(db);
	goto loop;
}

datum
dbmfirstkey(db)
	DBM *db;
{

	return (firsthash(db, 0L));
}

datum
dbmnextkey(db, key)
	register DBM *db;
	datum key;
{
	register i;
	datum item, bitem;
	long hash;
	int f;

	hash = dcalchash(key);
	dbm_access(db, hash);
	f = 1;
	for (i=0;; i+=2) {
		item = makdatum(db->db_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(db, hash);
	if (hash == 0)
		return (item);
	return (firsthash(db, hash));
}

static datum
firsthash(db, hash)
	register DBM *db;
	long hash;
{
	register i;
	datum item, bitem;

loop:
	dbm_access(db, hash);
	bitem = makdatum(db->db_pagbuf, 0);
	for (i=2;; i+=2) {
		item = makdatum(db->db_pagbuf, i);
		if (item.dptr == NULL)
			break;
		if (cmpdatum(bitem, item) < 0)
			bitem = item;
	}
	if (bitem.dptr != NULL)
		return (bitem);
	hash = hashinc(db, hash);
	if (hash == 0)
		return (item);
	goto loop;
}

static
dbm_access(db, hash)
	register DBM *db;
	long hash;
{
	
	for (db->db_hmask=0;; db->db_hmask=(db->db_hmask<<1)+1) {
		db->db_blkno = hash & db->db_hmask;
		db->db_bitno = db->db_blkno + db->db_hmask;
		if (getbit(db) == 0)
			break;
	}
	if (db->db_blkno != db->db_pagbno) {
		bzero(db->db_pagbuf, PBLKSIZ);
		(void) lseek(db->db_pagf, db->db_blkno*PBLKSIZ, L_SET);
		(void) read(db->db_pagf, db->db_pagbuf, PBLKSIZ);
		chkblk(db->db_pagbuf);
		db->db_pagbno = db->db_blkno;
	}
}

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

	if (db->db_bitno > db->db_maxbno)
		return (0);
	n = db->db_bitno % BYTESIZ;
	bn = db->db_bitno / BYTESIZ;
	i = bn % DBLKSIZ;
	b = bn / DBLKSIZ;
	if (b != db->db_dirbno) {
		bzero(db->db_dirbuf, DBLKSIZ);
		(void) lseek(db->db_dirf, (long)b*DBLKSIZ, L_SET);
		(void) read(db->db_dirf, db->db_dirbuf, DBLKSIZ);
		db->db_dirbno = b;
	}
	if (db->db_dirbuf[i] & (1<<n))
		return (1);
	return (0);
}

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

	if (dbrdonly(db)) {
		errno = EPERM;
		return (-1);
	}
	if (db->db_bitno > db->db_maxbno) {
		db->db_maxbno = db->db_bitno;
		getbit(db);
	}
	n = db->db_bitno % BYTESIZ;
	bn = db->db_bitno / BYTESIZ;
	i = bn % DBLKSIZ;
	b = bn / DBLKSIZ;
	db->db_dirbuf[i] |= 1<<n;
	(void) lseek(db->db_dirf, (long)b*DBLKSIZ, L_SET);
	(void) write(db->db_dirf, db->db_dirbuf, DBLKSIZ);
	db->db_dirbno = b;
}

static datum
makdatum(buf, n)
	char buf[PBLKSIZ];
{
	register short *sp;
	register 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);
}

static
cmpdatum(d1, d2)
	datum d1, d2;
{
	register n;
	register 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);
}

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->db_hmask;
	bit = db->db_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 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);
}

static
delitem(buf, n)
	char buf[PBLKSIZ];
{
	register short *sp;
	register 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:
	printf("ndbm: bad delitem\n");
	abort();
}

static
additem(buf, item)
	char buf[PBLKSIZ];
	datum item;
{
	register short *sp;
	register i1, i2;

	sp = (short *)buf;
	i1 = PBLKSIZ;
	if (sp[0] > 0)
		i1 = sp[sp[0]+1-1];
	i1 -= item.dsize;
	i2 = (sp[0]+2) * sizeof(short);
	if (i1 <= i2)
		return (-1);
	sp[sp[0]+1] = i1;
	for (i2=0; i2<item.dsize; i2++) {
		buf[i1] = item.dptr[i2];
		i1++;
	}
	sp[0]++;
	return (sp[0]-1);
}

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)
			goto bad;
		t = sp[i+1];
	}
	if (t < (sp[0]+1)*sizeof(short))
		goto bad;
	return;

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