xref: /illumos-gate/usr/src/lib/libnsl/yp/dbm.c (revision 89fbfe0d)
17c478bd9Sstevel@tonic-gate /*
27c478bd9Sstevel@tonic-gate  * CDDL HEADER START
37c478bd9Sstevel@tonic-gate  *
47c478bd9Sstevel@tonic-gate  * The contents of this file are subject to the terms of the
57c478bd9Sstevel@tonic-gate  * Common Development and Distribution License, Version 1.0 only
67c478bd9Sstevel@tonic-gate  * (the "License").  You may not use this file except in compliance
77c478bd9Sstevel@tonic-gate  * with the License.
87c478bd9Sstevel@tonic-gate  *
97c478bd9Sstevel@tonic-gate  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
107c478bd9Sstevel@tonic-gate  * or http://www.opensolaris.org/os/licensing.
117c478bd9Sstevel@tonic-gate  * See the License for the specific language governing permissions
127c478bd9Sstevel@tonic-gate  * and limitations under the License.
137c478bd9Sstevel@tonic-gate  *
147c478bd9Sstevel@tonic-gate  * When distributing Covered Code, include this CDDL HEADER in each
157c478bd9Sstevel@tonic-gate  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
167c478bd9Sstevel@tonic-gate  * If applicable, add the following below this CDDL HEADER, with the
177c478bd9Sstevel@tonic-gate  * fields enclosed by brackets "[]" replaced with your own identifying
187c478bd9Sstevel@tonic-gate  * information: Portions Copyright [yyyy] [name of copyright owner]
197c478bd9Sstevel@tonic-gate  *
207c478bd9Sstevel@tonic-gate  * CDDL HEADER END
217c478bd9Sstevel@tonic-gate  */
2261961e0fSrobinson 
237c478bd9Sstevel@tonic-gate /*
24e8031f0aSraf  * Copyright 2006 Sun Microsystems, Inc.  All rights reserved.
257c478bd9Sstevel@tonic-gate  * Use is subject to license terms.
267c478bd9Sstevel@tonic-gate  */
277c478bd9Sstevel@tonic-gate 
287c478bd9Sstevel@tonic-gate /*	Copyright (c) 1983, 1984, 1985, 1986, 1987, 1988, 1989 AT&T */
297c478bd9Sstevel@tonic-gate /*	  All Rights Reserved   */
307c478bd9Sstevel@tonic-gate 
317c478bd9Sstevel@tonic-gate /*
327c478bd9Sstevel@tonic-gate  * Portions of this source code were derived from Berkeley
337c478bd9Sstevel@tonic-gate  * under license from the Regents of the University of
347c478bd9Sstevel@tonic-gate  * California.
357c478bd9Sstevel@tonic-gate  */
367c478bd9Sstevel@tonic-gate 
37e8031f0aSraf #include "mt.h"
387c478bd9Sstevel@tonic-gate #include <rpcsvc/dbm.h>
397c478bd9Sstevel@tonic-gate #include <sys/types.h>
407c478bd9Sstevel@tonic-gate #include <sys/stat.h>
417c478bd9Sstevel@tonic-gate #include <string.h>
427c478bd9Sstevel@tonic-gate #include <unistd.h>
437c478bd9Sstevel@tonic-gate #include <stdlib.h>
447c478bd9Sstevel@tonic-gate #include <fcntl.h>
457c478bd9Sstevel@tonic-gate #include <stdio.h>
467c478bd9Sstevel@tonic-gate #include <errno.h>
477c478bd9Sstevel@tonic-gate 
487c478bd9Sstevel@tonic-gate void dbm_access(long);
497c478bd9Sstevel@tonic-gate void delitem(char *, int);
507c478bd9Sstevel@tonic-gate void chkblk(char *);
517c478bd9Sstevel@tonic-gate int  additem(char *, datum);
527c478bd9Sstevel@tonic-gate int  getbit(void);
537c478bd9Sstevel@tonic-gate int  setbit(void);
547c478bd9Sstevel@tonic-gate int  cmpdatum(datum, datum);
557c478bd9Sstevel@tonic-gate 
567c478bd9Sstevel@tonic-gate int
dbminit(char * file)5761961e0fSrobinson dbminit(char *file)
587c478bd9Sstevel@tonic-gate {
597c478bd9Sstevel@tonic-gate 	struct stat statb;
607c478bd9Sstevel@tonic-gate 
617c478bd9Sstevel@tonic-gate 	dbrdonly = 0;
627c478bd9Sstevel@tonic-gate 	if (strlcpy(pagbuf, file, sizeof (pagbuf)) >= sizeof (pagbuf) ||
637c478bd9Sstevel@tonic-gate 	    strlcat(pagbuf, ".pag", sizeof (pagbuf)) >= sizeof (pagbuf)) {
647c478bd9Sstevel@tonic-gate 		/*
657c478bd9Sstevel@tonic-gate 		 * file.pag does not fit into pagbuf.
667c478bd9Sstevel@tonic-gate 		 * fails with ENAMETOOLONG.
677c478bd9Sstevel@tonic-gate 		 */
687c478bd9Sstevel@tonic-gate 		errno = ENAMETOOLONG;
697c478bd9Sstevel@tonic-gate 		return (-1);
707c478bd9Sstevel@tonic-gate 	}
717c478bd9Sstevel@tonic-gate 	pagf = open(pagbuf, 2);
727c478bd9Sstevel@tonic-gate 	if (pagf < 0) {
737c478bd9Sstevel@tonic-gate 		pagf = open(pagbuf, 0);
747c478bd9Sstevel@tonic-gate 		dbrdonly = 1;
757c478bd9Sstevel@tonic-gate 	}
767c478bd9Sstevel@tonic-gate 	/*
777c478bd9Sstevel@tonic-gate 	 * We know this won't overflow so it is safe to ignore the
787c478bd9Sstevel@tonic-gate 	 * return value; we use strl* to prevent false hits in
797c478bd9Sstevel@tonic-gate 	 * code sweeps.
807c478bd9Sstevel@tonic-gate 	 */
817c478bd9Sstevel@tonic-gate 	(void) strlcpy(pagbuf, file, sizeof (pagbuf));
827c478bd9Sstevel@tonic-gate 	(void) strlcat(pagbuf, ".dir", sizeof (pagbuf));
837c478bd9Sstevel@tonic-gate 	dirf = open(pagbuf, 2);
847c478bd9Sstevel@tonic-gate 	if (dirf < 0) {
857c478bd9Sstevel@tonic-gate 		dirf = open(pagbuf, 0);
867c478bd9Sstevel@tonic-gate 		dbrdonly = 1;
877c478bd9Sstevel@tonic-gate 	}
8861961e0fSrobinson 	if (pagf < 0 || dirf < 0)
897c478bd9Sstevel@tonic-gate 		return (-1);
90e8031f0aSraf 	(void) fstat(dirf, &statb);
917c478bd9Sstevel@tonic-gate 	maxbno = statb.st_size*BYTESIZ-1;
927c478bd9Sstevel@tonic-gate 	return (0);
937c478bd9Sstevel@tonic-gate }
947c478bd9Sstevel@tonic-gate 
957c478bd9Sstevel@tonic-gate static long oldb1 = -1;
967c478bd9Sstevel@tonic-gate static long oldb2 = -1;
977c478bd9Sstevel@tonic-gate 
987c478bd9Sstevel@tonic-gate /* Avoid using cached data for subsequent accesses. */
997c478bd9Sstevel@tonic-gate int
dbmflush(void)10061961e0fSrobinson dbmflush(void)
1017c478bd9Sstevel@tonic-gate {
1027c478bd9Sstevel@tonic-gate 	oldb1 = -1;
1037c478bd9Sstevel@tonic-gate 	oldb2 = -1;
1047c478bd9Sstevel@tonic-gate 	return (0);
1057c478bd9Sstevel@tonic-gate }
1067c478bd9Sstevel@tonic-gate 
1077c478bd9Sstevel@tonic-gate /* Clean up after ourself. */
1087c478bd9Sstevel@tonic-gate int
dbmclose(void)10961961e0fSrobinson dbmclose(void)
1107c478bd9Sstevel@tonic-gate {
1117c478bd9Sstevel@tonic-gate 	(void) close(pagf);
1127c478bd9Sstevel@tonic-gate 	(void) close(dirf);
1137c478bd9Sstevel@tonic-gate 	bitno = 0;
1147c478bd9Sstevel@tonic-gate 	maxbno = 0;
1157c478bd9Sstevel@tonic-gate 	blkno = 0;
1167c478bd9Sstevel@tonic-gate 	hmask = 0;
1177c478bd9Sstevel@tonic-gate 	oldb1 = -1;
1187c478bd9Sstevel@tonic-gate 	oldb2 = -1;
1197c478bd9Sstevel@tonic-gate 	return (0);
1207c478bd9Sstevel@tonic-gate }
1217c478bd9Sstevel@tonic-gate 
1227c478bd9Sstevel@tonic-gate long
forder(datum key)12361961e0fSrobinson forder(datum key)
1247c478bd9Sstevel@tonic-gate {
1257c478bd9Sstevel@tonic-gate 	long hash;
1267c478bd9Sstevel@tonic-gate 
1277c478bd9Sstevel@tonic-gate 	hash = calchash(key);
1287c478bd9Sstevel@tonic-gate 	for (hmask = 0; ; hmask = (hmask<<1) + 1) {
1297c478bd9Sstevel@tonic-gate 		blkno = hash & hmask;
1307c478bd9Sstevel@tonic-gate 		bitno = blkno + hmask;
1317c478bd9Sstevel@tonic-gate 		if (getbit() == 0)
1327c478bd9Sstevel@tonic-gate 			break;
1337c478bd9Sstevel@tonic-gate 	}
1347c478bd9Sstevel@tonic-gate 	return (blkno);
1357c478bd9Sstevel@tonic-gate }
1367c478bd9Sstevel@tonic-gate 
1377c478bd9Sstevel@tonic-gate datum
fetch(datum key)13861961e0fSrobinson fetch(datum key)
1397c478bd9Sstevel@tonic-gate {
1407c478bd9Sstevel@tonic-gate 	int i;
1417c478bd9Sstevel@tonic-gate 	datum item;
1427c478bd9Sstevel@tonic-gate 
1437c478bd9Sstevel@tonic-gate 	dbm_access(calchash(key));
1447c478bd9Sstevel@tonic-gate 	for (i = 0; ; i += 2) {
1457c478bd9Sstevel@tonic-gate 		item = makdatum(pagbuf, i);
1467c478bd9Sstevel@tonic-gate 		if (item.dptr == NULL) {
1477c478bd9Sstevel@tonic-gate 			return (item);
1487c478bd9Sstevel@tonic-gate 		}
1497c478bd9Sstevel@tonic-gate 		if (cmpdatum(key, item) == 0) {
1507c478bd9Sstevel@tonic-gate 			item = makdatum(pagbuf, i+1);
1517c478bd9Sstevel@tonic-gate 			if (item.dptr == NULL)
1527c478bd9Sstevel@tonic-gate 				(void) printf("items not in pairs\n");
1537c478bd9Sstevel@tonic-gate 			return (item);
1547c478bd9Sstevel@tonic-gate 		}
1557c478bd9Sstevel@tonic-gate 	}
1567c478bd9Sstevel@tonic-gate }
1577c478bd9Sstevel@tonic-gate 
1587c478bd9Sstevel@tonic-gate int
delete(datum key)15961961e0fSrobinson delete(datum key)
1607c478bd9Sstevel@tonic-gate {
1617c478bd9Sstevel@tonic-gate 	int i;
1627c478bd9Sstevel@tonic-gate 	datum item;
1637c478bd9Sstevel@tonic-gate 
16461961e0fSrobinson 	if (dbrdonly)
1657c478bd9Sstevel@tonic-gate 		return (-1);
1667c478bd9Sstevel@tonic-gate 	dbm_access(calchash(key));
1677c478bd9Sstevel@tonic-gate 	for (i = 0; ; i += 2) {
1687c478bd9Sstevel@tonic-gate 		item = makdatum(pagbuf, i);
16961961e0fSrobinson 		if (item.dptr == NULL)
1707c478bd9Sstevel@tonic-gate 			return (-1);
1717c478bd9Sstevel@tonic-gate 		if (cmpdatum(key, item) == 0) {
1727c478bd9Sstevel@tonic-gate 			delitem(pagbuf, i);
1737c478bd9Sstevel@tonic-gate 			delitem(pagbuf, i);
1747c478bd9Sstevel@tonic-gate 			break;
1757c478bd9Sstevel@tonic-gate 		}
1767c478bd9Sstevel@tonic-gate 	}
1777c478bd9Sstevel@tonic-gate 	(void) lseek(pagf, blkno*PBLKSIZ, 0);
1787c478bd9Sstevel@tonic-gate 	(void) write(pagf, pagbuf, PBLKSIZ);
1797c478bd9Sstevel@tonic-gate 	return (0);
1807c478bd9Sstevel@tonic-gate }
1817c478bd9Sstevel@tonic-gate 
1827c478bd9Sstevel@tonic-gate int
store(datum key,datum dat)18361961e0fSrobinson store(datum key, datum dat)
1847c478bd9Sstevel@tonic-gate {
1857c478bd9Sstevel@tonic-gate 	int i;
1867c478bd9Sstevel@tonic-gate 	datum item;
1877c478bd9Sstevel@tonic-gate 	char ovfbuf[PBLKSIZ];
1887c478bd9Sstevel@tonic-gate 
18961961e0fSrobinson 	if (dbrdonly)
1907c478bd9Sstevel@tonic-gate 		return (-1);
1917c478bd9Sstevel@tonic-gate loop:
1927c478bd9Sstevel@tonic-gate 	dbm_access(calchash(key));
1937c478bd9Sstevel@tonic-gate 	for (i = 0; ; i += 2) {
1947c478bd9Sstevel@tonic-gate 		item = makdatum(pagbuf, i);
1957c478bd9Sstevel@tonic-gate 		if (item.dptr == NULL)
1967c478bd9Sstevel@tonic-gate 			break;
1977c478bd9Sstevel@tonic-gate 		if (cmpdatum(key, item) == 0) {
1987c478bd9Sstevel@tonic-gate 			delitem(pagbuf, i);
1997c478bd9Sstevel@tonic-gate 			delitem(pagbuf, i);
2007c478bd9Sstevel@tonic-gate 			break;
2017c478bd9Sstevel@tonic-gate 		}
2027c478bd9Sstevel@tonic-gate 	}
2037c478bd9Sstevel@tonic-gate 	i = additem(pagbuf, key);
2047c478bd9Sstevel@tonic-gate 	if (i < 0)
2057c478bd9Sstevel@tonic-gate 		goto split;
2067c478bd9Sstevel@tonic-gate 	if (additem(pagbuf, dat) < 0) {
2077c478bd9Sstevel@tonic-gate 		delitem(pagbuf, i);
2087c478bd9Sstevel@tonic-gate 		goto split;
2097c478bd9Sstevel@tonic-gate 	}
2107c478bd9Sstevel@tonic-gate 	(void) lseek(pagf, blkno*PBLKSIZ, 0);
2117c478bd9Sstevel@tonic-gate 	(void) write(pagf, pagbuf, PBLKSIZ);
2127c478bd9Sstevel@tonic-gate 	return (0);
2137c478bd9Sstevel@tonic-gate 
2147c478bd9Sstevel@tonic-gate split:
2157c478bd9Sstevel@tonic-gate 	if (key.dsize + dat.dsize + 3 * sizeof (short) >= PBLKSIZ) {
2167c478bd9Sstevel@tonic-gate 		(void) printf("entry too big\n");
2177c478bd9Sstevel@tonic-gate 		return (-1);
2187c478bd9Sstevel@tonic-gate 	}
21961961e0fSrobinson 	(void) memset(&ovfbuf, 0, PBLKSIZ);
2207c478bd9Sstevel@tonic-gate 	for (i = 0; ; ) {
2217c478bd9Sstevel@tonic-gate 		item = makdatum(pagbuf, i);
2227c478bd9Sstevel@tonic-gate 		if (item.dptr == NULL)
2237c478bd9Sstevel@tonic-gate 			break;
2247c478bd9Sstevel@tonic-gate 		if (calchash(item) & (hmask+1)) {
2257c478bd9Sstevel@tonic-gate 			(void) additem(ovfbuf, item);
2267c478bd9Sstevel@tonic-gate 			delitem(pagbuf, i);
2277c478bd9Sstevel@tonic-gate 			item = makdatum(pagbuf, i);
2287c478bd9Sstevel@tonic-gate 			if (item.dptr == NULL) {
2297c478bd9Sstevel@tonic-gate 				(void) printf("split not paired\n");
2307c478bd9Sstevel@tonic-gate 				break;
2317c478bd9Sstevel@tonic-gate 			}
2327c478bd9Sstevel@tonic-gate 			(void) additem(ovfbuf, item);
2337c478bd9Sstevel@tonic-gate 			delitem(pagbuf, i);
2347c478bd9Sstevel@tonic-gate 			continue;
2357c478bd9Sstevel@tonic-gate 		}
2367c478bd9Sstevel@tonic-gate 		i += 2;
2377c478bd9Sstevel@tonic-gate 	}
2387c478bd9Sstevel@tonic-gate 	(void) lseek(pagf, blkno*PBLKSIZ, 0);
2397c478bd9Sstevel@tonic-gate 	if (write(pagf, pagbuf, PBLKSIZ) < 0) {
2407c478bd9Sstevel@tonic-gate 		return (-1);
2417c478bd9Sstevel@tonic-gate 	}
2427c478bd9Sstevel@tonic-gate 	(void) lseek(pagf, (blkno+hmask+1)*PBLKSIZ, 0);
2437c478bd9Sstevel@tonic-gate 	if (write(pagf, ovfbuf, PBLKSIZ) < 0) {
2447c478bd9Sstevel@tonic-gate 		return (-1);
2457c478bd9Sstevel@tonic-gate 	}
2467c478bd9Sstevel@tonic-gate 	if (setbit() < 0) {
2477c478bd9Sstevel@tonic-gate 		return (-1);
2487c478bd9Sstevel@tonic-gate 	}
2497c478bd9Sstevel@tonic-gate 	goto loop;
2507c478bd9Sstevel@tonic-gate }
2517c478bd9Sstevel@tonic-gate 
2527c478bd9Sstevel@tonic-gate datum
firstkey(void)25361961e0fSrobinson firstkey(void)
2547c478bd9Sstevel@tonic-gate {
25561961e0fSrobinson 	return (firsthash(0L));
2567c478bd9Sstevel@tonic-gate }
2577c478bd9Sstevel@tonic-gate 
2587c478bd9Sstevel@tonic-gate datum
nextkey(datum key)25961961e0fSrobinson nextkey(datum key)
2607c478bd9Sstevel@tonic-gate {
2617c478bd9Sstevel@tonic-gate 	int i;
2627c478bd9Sstevel@tonic-gate 	datum item, bitem;
2637c478bd9Sstevel@tonic-gate 	long hash;
2647c478bd9Sstevel@tonic-gate 	int f;
2657c478bd9Sstevel@tonic-gate 
2667c478bd9Sstevel@tonic-gate #ifdef lint
2677c478bd9Sstevel@tonic-gate 	bitem.dptr = NULL;
2687c478bd9Sstevel@tonic-gate 	bitem.dsize = 0;
2697c478bd9Sstevel@tonic-gate #endif /* lint */
2707c478bd9Sstevel@tonic-gate 	hash = calchash(key);
2717c478bd9Sstevel@tonic-gate 	dbm_access(hash);
2727c478bd9Sstevel@tonic-gate 	f = 1;
2737c478bd9Sstevel@tonic-gate 	for (i = 0; ; i += 2) {
2747c478bd9Sstevel@tonic-gate 		item = makdatum(pagbuf, i);
2757c478bd9Sstevel@tonic-gate 		if (item.dptr == NULL)
2767c478bd9Sstevel@tonic-gate 			break;
2777c478bd9Sstevel@tonic-gate 		if (cmpdatum(key, item) <= 0)
2787c478bd9Sstevel@tonic-gate 			continue;
2797c478bd9Sstevel@tonic-gate 		if (f || cmpdatum(bitem, item) < 0) {
2807c478bd9Sstevel@tonic-gate 			bitem = item;
2817c478bd9Sstevel@tonic-gate 			f = 0;
2827c478bd9Sstevel@tonic-gate 		}
2837c478bd9Sstevel@tonic-gate 	}
28461961e0fSrobinson 	if (f == 0)
2857c478bd9Sstevel@tonic-gate 		return (bitem);
2867c478bd9Sstevel@tonic-gate 	hash = hashinc(hash);
28761961e0fSrobinson 	if (hash == 0)
2887c478bd9Sstevel@tonic-gate 		return (item);
28961961e0fSrobinson 	return (firsthash(hash));
2907c478bd9Sstevel@tonic-gate }
2917c478bd9Sstevel@tonic-gate 
2927c478bd9Sstevel@tonic-gate datum
firsthash(long hash)29361961e0fSrobinson firsthash(long hash)
2947c478bd9Sstevel@tonic-gate {
2957c478bd9Sstevel@tonic-gate 	int i;
2967c478bd9Sstevel@tonic-gate 	datum item, bitem;
2977c478bd9Sstevel@tonic-gate 
2987c478bd9Sstevel@tonic-gate loop:
2997c478bd9Sstevel@tonic-gate 	dbm_access(hash);
3007c478bd9Sstevel@tonic-gate 	bitem = makdatum(pagbuf, 0);
3017c478bd9Sstevel@tonic-gate 	for (i = 2; ; i += 2) {
3027c478bd9Sstevel@tonic-gate 		item = makdatum(pagbuf, i);
3037c478bd9Sstevel@tonic-gate 		if (item.dptr == NULL)
3047c478bd9Sstevel@tonic-gate 			break;
3057c478bd9Sstevel@tonic-gate 		if (cmpdatum(bitem, item) < 0)
3067c478bd9Sstevel@tonic-gate 			bitem = item;
3077c478bd9Sstevel@tonic-gate 	}
30861961e0fSrobinson 	if (bitem.dptr != NULL)
3097c478bd9Sstevel@tonic-gate 		return (bitem);
3107c478bd9Sstevel@tonic-gate 	hash = hashinc(hash);
31161961e0fSrobinson 	if (hash == 0)
3127c478bd9Sstevel@tonic-gate 		return (item);
3137c478bd9Sstevel@tonic-gate 	goto loop;
3147c478bd9Sstevel@tonic-gate }
3157c478bd9Sstevel@tonic-gate 
3167c478bd9Sstevel@tonic-gate void
dbm_access(long hash)31761961e0fSrobinson dbm_access(long hash)
3187c478bd9Sstevel@tonic-gate {
3197c478bd9Sstevel@tonic-gate 	ssize_t readsize;
3207c478bd9Sstevel@tonic-gate 
3217c478bd9Sstevel@tonic-gate 	for (hmask = 0; ; hmask = (hmask<<1) + 1) {
3227c478bd9Sstevel@tonic-gate 		blkno = hash & hmask;
3237c478bd9Sstevel@tonic-gate 		bitno = blkno + hmask;
3247c478bd9Sstevel@tonic-gate 		if (getbit() == 0)
3257c478bd9Sstevel@tonic-gate 			break;
3267c478bd9Sstevel@tonic-gate 	}
3277c478bd9Sstevel@tonic-gate 	if (blkno != oldb1) {
3287c478bd9Sstevel@tonic-gate 		(void) lseek(pagf, blkno*PBLKSIZ, 0);
3297c478bd9Sstevel@tonic-gate 		readsize = read(pagf, pagbuf, PBLKSIZ);
3307c478bd9Sstevel@tonic-gate 		if (readsize != PBLKSIZ) {
33161961e0fSrobinson 			if (readsize < 0)
33261961e0fSrobinson 				readsize = 0;
33361961e0fSrobinson 			(void) memset((&pagbuf+readsize), 0, PBLKSIZ-readsize);
3347c478bd9Sstevel@tonic-gate 		}
3357c478bd9Sstevel@tonic-gate 		chkblk(pagbuf);
3367c478bd9Sstevel@tonic-gate 		oldb1 = blkno;
3377c478bd9Sstevel@tonic-gate 	}
3387c478bd9Sstevel@tonic-gate }
3397c478bd9Sstevel@tonic-gate 
3407c478bd9Sstevel@tonic-gate int
getbit(void)3417c478bd9Sstevel@tonic-gate getbit(void)
3427c478bd9Sstevel@tonic-gate {
3437c478bd9Sstevel@tonic-gate 	long bn;
3447c478bd9Sstevel@tonic-gate 	ssize_t readsize;
3457c478bd9Sstevel@tonic-gate 	long b, i, n;
3467c478bd9Sstevel@tonic-gate 
34761961e0fSrobinson 	if (bitno > maxbno)
3487c478bd9Sstevel@tonic-gate 		return (0);
3497c478bd9Sstevel@tonic-gate 	n = bitno % BYTESIZ;
3507c478bd9Sstevel@tonic-gate 	bn = bitno / BYTESIZ;
3517c478bd9Sstevel@tonic-gate 	i = bn % DBLKSIZ;
3527c478bd9Sstevel@tonic-gate 	b = bn / DBLKSIZ;
3537c478bd9Sstevel@tonic-gate 	if (b != oldb2) {
3547c478bd9Sstevel@tonic-gate 		(void) lseek(dirf, (long)b*DBLKSIZ, 0);
3557c478bd9Sstevel@tonic-gate 		readsize = read(dirf, dirbuf, DBLKSIZ);
3567c478bd9Sstevel@tonic-gate 		if (readsize != DBLKSIZ) {
35761961e0fSrobinson 			if (readsize < 0)
35861961e0fSrobinson 				readsize = 0;
35961961e0fSrobinson 			(void) memset(&dirbuf+readsize, 0, DBLKSIZ-readsize);
3607c478bd9Sstevel@tonic-gate 		}
3617c478bd9Sstevel@tonic-gate 		oldb2 = b;
3627c478bd9Sstevel@tonic-gate 	}
36361961e0fSrobinson 	if (dirbuf[i] & (1<<n))
3647c478bd9Sstevel@tonic-gate 		return (1);
3657c478bd9Sstevel@tonic-gate 	return (0);
3667c478bd9Sstevel@tonic-gate }
3677c478bd9Sstevel@tonic-gate 
3687c478bd9Sstevel@tonic-gate int
setbit(void)3697c478bd9Sstevel@tonic-gate setbit(void)
3707c478bd9Sstevel@tonic-gate {
3717c478bd9Sstevel@tonic-gate 	long bn;
3727c478bd9Sstevel@tonic-gate 	long i, n, b;
3737c478bd9Sstevel@tonic-gate 
37461961e0fSrobinson 	if (dbrdonly)
3757c478bd9Sstevel@tonic-gate 		return (-1);
3767c478bd9Sstevel@tonic-gate 	if (bitno > maxbno) {
3777c478bd9Sstevel@tonic-gate 		maxbno = bitno;
3787c478bd9Sstevel@tonic-gate 		(void) getbit();
3797c478bd9Sstevel@tonic-gate 	}
3807c478bd9Sstevel@tonic-gate 	n = bitno % BYTESIZ;
3817c478bd9Sstevel@tonic-gate 	bn = bitno / BYTESIZ;
3827c478bd9Sstevel@tonic-gate 	i = bn % DBLKSIZ;
3837c478bd9Sstevel@tonic-gate 	b = bn / DBLKSIZ;
3847c478bd9Sstevel@tonic-gate 	dirbuf[i] |= 1<<n;
3857c478bd9Sstevel@tonic-gate 	(void) lseek(dirf, (long)b*DBLKSIZ, 0);
38661961e0fSrobinson 	if (write(dirf, dirbuf, DBLKSIZ) < 0)
3877c478bd9Sstevel@tonic-gate 		return (-1);
3887c478bd9Sstevel@tonic-gate 	return (0);
3897c478bd9Sstevel@tonic-gate }
3907c478bd9Sstevel@tonic-gate 
3917c478bd9Sstevel@tonic-gate datum
makdatum(char * buf,int n)392*89fbfe0dSToomas Soome makdatum(char *buf, int n)
3937c478bd9Sstevel@tonic-gate {
3947c478bd9Sstevel@tonic-gate 	short *sp;
3957c478bd9Sstevel@tonic-gate 	int t;
3967c478bd9Sstevel@tonic-gate 	datum item;
3977c478bd9Sstevel@tonic-gate 
39861961e0fSrobinson 	/* LINTED pointer cast */
3997c478bd9Sstevel@tonic-gate 	sp = (short *)buf;
4007c478bd9Sstevel@tonic-gate 	if (n < 0 || n >= sp[0])
4017c478bd9Sstevel@tonic-gate 		goto null;
4027c478bd9Sstevel@tonic-gate 	t = PBLKSIZ;
4037c478bd9Sstevel@tonic-gate 	if (n > 0)
4047c478bd9Sstevel@tonic-gate 		t = sp[n+1-1];
4057c478bd9Sstevel@tonic-gate 	item.dptr = buf+sp[n+1];
4067c478bd9Sstevel@tonic-gate 	item.dsize = t - sp[n+1];
4077c478bd9Sstevel@tonic-gate 	return (item);
4087c478bd9Sstevel@tonic-gate 
4097c478bd9Sstevel@tonic-gate null:
4107c478bd9Sstevel@tonic-gate 	item.dptr = NULL;
4117c478bd9Sstevel@tonic-gate 	item.dsize = 0;
4127c478bd9Sstevel@tonic-gate 	return (item);
4137c478bd9Sstevel@tonic-gate }
4147c478bd9Sstevel@tonic-gate 
4157c478bd9Sstevel@tonic-gate int
cmpdatum(datum d1,datum d2)41661961e0fSrobinson cmpdatum(datum d1, datum d2)
4177c478bd9Sstevel@tonic-gate {
4187c478bd9Sstevel@tonic-gate 	int n;
4197c478bd9Sstevel@tonic-gate 	char *p1, *p2;
4207c478bd9Sstevel@tonic-gate 
4217c478bd9Sstevel@tonic-gate 	n = d1.dsize;
42261961e0fSrobinson 	if (n != d2.dsize)
4237c478bd9Sstevel@tonic-gate 		return (n - d2.dsize);
42461961e0fSrobinson 	if (n == 0)
4257c478bd9Sstevel@tonic-gate 		return (0);
4267c478bd9Sstevel@tonic-gate 	p1 = d1.dptr;
4277c478bd9Sstevel@tonic-gate 	p2 = d2.dptr;
428*89fbfe0dSToomas Soome 	do {
42961961e0fSrobinson 		if (*p1++ != *p2++)
4307c478bd9Sstevel@tonic-gate 			return (*--p1 - *--p2);
431*89fbfe0dSToomas Soome 	} while (--n);
4327c478bd9Sstevel@tonic-gate 	return (0);
4337c478bd9Sstevel@tonic-gate }
4347c478bd9Sstevel@tonic-gate 
4357c478bd9Sstevel@tonic-gate int	hitab[16]
4367c478bd9Sstevel@tonic-gate /*
4377c478bd9Sstevel@tonic-gate  * ken's
4387c478bd9Sstevel@tonic-gate  * {
4397c478bd9Sstevel@tonic-gate  *	055, 043, 036, 054, 063, 014, 004, 005,
4407c478bd9Sstevel@tonic-gate  *	010, 064, 077, 000, 035, 027, 025, 071,
4417c478bd9Sstevel@tonic-gate  * };
4427c478bd9Sstevel@tonic-gate  */
4437c478bd9Sstevel@tonic-gate 	= {	61, 57, 53, 49, 45, 41, 37, 33,
4447c478bd9Sstevel@tonic-gate 	29, 25, 21, 17, 13,  9,  5,  1,
4457c478bd9Sstevel@tonic-gate };
4467c478bd9Sstevel@tonic-gate long	hltab[64]
4477c478bd9Sstevel@tonic-gate 	= {
4487c478bd9Sstevel@tonic-gate 	06100151277L, 06106161736L, 06452611562L, 05001724107L,
4497c478bd9Sstevel@tonic-gate 	02614772546L, 04120731531L, 04665262210L, 07347467531L,
4507c478bd9Sstevel@tonic-gate 	06735253126L, 06042345173L, 03072226605L, 01464164730L,
4517c478bd9Sstevel@tonic-gate 	03247435524L, 07652510057L, 01546775256L, 05714532133L,
4527c478bd9Sstevel@tonic-gate 	06173260402L, 07517101630L, 02431460343L, 01743245566L,
4537c478bd9Sstevel@tonic-gate 	00261675137L, 02433103631L, 03421772437L, 04447707466L,
4547c478bd9Sstevel@tonic-gate 	04435620103L, 03757017115L, 03641531772L, 06767633246L,
4557c478bd9Sstevel@tonic-gate 	02673230344L, 00260612216L, 04133454451L, 00615531516L,
4567c478bd9Sstevel@tonic-gate 	06137717526L, 02574116560L, 02304023373L, 07061702261L,
4577c478bd9Sstevel@tonic-gate 	05153031405L, 05322056705L, 07401116734L, 06552375715L,
4587c478bd9Sstevel@tonic-gate 	06165233473L, 05311063631L, 01212221723L, 01052267235L,
4597c478bd9Sstevel@tonic-gate 	06000615237L, 01075222665L, 06330216006L, 04402355630L,
4607c478bd9Sstevel@tonic-gate 	01451177262L, 02000133436L, 06025467062L, 07121076461L,
4617c478bd9Sstevel@tonic-gate 	03123433522L, 01010635225L, 01716177066L, 05161746527L,
4627c478bd9Sstevel@tonic-gate 	01736635071L, 06243505026L, 03637211610L, 01756474365L,
4637c478bd9Sstevel@tonic-gate 	04723077174L, 03642763134L, 05750130273L, 03655541561L,
4647c478bd9Sstevel@tonic-gate };
4657c478bd9Sstevel@tonic-gate 
4667c478bd9Sstevel@tonic-gate long
hashinc(long hash)46761961e0fSrobinson hashinc(long hash)
4687c478bd9Sstevel@tonic-gate {
4697c478bd9Sstevel@tonic-gate 	long bit;
4707c478bd9Sstevel@tonic-gate 
4717c478bd9Sstevel@tonic-gate 	hash &= hmask;
4727c478bd9Sstevel@tonic-gate 	bit = hmask+1;
4737c478bd9Sstevel@tonic-gate 	for (; ; ) {
4747c478bd9Sstevel@tonic-gate 		bit >>= 1;
47561961e0fSrobinson 		if (bit == 0)
4767c478bd9Sstevel@tonic-gate 			return (0L);
47761961e0fSrobinson 		if ((hash&bit) == 0)
4787c478bd9Sstevel@tonic-gate 			return (hash|bit);
4797c478bd9Sstevel@tonic-gate 		hash &= ~bit;
4807c478bd9Sstevel@tonic-gate 	}
4817c478bd9Sstevel@tonic-gate }
4827c478bd9Sstevel@tonic-gate 
4837c478bd9Sstevel@tonic-gate long
calchash(datum item)48461961e0fSrobinson calchash(datum item)
4857c478bd9Sstevel@tonic-gate {
4867c478bd9Sstevel@tonic-gate 	int i, j, f;
4877c478bd9Sstevel@tonic-gate 	long hashl;
4887c478bd9Sstevel@tonic-gate 	int hashi;
4897c478bd9Sstevel@tonic-gate 
4907c478bd9Sstevel@tonic-gate 	hashl = 0;
4917c478bd9Sstevel@tonic-gate 	hashi = 0;
4927c478bd9Sstevel@tonic-gate 	for (i = 0; i < item.dsize; i++) {
4937c478bd9Sstevel@tonic-gate 		f = item.dptr[i];
4947c478bd9Sstevel@tonic-gate 		for (j = 0; j < BYTESIZ; j += 4) {
4957c478bd9Sstevel@tonic-gate 			hashi += hitab[f&017];
4967c478bd9Sstevel@tonic-gate 			hashl += hltab[hashi&63];
4977c478bd9Sstevel@tonic-gate 			f >>= 4;
4987c478bd9Sstevel@tonic-gate 		}
4997c478bd9Sstevel@tonic-gate 	}
5007c478bd9Sstevel@tonic-gate 	return (hashl);
5017c478bd9Sstevel@tonic-gate }
5027c478bd9Sstevel@tonic-gate 
5037c478bd9Sstevel@tonic-gate void
delitem(char * buf,int n)504*89fbfe0dSToomas Soome delitem(char *buf, int n)
5057c478bd9Sstevel@tonic-gate {
5067c478bd9Sstevel@tonic-gate 	short *sp;
5077c478bd9Sstevel@tonic-gate 	int i1, i2, i3;
5087c478bd9Sstevel@tonic-gate 
50961961e0fSrobinson 	/* LINTED pointer cast */
5107c478bd9Sstevel@tonic-gate 	sp = (short *)buf;
5117c478bd9Sstevel@tonic-gate 	if (n < 0 || n >= sp[0])
5127c478bd9Sstevel@tonic-gate 		goto bad;
5137c478bd9Sstevel@tonic-gate 	i1 = sp[n+1];
5147c478bd9Sstevel@tonic-gate 	i2 = PBLKSIZ;
5157c478bd9Sstevel@tonic-gate 	if (n > 0)
5167c478bd9Sstevel@tonic-gate 		i2 = sp[n+1-1];
5177c478bd9Sstevel@tonic-gate 	i3 = sp[sp[0]+1-1];
5187c478bd9Sstevel@tonic-gate 	if (i2 > i1)
5197c478bd9Sstevel@tonic-gate 	while (i1 > i3) {
5207c478bd9Sstevel@tonic-gate 		i1--;
5217c478bd9Sstevel@tonic-gate 		i2--;
5227c478bd9Sstevel@tonic-gate 		buf[i2] = buf[i1];
5237c478bd9Sstevel@tonic-gate 		buf[i1] = 0;
5247c478bd9Sstevel@tonic-gate 	}
5257c478bd9Sstevel@tonic-gate 	i2 -= i1;
5267c478bd9Sstevel@tonic-gate 	for (i1 = n + 1; i1 < sp[0]; i1++)
5277c478bd9Sstevel@tonic-gate 		sp[i1+1-1] = sp[i1+1] + i2;
5287c478bd9Sstevel@tonic-gate 	sp[0]--;
5297c478bd9Sstevel@tonic-gate 	sp[sp[0]+1] = 0;
5307c478bd9Sstevel@tonic-gate 	return;
5317c478bd9Sstevel@tonic-gate 
5327c478bd9Sstevel@tonic-gate bad:
5337c478bd9Sstevel@tonic-gate 	(void) printf("bad delitem\n");
5347c478bd9Sstevel@tonic-gate 	abort();
5357c478bd9Sstevel@tonic-gate }
5367c478bd9Sstevel@tonic-gate 
5377c478bd9Sstevel@tonic-gate int
additem(char * buf,datum item)538*89fbfe0dSToomas Soome additem(char *buf, datum item)
5397c478bd9Sstevel@tonic-gate {
5407c478bd9Sstevel@tonic-gate 	short *sp;
5417c478bd9Sstevel@tonic-gate 	int i1, i2;
5427c478bd9Sstevel@tonic-gate 
5437c478bd9Sstevel@tonic-gate 	sp = (short *)buf;
5447c478bd9Sstevel@tonic-gate 	i1 = PBLKSIZ;
5457c478bd9Sstevel@tonic-gate 	if (sp[0] > 0)
5467c478bd9Sstevel@tonic-gate 		i1 = sp[sp[0]+1-1];
5477c478bd9Sstevel@tonic-gate 	i1 -= item.dsize;
5487c478bd9Sstevel@tonic-gate 	i2 = (sp[0]+2) * (int)sizeof (short);
54961961e0fSrobinson 	if (i1 <= i2)
5507c478bd9Sstevel@tonic-gate 		return (-1);
5517c478bd9Sstevel@tonic-gate 	sp[sp[0]+1] = (short)i1;
5527c478bd9Sstevel@tonic-gate 	for (i2 = 0; i2 < item.dsize; i2++) {
5537c478bd9Sstevel@tonic-gate 		buf[i1] = item.dptr[i2];
5547c478bd9Sstevel@tonic-gate 		i1++;
5557c478bd9Sstevel@tonic-gate 	}
5567c478bd9Sstevel@tonic-gate 	sp[0]++;
5577c478bd9Sstevel@tonic-gate 	return (sp[0]-1);
5587c478bd9Sstevel@tonic-gate }
5597c478bd9Sstevel@tonic-gate 
5607c478bd9Sstevel@tonic-gate void
chkblk(char * buf)561*89fbfe0dSToomas Soome chkblk(char *buf)
5627c478bd9Sstevel@tonic-gate {
5637c478bd9Sstevel@tonic-gate 	short *sp;
5647c478bd9Sstevel@tonic-gate 	int t, i;
5657c478bd9Sstevel@tonic-gate 
56661961e0fSrobinson 	/* LINTED pointer cast */
5677c478bd9Sstevel@tonic-gate 	sp = (short *)buf;
5687c478bd9Sstevel@tonic-gate 	t = PBLKSIZ;
5697c478bd9Sstevel@tonic-gate 	for (i = 0; i < sp[0]; i++) {
5707c478bd9Sstevel@tonic-gate 		if (sp[i+1] > t)
5717c478bd9Sstevel@tonic-gate 			goto bad;
5727c478bd9Sstevel@tonic-gate 		t = sp[i+1];
5737c478bd9Sstevel@tonic-gate 	}
5747c478bd9Sstevel@tonic-gate 	if (t < (sp[0]+1) * sizeof (short))
5757c478bd9Sstevel@tonic-gate 		goto bad;
5767c478bd9Sstevel@tonic-gate 	return;
5777c478bd9Sstevel@tonic-gate 
5787c478bd9Sstevel@tonic-gate bad:
5797c478bd9Sstevel@tonic-gate 	(void) printf("bad block\n");
5807c478bd9Sstevel@tonic-gate 	abort();
58161961e0fSrobinson 	(void) memset(&buf, 0, PBLKSIZ);
5827c478bd9Sstevel@tonic-gate }
583