xref: /illumos-gate/usr/src/lib/libc/port/gen/ndbm.c (revision 5d9d9091f564c198a760790b0bfa72c44e17912b) 
1 /*
2  * CDDL HEADER START
3  *
4  * The contents of this file are subject to the terms of the
5  * Common Development and Distribution License (the "License").
6  * You may not use this file except in compliance with the License.
7  *
8  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
9  * or http://www.opensolaris.org/os/licensing.
10  * See the License for the specific language governing permissions
11  * and limitations under the License.
12  *
13  * When distributing Covered Code, include this CDDL HEADER in each
14  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
15  * If applicable, add the following below this CDDL HEADER, with the
16  * fields enclosed by brackets "[]" replaced with your own identifying
17  * information: Portions Copyright [yyyy] [name of copyright owner]
18  *
19  * CDDL HEADER END
20  */
21 
22 /*
23  * Copyright 2008 Sun Microsystems, Inc.  All rights reserved.
24  * Use is subject to license terms.
25  * Copyright (c) 2016 by Delphix. All rights reserved.
26  */
27 
28 /*	Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T	*/
29 /*	  All Rights Reserved	*/
30 
31 /*
32  * University Copyright- Copyright (c) 1982, 1986, 1988
33  * The Regents of the University of California
34  * All Rights Reserved
35  *
36  * University Acknowledgment- Portions of this document are derived from
37  * software developed by the University of California, Berkeley, and its
38  * contributors.
39  */
40 
41 #include "lint.h"
42 #include <sys/types.h>
43 #include <sys/stat.h>
44 #include <fcntl.h>
45 #include <sys/file.h>
46 #include <stdio.h>
47 #include <stdlib.h>
48 #include <errno.h>
49 #include <ndbm.h>
50 #include <unistd.h>
51 #include <string.h>
52 #include <pthread.h>
53 
54 /* add support for batched writing for NIS */
55 
56 #define	_DBM_DEFWRITE 0x4
57 #define	_DBM_DIRTY 0x8
58 #define	_DBM_DIRDIRTY 0x10
59 #define	dbm_dirty(db) ((db)->dbm_flags & _DBM_DIRTY)
60 #define	dbm_dirdirty(db) ((db)->dbm_flags & _DBM_DIRDIRTY)
61 #define	dbm_defwrite(db) ((db)->dbm_flags & _DBM_DEFWRITE)
62 #define	dbm_setdirty(db) (db)->dbm_flags |= _DBM_DIRTY
63 #define	dbm_clrdirty(db) (db)->dbm_flags &= ~_DBM_DIRTY
64 #define	dbm_setdirdirty(db) (db)->dbm_flags |= _DBM_DIRDIRTY
65 #define	dbm_clrdirdirty(db) (db)->dbm_flags &= ~_DBM_DIRDIRTY
66 
67 /*
68  * forward declarations
69  */
70 static datum makdatum(char *, int);
71 static unsigned long dcalchash(datum);
72 static void dbm_access(DBM *, unsigned long);
73 static int finddatum(char *, datum);
74 static int delitem(char *, int);
75 static int additem(char *, datum, datum);
76 static int cmpdatum(datum, datum);
77 static int setbit(DBM *);
78 static int getbit(DBM *);
79 static int dbm_flushdir(DBM *);
80 static int dbm_flushpag(DBM *db);
81 
82 /* the following three are required by mapfile-vers */
83 datum dbm_do_nextkey(DBM *, datum);
84 int dbm_close_status(DBM *);
85 
86 /* used to make a dbm file all at once instead of incrementally */
87 void
88 dbm_setdefwrite(DBM *db)
89 {
90 	db->dbm_flags |= _DBM_DEFWRITE;
91 }
92 
93 #undef	dbm_error
94 
95 int
96 dbm_error(DBM *db)
97 {
98 	return (db->dbm_flags & _DBM_IOERR);
99 }
100 
101 #undef	dbm_clearerr
102 
103 int
104 dbm_clearerr(DBM *db)
105 {
106 	return (db->dbm_flags &= ~_DBM_IOERR);
107 }
108 
109 int
110 dbm_flush(DBM *db)
111 {
112 	int ok = 0;
113 	if (dbm_flushpag(db) < 0)
114 		ok = -1;
115 	if (dbm_flushdir(db) < 0)
116 		ok = -1;
117 	return (ok);
118 }
119 
120 static int
121 dbm_flushpag(DBM *db)
122 {
123 	int ok = 0;
124 	off64_t where;
125 
126 	if (dbm_dirty(db)) { /* must page out the page */
127 		where = (((off64_t)db->dbm_pagbno) * PBLKSIZ);
128 		if ((lseek64(db->dbm_pagf, where, L_SET) != where) ||
129 		    (write(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) != PBLKSIZ)) {
130 			db->dbm_flags |= _DBM_IOERR;
131 			ok = -1;
132 		}
133 		dbm_clrdirty(db);
134 	}
135 	return (ok);
136 }
137 
138 static int
139 dbm_flushdir(DBM *db)
140 {
141 	int ok = 0;
142 	off64_t where;
143 	if (dbm_dirdirty(db)) { /* must page out the dir */
144 		where = (((off64_t)db->dbm_dirbno) * DBLKSIZ);
145 		if ((lseek64(db->dbm_dirf, where, L_SET) != where) ||
146 		    (write(db->dbm_dirf, db->dbm_dirbuf, DBLKSIZ) != DBLKSIZ)) {
147 			ok = -1;
148 		}
149 		dbm_clrdirdirty(db);
150 	}
151 	return (ok);
152 }
153 
154 #define	BYTESIZ 8
155 #undef setbit
156 
157 DBM *
158 dbm_open(const char *file, int flags, mode_t mode)
159 {
160 	struct stat64 statb;
161 	DBM *db;
162 	int	serrno;
163 
164 	if ((db = (DBM *)malloc(sizeof (*db))) == 0) {
165 		errno = ENOMEM;
166 		return ((DBM *)0);
167 	}
168 	db->dbm_flags = (flags & 03) == O_RDONLY ? _DBM_RDONLY : 0;
169 	if ((flags & 03) == O_WRONLY)
170 		flags = (flags & ~03) | O_RDWR;
171 	if (strlcpy(db->dbm_pagbuf, file, sizeof (db->dbm_pagbuf)) >=
172 	    sizeof (db->dbm_pagbuf) ||
173 	    strlcat(db->dbm_pagbuf, ".pag", sizeof (db->dbm_pagbuf)) >=
174 	    sizeof (db->dbm_pagbuf)) {
175 		/*
176 		 * file.pag does not fit into dbm_pagbuf.
177 		 * fail with ENAMETOOLONG.
178 		 */
179 		serrno = ENAMETOOLONG;
180 		goto bad;
181 	}
182 	db->dbm_pagf = open64(db->dbm_pagbuf, flags, mode);
183 	if (db->dbm_pagf < 0) {
184 		serrno = errno;
185 		goto bad;
186 	}
187 	/*
188 	 * We know this won't overflow so it is safe to ignore the
189 	 * return value; we use strl* to prevent false hits in
190 	 * code sweeps.
191 	 */
192 	(void) strlcpy(db->dbm_pagbuf, file, sizeof (db->dbm_pagbuf));
193 	(void) strlcat(db->dbm_pagbuf, ".dir", sizeof (db->dbm_pagbuf));
194 	db->dbm_dirf = open64(db->dbm_pagbuf, flags, mode);
195 	if (db->dbm_dirf < 0) {
196 		serrno = errno;
197 		goto bad1;
198 	}
199 	(void) fstat64(db->dbm_dirf, &statb);
200 	db->dbm_maxbno = statb.st_size * BYTESIZ-1;
201 	db->dbm_pagbno = db->dbm_dirbno = -1;
202 	return (db);
203 bad1:
204 	(void) close(db->dbm_pagf);
205 bad:
206 	free((char *)db);
207 	errno = serrno;
208 	return ((DBM *)0);
209 }
210 
211 void
212 dbm_close(DBM *db)
213 {
214 (void) dbm_close_status(db);
215 }
216 
217 /* close with return code */
218 int
219 dbm_close_status(DBM *db)
220 {
221 	int ok;
222 	ok = 0;
223 
224 	if (dbm_flush(db) < 0)
225 		ok = -1;
226 	if (close(db->dbm_dirf) < 0)
227 		ok = -1;
228 	if (close(db->dbm_pagf) < 0)
229 		ok = -1;
230 	free((char *)db);
231 	return (ok);
232 }
233 
234 long
235 dbm_forder(DBM *db, datum key)
236 {
237 	unsigned long hash;
238 
239 	hash = dcalchash(key);
240 	for (db->dbm_hmask = 0; ; db->dbm_hmask = (db->dbm_hmask<<1)+1) {
241 		db->dbm_blkno = hash & db->dbm_hmask;
242 		db->dbm_bitno = db->dbm_blkno + db->dbm_hmask;
243 		if (getbit(db) == 0)
244 			break;
245 	}
246 	return (db->dbm_blkno);
247 }
248 
249 datum
250 dbm_fetch(DBM *db, datum key)
251 {
252 	int i;
253 	datum item;
254 
255 	if (dbm_error(db))
256 		goto err;
257 	dbm_access(db, dcalchash(key));
258 	if ((i = finddatum(db->dbm_pagbuf, key)) >= 0) {
259 		item = makdatum(db->dbm_pagbuf, i+1);
260 		if (item.dptr != NULL)
261 			return (item);
262 	}
263 err:
264 	item.dptr = NULL;
265 	item.dsize = 0;
266 	return (item);
267 }
268 
269 int
270 dbm_delete(DBM *db, datum key)
271 {
272 	int i;
273 	off64_t where;
274 
275 	if (dbm_error(db))
276 		return (-1);
277 	if (dbm_rdonly(db)) {
278 		errno = EPERM;
279 		return (-1);
280 	}
281 	dbm_access(db, dcalchash(key));
282 	if ((i = finddatum(db->dbm_pagbuf, key)) < 0)
283 		return (-1);
284 	if (!delitem(db->dbm_pagbuf, i))
285 		goto err;
286 	db->dbm_pagbno = db->dbm_blkno;
287 	if (dbm_defwrite(db)) {
288 		dbm_setdirty(db);
289 	} else {
290 		where = (((off64_t)db->dbm_blkno) * PBLKSIZ);
291 		if ((lseek64(db->dbm_pagf, where, L_SET) != where) ||
292 		    (write(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) != PBLKSIZ)) {
293 			err:
294 				db->dbm_flags |= _DBM_IOERR;
295 				return (-1);
296 		}
297 	}
298 	return (0);
299 }
300 
301 int
302 dbm_store(DBM *db, datum key, datum dat, int replace)
303 {
304 	int i;
305 	datum item, item1;
306 	char ovfbuf[PBLKSIZ];
307 	unsigned long hashdiff, key_hash, item_hash;
308 	off64_t where;
309 
310 	if (dbm_error(db))
311 		return (-1);
312 	if (dbm_rdonly(db)) {
313 		errno = EPERM;
314 		return (-1);
315 	}
316 loop:
317 	key_hash = dcalchash(key);
318 	dbm_access(db, key_hash);
319 	if ((i = finddatum(db->dbm_pagbuf, key)) >= 0) {
320 		if (!replace)
321 			return (1);
322 		if (!delitem(db->dbm_pagbuf, i)) {
323 			db->dbm_flags |= _DBM_IOERR;
324 			return (-1);
325 		}
326 	}
327 	if (!additem(db->dbm_pagbuf, key, dat))
328 		goto split;
329 	db->dbm_pagbno = db->dbm_blkno;
330 	if (dbm_defwrite(db)) {
331 		dbm_setdirty(db);
332 	} else {
333 		where = (((off64_t)db->dbm_blkno) * PBLKSIZ);
334 		if ((lseek64(db->dbm_pagf, where, L_SET) != where) ||
335 		    (write(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) != PBLKSIZ)) {
336 			db->dbm_flags |= _DBM_IOERR;
337 			return (-1);
338 		}
339 	}
340 	return (0);
341 split:
342 	hashdiff = 0;
343 	if (key.dsize + dat.dsize + 3 * (int)sizeof (short) >= PBLKSIZ) {
344 		db->dbm_flags |= _DBM_IOERR;
345 		errno = ENOSPC;
346 		return (-1);
347 	}
348 	(void) memset(ovfbuf, 0, PBLKSIZ);
349 	for (i = 0; ; ) {
350 		item = makdatum(db->dbm_pagbuf, i);
351 		if (item.dptr == NULL)
352 			break;
353 		item_hash = dcalchash(item);
354 		if (item_hash != key_hash) {
355 			hashdiff++;
356 		}
357 
358 		if (item_hash & (db->dbm_hmask+1)) {
359 			item1 = makdatum(db->dbm_pagbuf, i+1);
360 			if (item1.dptr == NULL) {
361 				/* (void) fprintf(stderr, "ndbm: */
362 				/* split not paired\n"); */
363 				db->dbm_flags |= _DBM_IOERR;
364 				break;
365 			}
366 			if (!additem(ovfbuf, item, item1) ||
367 			    !delitem(db->dbm_pagbuf, i)) {
368 				db->dbm_flags |= _DBM_IOERR;
369 				return (-1);
370 			}
371 			continue;
372 		}
373 		i += 2;
374 	}
375 	db->dbm_pagbno = db->dbm_blkno;
376 	where = (((off64_t)db->dbm_blkno) * PBLKSIZ);
377 	if ((lseek64(db->dbm_pagf, where, L_SET) != where) ||
378 	    (write(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) != PBLKSIZ)) {
379 		db->dbm_flags |= _DBM_IOERR;
380 		return (-1);
381 	}
382 	dbm_clrdirty(db); /* clear dirty */
383 	where = (((off64_t)db->dbm_blkno + db->dbm_hmask + 1) * PBLKSIZ);
384 	if ((lseek64(db->dbm_pagf, where, L_SET) != where) ||
385 	    (write(db->dbm_pagf, ovfbuf, PBLKSIZ) != PBLKSIZ)) {
386 		db->dbm_flags |= _DBM_IOERR;
387 		return (-1);
388 	}
389 	if (setbit(db) < 0) {
390 		db->dbm_flags |= _DBM_IOERR;
391 		return (-1);
392 	}
393 	if (hashdiff == 0) {
394 		db->dbm_flags |= _DBM_IOERR;
395 		return (-1);
396 	}
397 	goto loop;
398 }
399 
400 static unsigned long
401 dbm_hashinc(DBM *db, unsigned long hash)
402 {
403 	long bit;
404 
405 	hash &= db->dbm_hmask;
406 	bit = db->dbm_hmask+1;
407 	for (;;) {
408 		bit >>= 1;
409 		if (bit == 0)
410 			return (0L);
411 		if ((hash&bit) == 0)
412 			return (hash|bit);
413 		hash &= ~bit;
414 	}
415 }
416 
417 
418 
419 static datum nullkey = {NULL, 0};
420 
421 datum
422 dbm_firsthash(DBM *db, unsigned long hash)
423 {
424 	int i, j;
425 	datum item, bitem;
426 
427 loop:
428 	dbm_access(db, hash);
429 	j = 0;
430 	bitem = makdatum(db->dbm_pagbuf, 0);
431 	for (i = 2; ; i += 2) {
432 		item = makdatum(db->dbm_pagbuf, i);
433 		if (item.dptr == NULL)
434 			break;
435 		if (cmpdatum(bitem, item) < 0) {
436 			j = i;
437 			bitem = item;
438 		}
439 	}
440 	if (bitem.dptr != NULL) {
441 		db->dbm_keyptr = j + 2;
442 		db->dbm_blkptr = db->dbm_blkno;
443 		return (bitem);
444 	}
445 	hash = dbm_hashinc(db, hash);
446 	if (hash == 0)
447 		return (item); /* null item */
448 	goto loop;
449 
450 }
451 
452 datum
453 dbm_firstkey(DBM *db)
454 {
455 	/*
456 	 * For some reason, the Posix specification (SUSv3)
457 	 * says that dbm_firstkey() is not a cancellation point.
458 	 * It really should be, but in order to pass the SUSv3
459 	 * test suite we make it not a cancellation point.
460 	 * XXX: fix me when the SUSv3 specification gets fixed.
461 	 */
462 	int cancel_state;
463 	datum rval;
464 
465 	db->dbm_blkptr = 0L;
466 	db->dbm_keyptr = 0;
467 	(void) pthread_setcancelstate(PTHREAD_CANCEL_DISABLE, &cancel_state);
468 	rval = dbm_firsthash(db, 0L);
469 	(void) pthread_setcancelstate(cancel_state, NULL);
470 	return (rval);
471 }
472 
473 datum
474 dbm_nextkey(DBM *db)
475 {
476 
477 	return (dbm_do_nextkey(db, nullkey));
478 }
479 
480 /*
481  * this is used if keyptr-2, blocknum doesn't point to the previous
482  * specific key allowing the fast hash order search --
483  * its use indicates user tampering with our state variables,
484  * which some evil users might do to search from some specific place.
485  * It finds the first key at or after blkptr, keyptr in block seq order
486  * this requires looking at all sorts of emtpy blocks in many cases
487  */
488 
489 static
490 datum
491 dbm_slow_nextkey(DBM *db)
492 {
493 
494 	struct stat64 statb;
495 	datum item;
496 	off64_t where;
497 
498 	if (dbm_error(db) || fstat64(db->dbm_pagf, &statb) < 0)
499 		goto err;
500 	statb.st_size /= PBLKSIZ;
501 
502 	for (;;) {
503 		if (db->dbm_blkptr != db->dbm_pagbno) {
504 
505 			if (dbm_dirty(db)) (void) dbm_flushpag(db);
506 
507 			db->dbm_pagbno = db->dbm_blkptr;
508 			where = (((off64_t)db->dbm_blkptr) * PBLKSIZ);
509 			if ((lseek64(db->dbm_pagf, where, L_SET) != where) ||
510 			    (read(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) !=
511 			    PBLKSIZ))
512 				(void) memset(db->dbm_pagbuf, 0, PBLKSIZ);
513 #ifdef DEBUG
514 			else if (chkblk(db->dbm_pagbuf) < 0)
515 				db->dbm_flags |= _DBM_IOERR;
516 #endif
517 		}
518 		/* Am I an empty block? */
519 		if (((short *)(uintptr_t)db->dbm_pagbuf)[0] != 0) {
520 			item = makdatum(db->dbm_pagbuf, db->dbm_keyptr);
521 			if (item.dptr != NULL) {
522 				db->dbm_keyptr += 2;
523 				return (item);
524 			}
525 			db->dbm_keyptr = 0;
526 		}
527 		/* go to next sequential block */
528 		if (++db->dbm_blkptr >= statb.st_size)
529 			break;
530 	}
531 err:
532 	item.dptr = NULL;
533 	item.dsize = 0;
534 	return (item);
535 }
536 
537 
538 
539 datum
540 dbm_do_nextkey(DBM *db, datum inkey)
541 {
542 	datum item, bitem;
543 	unsigned long hash;
544 	datum key;
545 	int f;
546 	int i;
547 	int j;
548 	short *sp;
549 	long n;
550 	char *p1, *p2;
551 	off64_t where;
552 
553 	if (dbm_error(db)) {
554 		item.dptr = NULL;
555 		item.dsize = 0;
556 		return (item);
557 	}
558 
559 	/* user has supplied lastkey */
560 
561 	if (inkey.dptr != NULL) {
562 		dbm_access(db, (hash = dcalchash(inkey)));
563 		if ((i = finddatum(db->dbm_pagbuf, inkey)) >= 0) {
564 			db->dbm_keyptr = i + 2;
565 			db->dbm_blkptr = db->dbm_blkno;
566 		}
567 		key = inkey;
568 	} else  {
569 		/* is this a manual firstkey request? */
570 
571 		if (db->dbm_blkptr == 0L &&
572 		    db->dbm_keyptr == 0)
573 			return (dbm_firsthash(db, 0L));
574 
575 		/* no -- get lastkey this is like dbm_access by blkptr */
576 
577 		if (db->dbm_blkptr != db->dbm_pagbno) {
578 
579 			if (dbm_dirty(db)) (void) dbm_flushpag(db);
580 			db->dbm_pagbno = db->dbm_blkptr;
581 			where = (((off64_t)db->dbm_blkptr) * PBLKSIZ);
582 			if ((lseek64(db->dbm_pagf, where, L_SET) != where) ||
583 			    (read(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) !=
584 			    PBLKSIZ))
585 				(void) memset(db->dbm_pagbuf, 0, PBLKSIZ);
586 #ifdef DEBUG
587 			else if (chkblk(db->dbm_pagbuf) < 0)
588 			db->dbm_flags |= _DBM_IOERR;
589 #endif
590 		}
591 		/* now just make up last key datum */
592 		if (db->dbm_keyptr >= 2)
593 			key = makdatum(db->dbm_pagbuf, (db->dbm_keyptr-2));
594 		else key = nullkey;
595 
596 		/*
597 		 * the keyptr pagbuf have failed us, the user must
598 		 * be an extra clever moron who depends on
599 		 * these variables and their former meaning.
600 		 * If we set the variables this would have got
601 		 * us the key for sure! So give it the old algorithm.
602 		 */
603 		if (key.dptr == NULL)
604 			return (dbm_slow_nextkey(db));
605 	}
606 
607 	/*
608 	 * at this point the last key is paged in and
609 	 * we can proceed as in old dbm -- like Ken did his.
610 	 */
611 
612 	f = 1;
613 	j = 0;
614 	sp = (short *)(uintptr_t)db->dbm_pagbuf;
615 
616 	for (i = 0; ; i += 2) {
617 
618 		/* begin put makdatum inline */
619 
620 		if ((unsigned)i >= sp[0]) {
621 			item.dptr = NULL;
622 			item.dsize = 0;
623 			break; /* from below */
624 		} else {
625 			if (i > 0) item.dsize = sp[i] - sp[i + 1];
626 			else item.dsize = PBLKSIZ - sp[i + 1];
627 			item.dptr = db->dbm_pagbuf+sp[i + 1];
628 		}
629 
630 		/* item = makdatum(db->dbm_pagbuf, i); */
631 		/* end put makdatum inline */
632 
633 		if (item.dptr == NULL)
634 			break;
635 /* inline cmpdatum */
636 
637 
638 		n = key.dsize;
639 		if (n != item.dsize) {
640 			if ((n - item.dsize) <= 0)
641 				continue;
642 		} else {
643 			if (n == 0) continue;
644 			p1 = key.dptr;
645 			p2 = item.dptr;
646 			do {
647 				if (*p1++ != *p2++)
648 					if ((*--p1 - *--p2) > 0)
649 						goto keep_going;
650 					else continue;
651 			} while (--n);
652 			continue;
653 		}
654 
655 keep_going:
656 
657 /* end inline cmpdatum */
658 		/*
659 		 * if (cmpdatum(key, item) <= 0)
660 		 *	continue;
661 		 */
662 
663 		if (f) {
664 			bitem = item;
665 			j = i;
666 			f = 0;
667 		} else {
668 
669 			/* if (cmpdatum(bitem, item) < 0) */
670 
671 			n = bitem.dsize;
672 			if (n != item.dsize) {
673 				if ((n - item.dsize) < 0) {
674 					bitem = item;
675 					j = i;
676 				}
677 			} else
678 				if (n != 0) {
679 					p1 = bitem.dptr;
680 					p2 = item.dptr;
681 					do {
682 					if (*p1++ != *p2++) {
683 						if ((*--p1 - *--p2) < 0) {
684 							bitem = item;
685 							j = i;
686 						}
687 						break;
688 					}
689 					} while (--n);
690 				}
691 			}
692 	}
693 
694 	if (f == 0) {
695 		db->dbm_keyptr = j + 2;
696 		db->dbm_blkptr = db->dbm_blkno;
697 		return (bitem);
698 	}
699 
700 	/* really need hash at this point */
701 	/* if it gave us a key we have already calculated the hash */
702 	/* if not get the hash */
703 	if (inkey.dptr == NULL)
704 		hash = dcalchash(key);
705 	hash = dbm_hashinc(db, hash);
706 
707 	if (hash == 0)
708 		return (item); /* null */
709 	/* get first item on next page in hash table order */
710 	return (dbm_firsthash(db, hash));
711 
712 
713 }
714 
715 static void
716 dbm_access(DBM *db, unsigned long hash)
717 {
718 	long b, i, n;
719 	long bn;
720 	long my_bitno;
721 	long my_hmask;
722 	long my_blkno;
723 	int j = (sizeof (my_hmask)) * 8;
724 	off64_t where;
725 
726 	for (my_hmask = 0; j-- > 0; my_hmask = (my_hmask<<1) + 1) {
727 		my_blkno = hash & my_hmask;
728 		my_bitno = my_blkno + my_hmask;
729 		/* getbit inline */
730 		if (my_bitno > db->dbm_maxbno) break;
731 		n = my_bitno % BYTESIZ;
732 		bn = my_bitno / BYTESIZ;
733 		i = bn % DBLKSIZ;
734 		b = bn / DBLKSIZ;
735 		if (b != db->dbm_dirbno) {
736 			if (dbm_dirdirty(db))
737 				(void) dbm_flushdir(db); /* must flush */
738 			db->dbm_dirbno = b;
739 			where = (((off64_t)b) * DBLKSIZ);
740 			if ((lseek64(db->dbm_dirf, where, L_SET) != where) ||
741 			    (read(db->dbm_dirf, db->dbm_dirbuf, DBLKSIZ) !=
742 			    DBLKSIZ))
743 				(void) memset(db->dbm_dirbuf, 0, DBLKSIZ);
744 		}
745 		if ((db->dbm_dirbuf[i] & (1<<n)) == 0) break;
746 
747 		/*
748 		 * if (getbit(db) == 0)
749 		 *	break;
750 		 */
751 	}
752 	/* copy */
753 	db->dbm_blkno = my_blkno;
754 	db->dbm_bitno = my_bitno;
755 	db->dbm_hmask = my_hmask;
756 
757 	if (my_blkno != db->dbm_pagbno) {
758 		if (dbm_dirty(db)) { /* must page out the page */
759 			where = (((off64_t)db->dbm_pagbno) * PBLKSIZ);
760 			if ((lseek64(db->dbm_pagf, where, L_SET) != where) ||
761 			    (write(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) !=
762 			    PBLKSIZ)) {
763 				db->dbm_flags |= _DBM_IOERR;
764 			}
765 		dbm_clrdirty(db);
766 		}
767 
768 		db->dbm_pagbno = my_blkno;
769 		where = (((off64_t)my_blkno) * PBLKSIZ);
770 		if ((lseek64(db->dbm_pagf, where, L_SET) != where) ||
771 		    (read(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) != PBLKSIZ))
772 			(void) memset(db->dbm_pagbuf, 0, PBLKSIZ);
773 #ifdef DEBUG
774 		else if (chkblk(db->dbm_pagbuf) < 0)
775 			db->dbm_flags |= _DBM_IOERR;
776 #endif
777 	}
778 }
779 
780 static int
781 getbit(DBM *db)
782 {
783 	long bn;
784 	long b, i, n;
785 	off64_t where;
786 
787 	if (db->dbm_bitno > db->dbm_maxbno)
788 		return (0);
789 	n = db->dbm_bitno % BYTESIZ;
790 	bn = db->dbm_bitno / BYTESIZ;
791 	i = bn % DBLKSIZ;
792 	b = bn / DBLKSIZ;
793 	if (b != db->dbm_dirbno) {
794 		if (dbm_dirdirty(db))
795 			(void) dbm_flushdir(db); /* must flush */
796 		db->dbm_dirbno = b;
797 		where = (((off64_t)b) * DBLKSIZ);
798 		if ((lseek64(db->dbm_dirf, where, L_SET) != where) ||
799 		    (read(db->dbm_dirf, db->dbm_dirbuf, DBLKSIZ) != DBLKSIZ))
800 			(void) memset(db->dbm_dirbuf, 0, DBLKSIZ);
801 	}
802 	return (db->dbm_dirbuf[i] & (1<<n));
803 }
804 
805 static int
806 setbit(DBM *db)
807 {
808 	long bn;
809 	long i, n, b;
810 	off64_t where;
811 
812 	if (db->dbm_bitno > db->dbm_maxbno)
813 		db->dbm_maxbno = db->dbm_bitno;
814 	n = db->dbm_bitno % BYTESIZ;
815 	bn = db->dbm_bitno / BYTESIZ;
816 	i = bn % DBLKSIZ;
817 	b = bn / DBLKSIZ;
818 	if (b != db->dbm_dirbno) {
819 		if (dbm_dirdirty(db))
820 			(void) dbm_flushdir(db);
821 		db->dbm_dirbno = b;
822 		where = (((off64_t)b) * DBLKSIZ);
823 		if ((lseek64(db->dbm_dirf, where, L_SET) != where) ||
824 		    (read(db->dbm_dirf, db->dbm_dirbuf, DBLKSIZ) != DBLKSIZ))
825 			(void) memset(db->dbm_dirbuf, 0, DBLKSIZ);
826 	}
827 	db->dbm_dirbuf[i] |= 1<<n;
828 	db->dbm_dirbno = b;
829 	if (dbm_defwrite(db)) {
830 		dbm_setdirdirty(db);
831 	} else {
832 		where = (((off64_t)b) * DBLKSIZ);
833 		if ((lseek64(db->dbm_dirf, where, L_SET) != where) ||
834 		    (write(db->dbm_dirf, db->dbm_dirbuf, DBLKSIZ) != DBLKSIZ)) {
835 			return (-1);
836 		}
837 	}
838 	return (0);
839 }
840 
841 static datum
842 makdatum(char *buf, int n)
843 {
844 	short *sp;
845 	int t;
846 	datum item;
847 
848 	sp = (short *)(uintptr_t)buf;
849 	if ((unsigned)n >= sp[0]) {
850 		item.dptr = NULL;
851 		item.dsize = 0;
852 		return (item);
853 	}
854 	t = PBLKSIZ;
855 	if (n > 0)
856 		t = sp[n];
857 	item.dptr = buf + sp[n + 1];
858 	item.dsize = t - sp[n + 1];
859 	return (item);
860 }
861 
862 static int
863 cmpdatum(datum d1, datum d2)
864 {
865 	long n;
866 	char *p1, *p2;
867 
868 	n = d1.dsize;
869 	if (n != d2.dsize)
870 		return ((int)(n - d2.dsize));
871 	if (n == 0)
872 		return (0);
873 	p1 = d1.dptr;
874 	p2 = d2.dptr;
875 	do {
876 		if (*p1 != *p2)
877 			return (*p1 - *p2);
878 		else {
879 			p1++;
880 			p2++;
881 		}
882 	} while (--n);
883 	return (0);
884 }
885 
886 static int
887 finddatum(char *buf, datum item)
888 {
889 	short *sp;
890 	int i, n, j;
891 
892 	sp = (short *)(uintptr_t)buf;
893 	n = PBLKSIZ;
894 	for (i = 0, j = sp[0]; i < j; i += 2, n = sp[i]) {
895 		n -= sp[i + 1];
896 		if (n != item.dsize)
897 			continue;
898 		if (n == 0 || memcmp(&buf[sp[i+1]], item.dptr, n) == 0)
899 			return (i);
900 	}
901 	return (-1);
902 }
903 
904 static const int hitab[16]
905 /*
906  * ken's
907  * {
908  *	055, 043, 036, 054, 063, 014, 004, 005,
909  *	010, 064, 077, 000, 035, 027, 025, 071,
910  * };
911  */
912 	= {    61, 57, 53, 49, 45, 41, 37, 33,
913 		29, 25, 21, 17, 13,  9,  5,  1,
914 };
915 
916 /* could consider to make it 32-bit int table to minimize memory usage */
917 static const long hltab[64]
918 	= {
919 	06100151277L, 06106161736L, 06452611562L, 05001724107L,
920 	02614772546L, 04120731531L, 04665262210L, 07347467531L,
921 	06735253126L, 06042345173L, 03072226605L, 01464164730L,
922 	03247435524L, 07652510057L, 01546775256L, 05714532133L,
923 	06173260402L, 07517101630L, 02431460343L, 01743245566L,
924 	00261675137L, 02433103631L, 03421772437L, 04447707466L,
925 	04435620103L, 03757017115L, 03641531772L, 06767633246L,
926 	02673230344L, 00260612216L, 04133454451L, 00615531516L,
927 	06137717526L, 02574116560L, 02304023373L, 07061702261L,
928 	05153031405L, 05322056705L, 07401116734L, 06552375715L,
929 	06165233473L, 05311063631L, 01212221723L, 01052267235L,
930 	06000615237L, 01075222665L, 06330216006L, 04402355630L,
931 	01451177262L, 02000133436L, 06025467062L, 07121076461L,
932 	03123433522L, 01010635225L, 01716177066L, 05161746527L,
933 	01736635071L, 06243505026L, 03637211610L, 01756474365L,
934 	04723077174L, 03642763134L, 05750130273L, 03655541561L,
935 };
936 
937 static unsigned long
938 dcalchash(datum item)
939 {
940 	long s;
941 	int c, j;
942 	char *cp;
943 	unsigned long hashl;
944 	long hashi;
945 
946 	hashl = 0;
947 	hashi = 0;
948 	for (cp = item.dptr, s = item.dsize; --s >= 0; ) {
949 		c = *cp++;
950 		for (j = 0; j < BYTESIZ; j += 4) {
951 			hashi += hitab[c&017];
952 			hashl += hltab[hashi&63];
953 			c >>= 4;
954 		}
955 	}
956 	return (hashl);
957 }
958 
959 /*
960  * Delete pairs of items (n & n+1).
961  */
962 static int
963 delitem(char *buf, int n)
964 {
965 	short *sp, *sp1;
966 	int i1, i2;
967 
968 	sp = (short *)(uintptr_t)buf;
969 	i2 = sp[0];
970 	if ((unsigned)n >= i2 || (n & 1))
971 		return (0);
972 	if (n == i2-2) {
973 		sp[0] -= 2;
974 		return (1);
975 	}
976 	i1 = PBLKSIZ;
977 	if (n > 0)
978 		i1 = sp[n];
979 	i1 -= sp[n+2];
980 	if (i1 > 0) {
981 		i2 = sp[i2];
982 		(void) memmove(&buf[i2 + i1], &buf[i2], sp[n+2] - i2);
983 	}
984 	sp[0] -= 2;
985 	for (sp1 = sp + sp[0], sp += n+1; sp <= sp1; sp++)
986 		sp[0] = sp[2] + i1;
987 	return (1);
988 }
989 
990 /*
991  * Add pairs of items (item & item1).
992  */
993 static int
994 additem(char *buf, datum item, datum item1)
995 {
996 	short *sp;
997 	int i1, i2;
998 
999 	sp = (short *)(uintptr_t)buf;
1000 	i1 = PBLKSIZ;
1001 	i2 = sp[0];
1002 	if (i2 > 0)
1003 		i1 = sp[i2];
1004 	i1 -= item.dsize + item1.dsize;
1005 	if (i1 <= (i2+3) * (int)sizeof (short))
1006 		return (0);
1007 	sp[0] += 2;
1008 	sp[++i2] = (short)(i1 + item1.dsize);
1009 	(void) memmove(&buf[i1 + item1.dsize], item.dptr, item.dsize);
1010 	sp[++i2] = i1;
1011 	(void) memmove(&buf[i1], item1.dptr, item1.dsize);
1012 	return (1);
1013 }
1014 
1015 #ifdef DEBUG
1016 static int
1017 chkblk(char buf[PBLKSIZ])
1018 {
1019 	short *sp;
1020 	int t, i;
1021 
1022 	sp = (short *)buf;
1023 	t = PBLKSIZ;
1024 	for (i = 0; i < sp[0]; i++) {
1025 		if (sp[i + 1] > t)
1026 			return (-1);
1027 		t = sp[i + 1];
1028 	}
1029 	if (t < (sp[0] + 1) * sizeof (short))
1030 		return (-1);
1031 	return (0);
1032 }
1033 #endif
1034