xref: /illumos-gate/usr/src/lib/libnsl/yp/dbm.c (revision e8031f0a)
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 /*
24*e8031f0aSraf  * 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 
377c478bd9Sstevel@tonic-gate #pragma ident	"%Z%%M%	%I%	%E% SMI"
387c478bd9Sstevel@tonic-gate 
39*e8031f0aSraf #include "mt.h"
407c478bd9Sstevel@tonic-gate #include <rpcsvc/dbm.h>
417c478bd9Sstevel@tonic-gate #include <sys/types.h>
427c478bd9Sstevel@tonic-gate #include <sys/stat.h>
437c478bd9Sstevel@tonic-gate #include <string.h>
447c478bd9Sstevel@tonic-gate #include <unistd.h>
457c478bd9Sstevel@tonic-gate #include <stdlib.h>
467c478bd9Sstevel@tonic-gate #include <fcntl.h>
477c478bd9Sstevel@tonic-gate #include <stdio.h>
487c478bd9Sstevel@tonic-gate #include <errno.h>
497c478bd9Sstevel@tonic-gate 
507c478bd9Sstevel@tonic-gate void dbm_access(long);
517c478bd9Sstevel@tonic-gate void delitem(char *, int);
527c478bd9Sstevel@tonic-gate void chkblk(char *);
537c478bd9Sstevel@tonic-gate int  additem(char *, datum);
547c478bd9Sstevel@tonic-gate int  getbit(void);
557c478bd9Sstevel@tonic-gate int  setbit(void);
567c478bd9Sstevel@tonic-gate int  cmpdatum(datum, datum);
577c478bd9Sstevel@tonic-gate 
587c478bd9Sstevel@tonic-gate int
dbminit(char * file)5961961e0fSrobinson dbminit(char *file)
607c478bd9Sstevel@tonic-gate {
617c478bd9Sstevel@tonic-gate 	struct stat statb;
627c478bd9Sstevel@tonic-gate 
637c478bd9Sstevel@tonic-gate 	dbrdonly = 0;
647c478bd9Sstevel@tonic-gate 	if (strlcpy(pagbuf, file, sizeof (pagbuf)) >= sizeof (pagbuf) ||
657c478bd9Sstevel@tonic-gate 	    strlcat(pagbuf, ".pag", sizeof (pagbuf)) >= sizeof (pagbuf)) {
667c478bd9Sstevel@tonic-gate 		/*
677c478bd9Sstevel@tonic-gate 		 * file.pag does not fit into pagbuf.
687c478bd9Sstevel@tonic-gate 		 * fails with ENAMETOOLONG.
697c478bd9Sstevel@tonic-gate 		 */
707c478bd9Sstevel@tonic-gate 		errno = ENAMETOOLONG;
717c478bd9Sstevel@tonic-gate 		return (-1);
727c478bd9Sstevel@tonic-gate 	}
737c478bd9Sstevel@tonic-gate 	pagf = open(pagbuf, 2);
747c478bd9Sstevel@tonic-gate 	if (pagf < 0) {
757c478bd9Sstevel@tonic-gate 		pagf = open(pagbuf, 0);
767c478bd9Sstevel@tonic-gate 		dbrdonly = 1;
777c478bd9Sstevel@tonic-gate 	}
787c478bd9Sstevel@tonic-gate 	/*
797c478bd9Sstevel@tonic-gate 	 * We know this won't overflow so it is safe to ignore the
807c478bd9Sstevel@tonic-gate 	 * return value; we use strl* to prevent false hits in
817c478bd9Sstevel@tonic-gate 	 * code sweeps.
827c478bd9Sstevel@tonic-gate 	 */
837c478bd9Sstevel@tonic-gate 	(void) strlcpy(pagbuf, file, sizeof (pagbuf));
847c478bd9Sstevel@tonic-gate 	(void) strlcat(pagbuf, ".dir", sizeof (pagbuf));
857c478bd9Sstevel@tonic-gate 	dirf = open(pagbuf, 2);
867c478bd9Sstevel@tonic-gate 	if (dirf < 0) {
877c478bd9Sstevel@tonic-gate 		dirf = open(pagbuf, 0);
887c478bd9Sstevel@tonic-gate 		dbrdonly = 1;
897c478bd9Sstevel@tonic-gate 	}
9061961e0fSrobinson 	if (pagf < 0 || dirf < 0)
917c478bd9Sstevel@tonic-gate 		return (-1);
92*e8031f0aSraf 	(void) fstat(dirf, &statb);
937c478bd9Sstevel@tonic-gate 	maxbno = statb.st_size*BYTESIZ-1;
947c478bd9Sstevel@tonic-gate 	return (0);
957c478bd9Sstevel@tonic-gate }
967c478bd9Sstevel@tonic-gate 
977c478bd9Sstevel@tonic-gate static long oldb1 = -1;
987c478bd9Sstevel@tonic-gate static long oldb2 = -1;
997c478bd9Sstevel@tonic-gate 
1007c478bd9Sstevel@tonic-gate /* Avoid using cached data for subsequent accesses. */
1017c478bd9Sstevel@tonic-gate int
dbmflush(void)10261961e0fSrobinson dbmflush(void)
1037c478bd9Sstevel@tonic-gate {
1047c478bd9Sstevel@tonic-gate 	oldb1 = -1;
1057c478bd9Sstevel@tonic-gate 	oldb2 = -1;
1067c478bd9Sstevel@tonic-gate 	return (0);
1077c478bd9Sstevel@tonic-gate }
1087c478bd9Sstevel@tonic-gate 
1097c478bd9Sstevel@tonic-gate /* Clean up after ourself. */
1107c478bd9Sstevel@tonic-gate int
dbmclose(void)11161961e0fSrobinson dbmclose(void)
1127c478bd9Sstevel@tonic-gate {
1137c478bd9Sstevel@tonic-gate 	(void) close(pagf);
1147c478bd9Sstevel@tonic-gate 	(void) close(dirf);
1157c478bd9Sstevel@tonic-gate 	bitno = 0;
1167c478bd9Sstevel@tonic-gate 	maxbno = 0;
1177c478bd9Sstevel@tonic-gate 	blkno = 0;
1187c478bd9Sstevel@tonic-gate 	hmask = 0;
1197c478bd9Sstevel@tonic-gate 	oldb1 = -1;
1207c478bd9Sstevel@tonic-gate 	oldb2 = -1;
1217c478bd9Sstevel@tonic-gate 	return (0);
1227c478bd9Sstevel@tonic-gate }
1237c478bd9Sstevel@tonic-gate 
1247c478bd9Sstevel@tonic-gate long
forder(datum key)12561961e0fSrobinson forder(datum key)
1267c478bd9Sstevel@tonic-gate {
1277c478bd9Sstevel@tonic-gate 	long hash;
1287c478bd9Sstevel@tonic-gate 
1297c478bd9Sstevel@tonic-gate 	hash = calchash(key);
1307c478bd9Sstevel@tonic-gate 	for (hmask = 0; ; hmask = (hmask<<1) + 1) {
1317c478bd9Sstevel@tonic-gate 		blkno = hash & hmask;
1327c478bd9Sstevel@tonic-gate 		bitno = blkno + hmask;
1337c478bd9Sstevel@tonic-gate 		if (getbit() == 0)
1347c478bd9Sstevel@tonic-gate 			break;
1357c478bd9Sstevel@tonic-gate 	}
1367c478bd9Sstevel@tonic-gate 	return (blkno);
1377c478bd9Sstevel@tonic-gate }
1387c478bd9Sstevel@tonic-gate 
1397c478bd9Sstevel@tonic-gate datum
fetch(datum key)14061961e0fSrobinson fetch(datum key)
1417c478bd9Sstevel@tonic-gate {
1427c478bd9Sstevel@tonic-gate 	int i;
1437c478bd9Sstevel@tonic-gate 	datum item;
1447c478bd9Sstevel@tonic-gate 
1457c478bd9Sstevel@tonic-gate 	dbm_access(calchash(key));
1467c478bd9Sstevel@tonic-gate 	for (i = 0; ; i += 2) {
1477c478bd9Sstevel@tonic-gate 		item = makdatum(pagbuf, i);
1487c478bd9Sstevel@tonic-gate 		if (item.dptr == NULL) {
1497c478bd9Sstevel@tonic-gate 			return (item);
1507c478bd9Sstevel@tonic-gate 		}
1517c478bd9Sstevel@tonic-gate 		if (cmpdatum(key, item) == 0) {
1527c478bd9Sstevel@tonic-gate 			item = makdatum(pagbuf, i+1);
1537c478bd9Sstevel@tonic-gate 			if (item.dptr == NULL)
1547c478bd9Sstevel@tonic-gate 				(void) printf("items not in pairs\n");
1557c478bd9Sstevel@tonic-gate 			return (item);
1567c478bd9Sstevel@tonic-gate 		}
1577c478bd9Sstevel@tonic-gate 	}
1587c478bd9Sstevel@tonic-gate }
1597c478bd9Sstevel@tonic-gate 
1607c478bd9Sstevel@tonic-gate int
delete(datum key)16161961e0fSrobinson delete(datum key)
1627c478bd9Sstevel@tonic-gate {
1637c478bd9Sstevel@tonic-gate 	int i;
1647c478bd9Sstevel@tonic-gate 	datum item;
1657c478bd9Sstevel@tonic-gate 
16661961e0fSrobinson 	if (dbrdonly)
1677c478bd9Sstevel@tonic-gate 		return (-1);
1687c478bd9Sstevel@tonic-gate 	dbm_access(calchash(key));
1697c478bd9Sstevel@tonic-gate 	for (i = 0; ; i += 2) {
1707c478bd9Sstevel@tonic-gate 		item = makdatum(pagbuf, i);
17161961e0fSrobinson 		if (item.dptr == NULL)
1727c478bd9Sstevel@tonic-gate 			return (-1);
1737c478bd9Sstevel@tonic-gate 		if (cmpdatum(key, item) == 0) {
1747c478bd9Sstevel@tonic-gate 			delitem(pagbuf, i);
1757c478bd9Sstevel@tonic-gate 			delitem(pagbuf, i);
1767c478bd9Sstevel@tonic-gate 			break;
1777c478bd9Sstevel@tonic-gate 		}
1787c478bd9Sstevel@tonic-gate 	}
1797c478bd9Sstevel@tonic-gate 	(void) lseek(pagf, blkno*PBLKSIZ, 0);
1807c478bd9Sstevel@tonic-gate 	(void) write(pagf, pagbuf, PBLKSIZ);
1817c478bd9Sstevel@tonic-gate 	return (0);
1827c478bd9Sstevel@tonic-gate }
1837c478bd9Sstevel@tonic-gate 
1847c478bd9Sstevel@tonic-gate int
store(datum key,datum dat)18561961e0fSrobinson store(datum key, datum dat)
1867c478bd9Sstevel@tonic-gate {
1877c478bd9Sstevel@tonic-gate 	int i;
1887c478bd9Sstevel@tonic-gate 	datum item;
1897c478bd9Sstevel@tonic-gate 	char ovfbuf[PBLKSIZ];
1907c478bd9Sstevel@tonic-gate 
19161961e0fSrobinson 	if (dbrdonly)
1927c478bd9Sstevel@tonic-gate 		return (-1);
1937c478bd9Sstevel@tonic-gate loop:
1947c478bd9Sstevel@tonic-gate 	dbm_access(calchash(key));
1957c478bd9Sstevel@tonic-gate 	for (i = 0; ; i += 2) {
1967c478bd9Sstevel@tonic-gate 		item = makdatum(pagbuf, i);
1977c478bd9Sstevel@tonic-gate 		if (item.dptr == NULL)
1987c478bd9Sstevel@tonic-gate 			break;
1997c478bd9Sstevel@tonic-gate 		if (cmpdatum(key, item) == 0) {
2007c478bd9Sstevel@tonic-gate 			delitem(pagbuf, i);
2017c478bd9Sstevel@tonic-gate 			delitem(pagbuf, i);
2027c478bd9Sstevel@tonic-gate 			break;
2037c478bd9Sstevel@tonic-gate 		}
2047c478bd9Sstevel@tonic-gate 	}
2057c478bd9Sstevel@tonic-gate 	i = additem(pagbuf, key);
2067c478bd9Sstevel@tonic-gate 	if (i < 0)
2077c478bd9Sstevel@tonic-gate 		goto split;
2087c478bd9Sstevel@tonic-gate 	if (additem(pagbuf, dat) < 0) {
2097c478bd9Sstevel@tonic-gate 		delitem(pagbuf, i);
2107c478bd9Sstevel@tonic-gate 		goto split;
2117c478bd9Sstevel@tonic-gate 	}
2127c478bd9Sstevel@tonic-gate 	(void) lseek(pagf, blkno*PBLKSIZ, 0);
2137c478bd9Sstevel@tonic-gate 	(void) write(pagf, pagbuf, PBLKSIZ);
2147c478bd9Sstevel@tonic-gate 	return (0);
2157c478bd9Sstevel@tonic-gate 
2167c478bd9Sstevel@tonic-gate split:
2177c478bd9Sstevel@tonic-gate 	if (key.dsize + dat.dsize + 3 * sizeof (short) >= PBLKSIZ) {
2187c478bd9Sstevel@tonic-gate 		(void) printf("entry too big\n");
2197c478bd9Sstevel@tonic-gate 		return (-1);
2207c478bd9Sstevel@tonic-gate 	}
22161961e0fSrobinson 	(void) memset(&ovfbuf, 0, PBLKSIZ);
2227c478bd9Sstevel@tonic-gate 	for (i = 0; ; ) {
2237c478bd9Sstevel@tonic-gate 		item = makdatum(pagbuf, i);
2247c478bd9Sstevel@tonic-gate 		if (item.dptr == NULL)
2257c478bd9Sstevel@tonic-gate 			break;
2267c478bd9Sstevel@tonic-gate 		if (calchash(item) & (hmask+1)) {
2277c478bd9Sstevel@tonic-gate 			(void) additem(ovfbuf, item);
2287c478bd9Sstevel@tonic-gate 			delitem(pagbuf, i);
2297c478bd9Sstevel@tonic-gate 			item = makdatum(pagbuf, i);
2307c478bd9Sstevel@tonic-gate 			if (item.dptr == NULL) {
2317c478bd9Sstevel@tonic-gate 				(void) printf("split not paired\n");
2327c478bd9Sstevel@tonic-gate 				break;
2337c478bd9Sstevel@tonic-gate 			}
2347c478bd9Sstevel@tonic-gate 			(void) additem(ovfbuf, item);
2357c478bd9Sstevel@tonic-gate 			delitem(pagbuf, i);
2367c478bd9Sstevel@tonic-gate 			continue;
2377c478bd9Sstevel@tonic-gate 		}
2387c478bd9Sstevel@tonic-gate 		i += 2;
2397c478bd9Sstevel@tonic-gate 	}
2407c478bd9Sstevel@tonic-gate 	(void) lseek(pagf, blkno*PBLKSIZ, 0);
2417c478bd9Sstevel@tonic-gate 	if (write(pagf, pagbuf, PBLKSIZ) < 0) {
2427c478bd9Sstevel@tonic-gate 		return (-1);
2437c478bd9Sstevel@tonic-gate 	}
2447c478bd9Sstevel@tonic-gate 	(void) lseek(pagf, (blkno+hmask+1)*PBLKSIZ, 0);
2457c478bd9Sstevel@tonic-gate 	if (write(pagf, ovfbuf, PBLKSIZ) < 0) {
2467c478bd9Sstevel@tonic-gate 		return (-1);
2477c478bd9Sstevel@tonic-gate 	}
2487c478bd9Sstevel@tonic-gate 	if (setbit() < 0) {
2497c478bd9Sstevel@tonic-gate 		return (-1);
2507c478bd9Sstevel@tonic-gate 	}
2517c478bd9Sstevel@tonic-gate 	goto loop;
2527c478bd9Sstevel@tonic-gate }
2537c478bd9Sstevel@tonic-gate 
2547c478bd9Sstevel@tonic-gate datum
firstkey(void)25561961e0fSrobinson firstkey(void)
2567c478bd9Sstevel@tonic-gate {
25761961e0fSrobinson 	return (firsthash(0L));
2587c478bd9Sstevel@tonic-gate }
2597c478bd9Sstevel@tonic-gate 
2607c478bd9Sstevel@tonic-gate datum
nextkey(datum key)26161961e0fSrobinson nextkey(datum key)
2627c478bd9Sstevel@tonic-gate {
2637c478bd9Sstevel@tonic-gate 	int i;
2647c478bd9Sstevel@tonic-gate 	datum item, bitem;
2657c478bd9Sstevel@tonic-gate 	long hash;
2667c478bd9Sstevel@tonic-gate 	int f;
2677c478bd9Sstevel@tonic-gate 
2687c478bd9Sstevel@tonic-gate #ifdef lint
2697c478bd9Sstevel@tonic-gate 	bitem.dptr = NULL;
2707c478bd9Sstevel@tonic-gate 	bitem.dsize = 0;
2717c478bd9Sstevel@tonic-gate #endif /* lint */
2727c478bd9Sstevel@tonic-gate 	hash = calchash(key);
2737c478bd9Sstevel@tonic-gate 	dbm_access(hash);
2747c478bd9Sstevel@tonic-gate 	f = 1;
2757c478bd9Sstevel@tonic-gate 	for (i = 0; ; i += 2) {
2767c478bd9Sstevel@tonic-gate 		item = makdatum(pagbuf, i);
2777c478bd9Sstevel@tonic-gate 		if (item.dptr == NULL)
2787c478bd9Sstevel@tonic-gate 			break;
2797c478bd9Sstevel@tonic-gate 		if (cmpdatum(key, item) <= 0)
2807c478bd9Sstevel@tonic-gate 			continue;
2817c478bd9Sstevel@tonic-gate 		if (f || cmpdatum(bitem, item) < 0) {
2827c478bd9Sstevel@tonic-gate 			bitem = item;
2837c478bd9Sstevel@tonic-gate 			f = 0;
2847c478bd9Sstevel@tonic-gate 		}
2857c478bd9Sstevel@tonic-gate 	}
28661961e0fSrobinson 	if (f == 0)
2877c478bd9Sstevel@tonic-gate 		return (bitem);
2887c478bd9Sstevel@tonic-gate 	hash = hashinc(hash);
28961961e0fSrobinson 	if (hash == 0)
2907c478bd9Sstevel@tonic-gate 		return (item);
29161961e0fSrobinson 	return (firsthash(hash));
2927c478bd9Sstevel@tonic-gate }
2937c478bd9Sstevel@tonic-gate 
2947c478bd9Sstevel@tonic-gate datum
firsthash(long hash)29561961e0fSrobinson firsthash(long hash)
2967c478bd9Sstevel@tonic-gate {
2977c478bd9Sstevel@tonic-gate 	int i;
2987c478bd9Sstevel@tonic-gate 	datum item, bitem;
2997c478bd9Sstevel@tonic-gate 
3007c478bd9Sstevel@tonic-gate loop:
3017c478bd9Sstevel@tonic-gate 	dbm_access(hash);
3027c478bd9Sstevel@tonic-gate 	bitem = makdatum(pagbuf, 0);
3037c478bd9Sstevel@tonic-gate 	for (i = 2; ; i += 2) {
3047c478bd9Sstevel@tonic-gate 		item = makdatum(pagbuf, i);
3057c478bd9Sstevel@tonic-gate 		if (item.dptr == NULL)
3067c478bd9Sstevel@tonic-gate 			break;
3077c478bd9Sstevel@tonic-gate 		if (cmpdatum(bitem, item) < 0)
3087c478bd9Sstevel@tonic-gate 			bitem = item;
3097c478bd9Sstevel@tonic-gate 	}
31061961e0fSrobinson 	if (bitem.dptr != NULL)
3117c478bd9Sstevel@tonic-gate 		return (bitem);
3127c478bd9Sstevel@tonic-gate 	hash = hashinc(hash);
31361961e0fSrobinson 	if (hash == 0)
3147c478bd9Sstevel@tonic-gate 		return (item);
3157c478bd9Sstevel@tonic-gate 	goto loop;
3167c478bd9Sstevel@tonic-gate }
3177c478bd9Sstevel@tonic-gate 
3187c478bd9Sstevel@tonic-gate void
dbm_access(long hash)31961961e0fSrobinson dbm_access(long hash)
3207c478bd9Sstevel@tonic-gate {
3217c478bd9Sstevel@tonic-gate 	ssize_t readsize;
3227c478bd9Sstevel@tonic-gate 
3237c478bd9Sstevel@tonic-gate 	for (hmask = 0; ; hmask = (hmask<<1) + 1) {
3247c478bd9Sstevel@tonic-gate 		blkno = hash & hmask;
3257c478bd9Sstevel@tonic-gate 		bitno = blkno + hmask;
3267c478bd9Sstevel@tonic-gate 		if (getbit() == 0)
3277c478bd9Sstevel@tonic-gate 			break;
3287c478bd9Sstevel@tonic-gate 	}
3297c478bd9Sstevel@tonic-gate 	if (blkno != oldb1) {
3307c478bd9Sstevel@tonic-gate 		(void) lseek(pagf, blkno*PBLKSIZ, 0);
3317c478bd9Sstevel@tonic-gate 		readsize = read(pagf, pagbuf, PBLKSIZ);
3327c478bd9Sstevel@tonic-gate 		if (readsize != PBLKSIZ) {
33361961e0fSrobinson 			if (readsize < 0)
33461961e0fSrobinson 				readsize = 0;
33561961e0fSrobinson 			(void) memset((&pagbuf+readsize), 0, PBLKSIZ-readsize);
3367c478bd9Sstevel@tonic-gate 		}
3377c478bd9Sstevel@tonic-gate 		chkblk(pagbuf);
3387c478bd9Sstevel@tonic-gate 		oldb1 = blkno;
3397c478bd9Sstevel@tonic-gate 	}
3407c478bd9Sstevel@tonic-gate }
3417c478bd9Sstevel@tonic-gate 
3427c478bd9Sstevel@tonic-gate int
getbit(void)3437c478bd9Sstevel@tonic-gate getbit(void)
3447c478bd9Sstevel@tonic-gate {
3457c478bd9Sstevel@tonic-gate 	long bn;
3467c478bd9Sstevel@tonic-gate 	ssize_t readsize;
3477c478bd9Sstevel@tonic-gate 	long b, i, n;
3487c478bd9Sstevel@tonic-gate 
34961961e0fSrobinson 	if (bitno > maxbno)
3507c478bd9Sstevel@tonic-gate 		return (0);
3517c478bd9Sstevel@tonic-gate 	n = bitno % BYTESIZ;
3527c478bd9Sstevel@tonic-gate 	bn = bitno / BYTESIZ;
3537c478bd9Sstevel@tonic-gate 	i = bn % DBLKSIZ;
3547c478bd9Sstevel@tonic-gate 	b = bn / DBLKSIZ;
3557c478bd9Sstevel@tonic-gate 	if (b != oldb2) {
3567c478bd9Sstevel@tonic-gate 		(void) lseek(dirf, (long)b*DBLKSIZ, 0);
3577c478bd9Sstevel@tonic-gate 		readsize = read(dirf, dirbuf, DBLKSIZ);
3587c478bd9Sstevel@tonic-gate 		if (readsize != DBLKSIZ) {
35961961e0fSrobinson 			if (readsize < 0)
36061961e0fSrobinson 				readsize = 0;
36161961e0fSrobinson 			(void) memset(&dirbuf+readsize, 0, DBLKSIZ-readsize);
3627c478bd9Sstevel@tonic-gate 		}
3637c478bd9Sstevel@tonic-gate 		oldb2 = b;
3647c478bd9Sstevel@tonic-gate 	}
36561961e0fSrobinson 	if (dirbuf[i] & (1<<n))
3667c478bd9Sstevel@tonic-gate 		return (1);
3677c478bd9Sstevel@tonic-gate 	return (0);
3687c478bd9Sstevel@tonic-gate }
3697c478bd9Sstevel@tonic-gate 
3707c478bd9Sstevel@tonic-gate int
setbit(void)3717c478bd9Sstevel@tonic-gate setbit(void)
3727c478bd9Sstevel@tonic-gate {
3737c478bd9Sstevel@tonic-gate 	long bn;
3747c478bd9Sstevel@tonic-gate 	long i, n, b;
3757c478bd9Sstevel@tonic-gate 
37661961e0fSrobinson 	if (dbrdonly)
3777c478bd9Sstevel@tonic-gate 		return (-1);
3787c478bd9Sstevel@tonic-gate 	if (bitno > maxbno) {
3797c478bd9Sstevel@tonic-gate 		maxbno = bitno;
3807c478bd9Sstevel@tonic-gate 		(void) getbit();
3817c478bd9Sstevel@tonic-gate 	}
3827c478bd9Sstevel@tonic-gate 	n = bitno % BYTESIZ;
3837c478bd9Sstevel@tonic-gate 	bn = bitno / BYTESIZ;
3847c478bd9Sstevel@tonic-gate 	i = bn % DBLKSIZ;
3857c478bd9Sstevel@tonic-gate 	b = bn / DBLKSIZ;
3867c478bd9Sstevel@tonic-gate 	dirbuf[i] |= 1<<n;
3877c478bd9Sstevel@tonic-gate 	(void) lseek(dirf, (long)b*DBLKSIZ, 0);
38861961e0fSrobinson 	if (write(dirf, dirbuf, DBLKSIZ) < 0)
3897c478bd9Sstevel@tonic-gate 		return (-1);
3907c478bd9Sstevel@tonic-gate 	return (0);
3917c478bd9Sstevel@tonic-gate }
3927c478bd9Sstevel@tonic-gate 
3937c478bd9Sstevel@tonic-gate datum
makdatum(char buf[PBLKSIZ],int n)3947c478bd9Sstevel@tonic-gate makdatum(char buf[PBLKSIZ], int n)
3957c478bd9Sstevel@tonic-gate {
3967c478bd9Sstevel@tonic-gate 	short *sp;
3977c478bd9Sstevel@tonic-gate 	int t;
3987c478bd9Sstevel@tonic-gate 	datum item;
3997c478bd9Sstevel@tonic-gate 
40061961e0fSrobinson 	/* LINTED pointer cast */
4017c478bd9Sstevel@tonic-gate 	sp = (short *)buf;
4027c478bd9Sstevel@tonic-gate 	if (n < 0 || n >= sp[0])
4037c478bd9Sstevel@tonic-gate 		goto null;
4047c478bd9Sstevel@tonic-gate 	t = PBLKSIZ;
4057c478bd9Sstevel@tonic-gate 	if (n > 0)
4067c478bd9Sstevel@tonic-gate 		t = sp[n+1-1];
4077c478bd9Sstevel@tonic-gate 	item.dptr = buf+sp[n+1];
4087c478bd9Sstevel@tonic-gate 	item.dsize = t - sp[n+1];
4097c478bd9Sstevel@tonic-gate 	return (item);
4107c478bd9Sstevel@tonic-gate 
4117c478bd9Sstevel@tonic-gate null:
4127c478bd9Sstevel@tonic-gate 	item.dptr = NULL;
4137c478bd9Sstevel@tonic-gate 	item.dsize = 0;
4147c478bd9Sstevel@tonic-gate 	return (item);
4157c478bd9Sstevel@tonic-gate }
4167c478bd9Sstevel@tonic-gate 
4177c478bd9Sstevel@tonic-gate int
cmpdatum(datum d1,datum d2)41861961e0fSrobinson cmpdatum(datum d1, datum d2)
4197c478bd9Sstevel@tonic-gate {
4207c478bd9Sstevel@tonic-gate 	int n;
4217c478bd9Sstevel@tonic-gate 	char *p1, *p2;
4227c478bd9Sstevel@tonic-gate 
4237c478bd9Sstevel@tonic-gate 	n = d1.dsize;
42461961e0fSrobinson 	if (n != d2.dsize)
4257c478bd9Sstevel@tonic-gate 		return (n - d2.dsize);
42661961e0fSrobinson 	if (n == 0)
4277c478bd9Sstevel@tonic-gate 		return (0);
4287c478bd9Sstevel@tonic-gate 	p1 = d1.dptr;
4297c478bd9Sstevel@tonic-gate 	p2 = d2.dptr;
4307c478bd9Sstevel@tonic-gate 	do
43161961e0fSrobinson 		if (*p1++ != *p2++)
4327c478bd9Sstevel@tonic-gate 			return (*--p1 - *--p2);
4337c478bd9Sstevel@tonic-gate 	while (--n);
4347c478bd9Sstevel@tonic-gate 	return (0);
4357c478bd9Sstevel@tonic-gate }
4367c478bd9Sstevel@tonic-gate 
4377c478bd9Sstevel@tonic-gate int	hitab[16]
4387c478bd9Sstevel@tonic-gate /*
4397c478bd9Sstevel@tonic-gate  * ken's
4407c478bd9Sstevel@tonic-gate  * {
4417c478bd9Sstevel@tonic-gate  *	055, 043, 036, 054, 063, 014, 004, 005,
4427c478bd9Sstevel@tonic-gate  *	010, 064, 077, 000, 035, 027, 025, 071,
4437c478bd9Sstevel@tonic-gate  * };
4447c478bd9Sstevel@tonic-gate  */
4457c478bd9Sstevel@tonic-gate 	= {	61, 57, 53, 49, 45, 41, 37, 33,
4467c478bd9Sstevel@tonic-gate 	29, 25, 21, 17, 13,  9,  5,  1,
4477c478bd9Sstevel@tonic-gate };
4487c478bd9Sstevel@tonic-gate long	hltab[64]
4497c478bd9Sstevel@tonic-gate 	= {
4507c478bd9Sstevel@tonic-gate 	06100151277L, 06106161736L, 06452611562L, 05001724107L,
4517c478bd9Sstevel@tonic-gate 	02614772546L, 04120731531L, 04665262210L, 07347467531L,
4527c478bd9Sstevel@tonic-gate 	06735253126L, 06042345173L, 03072226605L, 01464164730L,
4537c478bd9Sstevel@tonic-gate 	03247435524L, 07652510057L, 01546775256L, 05714532133L,
4547c478bd9Sstevel@tonic-gate 	06173260402L, 07517101630L, 02431460343L, 01743245566L,
4557c478bd9Sstevel@tonic-gate 	00261675137L, 02433103631L, 03421772437L, 04447707466L,
4567c478bd9Sstevel@tonic-gate 	04435620103L, 03757017115L, 03641531772L, 06767633246L,
4577c478bd9Sstevel@tonic-gate 	02673230344L, 00260612216L, 04133454451L, 00615531516L,
4587c478bd9Sstevel@tonic-gate 	06137717526L, 02574116560L, 02304023373L, 07061702261L,
4597c478bd9Sstevel@tonic-gate 	05153031405L, 05322056705L, 07401116734L, 06552375715L,
4607c478bd9Sstevel@tonic-gate 	06165233473L, 05311063631L, 01212221723L, 01052267235L,
4617c478bd9Sstevel@tonic-gate 	06000615237L, 01075222665L, 06330216006L, 04402355630L,
4627c478bd9Sstevel@tonic-gate 	01451177262L, 02000133436L, 06025467062L, 07121076461L,
4637c478bd9Sstevel@tonic-gate 	03123433522L, 01010635225L, 01716177066L, 05161746527L,
4647c478bd9Sstevel@tonic-gate 	01736635071L, 06243505026L, 03637211610L, 01756474365L,
4657c478bd9Sstevel@tonic-gate 	04723077174L, 03642763134L, 05750130273L, 03655541561L,
4667c478bd9Sstevel@tonic-gate };
4677c478bd9Sstevel@tonic-gate 
4687c478bd9Sstevel@tonic-gate long
hashinc(long hash)46961961e0fSrobinson hashinc(long hash)
4707c478bd9Sstevel@tonic-gate {
4717c478bd9Sstevel@tonic-gate 	long bit;
4727c478bd9Sstevel@tonic-gate 
4737c478bd9Sstevel@tonic-gate 	hash &= hmask;
4747c478bd9Sstevel@tonic-gate 	bit = hmask+1;
4757c478bd9Sstevel@tonic-gate 	for (; ; ) {
4767c478bd9Sstevel@tonic-gate 		bit >>= 1;
47761961e0fSrobinson 		if (bit == 0)
4787c478bd9Sstevel@tonic-gate 			return (0L);
47961961e0fSrobinson 		if ((hash&bit) == 0)
4807c478bd9Sstevel@tonic-gate 			return (hash|bit);
4817c478bd9Sstevel@tonic-gate 		hash &= ~bit;
4827c478bd9Sstevel@tonic-gate 	}
4837c478bd9Sstevel@tonic-gate }
4847c478bd9Sstevel@tonic-gate 
4857c478bd9Sstevel@tonic-gate long
calchash(datum item)48661961e0fSrobinson calchash(datum item)
4877c478bd9Sstevel@tonic-gate {
4887c478bd9Sstevel@tonic-gate 	int i, j, f;
4897c478bd9Sstevel@tonic-gate 	long hashl;
4907c478bd9Sstevel@tonic-gate 	int hashi;
4917c478bd9Sstevel@tonic-gate 
4927c478bd9Sstevel@tonic-gate 	hashl = 0;
4937c478bd9Sstevel@tonic-gate 	hashi = 0;
4947c478bd9Sstevel@tonic-gate 	for (i = 0; i < item.dsize; i++) {
4957c478bd9Sstevel@tonic-gate 		f = item.dptr[i];
4967c478bd9Sstevel@tonic-gate 		for (j = 0; j < BYTESIZ; j += 4) {
4977c478bd9Sstevel@tonic-gate 			hashi += hitab[f&017];
4987c478bd9Sstevel@tonic-gate 			hashl += hltab[hashi&63];
4997c478bd9Sstevel@tonic-gate 			f >>= 4;
5007c478bd9Sstevel@tonic-gate 		}
5017c478bd9Sstevel@tonic-gate 	}
5027c478bd9Sstevel@tonic-gate 	return (hashl);
5037c478bd9Sstevel@tonic-gate }
5047c478bd9Sstevel@tonic-gate 
5057c478bd9Sstevel@tonic-gate void
delitem(char buf[PBLKSIZ],int n)50661961e0fSrobinson delitem(char buf[PBLKSIZ], int n)
5077c478bd9Sstevel@tonic-gate {
5087c478bd9Sstevel@tonic-gate 	short *sp;
5097c478bd9Sstevel@tonic-gate 	int i1, i2, i3;
5107c478bd9Sstevel@tonic-gate 
51161961e0fSrobinson 	/* LINTED pointer cast */
5127c478bd9Sstevel@tonic-gate 	sp = (short *)buf;
5137c478bd9Sstevel@tonic-gate 	if (n < 0 || n >= sp[0])
5147c478bd9Sstevel@tonic-gate 		goto bad;
5157c478bd9Sstevel@tonic-gate 	i1 = sp[n+1];
5167c478bd9Sstevel@tonic-gate 	i2 = PBLKSIZ;
5177c478bd9Sstevel@tonic-gate 	if (n > 0)
5187c478bd9Sstevel@tonic-gate 		i2 = sp[n+1-1];
5197c478bd9Sstevel@tonic-gate 	i3 = sp[sp[0]+1-1];
5207c478bd9Sstevel@tonic-gate 	if (i2 > i1)
5217c478bd9Sstevel@tonic-gate 	while (i1 > i3) {
5227c478bd9Sstevel@tonic-gate 		i1--;
5237c478bd9Sstevel@tonic-gate 		i2--;
5247c478bd9Sstevel@tonic-gate 		buf[i2] = buf[i1];
5257c478bd9Sstevel@tonic-gate 		buf[i1] = 0;
5267c478bd9Sstevel@tonic-gate 	}
5277c478bd9Sstevel@tonic-gate 	i2 -= i1;
5287c478bd9Sstevel@tonic-gate 	for (i1 = n + 1; i1 < sp[0]; i1++)
5297c478bd9Sstevel@tonic-gate 		sp[i1+1-1] = sp[i1+1] + i2;
5307c478bd9Sstevel@tonic-gate 	sp[0]--;
5317c478bd9Sstevel@tonic-gate 	sp[sp[0]+1] = 0;
5327c478bd9Sstevel@tonic-gate 	return;
5337c478bd9Sstevel@tonic-gate 
5347c478bd9Sstevel@tonic-gate bad:
5357c478bd9Sstevel@tonic-gate 	(void) printf("bad delitem\n");
5367c478bd9Sstevel@tonic-gate 	abort();
5377c478bd9Sstevel@tonic-gate }
5387c478bd9Sstevel@tonic-gate 
5397c478bd9Sstevel@tonic-gate int
additem(char buf[PBLKSIZ],datum item)54061961e0fSrobinson additem(char buf[PBLKSIZ], datum item)
5417c478bd9Sstevel@tonic-gate {
5427c478bd9Sstevel@tonic-gate 	short *sp;
5437c478bd9Sstevel@tonic-gate 	int i1, i2;
5447c478bd9Sstevel@tonic-gate 
54561961e0fSrobinson 	/* LINTED pointer cast */
5467c478bd9Sstevel@tonic-gate 	sp = (short *)buf;
5477c478bd9Sstevel@tonic-gate 	i1 = PBLKSIZ;
5487c478bd9Sstevel@tonic-gate 	if (sp[0] > 0)
5497c478bd9Sstevel@tonic-gate 		i1 = sp[sp[0]+1-1];
5507c478bd9Sstevel@tonic-gate 	i1 -= item.dsize;
5517c478bd9Sstevel@tonic-gate 	i2 = (sp[0]+2) * (int)sizeof (short);
55261961e0fSrobinson 	if (i1 <= i2)
5537c478bd9Sstevel@tonic-gate 		return (-1);
5547c478bd9Sstevel@tonic-gate 	sp[sp[0]+1] = (short)i1;
5557c478bd9Sstevel@tonic-gate 	for (i2 = 0; i2 < item.dsize; i2++) {
5567c478bd9Sstevel@tonic-gate 		buf[i1] = item.dptr[i2];
5577c478bd9Sstevel@tonic-gate 		i1++;
5587c478bd9Sstevel@tonic-gate 	}
5597c478bd9Sstevel@tonic-gate 	sp[0]++;
5607c478bd9Sstevel@tonic-gate 	return (sp[0]-1);
5617c478bd9Sstevel@tonic-gate }
5627c478bd9Sstevel@tonic-gate 
5637c478bd9Sstevel@tonic-gate void
chkblk(char buf[PBLKSIZ])56461961e0fSrobinson chkblk(char buf[PBLKSIZ])
5657c478bd9Sstevel@tonic-gate {
5667c478bd9Sstevel@tonic-gate 	short *sp;
5677c478bd9Sstevel@tonic-gate 	int t, i;
5687c478bd9Sstevel@tonic-gate 
56961961e0fSrobinson 	/* LINTED pointer cast */
5707c478bd9Sstevel@tonic-gate 	sp = (short *)buf;
5717c478bd9Sstevel@tonic-gate 	t = PBLKSIZ;
5727c478bd9Sstevel@tonic-gate 	for (i = 0; i < sp[0]; i++) {
5737c478bd9Sstevel@tonic-gate 		if (sp[i+1] > t)
5747c478bd9Sstevel@tonic-gate 			goto bad;
5757c478bd9Sstevel@tonic-gate 		t = sp[i+1];
5767c478bd9Sstevel@tonic-gate 	}
5777c478bd9Sstevel@tonic-gate 	if (t < (sp[0]+1) * sizeof (short))
5787c478bd9Sstevel@tonic-gate 		goto bad;
5797c478bd9Sstevel@tonic-gate 	return;
5807c478bd9Sstevel@tonic-gate 
5817c478bd9Sstevel@tonic-gate bad:
5827c478bd9Sstevel@tonic-gate 	(void) printf("bad block\n");
5837c478bd9Sstevel@tonic-gate 	abort();
58461961e0fSrobinson 	(void) memset(&buf, 0, PBLKSIZ);
5857c478bd9Sstevel@tonic-gate }
586