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