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