usr/src/lib/libc/port/gen/ndbm.c

   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