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