xref: /titanic_44/usr/src/lib/libc/port/gen/ndbm.c (revision 8eea8e29cc4374d1ee24c25a07f45af132db3499) 
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, Version 1.0 only
6  * (the "License").  You may not use this file except in compliance
7  * with the License.
8  *
9  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
10  * or http://www.opensolaris.org/os/licensing.
11  * See the License for the specific language governing permissions
12  * and limitations under the License.
13  *
14  * When distributing Covered Code, include this CDDL HEADER in each
15  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
16  * If applicable, add the following below this CDDL HEADER, with the
17  * fields enclosed by brackets "[]" replaced with your own identifying
18  * information: Portions Copyright [yyyy] [name of copyright owner]
19  *
20  * CDDL HEADER END
21  */
22 /*
23  * Copyright 2004 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 "synonyms.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 
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 	db->dbm_blkptr = 0L;
457 	db->dbm_keyptr = 0;
458 	return (dbm_firsthash(db, 0L));
459 }
460 
461 datum
462 dbm_nextkey(DBM *db)
463 {
464 
465 	return (dbm_do_nextkey(db, nullkey));
466 }
467 
468 /*
469  * this is used if keyptr-2, blocknum doesn't point to the previous
470  * specific key allowing the fast hash order search --
471  * its use indicates user tampering with our state variables,
472  * which some evil users might do to search from some specific place.
473  * It finds the first key at or after blkptr, keyptr in block seq order
474  * this requires looking at all sorts of emtpy blocks in many cases
475  */
476 
477 static
478 datum
479 dbm_slow_nextkey(DBM *db)
480 {
481 
482 	struct stat64 statb;
483 	datum item;
484 	off64_t where;
485 
486 	if (dbm_error(db) || fstat64(db->dbm_pagf, &statb) < 0)
487 		goto err;
488 	statb.st_size /= PBLKSIZ;
489 
490 	for (;;) {
491 		if (db->dbm_blkptr != db->dbm_pagbno) {
492 
493 			if (dbm_dirty(db)) (void) dbm_flushpag(db);
494 
495 			db->dbm_pagbno = db->dbm_blkptr;
496 			where = (((off64_t)db->dbm_blkptr) * PBLKSIZ);
497 			if ((lseek64(db->dbm_pagf, where, L_SET) != where) ||
498 			    (read(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) !=
499 				PBLKSIZ))
500 				(void) memset(db->dbm_pagbuf, 0, PBLKSIZ);
501 #ifdef DEBUG
502 			else if (chkblk(db->dbm_pagbuf) < 0)
503 				db->dbm_flags |= _DBM_IOERR;
504 #endif
505 		}
506 		/* Am I an empty block? */
507 		if (((short *)(uintptr_t)db->dbm_pagbuf)[0] != 0) {
508 			item = makdatum(db->dbm_pagbuf, db->dbm_keyptr);
509 			if (item.dptr != NULL) {
510 				db->dbm_keyptr += 2;
511 				return (item);
512 			}
513 			db->dbm_keyptr = 0;
514 		}
515 		/* go to next sequential block */
516 		if (++db->dbm_blkptr >= statb.st_size)
517 			break;
518 	}
519 err:
520 	item.dptr = NULL;
521 	item.dsize = 0;
522 	return (item);
523 }
524 
525 
526 
527 datum
528 dbm_do_nextkey(DBM *db, datum inkey)
529 {
530 	datum item, bitem;
531 	unsigned long hash;
532 	datum key;
533 	int f;
534 	int i;
535 	int j;
536 	short *sp;
537 	long n;
538 	char *p1, *p2;
539 	off64_t where;
540 
541 	if (dbm_error(db)) {
542 		item.dptr = NULL;
543 		item.dsize = 0;
544 		return (item);
545 	}
546 
547 	/* user has supplied lastkey */
548 
549 	if (inkey.dptr != NULL) {
550 		dbm_access(db, (hash = dcalchash(inkey)));
551 		if ((i = finddatum(db->dbm_pagbuf, inkey)) >= 0) {
552 			db->dbm_keyptr = i + 2;
553 			db->dbm_blkptr = db->dbm_blkno;
554 		}
555 		key = inkey;
556 	} else  {
557 		/* is this a manual firstkey request? */
558 
559 		if (db->dbm_blkptr == 0L &&
560 			db->dbm_keyptr == 0)
561 			return (dbm_firsthash(db, 0L));
562 
563 		/* no -- get lastkey this is like dbm_access by blkptr */
564 
565 		if (db->dbm_blkptr != db->dbm_pagbno) {
566 
567 			if (dbm_dirty(db)) (void) dbm_flushpag(db);
568 			db->dbm_pagbno = db->dbm_blkptr;
569 			where = (((off64_t)db->dbm_blkptr) * PBLKSIZ);
570 			if ((lseek64(db->dbm_pagf, where, L_SET) != where) ||
571 			    (read(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) !=
572 				PBLKSIZ))
573 				(void) memset(db->dbm_pagbuf, 0, PBLKSIZ);
574 #ifdef DEBUG
575 			else if (chkblk(db->dbm_pagbuf) < 0)
576 			db->dbm_flags |= _DBM_IOERR;
577 #endif
578 		}
579 		/* now just make up last key datum */
580 		if (db->dbm_keyptr >= 2)
581 			key = makdatum(db->dbm_pagbuf, (db->dbm_keyptr-2));
582 		else key = nullkey;
583 
584 		/*
585 		 * the keyptr pagbuf have failed us, the user must
586 		 * be an extra clever moron who depends on
587 		 * these variables and their former meaning.
588 		 * If we set the variables this would have got
589 		 * us the key for sure! So give him the old algorithm.
590 		 */
591 		if (key.dptr == NULL)
592 			return (dbm_slow_nextkey(db));
593 	}
594 
595 	/*
596 	 * at this point the last key is paged in and
597 	 * we can proceed as in old dbm -- like Ken did his.
598 	 */
599 
600 	f = 1;
601 	j = 0;
602 	sp = (short *)(uintptr_t)db->dbm_pagbuf;
603 
604 	for (i = 0; ; i += 2) {
605 
606 		/* begin put makdatum inline */
607 
608 		if ((unsigned)i >= sp[0]) {
609 			item.dptr = NULL;
610 			item.dsize = 0;
611 			break; /* from below */
612 		} else {
613 			if (i > 0) item.dsize = sp[i] - sp[i + 1];
614 			else item.dsize = PBLKSIZ - sp[i + 1];
615 			item.dptr = db->dbm_pagbuf+sp[i + 1];
616 		}
617 
618 		/* item = makdatum(db->dbm_pagbuf, i); */
619 		/* end put makdatum inline */
620 
621 		if (item.dptr == NULL)
622 			break;
623 /* inline cmpdatum */
624 
625 
626 		n = key.dsize;
627 		if (n != item.dsize) {
628 			if ((n - item.dsize) <= 0)
629 				continue;
630 		} else {
631 			if (n == 0) continue;
632 			p1 = key.dptr;
633 			p2 = item.dptr;
634 			do {
635 				if (*p1++ != *p2++)
636 					if ((*--p1 - *--p2) > 0)
637 						goto keep_going;
638 					else continue;
639 			} while (--n);
640 			continue;
641 		}
642 
643 keep_going:
644 
645 /* end inline cmpdatum */
646 		/*
647 		 * if (cmpdatum(key, item) <= 0)
648 		 *	continue;
649 		 */
650 
651 		if (f) {
652 			bitem = item;
653 			j = i;
654 			f = 0;
655 		} else {
656 
657 			/* if (cmpdatum(bitem, item) < 0) */
658 
659 			n = bitem.dsize;
660 			if (n != item.dsize) {
661 				if ((n - item.dsize) < 0) {
662 					bitem = item;
663 					j = i;
664 				}
665 			} else
666 				if (n != 0) {
667 					p1 = bitem.dptr;
668 					p2 = item.dptr;
669 					do {
670 					if (*p1++ != *p2++) {
671 						if ((*--p1 - *--p2) < 0) {
672 							bitem = item;
673 							j = i;
674 						}
675 						break;
676 					}
677 					} while (--n);
678 				}
679 			}
680 	}
681 
682 	if (f == 0) {
683 		db->dbm_keyptr = j + 2;
684 		db->dbm_blkptr = db->dbm_blkno;
685 		return (bitem);
686 	}
687 
688 	/* really need hash at this point */
689 	/* if he gave us a key we have already calculated the hash */
690 	/* if not get it */
691 	if (inkey.dptr == NULL)
692 		hash = dcalchash(key);
693 	hash = dbm_hashinc(db, hash);
694 
695 	if (hash == 0)
696 		return (item); /* null */
697 	/* get first item on next page in hash table order */
698 	return (dbm_firsthash(db, hash));
699 
700 
701 }
702 
703 static void
704 dbm_access(DBM *db, unsigned long hash)
705 {
706 	long b, i, n;
707 	long bn;
708 	long my_bitno;
709 	long my_hmask;
710 	long my_blkno;
711 	int j = (sizeof (my_hmask)) * 8;
712 	off64_t where;
713 
714 	for (my_hmask = 0; j-- > 0; my_hmask = (my_hmask<<1) + 1) {
715 		my_blkno = hash & my_hmask;
716 		my_bitno = my_blkno + my_hmask;
717 		/* getbit inline */
718 		if (my_bitno > db->dbm_maxbno) break;
719 		n = my_bitno % BYTESIZ;
720 		bn = my_bitno / BYTESIZ;
721 		i = bn % DBLKSIZ;
722 		b = bn / DBLKSIZ;
723 		if (b != db->dbm_dirbno) {
724 			if (dbm_dirdirty(db))
725 				(void) dbm_flushdir(db); /* must flush */
726 			db->dbm_dirbno = b;
727 			where = (((off64_t)b) * DBLKSIZ);
728 			if ((lseek64(db->dbm_dirf, where, L_SET) != where) ||
729 			    (read(db->dbm_dirf, db->dbm_dirbuf, DBLKSIZ) !=
730 				DBLKSIZ))
731 				(void) memset(db->dbm_dirbuf, 0, DBLKSIZ);
732 		}
733 		if ((db->dbm_dirbuf[i] & (1<<n)) == 0) break;
734 
735 		/*
736 		 * if (getbit(db) == 0)
737 		 *	break;
738 		 */
739 	}
740 	/* copy */
741 	db->dbm_blkno = my_blkno;
742 	db->dbm_bitno = my_bitno;
743 	db->dbm_hmask = my_hmask;
744 
745 	if (my_blkno != db->dbm_pagbno) {
746 		if (dbm_dirty(db)) { /* must page out the page */
747 			where = (((off64_t)db->dbm_pagbno) * PBLKSIZ);
748 			if ((lseek64(db->dbm_pagf, where, L_SET) != where) ||
749 			    (write(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) !=
750 				PBLKSIZ)) {
751 				db->dbm_flags |= _DBM_IOERR;
752 			}
753 		dbm_clrdirty(db);
754 		}
755 
756 		db->dbm_pagbno = my_blkno;
757 		where = (((off64_t)my_blkno) * PBLKSIZ);
758 		if ((lseek64(db->dbm_pagf, where, L_SET) != where) ||
759 		    (read(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) != PBLKSIZ))
760 			(void) memset(db->dbm_pagbuf, 0, PBLKSIZ);
761 #ifdef DEBUG
762 		else if (chkblk(db->dbm_pagbuf) < 0)
763 			db->dbm_flags |= _DBM_IOERR;
764 #endif
765 	}
766 }
767 
768 static int
769 getbit(DBM *db)
770 {
771 	long bn;
772 	long b, i, n;
773 	off64_t where;
774 
775 	if (db->dbm_bitno > db->dbm_maxbno)
776 		return (0);
777 	n = db->dbm_bitno % BYTESIZ;
778 	bn = db->dbm_bitno / BYTESIZ;
779 	i = bn % DBLKSIZ;
780 	b = bn / DBLKSIZ;
781 	if (b != db->dbm_dirbno) {
782 		if (dbm_dirdirty(db))
783 			(void) dbm_flushdir(db); /* must flush */
784 		db->dbm_dirbno = b;
785 		where = (((off64_t)b) * DBLKSIZ);
786 		if ((lseek64(db->dbm_dirf, where, L_SET) != where) ||
787 		    (read(db->dbm_dirf, db->dbm_dirbuf, DBLKSIZ) != DBLKSIZ))
788 			(void) memset(db->dbm_dirbuf, 0, DBLKSIZ);
789 	}
790 	return (db->dbm_dirbuf[i] & (1<<n));
791 }
792 
793 static int
794 setbit(DBM *db)
795 {
796 	long bn;
797 	long i, n, b;
798 	off64_t where;
799 
800 	if (db->dbm_bitno > db->dbm_maxbno)
801 		db->dbm_maxbno = db->dbm_bitno;
802 	n = db->dbm_bitno % BYTESIZ;
803 	bn = db->dbm_bitno / BYTESIZ;
804 	i = bn % DBLKSIZ;
805 	b = bn / DBLKSIZ;
806 	if (b != db->dbm_dirbno) {
807 		if (dbm_dirdirty(db))
808 			(void) dbm_flushdir(db);
809 		db->dbm_dirbno = b;
810 		where = (((off64_t)b) * DBLKSIZ);
811 		if ((lseek64(db->dbm_dirf, where, L_SET) != where) ||
812 		    (read(db->dbm_dirf, db->dbm_dirbuf, DBLKSIZ) != DBLKSIZ))
813 			(void) memset(db->dbm_dirbuf, 0, DBLKSIZ);
814 	}
815 	db->dbm_dirbuf[i] |= 1<<n;
816 	db->dbm_dirbno = b;
817 	if (dbm_defwrite(db)) {
818 		dbm_setdirdirty(db);
819 	} else {
820 		where = (((off64_t)b) * DBLKSIZ);
821 		if ((lseek64(db->dbm_dirf, where, L_SET) != where) ||
822 		    (write(db->dbm_dirf, db->dbm_dirbuf, DBLKSIZ) != DBLKSIZ)) {
823 			return (-1);
824 		}
825 	}
826 	return (0);
827 }
828 
829 static datum
830 makdatum(char buf[PBLKSIZ], int n)
831 {
832 	short *sp;
833 	int t;
834 	datum item;
835 
836 	sp = (short *)(uintptr_t)buf;
837 	if ((unsigned)n >= sp[0]) {
838 		item.dptr = NULL;
839 		item.dsize = 0;
840 		return (item);
841 	}
842 	t = PBLKSIZ;
843 	if (n > 0)
844 		t = sp[n];
845 	item.dptr = buf + sp[n + 1];
846 	item.dsize = t - sp[n + 1];
847 	return (item);
848 }
849 
850 static int
851 cmpdatum(datum d1, datum d2)
852 {
853 	long n;
854 	char *p1, *p2;
855 
856 	n = d1.dsize;
857 	if (n != d2.dsize)
858 		return ((int)(n - d2.dsize));
859 	if (n == 0)
860 		return (0);
861 	p1 = d1.dptr;
862 	p2 = d2.dptr;
863 	do {
864 		if (*p1 != *p2)
865 			return (*p1 - *p2);
866 		else {
867 			p1++;
868 			p2++;
869 		}
870 	} while (--n);
871 	return (0);
872 }
873 
874 static int
875 finddatum(char buf[PBLKSIZ], datum item)
876 {
877 	short *sp;
878 	int i, n, j;
879 
880 	sp = (short *)(uintptr_t)buf;
881 	n = PBLKSIZ;
882 	for (i = 0, j = sp[0]; i < j; i += 2, n = sp[i]) {
883 		n -= sp[i + 1];
884 		if (n != item.dsize)
885 			continue;
886 		if (n == 0 || memcmp(&buf[sp[i+1]], item.dptr, n) == 0)
887 			return (i);
888 	}
889 	return (-1);
890 }
891 
892 static const int hitab[16]
893 /*
894  * ken's
895  * {
896  *	055, 043, 036, 054, 063, 014, 004, 005,
897  *	010, 064, 077, 000, 035, 027, 025, 071,
898  * };
899  */
900 	= {    61, 57, 53, 49, 45, 41, 37, 33,
901 		29, 25, 21, 17, 13,  9,  5,  1,
902 };
903 
904 /* could consider to make it 32-bit int table to minimize memory usage */
905 static const long hltab[64]
906 	= {
907 	06100151277L, 06106161736L, 06452611562L, 05001724107L,
908 	02614772546L, 04120731531L, 04665262210L, 07347467531L,
909 	06735253126L, 06042345173L, 03072226605L, 01464164730L,
910 	03247435524L, 07652510057L, 01546775256L, 05714532133L,
911 	06173260402L, 07517101630L, 02431460343L, 01743245566L,
912 	00261675137L, 02433103631L, 03421772437L, 04447707466L,
913 	04435620103L, 03757017115L, 03641531772L, 06767633246L,
914 	02673230344L, 00260612216L, 04133454451L, 00615531516L,
915 	06137717526L, 02574116560L, 02304023373L, 07061702261L,
916 	05153031405L, 05322056705L, 07401116734L, 06552375715L,
917 	06165233473L, 05311063631L, 01212221723L, 01052267235L,
918 	06000615237L, 01075222665L, 06330216006L, 04402355630L,
919 	01451177262L, 02000133436L, 06025467062L, 07121076461L,
920 	03123433522L, 01010635225L, 01716177066L, 05161746527L,
921 	01736635071L, 06243505026L, 03637211610L, 01756474365L,
922 	04723077174L, 03642763134L, 05750130273L, 03655541561L,
923 };
924 
925 static unsigned long
926 dcalchash(datum item)
927 {
928 	long s;
929 	int c, j;
930 	char *cp;
931 	unsigned long hashl;
932 	long hashi;
933 
934 	hashl = 0;
935 	hashi = 0;
936 	for (cp = item.dptr, s = item.dsize; --s >= 0; ) {
937 		c = *cp++;
938 		for (j = 0; j < BYTESIZ; j += 4) {
939 			hashi += hitab[c&017];
940 			hashl += hltab[hashi&63];
941 			c >>= 4;
942 		}
943 	}
944 	return (hashl);
945 }
946 
947 /*
948  * Delete pairs of items (n & n+1).
949  */
950 static int
951 delitem(char buf[PBLKSIZ], int n)
952 {
953 	short *sp, *sp1;
954 	int i1, i2;
955 
956 	sp = (short *)(uintptr_t)buf;
957 	i2 = sp[0];
958 	if ((unsigned)n >= i2 || (n & 1))
959 		return (0);
960 	if (n == i2-2) {
961 		sp[0] -= 2;
962 		return (1);
963 	}
964 	i1 = PBLKSIZ;
965 	if (n > 0)
966 		i1 = sp[n];
967 	i1 -= sp[n+2];
968 	if (i1 > 0) {
969 		i2 = sp[i2];
970 		(void) memmove(&buf[i2 + i1], &buf[i2], sp[n+2] - i2);
971 	}
972 	sp[0] -= 2;
973 	for (sp1 = sp + sp[0], sp += n+1; sp <= sp1; sp++)
974 		sp[0] = sp[2] + i1;
975 	return (1);
976 }
977 
978 /*
979  * Add pairs of items (item & item1).
980  */
981 static int
982 additem(char buf[PBLKSIZ], datum item, datum item1)
983 {
984 	short *sp;
985 	int i1, i2;
986 
987 	sp = (short *)(uintptr_t)buf;
988 	i1 = PBLKSIZ;
989 	i2 = sp[0];
990 	if (i2 > 0)
991 		i1 = sp[i2];
992 	i1 -= item.dsize + item1.dsize;
993 	if (i1 <= (i2+3) * (int)sizeof (short))
994 		return (0);
995 	sp[0] += 2;
996 	sp[++i2] = (short)(i1 + item1.dsize);
997 	(void) memmove(&buf[i1 + item1.dsize], item.dptr, item.dsize);
998 	sp[++i2] = i1;
999 	(void) memmove(&buf[i1], item1.dptr, item1.dsize);
1000 	return (1);
1001 }
1002 
1003 #ifdef DEBUG
1004 static int
1005 chkblk(char buf[PBLKSIZ])
1006 {
1007 	short *sp;
1008 	int t, i;
1009 
1010 	sp = (short *)buf;
1011 	t = PBLKSIZ;
1012 	for (i = 0; i < sp[0]; i++) {
1013 		if (sp[i + 1] > t)
1014 			return (-1);
1015 		t = sp[i + 1];
1016 	}
1017 	if (t < (sp[0] + 1) * sizeof (short))
1018 		return (-1);
1019 	return (0);
1020 }
1021 #endif
1022