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
dbm_setdefwrite(DBM * db)91 dbm_setdefwrite(DBM *db)
92 {
93 db->dbm_flags |= _DBM_DEFWRITE;
94 }
95
96 #undef dbm_error
97
98 int
dbm_error(DBM * db)99 dbm_error(DBM *db)
100 {
101 return (db->dbm_flags & _DBM_IOERR);
102 }
103
104 #undef dbm_clearerr
105
106 int
dbm_clearerr(DBM * db)107 dbm_clearerr(DBM *db)
108 {
109 return (db->dbm_flags &= ~_DBM_IOERR);
110 }
111
112 int
dbm_flush(DBM * db)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
dbm_flushpag(DBM * db)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
dbm_flushdir(DBM * db)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 *
dbm_open(const char * file,int flags,mode_t mode)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
dbm_close(DBM * db)215 dbm_close(DBM *db)
216 {
217 (void) dbm_close_status(db);
218 }
219
220 /* close with return code */
221 int
dbm_close_status(DBM * db)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
dbm_forder(DBM * db,datum key)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
dbm_fetch(DBM * db,datum key)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
dbm_delete(DBM * db,datum key)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
dbm_store(DBM * db,datum key,datum dat,int replace)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
dbm_hashinc(DBM * db,unsigned long hash)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
dbm_firsthash(DBM * db,unsigned long hash)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
dbm_firstkey(DBM * db)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
dbm_nextkey(DBM * db)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
dbm_slow_nextkey(DBM * db)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
dbm_do_nextkey(DBM * db,datum inkey)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
dbm_access(DBM * db,unsigned long hash)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
getbit(DBM * db)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
setbit(DBM * db)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
makdatum(char * buf,int n)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
cmpdatum(datum d1,datum d2)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
finddatum(char * buf,datum item)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
dcalchash(datum item)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
delitem(char * buf,int n)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
additem(char * buf,datum item,datum item1)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
chkblk(char buf[PBLKSIZ])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