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