xref: /illumos-gate/usr/src/ucblib/libdbm/dbm.c (revision 44bf619d)
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
55bbb4db2SGarrett D'Amore  * Common Development and Distribution License (the "License").
65bbb4db2SGarrett D'Amore  * You may not use this file except in compliance with the License.
77c478bd9Sstevel@tonic-gate  *
87c478bd9Sstevel@tonic-gate  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
97c478bd9Sstevel@tonic-gate  * or http://www.opensolaris.org/os/licensing.
107c478bd9Sstevel@tonic-gate  * See the License for the specific language governing permissions
117c478bd9Sstevel@tonic-gate  * and limitations under the License.
127c478bd9Sstevel@tonic-gate  *
137c478bd9Sstevel@tonic-gate  * When distributing Covered Code, include this CDDL HEADER in each
147c478bd9Sstevel@tonic-gate  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
157c478bd9Sstevel@tonic-gate  * If applicable, add the following below this CDDL HEADER, with the
167c478bd9Sstevel@tonic-gate  * fields enclosed by brackets "[]" replaced with your own identifying
177c478bd9Sstevel@tonic-gate  * information: Portions Copyright [yyyy] [name of copyright owner]
187c478bd9Sstevel@tonic-gate  *
197c478bd9Sstevel@tonic-gate  * CDDL HEADER END
207c478bd9Sstevel@tonic-gate  */
217c478bd9Sstevel@tonic-gate /*
225bbb4db2SGarrett D'Amore  * Copyright 2009 Sun Microsystems, Inc.  All rights reserved.
237c478bd9Sstevel@tonic-gate  * Use is subject to license terms.
247c478bd9Sstevel@tonic-gate  */
257c478bd9Sstevel@tonic-gate 
267c478bd9Sstevel@tonic-gate /*	Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T	*/
27*44bf619dSJohn Levon /*	  All Rights Reserved 	*/
287c478bd9Sstevel@tonic-gate 
297c478bd9Sstevel@tonic-gate /*
307c478bd9Sstevel@tonic-gate  * Portions of this source code were derived from Berkeley 4.3 BSD
317c478bd9Sstevel@tonic-gate  * under license from the Regents of the University of California.
327c478bd9Sstevel@tonic-gate  */
337c478bd9Sstevel@tonic-gate 
34cadd68eaSJohn Levon /*
35*44bf619dSJohn Levon  * Copyright 2019 Joyent, Inc.
36cadd68eaSJohn Levon  */
37cadd68eaSJohn Levon 
387c478bd9Sstevel@tonic-gate /*LINTLIBRARY*/
397c478bd9Sstevel@tonic-gate 
407c478bd9Sstevel@tonic-gate #include	<sys/types.h>
417c478bd9Sstevel@tonic-gate #include	<stdio.h>
427c478bd9Sstevel@tonic-gate #include	<unistd.h>
437c478bd9Sstevel@tonic-gate #include	<stdlib.h>
447c478bd9Sstevel@tonic-gate #include	<strings.h>
457c478bd9Sstevel@tonic-gate #include	<malloc.h>
467c478bd9Sstevel@tonic-gate #include	<sys/stat.h>
475bbb4db2SGarrett D'Amore #include	<sys/fcntl.h>
487c478bd9Sstevel@tonic-gate #include	<dbm.h>
497c478bd9Sstevel@tonic-gate #include	<errno.h>
507c478bd9Sstevel@tonic-gate 
517c478bd9Sstevel@tonic-gate /* forward declarations */
527c478bd9Sstevel@tonic-gate /* could be all static if not were for older *.a releases */
537c478bd9Sstevel@tonic-gate void chkblk(char buf[PBLKSIZ]);
547c478bd9Sstevel@tonic-gate void delitem(char buf[PBLKSIZ], int n);
557c478bd9Sstevel@tonic-gate void dbm_access(long hash);
567c478bd9Sstevel@tonic-gate int getbit(void);
577c478bd9Sstevel@tonic-gate int setbit(void);
587c478bd9Sstevel@tonic-gate int additem(char buf[PBLKSIZ], datum item);
597c478bd9Sstevel@tonic-gate int cmpdatum(datum d1, datum d2);
607c478bd9Sstevel@tonic-gate 
617c478bd9Sstevel@tonic-gate int
dbminit(char * file)627c478bd9Sstevel@tonic-gate dbminit(char *file)
637c478bd9Sstevel@tonic-gate {
647c478bd9Sstevel@tonic-gate 	struct stat64 statb;
657c478bd9Sstevel@tonic-gate 
667c478bd9Sstevel@tonic-gate 	dbrdonly = 0;
677c478bd9Sstevel@tonic-gate 	if (strlcpy(pagbuf, file, sizeof (pagbuf)) >= sizeof (pagbuf) ||
687c478bd9Sstevel@tonic-gate 	    strlcat(pagbuf, ".pag", sizeof (pagbuf)) >= sizeof (pagbuf)) {
697c478bd9Sstevel@tonic-gate 		/*
707c478bd9Sstevel@tonic-gate 		 * file.pag does not fit into pagbuf.
717c478bd9Sstevel@tonic-gate 		 * fails with ENAMETOOLONG.
727c478bd9Sstevel@tonic-gate 		 */
737c478bd9Sstevel@tonic-gate 		errno = ENAMETOOLONG;
747c478bd9Sstevel@tonic-gate 		return (-1);
757c478bd9Sstevel@tonic-gate 	}
767c478bd9Sstevel@tonic-gate 	pagf = open(pagbuf, 2);
777c478bd9Sstevel@tonic-gate 	if (pagf < 0) {
787c478bd9Sstevel@tonic-gate 		pagf = open(pagbuf, 0);
797c478bd9Sstevel@tonic-gate 		dbrdonly = 1;
807c478bd9Sstevel@tonic-gate 	}
817c478bd9Sstevel@tonic-gate 
827c478bd9Sstevel@tonic-gate 	/*
837c478bd9Sstevel@tonic-gate 	 * We know this won't overflow so it is safe to ignore the
847c478bd9Sstevel@tonic-gate 	 * return value; we use strl* to prevent false hits in
857c478bd9Sstevel@tonic-gate 	 * code sweeps.
867c478bd9Sstevel@tonic-gate 	 */
877c478bd9Sstevel@tonic-gate 	(void) strlcpy(pagbuf, file, sizeof (pagbuf));
887c478bd9Sstevel@tonic-gate 	(void) strlcat(pagbuf, ".dir", sizeof (pagbuf));
897c478bd9Sstevel@tonic-gate 	dirf = open(pagbuf, 2);
907c478bd9Sstevel@tonic-gate 	if (dirf < 0) {
917c478bd9Sstevel@tonic-gate 		dirf = open(pagbuf, 0);
927c478bd9Sstevel@tonic-gate 		dbrdonly = 1;
937c478bd9Sstevel@tonic-gate 	}
947c478bd9Sstevel@tonic-gate 	if (pagf < 0 || dirf < 0) {
957c478bd9Sstevel@tonic-gate 		(void) printf("cannot open database %s\n", file);
967c478bd9Sstevel@tonic-gate 		return (-1);
977c478bd9Sstevel@tonic-gate 	}
987c478bd9Sstevel@tonic-gate 	/* Guards against large inodes */
997c478bd9Sstevel@tonic-gate 	(void) fstat64(dirf, &statb);
1007c478bd9Sstevel@tonic-gate 	maxbno = (off_t)statb.st_size * BYTESIZ - 1;
1017c478bd9Sstevel@tonic-gate 	return (0);
1027c478bd9Sstevel@tonic-gate }
1037c478bd9Sstevel@tonic-gate 
1047c478bd9Sstevel@tonic-gate static long oldb1 = -1L;
1057c478bd9Sstevel@tonic-gate static long oldb2 = -1L;
1067c478bd9Sstevel@tonic-gate 
1077c478bd9Sstevel@tonic-gate /* Avoid using cached data for subsequent accesses. */
1087c478bd9Sstevel@tonic-gate int
dbmflush(void)1097c478bd9Sstevel@tonic-gate dbmflush(void)
1107c478bd9Sstevel@tonic-gate {
1117c478bd9Sstevel@tonic-gate 	oldb1 = -1L;
1127c478bd9Sstevel@tonic-gate 	oldb2 = -1L;
1137c478bd9Sstevel@tonic-gate 	return (0);
1147c478bd9Sstevel@tonic-gate }
1157c478bd9Sstevel@tonic-gate 
1167c478bd9Sstevel@tonic-gate /* Clean up after ourself. */
1177c478bd9Sstevel@tonic-gate int
dbmclose(void)1187c478bd9Sstevel@tonic-gate dbmclose(void)
1197c478bd9Sstevel@tonic-gate {
1207c478bd9Sstevel@tonic-gate 	(void) close(pagf);
1217c478bd9Sstevel@tonic-gate 	(void) close(dirf);
1227c478bd9Sstevel@tonic-gate 	bitno = 0;
1237c478bd9Sstevel@tonic-gate 	maxbno = 0;
1247c478bd9Sstevel@tonic-gate 	blkno = 0;
1257c478bd9Sstevel@tonic-gate 	hmask = 0;
1267c478bd9Sstevel@tonic-gate 	oldb1 = -1L;
1277c478bd9Sstevel@tonic-gate 	oldb2 = -1L;
1287c478bd9Sstevel@tonic-gate 	return (0);
1297c478bd9Sstevel@tonic-gate }
1307c478bd9Sstevel@tonic-gate 
1317c478bd9Sstevel@tonic-gate long
forder(datum key)1327c478bd9Sstevel@tonic-gate forder(datum key)
1337c478bd9Sstevel@tonic-gate {
1347c478bd9Sstevel@tonic-gate 	long hash;
1357c478bd9Sstevel@tonic-gate 
1367c478bd9Sstevel@tonic-gate 	hash = calchash(key);
1377c478bd9Sstevel@tonic-gate 	for (hmask = 0; ; hmask = (hmask<<1)+1) {
1387c478bd9Sstevel@tonic-gate 		blkno = hash & hmask;
1397c478bd9Sstevel@tonic-gate 		bitno = blkno + hmask;
1407c478bd9Sstevel@tonic-gate 		if (getbit() == 0)
1417c478bd9Sstevel@tonic-gate 			break;
1427c478bd9Sstevel@tonic-gate 	}
1437c478bd9Sstevel@tonic-gate 	return (blkno);
1447c478bd9Sstevel@tonic-gate }
1457c478bd9Sstevel@tonic-gate 
1467c478bd9Sstevel@tonic-gate datum
fetch(datum key)1477c478bd9Sstevel@tonic-gate fetch(datum key)
1487c478bd9Sstevel@tonic-gate {
1497c478bd9Sstevel@tonic-gate 	int i;
1507c478bd9Sstevel@tonic-gate 	datum item;
1517c478bd9Sstevel@tonic-gate 
1527c478bd9Sstevel@tonic-gate 	dbm_access(calchash(key));
1537c478bd9Sstevel@tonic-gate 	for (i = 0; ; i += 2) {
1547c478bd9Sstevel@tonic-gate 		item = makdatum(pagbuf, i);
1557c478bd9Sstevel@tonic-gate 		if (item.dptr == NULL)
1567c478bd9Sstevel@tonic-gate 			return (item);
1577c478bd9Sstevel@tonic-gate 		if (cmpdatum(key, item) == 0) {
1587c478bd9Sstevel@tonic-gate 			item = makdatum(pagbuf, i+1);
1597c478bd9Sstevel@tonic-gate 			if (item.dptr == NULL)
1607c478bd9Sstevel@tonic-gate 				(void) printf("items not in pairs\n");
1617c478bd9Sstevel@tonic-gate 			return (item);
1627c478bd9Sstevel@tonic-gate 		}
1637c478bd9Sstevel@tonic-gate 	}
1647c478bd9Sstevel@tonic-gate }
1657c478bd9Sstevel@tonic-gate 
1667c478bd9Sstevel@tonic-gate int
delete(datum key)1677c478bd9Sstevel@tonic-gate delete(datum key)
1687c478bd9Sstevel@tonic-gate {
1697c478bd9Sstevel@tonic-gate 	int i;
1707c478bd9Sstevel@tonic-gate 	datum item;
1717c478bd9Sstevel@tonic-gate 
1727c478bd9Sstevel@tonic-gate 	if (dbrdonly)
1737c478bd9Sstevel@tonic-gate 		return (-1);
1747c478bd9Sstevel@tonic-gate 	dbm_access(calchash(key));
1757c478bd9Sstevel@tonic-gate 	for (i = 0; ; i += 2) {
1767c478bd9Sstevel@tonic-gate 		item = makdatum(pagbuf, i);
1777c478bd9Sstevel@tonic-gate 		if (item.dptr == NULL)
1787c478bd9Sstevel@tonic-gate 			return (-1);
1797c478bd9Sstevel@tonic-gate 		if (cmpdatum(key, item) == 0) {
1807c478bd9Sstevel@tonic-gate 			delitem(pagbuf, i);
1817c478bd9Sstevel@tonic-gate 			delitem(pagbuf, i);
1827c478bd9Sstevel@tonic-gate 			break;
1837c478bd9Sstevel@tonic-gate 		}
1847c478bd9Sstevel@tonic-gate 	}
1857c478bd9Sstevel@tonic-gate 	(void) lseek(pagf, blkno*PBLKSIZ, 0);
1867c478bd9Sstevel@tonic-gate 	(void) write(pagf, pagbuf, PBLKSIZ);
1877c478bd9Sstevel@tonic-gate 	return (0);
1887c478bd9Sstevel@tonic-gate }
1897c478bd9Sstevel@tonic-gate 
1907c478bd9Sstevel@tonic-gate int
store(datum key,datum dat)1917c478bd9Sstevel@tonic-gate store(datum key, datum dat)
1927c478bd9Sstevel@tonic-gate {
1937c478bd9Sstevel@tonic-gate 	int i;
1947c478bd9Sstevel@tonic-gate 	datum item;
1957c478bd9Sstevel@tonic-gate 	char ovfbuf[PBLKSIZ];
1967c478bd9Sstevel@tonic-gate 	datum Sentry;
1977c478bd9Sstevel@tonic-gate 	int Oneflag;
1987c478bd9Sstevel@tonic-gate 
1997c478bd9Sstevel@tonic-gate 	Sentry.dsize = 0;
2007c478bd9Sstevel@tonic-gate 	Sentry.dptr = NULL;
2017c478bd9Sstevel@tonic-gate 
2027c478bd9Sstevel@tonic-gate 	if (dbrdonly)
2037c478bd9Sstevel@tonic-gate 		return (-1);
2047c478bd9Sstevel@tonic-gate loop:
2057c478bd9Sstevel@tonic-gate 	dbm_access(calchash(key));
2067c478bd9Sstevel@tonic-gate 	for (i = 0; ; i += 2) {
2077c478bd9Sstevel@tonic-gate 		item = makdatum(pagbuf, i);
2087c478bd9Sstevel@tonic-gate 		if (item.dptr == NULL)
2097c478bd9Sstevel@tonic-gate 			break;
2107c478bd9Sstevel@tonic-gate 		if (cmpdatum(key, item) == 0) {
2117c478bd9Sstevel@tonic-gate 			delitem(pagbuf, i);
2127c478bd9Sstevel@tonic-gate 			delitem(pagbuf, i);
2137c478bd9Sstevel@tonic-gate 			break;
2147c478bd9Sstevel@tonic-gate 		}
2157c478bd9Sstevel@tonic-gate 	}
2167c478bd9Sstevel@tonic-gate 	i = additem(pagbuf, key);
2177c478bd9Sstevel@tonic-gate 	if (i < 0)
2187c478bd9Sstevel@tonic-gate 		goto split;
2197c478bd9Sstevel@tonic-gate 	if (additem(pagbuf, dat) < 0) {
2207c478bd9Sstevel@tonic-gate 		delitem(pagbuf, i);
2217c478bd9Sstevel@tonic-gate 		goto split;
2227c478bd9Sstevel@tonic-gate 	}
2237c478bd9Sstevel@tonic-gate 	(void) lseek(pagf, blkno*PBLKSIZ, 0);
2247c478bd9Sstevel@tonic-gate 	(void) write(pagf, pagbuf, PBLKSIZ);
2257c478bd9Sstevel@tonic-gate 	return (0);
2267c478bd9Sstevel@tonic-gate split:
2277c478bd9Sstevel@tonic-gate 	if (key.dsize+dat.dsize+3*sizeof (short) >= PBLKSIZ) {
2287c478bd9Sstevel@tonic-gate 		(void) printf("entry too big\n");
2297c478bd9Sstevel@tonic-gate 		return (-1);
2307c478bd9Sstevel@tonic-gate 	}
2317c478bd9Sstevel@tonic-gate 	bzero(ovfbuf, PBLKSIZ);
2327c478bd9Sstevel@tonic-gate 	Oneflag = 0;
2337c478bd9Sstevel@tonic-gate 	for (i = 0; ; ) {
2347c478bd9Sstevel@tonic-gate 		item = makdatum(pagbuf, i);
2357c478bd9Sstevel@tonic-gate 		Oneflag++;
2367c478bd9Sstevel@tonic-gate 		if (item.dptr == NULL) {
2377c478bd9Sstevel@tonic-gate 			if ((Sentry.dsize == key.dsize) &&
2387c478bd9Sstevel@tonic-gate 			    (strncmp(Sentry.dptr, key.dptr, key.dsize) == 0))
2397c478bd9Sstevel@tonic-gate 				return (-1);
2407c478bd9Sstevel@tonic-gate 			if (Oneflag == 2) {
2417c478bd9Sstevel@tonic-gate 				Sentry.dsize = key.dsize;
2427c478bd9Sstevel@tonic-gate 				Sentry.dptr = malloc(strlen(key.dptr)+1);
2437c478bd9Sstevel@tonic-gate 				(void) strncpy(Sentry.dptr, key.dptr,
244*44bf619dSJohn Levon 				    key.dsize);
2457c478bd9Sstevel@tonic-gate 			}
2467c478bd9Sstevel@tonic-gate 			break;
2477c478bd9Sstevel@tonic-gate 		}
2487c478bd9Sstevel@tonic-gate 		if (calchash(item) & (hmask+1)) {
2497c478bd9Sstevel@tonic-gate 			(void) additem(ovfbuf, item);
2507c478bd9Sstevel@tonic-gate 			delitem(pagbuf, i);
2517c478bd9Sstevel@tonic-gate 			item = makdatum(pagbuf, i);
2527c478bd9Sstevel@tonic-gate 			if (item.dptr == NULL) {
2537c478bd9Sstevel@tonic-gate 				(void) printf("split not paired\n");
2547c478bd9Sstevel@tonic-gate 				break;
2557c478bd9Sstevel@tonic-gate 			}
2567c478bd9Sstevel@tonic-gate 			(void) additem(ovfbuf, item);
2577c478bd9Sstevel@tonic-gate 			delitem(pagbuf, i);
2587c478bd9Sstevel@tonic-gate 			continue;
2597c478bd9Sstevel@tonic-gate 		}
2607c478bd9Sstevel@tonic-gate 		i += 2;
2617c478bd9Sstevel@tonic-gate 	}
2627c478bd9Sstevel@tonic-gate 	(void) lseek(pagf, blkno*PBLKSIZ, 0);
2637c478bd9Sstevel@tonic-gate 	if (write(pagf, pagbuf, PBLKSIZ) < 0)
2647c478bd9Sstevel@tonic-gate 		return (-1);
2657c478bd9Sstevel@tonic-gate 	(void) lseek(pagf, (blkno+hmask+1)*PBLKSIZ, 0);
2667c478bd9Sstevel@tonic-gate 	if (write(pagf, ovfbuf, PBLKSIZ) < 0)
2677c478bd9Sstevel@tonic-gate 		return (-1);
2687c478bd9Sstevel@tonic-gate 	if (setbit() < 0)
2697c478bd9Sstevel@tonic-gate 		return (-1);
2707c478bd9Sstevel@tonic-gate 	goto loop;
2717c478bd9Sstevel@tonic-gate }
2727c478bd9Sstevel@tonic-gate 
2737c478bd9Sstevel@tonic-gate datum
firstkey(void)2747c478bd9Sstevel@tonic-gate firstkey(void)
2757c478bd9Sstevel@tonic-gate {
2767c478bd9Sstevel@tonic-gate 	return (firsthash(0L));
2777c478bd9Sstevel@tonic-gate }
2787c478bd9Sstevel@tonic-gate 
2797c478bd9Sstevel@tonic-gate datum
nextkey(datum key)2807c478bd9Sstevel@tonic-gate nextkey(datum key)
2817c478bd9Sstevel@tonic-gate {
2827c478bd9Sstevel@tonic-gate 	int i;
2837c478bd9Sstevel@tonic-gate 	datum item, bitem;
2847c478bd9Sstevel@tonic-gate 	long hash;
2857c478bd9Sstevel@tonic-gate 	int f;
2867c478bd9Sstevel@tonic-gate 
2877c478bd9Sstevel@tonic-gate 	hash = calchash(key);
2887c478bd9Sstevel@tonic-gate 	dbm_access(hash);
2897c478bd9Sstevel@tonic-gate 	f = 1;
2907c478bd9Sstevel@tonic-gate 	for (i = 0; ; i += 2) {
2917c478bd9Sstevel@tonic-gate 		item = makdatum(pagbuf, i);
2927c478bd9Sstevel@tonic-gate 		if (item.dptr == NULL)
2937c478bd9Sstevel@tonic-gate 			break;
2947c478bd9Sstevel@tonic-gate 		if (cmpdatum(key, item) <= 0)
2957c478bd9Sstevel@tonic-gate 			continue;
2967c478bd9Sstevel@tonic-gate 		if (f || cmpdatum(bitem, item) < 0) {
2977c478bd9Sstevel@tonic-gate 			bitem = item;
2987c478bd9Sstevel@tonic-gate 			f = 0;
2997c478bd9Sstevel@tonic-gate 		}
3007c478bd9Sstevel@tonic-gate 	}
3017c478bd9Sstevel@tonic-gate 	if (f == 0)
3027c478bd9Sstevel@tonic-gate 		return (bitem);
3037c478bd9Sstevel@tonic-gate 	hash = hashinc(hash);
3047c478bd9Sstevel@tonic-gate 	if (hash == 0)
3057c478bd9Sstevel@tonic-gate 		return (item);
3067c478bd9Sstevel@tonic-gate 	return (firsthash(hash));
3077c478bd9Sstevel@tonic-gate }
3087c478bd9Sstevel@tonic-gate 
3097c478bd9Sstevel@tonic-gate datum
firsthash(long hash)3107c478bd9Sstevel@tonic-gate firsthash(long hash)
3117c478bd9Sstevel@tonic-gate {
3127c478bd9Sstevel@tonic-gate 	int i;
3137c478bd9Sstevel@tonic-gate 	datum item, bitem;
3147c478bd9Sstevel@tonic-gate 
3157c478bd9Sstevel@tonic-gate loop:
3167c478bd9Sstevel@tonic-gate 	dbm_access(hash);
3177c478bd9Sstevel@tonic-gate 	bitem = makdatum(pagbuf, 0);
3187c478bd9Sstevel@tonic-gate 	for (i = 2; ; i += 2) {
3197c478bd9Sstevel@tonic-gate 		item = makdatum(pagbuf, i);
3207c478bd9Sstevel@tonic-gate 		if (item.dptr == NULL)
3217c478bd9Sstevel@tonic-gate 			break;
3227c478bd9Sstevel@tonic-gate 		if (cmpdatum(bitem, item) < 0)
3237c478bd9Sstevel@tonic-gate 			bitem = item;
3247c478bd9Sstevel@tonic-gate 	}
3257c478bd9Sstevel@tonic-gate 	if (bitem.dptr != NULL)
3267c478bd9Sstevel@tonic-gate 		return (bitem);
3277c478bd9Sstevel@tonic-gate 	hash = hashinc(hash);
3287c478bd9Sstevel@tonic-gate 	if (hash == 0)
3297c478bd9Sstevel@tonic-gate 		return (item);
3307c478bd9Sstevel@tonic-gate 	goto loop;
3317c478bd9Sstevel@tonic-gate }
3327c478bd9Sstevel@tonic-gate 
3337c478bd9Sstevel@tonic-gate void
dbm_access(long hash)3347c478bd9Sstevel@tonic-gate dbm_access(long hash)
3357c478bd9Sstevel@tonic-gate {
3367c478bd9Sstevel@tonic-gate 	ssize_t readsize;
3377c478bd9Sstevel@tonic-gate 
3387c478bd9Sstevel@tonic-gate 	for (hmask = 0; ; hmask = (hmask<<1)+1) {
3397c478bd9Sstevel@tonic-gate 		blkno = hash & hmask;
3407c478bd9Sstevel@tonic-gate 		bitno = blkno + hmask;
3417c478bd9Sstevel@tonic-gate 		if (getbit() == 0)
3427c478bd9Sstevel@tonic-gate 			break;
3437c478bd9Sstevel@tonic-gate 	}
3447c478bd9Sstevel@tonic-gate 	if (blkno != oldb1) {
3457c478bd9Sstevel@tonic-gate 		(void) lseek(pagf, blkno*PBLKSIZ, 0);
3467c478bd9Sstevel@tonic-gate 		readsize = read(pagf, pagbuf, PBLKSIZ);
3477c478bd9Sstevel@tonic-gate 		if (readsize != PBLKSIZ) {
3487c478bd9Sstevel@tonic-gate 			if (readsize < 0) readsize = 0;
3497c478bd9Sstevel@tonic-gate 			bzero(pagbuf+readsize, PBLKSIZ-readsize);
3507c478bd9Sstevel@tonic-gate 		}
3517c478bd9Sstevel@tonic-gate 		chkblk(pagbuf);
3527c478bd9Sstevel@tonic-gate 		oldb1 = blkno;
3537c478bd9Sstevel@tonic-gate 	}
3547c478bd9Sstevel@tonic-gate }
3557c478bd9Sstevel@tonic-gate 
3567c478bd9Sstevel@tonic-gate int
getbit(void)3577c478bd9Sstevel@tonic-gate getbit(void)
3587c478bd9Sstevel@tonic-gate {
3597c478bd9Sstevel@tonic-gate 	long bn;
3607c478bd9Sstevel@tonic-gate 	ssize_t readsize;
3617c478bd9Sstevel@tonic-gate 	long b, i, n;
3627c478bd9Sstevel@tonic-gate 
3637c478bd9Sstevel@tonic-gate 	if (bitno > maxbno)
3647c478bd9Sstevel@tonic-gate 		return (0);
3657c478bd9Sstevel@tonic-gate 	n = bitno % BYTESIZ;
3667c478bd9Sstevel@tonic-gate 	bn = bitno / BYTESIZ;
3677c478bd9Sstevel@tonic-gate 	i = bn % DBLKSIZ;
3687c478bd9Sstevel@tonic-gate 	b = bn / DBLKSIZ;
3697c478bd9Sstevel@tonic-gate 	if (b != oldb2) {
3707c478bd9Sstevel@tonic-gate 		(void) lseek(dirf, (long)b*DBLKSIZ, 0);
3717c478bd9Sstevel@tonic-gate 		readsize = read(dirf, dirbuf, DBLKSIZ);
3727c478bd9Sstevel@tonic-gate 		if (readsize != DBLKSIZ) {
3737c478bd9Sstevel@tonic-gate 			if (readsize < 0) readsize = 0;
3747c478bd9Sstevel@tonic-gate 			bzero(dirbuf+readsize, DBLKSIZ-readsize);
3757c478bd9Sstevel@tonic-gate 		}
3767c478bd9Sstevel@tonic-gate 		oldb2 = b;
3777c478bd9Sstevel@tonic-gate 	}
3787c478bd9Sstevel@tonic-gate 	if (dirbuf[i] & (1<<n))
3797c478bd9Sstevel@tonic-gate 		return (1);
3807c478bd9Sstevel@tonic-gate 	return (0);
3817c478bd9Sstevel@tonic-gate }
3827c478bd9Sstevel@tonic-gate 
3837c478bd9Sstevel@tonic-gate int
setbit(void)3847c478bd9Sstevel@tonic-gate setbit(void)
3857c478bd9Sstevel@tonic-gate {
3867c478bd9Sstevel@tonic-gate 	long bn;
3877c478bd9Sstevel@tonic-gate 	long i, n, b;
3887c478bd9Sstevel@tonic-gate 
3897c478bd9Sstevel@tonic-gate 	if (dbrdonly)
3907c478bd9Sstevel@tonic-gate 		return (-1);
3917c478bd9Sstevel@tonic-gate 	if (bitno > maxbno) {
3927c478bd9Sstevel@tonic-gate 		maxbno = bitno;
3937c478bd9Sstevel@tonic-gate 		(void) getbit();
3947c478bd9Sstevel@tonic-gate 	}
3957c478bd9Sstevel@tonic-gate 	n = bitno % BYTESIZ;
3967c478bd9Sstevel@tonic-gate 	bn = bitno / BYTESIZ;
3977c478bd9Sstevel@tonic-gate 	i = bn % DBLKSIZ;
3987c478bd9Sstevel@tonic-gate 	b = bn / DBLKSIZ;
3997c478bd9Sstevel@tonic-gate 	dirbuf[i] |= 1<<n;
4007c478bd9Sstevel@tonic-gate 	(void) lseek(dirf, (long)b*DBLKSIZ, 0);
4017c478bd9Sstevel@tonic-gate 	if (write(dirf, dirbuf, DBLKSIZ) < 0)
4027c478bd9Sstevel@tonic-gate 		return (-1);
4037c478bd9Sstevel@tonic-gate 	return (0);
4047c478bd9Sstevel@tonic-gate }
4057c478bd9Sstevel@tonic-gate 
4067c478bd9Sstevel@tonic-gate datum
makdatum(char buf[PBLKSIZ],int n)4077c478bd9Sstevel@tonic-gate makdatum(char buf[PBLKSIZ], int n)
4087c478bd9Sstevel@tonic-gate {
4097c478bd9Sstevel@tonic-gate 	short *sp;
4107c478bd9Sstevel@tonic-gate 	int t;
4117c478bd9Sstevel@tonic-gate 	datum item;
4127c478bd9Sstevel@tonic-gate 
4137c478bd9Sstevel@tonic-gate 	sp = (short *)buf;
4147c478bd9Sstevel@tonic-gate 	if (n < 0 || n >= sp[0])
4157c478bd9Sstevel@tonic-gate 		goto null;
4167c478bd9Sstevel@tonic-gate 	t = PBLKSIZ;
4177c478bd9Sstevel@tonic-gate 	if (n > 0)
4187c478bd9Sstevel@tonic-gate 		t = sp[n+1-1];
4197c478bd9Sstevel@tonic-gate 	item.dptr = buf+sp[n+1];
4207c478bd9Sstevel@tonic-gate 	item.dsize = t - sp[n+1];
4217c478bd9Sstevel@tonic-gate 	return (item);
4227c478bd9Sstevel@tonic-gate 
4237c478bd9Sstevel@tonic-gate null:
4247c478bd9Sstevel@tonic-gate 	item.dptr = NULL;
4257c478bd9Sstevel@tonic-gate 	item.dsize = 0;
4267c478bd9Sstevel@tonic-gate 	return (item);
4277c478bd9Sstevel@tonic-gate }
4287c478bd9Sstevel@tonic-gate 
4297c478bd9Sstevel@tonic-gate int
cmpdatum(datum d1,datum d2)4307c478bd9Sstevel@tonic-gate cmpdatum(datum d1, datum d2)
4317c478bd9Sstevel@tonic-gate {
4327c478bd9Sstevel@tonic-gate 	int n;
4337c478bd9Sstevel@tonic-gate 	char *p1, *p2;
4347c478bd9Sstevel@tonic-gate 
4357c478bd9Sstevel@tonic-gate 	n = d1.dsize;
4367c478bd9Sstevel@tonic-gate 	if (n != d2.dsize)
4377c478bd9Sstevel@tonic-gate 		return (n - d2.dsize);
4387c478bd9Sstevel@tonic-gate 	if (n == 0)
4397c478bd9Sstevel@tonic-gate 		return (0);
4407c478bd9Sstevel@tonic-gate 	p1 = d1.dptr;
4417c478bd9Sstevel@tonic-gate 	p2 = d2.dptr;
4427c478bd9Sstevel@tonic-gate 	do
4437c478bd9Sstevel@tonic-gate 		if (*p1++ != *p2++)
4447c478bd9Sstevel@tonic-gate 			return (*--p1 - *--p2);
445*44bf619dSJohn Levon 	while (--n)
446*44bf619dSJohn Levon 		;
4477c478bd9Sstevel@tonic-gate 	return (0);
4487c478bd9Sstevel@tonic-gate }
4497c478bd9Sstevel@tonic-gate 
4507c478bd9Sstevel@tonic-gate int	hitab[16]
4517c478bd9Sstevel@tonic-gate /*
4527c478bd9Sstevel@tonic-gate  * ken's
4537c478bd9Sstevel@tonic-gate  * {
4547c478bd9Sstevel@tonic-gate  *	055,043,036,054,063,014,004,005,
4557c478bd9Sstevel@tonic-gate  *	010,064,077,000,035,027,025,071,
4567c478bd9Sstevel@tonic-gate  * };
4577c478bd9Sstevel@tonic-gate  */
4587c478bd9Sstevel@tonic-gate 	= {	61, 57, 53, 49, 45, 41, 37, 33,
4597c478bd9Sstevel@tonic-gate 		29, 25, 21, 17, 13,  9,  5,  1,
4607c478bd9Sstevel@tonic-gate 	};
4617c478bd9Sstevel@tonic-gate long	hltab[64] = {
4627c478bd9Sstevel@tonic-gate 	06100151277L, 06106161736L, 06452611562L, 05001724107L,
4637c478bd9Sstevel@tonic-gate 	02614772546L, 04120731531L, 04665262210L, 07347467531L,
4647c478bd9Sstevel@tonic-gate 	06735253126L, 06042345173L, 03072226605L, 01464164730L,
4657c478bd9Sstevel@tonic-gate 	03247435524L, 07652510057L, 01546775256L, 05714532133L,
4667c478bd9Sstevel@tonic-gate 	06173260402L, 07517101630L, 02431460343L, 01743245566L,
4677c478bd9Sstevel@tonic-gate 	00261675137L, 02433103631L, 03421772437L, 04447707466L,
4687c478bd9Sstevel@tonic-gate 	04435620103L, 03757017115L, 03641531772L, 06767633246L,
4697c478bd9Sstevel@tonic-gate 	02673230344L, 00260612216L, 04133454451L, 00615531516L,
4707c478bd9Sstevel@tonic-gate 	06137717526L, 02574116560L, 02304023373L, 07061702261L,
4717c478bd9Sstevel@tonic-gate 	05153031405L, 05322056705L, 07401116734L, 06552375715L,
4727c478bd9Sstevel@tonic-gate 	06165233473L, 05311063631L, 01212221723L, 01052267235L,
4737c478bd9Sstevel@tonic-gate 	06000615237L, 01075222665L, 06330216006L, 04402355630L,
4747c478bd9Sstevel@tonic-gate 	01451177262L, 02000133436L, 06025467062L, 07121076461L,
4757c478bd9Sstevel@tonic-gate 	03123433522L, 01010635225L, 01716177066L, 05161746527L,
4767c478bd9Sstevel@tonic-gate 	01736635071L, 06243505026L, 03637211610L, 01756474365L,
4777c478bd9Sstevel@tonic-gate 	04723077174L, 03642763134L, 05750130273L, 03655541561L,
4787c478bd9Sstevel@tonic-gate };
4797c478bd9Sstevel@tonic-gate 
4807c478bd9Sstevel@tonic-gate long
hashinc(long hash)4817c478bd9Sstevel@tonic-gate hashinc(long hash)
4827c478bd9Sstevel@tonic-gate {
4837c478bd9Sstevel@tonic-gate 	long bit;
4847c478bd9Sstevel@tonic-gate 
4857c478bd9Sstevel@tonic-gate 	hash &= hmask;
4867c478bd9Sstevel@tonic-gate 	bit = hmask+1;
4877c478bd9Sstevel@tonic-gate 	for (;;) {
4887c478bd9Sstevel@tonic-gate 		bit >>= 1;
4897c478bd9Sstevel@tonic-gate 		if (bit == 0)
4907c478bd9Sstevel@tonic-gate 			return (0L);
4917c478bd9Sstevel@tonic-gate 		if ((hash&bit) == 0)
4927c478bd9Sstevel@tonic-gate 			return (hash|bit);
4937c478bd9Sstevel@tonic-gate 		hash &= ~bit;
4947c478bd9Sstevel@tonic-gate 	}
4957c478bd9Sstevel@tonic-gate }
4967c478bd9Sstevel@tonic-gate 
4977c478bd9Sstevel@tonic-gate long
calchash(datum item)4987c478bd9Sstevel@tonic-gate calchash(datum item)
4997c478bd9Sstevel@tonic-gate {
5007c478bd9Sstevel@tonic-gate 	int i, j, f;
5017c478bd9Sstevel@tonic-gate 	long hashl;
5027c478bd9Sstevel@tonic-gate 	int hashi;
5037c478bd9Sstevel@tonic-gate 
5047c478bd9Sstevel@tonic-gate 	hashl = 0;
5057c478bd9Sstevel@tonic-gate 	hashi = 0;
5067c478bd9Sstevel@tonic-gate 	for (i = 0; i < item.dsize; i++) {
5077c478bd9Sstevel@tonic-gate 		f = item.dptr[i];
5087c478bd9Sstevel@tonic-gate 		for (j = 0; j < BYTESIZ; j += 4) {
5097c478bd9Sstevel@tonic-gate 			hashi += hitab[f&017];
5107c478bd9Sstevel@tonic-gate 			hashl += hltab[hashi&63];
5117c478bd9Sstevel@tonic-gate 			f >>= 4;
5127c478bd9Sstevel@tonic-gate 		}
5137c478bd9Sstevel@tonic-gate 	}
5147c478bd9Sstevel@tonic-gate 	return (hashl);
5157c478bd9Sstevel@tonic-gate }
5167c478bd9Sstevel@tonic-gate 
5177c478bd9Sstevel@tonic-gate void
delitem(char buf[PBLKSIZ],int n)5187c478bd9Sstevel@tonic-gate delitem(char buf[PBLKSIZ], int n)
5197c478bd9Sstevel@tonic-gate {
5207c478bd9Sstevel@tonic-gate 	short *sp;
5217c478bd9Sstevel@tonic-gate 	int i1, i2, i3;
5227c478bd9Sstevel@tonic-gate 
5237c478bd9Sstevel@tonic-gate 	sp = (short *)buf;
5247c478bd9Sstevel@tonic-gate 	if (n < 0 || n >= sp[0])
5257c478bd9Sstevel@tonic-gate 		goto bad;
5267c478bd9Sstevel@tonic-gate 	i1 = sp[n+1];
5277c478bd9Sstevel@tonic-gate 	i2 = PBLKSIZ;
5287c478bd9Sstevel@tonic-gate 	if (n > 0)
5297c478bd9Sstevel@tonic-gate 		i2 = sp[n+1-1];
5307c478bd9Sstevel@tonic-gate 	i3 = sp[sp[0]+1-1];
5317c478bd9Sstevel@tonic-gate 	if (i2 > i1)
532cadd68eaSJohn Levon 		while (i1 > i3) {
533cadd68eaSJohn Levon 			i1--;
534cadd68eaSJohn Levon 			i2--;
535cadd68eaSJohn Levon 			buf[i2] = buf[i1];
536cadd68eaSJohn Levon 			buf[i1] = 0;
537cadd68eaSJohn Levon 		}
5387c478bd9Sstevel@tonic-gate 	i2 -= i1;
5397c478bd9Sstevel@tonic-gate 	for (i1 = n+1; i1 < sp[0]; i1++)
5407c478bd9Sstevel@tonic-gate 		sp[i1+1-1] = sp[i1+1] + i2;
5417c478bd9Sstevel@tonic-gate 	sp[0]--;
5427c478bd9Sstevel@tonic-gate 	sp[sp[0]+1] = 0;
5437c478bd9Sstevel@tonic-gate 	return;
5447c478bd9Sstevel@tonic-gate 
5457c478bd9Sstevel@tonic-gate bad:
5467c478bd9Sstevel@tonic-gate 	(void) printf("bad delitem\n");
5477c478bd9Sstevel@tonic-gate 	abort();
5487c478bd9Sstevel@tonic-gate }
5497c478bd9Sstevel@tonic-gate 
5507c478bd9Sstevel@tonic-gate int
additem(char buf[PBLKSIZ],datum item)5517c478bd9Sstevel@tonic-gate additem(char buf[PBLKSIZ], datum item)
5527c478bd9Sstevel@tonic-gate {
5537c478bd9Sstevel@tonic-gate 	short *sp;
5547c478bd9Sstevel@tonic-gate 	int i1, i2;
5557c478bd9Sstevel@tonic-gate 
5567c478bd9Sstevel@tonic-gate 	sp = (short *)buf;
5577c478bd9Sstevel@tonic-gate 	i1 = PBLKSIZ;
5587c478bd9Sstevel@tonic-gate 	if (sp[0] > 0)
5597c478bd9Sstevel@tonic-gate 		i1 = sp[sp[0]+1-1];
5607c478bd9Sstevel@tonic-gate 	i1 -= item.dsize;
5617c478bd9Sstevel@tonic-gate 	i2 = (int)((sp[0]+2) * sizeof (short));
5627c478bd9Sstevel@tonic-gate 	if (i1 <= i2)
5637c478bd9Sstevel@tonic-gate 		return (-1);
5647c478bd9Sstevel@tonic-gate 	sp[sp[0]+1] = (short)i1;
5657c478bd9Sstevel@tonic-gate 	for (i2 = 0; i2 < item.dsize; i2++) {
5667c478bd9Sstevel@tonic-gate 		buf[i1] = item.dptr[i2];
5677c478bd9Sstevel@tonic-gate 		i1++;
5687c478bd9Sstevel@tonic-gate 	}
5697c478bd9Sstevel@tonic-gate 	sp[0]++;
5707c478bd9Sstevel@tonic-gate 	return (sp[0]-1);
5717c478bd9Sstevel@tonic-gate }
5727c478bd9Sstevel@tonic-gate 
5737c478bd9Sstevel@tonic-gate void
chkblk(char buf[PBLKSIZ])5747c478bd9Sstevel@tonic-gate chkblk(char buf[PBLKSIZ])
5757c478bd9Sstevel@tonic-gate {
5767c478bd9Sstevel@tonic-gate 	short *sp;
5777c478bd9Sstevel@tonic-gate 	int t, i;
5787c478bd9Sstevel@tonic-gate 
5797c478bd9Sstevel@tonic-gate 	sp = (short *)buf;
5807c478bd9Sstevel@tonic-gate 	t = PBLKSIZ;
5817c478bd9Sstevel@tonic-gate 	for (i = 0; i < sp[0]; i++) {
5827c478bd9Sstevel@tonic-gate 		if (sp[i+1] > t)
5837c478bd9Sstevel@tonic-gate 			goto bad;
5847c478bd9Sstevel@tonic-gate 		t = sp[i+1];
5857c478bd9Sstevel@tonic-gate 	}
5867c478bd9Sstevel@tonic-gate 	if (t < (sp[0]+1)*sizeof (short))
5877c478bd9Sstevel@tonic-gate 		goto bad;
5887c478bd9Sstevel@tonic-gate 	return;
5897c478bd9Sstevel@tonic-gate 
5907c478bd9Sstevel@tonic-gate bad:
5917c478bd9Sstevel@tonic-gate 	(void) printf("bad block\n");
5927c478bd9Sstevel@tonic-gate 	abort();
5937c478bd9Sstevel@tonic-gate }
594