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