usr/src/lib/libbc/libc/gen/common/ndbm.c

   1 /*
   2  * Copyright 2002 Sun Microsystems, Inc.  All rights reserved.
   3  * Use is subject to license terms.
   4  * Copyright (c) 2016 by Delphix. All rights reserved.
   5  */
   6
   7 /*
   8  * Copyright (c) 1983 Regents of the University of California.
   9  * All rights reserved.  The Berkeley software License Agreement
  10  * specifies the terms and conditions for redistribution.
  11  */
  12
  13 #pragma ident   "%Z%%M% %I%     %E% SMI"
  14
  15 #include <sys/types.h>
  16 #include <sys/stat.h>
  17 #include <sys/file.h>
  18 #include <stdio.h>
  19 #include <errno.h>
  20 #include <ndbm.h>
  21 #include <stdlib.h>
  22 #include <string.h>
  23
  24 datum dbm_do_nextkey(DBM *, datum);
  25
  26
  27 /*add support for batched writing for NIS*/
  28
  29 #define _DBM_DEFWRITE 0x4
  30 #define _DBM_DIRTY 0x8
  31 #define _DBM_DIRDIRTY 0x10
  32 #define dbm_dirty(db) ((db)->dbm_flags & _DBM_DIRTY)
  33 #define dbm_dirdirty(db) ((db)->dbm_flags & _DBM_DIRDIRTY)
  34 #define dbm_defwrite(db) ((db)->dbm_flags & _DBM_DEFWRITE)
  35 #define dbm_setdirty(db) (db)->dbm_flags |= _DBM_DIRTY
  36 #define dbm_clrdirty(db) (db)->dbm_flags &= ~_DBM_DIRTY
  37 #define dbm_setdirdirty(db) (db)->dbm_flags |= _DBM_DIRDIRTY
  38 #define dbm_clrdirdirty(db) (db)->dbm_flags &= ~_DBM_DIRDIRTY
  39
  40
  41 static void     dbm_access(DBM *, long);
  42 static int      getbit(DBM *);
  43 static int      setbit(DBM *);
  44 static int      cmpdatum(datum, datum);
  45 static int      finddatum(char [PBLKSIZ], datum);
  46 static int      delitem(char [PBLKSIZ], int);
  47 static int      additem(char [PBLKSIZ], datum, datum);
  48 static datum    makdatum(char [PBLKSIZ], int);
  49 static long     dcalchash(datum);
  50
  51 /*used to make a dbm file all at once instead of incrementally*/
  52 void
  53 dbm_setdefwrite(DBM *db)
  54 {
  55         db->dbm_flags |= _DBM_DEFWRITE;
  56 }
  57
  58 int
  59 dbm_flush(DBM *db)
  60 {
  61         int ok=0;
  62         if (dbm_flushpag(db)<0) ok= -1;
  63         if (dbm_flushdir(db)<0) ok= -1;
  64         return(ok);
  65 }
  66
  67 int
  68 dbm_flushpag(DBM *db)
  69 {
  70         int ok=0;
  71         if (dbm_dirty(db)){ /*must page out the page*/
  72                 (void) lseek(db->dbm_pagf, (long)(db->dbm_pagbno*PBLKSIZ), L_SET);
  73                 if (write(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) != PBLKSIZ) {
  74                         db->dbm_flags |= _DBM_IOERR;
  75                         ok= -1;
  76                         }
  77                 dbm_clrdirty(db);
  78         }
  79         return(ok);
  80 }
  81
  82 int
  83 dbm_flushdir(DBM *db)
  84 {
  85         int ok=0;
  86         if (dbm_dirdirty(db)){ /*must page out the dir*/
  87         (void) lseek(db->dbm_dirf, (long)(db->dbm_dirbno*DBLKSIZ), L_SET);
  88         if (write(db->dbm_dirf, db->dbm_dirbuf, DBLKSIZ) != DBLKSIZ) {
  89                 ok= -1;
  90                 }
  91         dbm_clrdirdirty(db);
  92         }
  93         return(ok);
  94 }
  95 #define BYTESIZ 8
  96 #undef setbit
  97
  98 DBM *
  99 dbm_open(char *file, int flags, int mode)
 100 {
 101         struct stat statb;
 102         DBM *db;
 103         int     serrno;
 104
 105         if ((db = (DBM *)malloc(sizeof *db)) == 0) {
 106                 errno = ENOMEM;
 107                 return ((DBM *)0);
 108         }
 109         db->dbm_flags = (flags & 03) == O_RDONLY ? _DBM_RDONLY : 0;
 110         if ((flags & 03) == O_WRONLY)
 111                 flags = (flags & ~03) | O_RDWR;
 112         if (strlcpy(db->dbm_pagbuf, file, sizeof (db->dbm_pagbuf)) >=
 113             sizeof (db->dbm_pagbuf) ||
 114             strlcat(db->dbm_pagbuf, ".pag", sizeof (db->dbm_pagbuf)) >=
 115             sizeof (db->dbm_pagbuf)) {
 116                 /*
 117                  * file.pag does not fit into dbm_pagbuf.
 118                  * fails with ENAMETOOLONG.
 119                  */
 120                 serrno = ENAMETOOLONG;
 121                 goto bad;
 122         }
 123         db->dbm_pagf = open(db->dbm_pagbuf, flags, mode);
 124         if (db->dbm_pagf < 0) {
 125                 serrno = errno;
 126                 goto bad;
 127         }
 128         /*
 129          * We know this won't overflow so it is safe to ignore the
 130          * return value; we use strl* to prevent false hits in
 131          * code sweeps.
 132          */
 133         (void) strlcpy(db->dbm_pagbuf, file, sizeof (db->dbm_pagbuf));
 134         (void) strlcat(db->dbm_pagbuf, ".dir", sizeof (db->dbm_pagbuf));
 135         db->dbm_dirf = open(db->dbm_pagbuf, flags, mode);
 136         if (db->dbm_dirf < 0) {
 137                 serrno = errno;
 138                 goto bad1;
 139         }
 140         (void) fstat(db->dbm_dirf, &statb);
 141         db->dbm_maxbno = statb.st_size*BYTESIZ-1;
 142         db->dbm_pagbno = db->dbm_dirbno = -1;
 143         return (db);
 144 bad1:
 145         (void) close(db->dbm_pagf);
 146 bad:
 147         free((char *)db);
 148         errno = serrno;
 149         return ((DBM *)0);
 150 }
 151
 152 void
 153 dbm_close(DBM *db)
 154 {
 155         (void) dbm_close_status(db);
 156 }
 157
 158 /*close with return code*/
 159 int
 160 dbm_close_status(DBM *db)
 161 {
 162         int ok;
 163         ok=0;
 164
 165         if (dbm_flush(db) <0)   ok = -1;
 166         if (close(db->dbm_dirf)<0) ok= -1;
 167         if ( close(db->dbm_pagf)<0) ok= -1;
 168         free((char *)db);
 169         return (ok);
 170 }
 171
 172 long
 173 dbm_forder(DBM *db, datum key)
 174 {
 175         long hash;
 176
 177         hash = dcalchash(key);
 178         for (db->dbm_hmask=0;; db->dbm_hmask=(db->dbm_hmask<<1)+1) {
 179                 db->dbm_blkno = hash & db->dbm_hmask;
 180                 db->dbm_bitno = db->dbm_blkno + db->dbm_hmask;
 181                 if (getbit(db) == 0)
 182                         break;
 183         }
 184         return (db->dbm_blkno);
 185 }
 186
 187 datum
 188 dbm_fetch(DBM *db, datum key)
 189 {
 190         int i;
 191         datum item;
 192
 193         if (dbm_error(db))
 194                 goto err;
 195         dbm_access(db, dcalchash(key));
 196         if ((i = finddatum(db->dbm_pagbuf, key)) >= 0) {
 197                 item = makdatum(db->dbm_pagbuf, i+1);
 198                 if (item.dptr != NULL)
 199                         return (item);
 200         }
 201 err:
 202         item.dptr = NULL;
 203         item.dsize = 0;
 204         return (item);
 205 }
 206
 207 int
 208 dbm_delete(DBM *db, datum key)
 209 {
 210         int i;
 211
 212         if (dbm_error(db))
 213                 return (-1);
 214         if (dbm_rdonly(db)) {
 215                 errno = EPERM;
 216                 return (-1);
 217         }
 218         dbm_access(db, dcalchash(key));
 219         if ((i = finddatum(db->dbm_pagbuf, key)) < 0)
 220                 return (-1);
 221         if (!delitem(db->dbm_pagbuf, i))
 222                 goto err;
 223         db->dbm_pagbno = db->dbm_blkno;
 224         if (dbm_defwrite(db)) {
 225                 dbm_setdirty(db);
 226         }
 227         else {
 228         (void) lseek(db->dbm_pagf, (long)(db->dbm_blkno*PBLKSIZ), L_SET);
 229         if (write(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) != PBLKSIZ) {
 230         err:
 231                 db->dbm_flags |= _DBM_IOERR;
 232                 return (-1);
 233         }
 234         }
 235         return (0);
 236 }
 237
 238 int
 239 dbm_store(DBM *db, datum key, datum dat, int replace)
 240 {
 241         int i;
 242         datum item, item1;
 243         char ovfbuf[PBLKSIZ];
 244
 245         if (dbm_error(db))
 246                 return (-1);
 247         if (dbm_rdonly(db)) {
 248                 errno = EPERM;
 249                 return (-1);
 250         }
 251 loop:
 252         dbm_access(db, dcalchash(key));
 253         if ((i = finddatum(db->dbm_pagbuf, key)) >= 0) {
 254                 if (!replace)
 255                         return (1);
 256                 if (!delitem(db->dbm_pagbuf, i)) {
 257                         db->dbm_flags |= _DBM_IOERR;
 258                         return (-1);
 259                 }
 260         }
 261         if (!additem(db->dbm_pagbuf, key, dat))
 262                 goto split;
 263         db->dbm_pagbno = db->dbm_blkno;
 264         if (dbm_defwrite(db)) {
 265                 dbm_setdirty(db);
 266         }
 267         else {
 268
 269                 (void) lseek(db->dbm_pagf, (long)(db->dbm_blkno*PBLKSIZ), L_SET);
 270                 if (write(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) != PBLKSIZ) {
 271                         db->dbm_flags |= _DBM_IOERR;
 272                         return (-1);
 273                 }
 274         }
 275         return (0);
 276
 277 split:
 278         if (key.dsize+dat.dsize+3*sizeof(short) >= PBLKSIZ) {
 279                 db->dbm_flags |= _DBM_IOERR;
 280                 errno = ENOSPC;
 281                 return (-1);
 282         }
 283         bzero(ovfbuf, PBLKSIZ);
 284         for (i=0;;) {
 285                 item = makdatum(db->dbm_pagbuf, i);
 286                 if (item.dptr == NULL)
 287                         break;
 288                 if (dcalchash(item) & (db->dbm_hmask+1)) {
 289                         item1 = makdatum(db->dbm_pagbuf, i+1);
 290                         if (item1.dptr == NULL) {
 291                                 /*(void) fprintf(stderr, "ndbm: split not paired\n");*/
 292                                 db->dbm_flags |= _DBM_IOERR;
 293                                 break;
 294                         }
 295                         if (!additem(ovfbuf, item, item1) ||
 296                             !delitem(db->dbm_pagbuf, i)) {
 297                                 db->dbm_flags |= _DBM_IOERR;
 298                                 return (-1);
 299                         }
 300                         continue;
 301                 }
 302                 i += 2;
 303         }
 304         db->dbm_pagbno = db->dbm_blkno;
 305         (void) lseek(db->dbm_pagf, (long)(db->dbm_blkno*PBLKSIZ), L_SET);
 306         if (write(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) != PBLKSIZ) {
 307                 db->dbm_flags |= _DBM_IOERR;
 308                 return (-1);
 309         }
 310         dbm_clrdirty(db); /*clear dirty*/
 311         (void) lseek(db->dbm_pagf,
 312                 (long)((db->dbm_blkno+db->dbm_hmask+1)*PBLKSIZ), L_SET);
 313         if (write(db->dbm_pagf, ovfbuf, PBLKSIZ) != PBLKSIZ) {
 314                 db->dbm_flags |= _DBM_IOERR;
 315                 return (-1);
 316         }
 317         if (setbit(db) < 0) {
 318                 db->dbm_flags |= _DBM_IOERR;
 319                 return (-1);
 320         }
 321         goto loop;
 322 }
 323
 324 static long
 325 dbm_hashinc(DBM *db, long hash)
 326 {
 327
 328         long bit;
 329
 330         hash &= db->dbm_hmask;
 331         bit = db->dbm_hmask+1;
 332         for(;;) {
 333                 bit >>= 1;
 334                 if(bit == 0)
 335                         return(0L);
 336                 if((hash&bit) == 0)
 337                         return(hash|bit);
 338                 hash &= ~bit;
 339         }
 340 }
 341
 342
 343
 344 static datum nullkey= {NULL, 0};
 345
 346 datum
 347 dbm_firsthash(DBM *db, long hash)
 348 {
 349         int i,j;
 350         datum item, bitem;
 351
 352 loop:
 353         dbm_access(db, hash);
 354         j=0;
 355         bitem = makdatum(db->dbm_pagbuf, 0);
 356         for(i=2;; i+=2) {
 357                 item = makdatum(db->dbm_pagbuf, i);
 358                 if(item.dptr == NULL)
 359                         break;
 360                 if(cmpdatum(bitem, item) < 0) {
 361                         j=i;
 362                         bitem = item;
 363                         }
 364         }
 365         if(bitem.dptr != NULL) {
 366                 db->dbm_keyptr = j + 2;
 367                 db->dbm_blkptr = db->dbm_blkno;
 368                 return(bitem);
 369         }
 370         hash = dbm_hashinc(db,hash);
 371         if(hash == 0)
 372                 return(item); /*null item*/
 373         goto loop;
 374
 375 }
 376
 377 datum
 378 dbm_firstkey(DBM *db)
 379 {
 380
 381         db->dbm_blkptr = 0L;
 382         db->dbm_keyptr = 0;
 383         return (dbm_firsthash(db, 0L));
 384 }
 385
 386 datum
 387 dbm_nextkey(DBM *db)
 388 {
 389
 390         return (dbm_do_nextkey(db, nullkey));
 391 }
 392
 393 /*this is used if keyptr-2,blocknum doesn't point to the previous
 394 specific key allowing the fast hash order search --
 395 its use indicates user tampering with our state variables,
 396 which some evil users might do to search from some specific place.
 397 It finds the first key at or after blkptr,keyptr in block seq order
 398 this requires looking at all sorts of emtpy blocks in many cases*/
 399
 400 static datum
 401 dbm_slow_nextkey(DBM *db)
 402 {
 403         struct stat statb;
 404         datum item;
 405
 406         if (dbm_error(db) || fstat(db->dbm_pagf, &statb) < 0)
 407                 goto err;
 408         statb.st_size /= PBLKSIZ;
 409
 410         for (;;) {
 411                 if (db->dbm_blkptr != db->dbm_pagbno) {
 412
 413                         if (dbm_dirty(db)) dbm_flushpag(db);
 414
 415                         db->dbm_pagbno = db->dbm_blkptr;
 416                         (void) lseek(db->dbm_pagf, (long)(db->dbm_blkptr*PBLKSIZ), L_SET);
 417                         if (read(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) != PBLKSIZ)
 418                                 bzero(db->dbm_pagbuf, PBLKSIZ);
 419 #ifdef DEBUG
 420                         else if (chkblk(db->dbm_pagbuf) < 0)
 421                                 db->dbm_flags |= _DBM_IOERR;
 422 #endif
 423                 }
 424                 /*Am I an empty block?*/
 425                 if (((short *)db->dbm_pagbuf)[0] != 0) {
 426                         item = makdatum(db->dbm_pagbuf, db->dbm_keyptr);
 427                         if (item.dptr != NULL) {
 428                                 db->dbm_keyptr += 2;
 429                                 return (item);
 430                         }
 431                         db->dbm_keyptr = 0;
 432                 }
 433                 /*go to next sequential block*/
 434                 if (++db->dbm_blkptr >= statb.st_size)
 435                         break;
 436         }
 437 err:
 438         item.dptr = NULL;
 439         item.dsize = 0;
 440         return (item);
 441 }
 442
 443 datum
 444 dbm_do_nextkey(DBM *db, datum inkey)
 445 {
 446         datum item,bitem;
 447         long hash;
 448         datum key;
 449         int f;
 450         int i;
 451         int j;
 452         short *sp;
 453         int n;
 454         char *p1, *p2;
 455
 456         if ( dbm_error(db) ) {
 457                 item.dptr = NULL;
 458                 item.dsize = 0;
 459                 return (item);
 460         }
 461
 462         /*user has supplied lastkey*/
 463
 464         if(inkey.dptr != NULL) {
 465                dbm_access(db, (hash=dcalchash(inkey)));
 466                if ((i = finddatum(db->dbm_pagbuf, inkey)) >= 0) {
 467                        db->dbm_keyptr = i + 2;
 468                        db->dbm_blkptr = db->dbm_blkno;
 469                }
 470                key=inkey;
 471        }
 472        else  {
 473                 /*is this a manual firstkey request? */
 474
 475                 if (db->dbm_blkptr == 0L &&
 476                         db->dbm_keyptr == 0)
 477                         return (dbm_firsthash(db, 0L));
 478
 479                 /*no -- get lastkey this is like dbm_access by blkptr*/
 480
 481                 if (db->dbm_blkptr != db->dbm_pagbno) {
 482
 483                         if (dbm_dirty(db)) dbm_flushpag(db);
 484                         db->dbm_pagbno = db->dbm_blkptr;
 485                         (void) lseek(db->dbm_pagf, (long)(db->dbm_blkptr*PBLKSIZ), L_SET);
 486                         if (read(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) != PBLKSIZ)
 487                                 bzero(db->dbm_pagbuf, PBLKSIZ);
 488 #ifdef DEBUG
 489                         else if (chkblk(db->dbm_pagbuf) < 0)
 490                         db->dbm_flags |= _DBM_IOERR;
 491 #endif
 492                 }
 493                 /*now just make up last key datum*/
 494                 if (db->dbm_keyptr >=2) key= makdatum(db->dbm_pagbuf,(db->dbm_keyptr-2));
 495                 else key=nullkey;
 496
 497         /* the keyptr pagbuf have failed us, the user must
 498         be an extra clever moron who depends on
 499         these variables and their former meaning.
 500         If we set the variables this would have got
 501         us the key for sure! So give him the old algorithm.*/
 502                 if (key.dptr == NULL) return (dbm_slow_nextkey(db));
 503         }
 504
 505         /*at this point the last key is paged in and
 506         we can proceed as in old dbm -- like Ken did his. */
 507
 508         f = 1;
 509         j=0;
 510         sp = (short *)db->dbm_pagbuf;
 511
 512         for(i=0;; i+=2) {
 513
 514                 /*begin put makdatum inline*/
 515
 516                 if ((unsigned)i >= sp[0]) {
 517                         item.dptr = NULL;
 518                         item.dsize = 0;
 519                         break; /*from below*/
 520                 }
 521                 else {
 522                         if (i > 0) item.dsize = sp[i] - sp[i+1];
 523                         else item.dsize = PBLKSIZ - sp[i+1];
 524                         item.dptr = db->dbm_pagbuf+sp[i+1];
 525                 }
 526
 527                 /*      item = makdatum(db->dbm_pagbuf, i);*/
 528                 /*end put makdatum inline*/
 529
 530                 if(item.dptr == NULL)
 531                         break;
 532 /*inline cmpdatum*/
 533
 534
 535                 n = key.dsize;
 536                 if(n != item.dsize)
 537                         if( (n - item.dsize) <= 0 ) continue;
 538                         else { }
 539                 else {
 540                         if(n == 0) continue;
 541                         p1 = key.dptr;
 542                         p2 = item.dptr;
 543                         do
 544                                 if(*p1++ != *p2++)
 545                                         if((*--p1 - *--p2) > 0) goto keep_going;
 546                                         else continue;
 547                         while(--n);
 548                         continue;
 549                         }
 550
 551 keep_going:
 552
 553 /*end inline cmpdatum*/
 554                 /*if(cmpdatum(key, item) <= 0)
 555                         continue;*/
 556                 if (f) {
 557                         bitem = item;
 558                         j=i;
 559                         f = 0;
 560                 }
 561                 else {
 562
 563 /*              if(cmpdatum(bitem, item) < 0)*/
 564
 565                 n = bitem.dsize;
 566                 if(n != item.dsize)
 567                         {
 568                         if((n - item.dsize) <0) {
 569                                         bitem = item;
 570                                         j=i;
 571                                 }
 572                         }
 573                         else  if (n != 0) {
 574                                 p1 = bitem.dptr;
 575                                 p2 = item.dptr;
 576                                 do
 577                                 if(*p1++ != *p2++) {
 578                                         if((*--p1 - *--p2) <0) {
 579                                                 bitem = item;
 580                                                 j=i;
 581                                         }
 582                                         break;
 583                                 }
 584                                 while(--n);
 585                         }
 586                 }
 587         }
 588
 589         if(f == 0) {
 590                 db->dbm_keyptr = j + 2;
 591                 db->dbm_blkptr = db->dbm_blkno;
 592                 return (bitem);
 593         }
 594
 595         /* really need hash at this point */
 596         /* if it gave us a key we have already calculated the hash */
 597         /* if not get the hash */
 598         if (inkey.dptr == NULL) hash=dcalchash(key);
 599         hash = dbm_hashinc(db,hash);
 600
 601         if(hash == 0)
 602                 return (item); /*null*/
 603         /*get first item on next page in hash table order*/
 604         return (dbm_firsthash(db, hash));
 605
 606
 607 }
 608
 609 static void
 610 dbm_access(DBM *db, long hash)
 611 {
 612         int b, i, n;
 613         long bn;
 614         long my_bitno;
 615         long my_hmask;
 616         long my_blkno;
 617
 618         for (my_hmask=0;; my_hmask=(my_hmask<<1)+1) {
 619                 my_blkno = hash & my_hmask;
 620                 my_bitno = my_blkno + my_hmask;
 621                 /*getbit inline*/
 622                 if (my_bitno > db->dbm_maxbno) break;
 623                 n = my_bitno % BYTESIZ;
 624                 bn = my_bitno / BYTESIZ;
 625                 i = bn % DBLKSIZ;
 626                 b = bn / DBLKSIZ;
 627                 if (b != db->dbm_dirbno) {
 628                         if (dbm_dirdirty(db)) dbm_flushdir(db); /*must flush*/
 629                         db->dbm_dirbno = b;
 630                         (void) lseek(db->dbm_dirf, (long)(b*DBLKSIZ), L_SET);
 631                         if (read(db->dbm_dirf, db->dbm_dirbuf, DBLKSIZ) != DBLKSIZ)
 632                                 bzero(db->dbm_dirbuf, DBLKSIZ);
 633                 }
 634                 if ( (db->dbm_dirbuf[i] & (1<<n)) == 0 ) break;
 635
 636                 /*
 637                 if (getbit(db) == 0)
 638                         break;
 639                 */
 640         }
 641         /*copy*/
 642         db->dbm_blkno=my_blkno;
 643         db->dbm_bitno=my_bitno;
 644         db->dbm_hmask=my_hmask;
 645
 646         if (my_blkno != db->dbm_pagbno) {
 647                 if (dbm_dirty(db)){ /*must page out the page*/
 648                         (void) lseek(db->dbm_pagf, (long)(db->dbm_pagbno*PBLKSIZ), L_SET);
 649                         if (write(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) != PBLKSIZ) {
 650                                 db->dbm_flags |= _DBM_IOERR;
 651                         }
 652                 dbm_clrdirty(db);
 653                 }
 654
 655                 db->dbm_pagbno = my_blkno;
 656                 (void) lseek(db->dbm_pagf, (long)(my_blkno*PBLKSIZ), L_SET);
 657                 if (read(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) != PBLKSIZ)
 658                         bzero(db->dbm_pagbuf, PBLKSIZ);
 659 #ifdef DEBUG
 660                 else if (chkblk(db->dbm_pagbuf) < 0)
 661                         db->dbm_flags |= _DBM_IOERR;
 662 #endif
 663         }
 664 }
 665
 666 static int
 667 getbit(DBM *db)
 668 {
 669         long bn;
 670         int b, i, n;
 671
 672
 673         if (db->dbm_bitno > db->dbm_maxbno)
 674                 return (0);
 675         n = db->dbm_bitno % BYTESIZ;
 676         bn = db->dbm_bitno / BYTESIZ;
 677         i = bn % DBLKSIZ;
 678         b = bn / DBLKSIZ;
 679         if (b != db->dbm_dirbno) {
 680                 if (dbm_dirdirty(db)) dbm_flushdir(db); /*must flush*/
 681                 db->dbm_dirbno = b;
 682                 (void) lseek(db->dbm_dirf, (long)(b*DBLKSIZ), L_SET);
 683                 if (read(db->dbm_dirf, db->dbm_dirbuf, DBLKSIZ) != DBLKSIZ)
 684                         bzero(db->dbm_dirbuf, DBLKSIZ);
 685         }
 686         return (db->dbm_dirbuf[i] & (1<<n));
 687 }
 688
 689 static int
 690 setbit(DBM *db)
 691 {
 692         long bn;
 693         int i, n, b;
 694
 695         if (db->dbm_bitno > db->dbm_maxbno)
 696                 db->dbm_maxbno = db->dbm_bitno;
 697         n = db->dbm_bitno % BYTESIZ;
 698         bn = db->dbm_bitno / BYTESIZ;
 699         i = bn % DBLKSIZ;
 700         b = bn / DBLKSIZ;
 701         if (b != db->dbm_dirbno) {
 702                 if (dbm_dirdirty(db)) dbm_flushdir(db);
 703                 db->dbm_dirbno = b;
 704                 (void) lseek(db->dbm_dirf, (long)(b*DBLKSIZ), L_SET);
 705                 if (read(db->dbm_dirf, db->dbm_dirbuf, DBLKSIZ) != DBLKSIZ)
 706                         bzero(db->dbm_dirbuf, DBLKSIZ);
 707         }
 708         db->dbm_dirbuf[i] |= 1<<n;
 709         db->dbm_dirbno = b;
 710         if (dbm_defwrite(db)) {
 711         dbm_setdirdirty(db);
 712         } else{
 713         (void) lseek(db->dbm_dirf, (long)(b*DBLKSIZ), L_SET);
 714         if (write(db->dbm_dirf, db->dbm_dirbuf, DBLKSIZ) != DBLKSIZ) {
 715                 return (-1);
 716         }
 717         }
 718         return (0);
 719 }
 720
 721 static datum
 722 makdatum(char buf[PBLKSIZ], int n)
 723 {
 724         short *sp;
 725         int t;
 726         datum item;
 727
 728         sp = (short *)buf;
 729         if ((unsigned)n >= sp[0]) {
 730                 item.dptr = NULL;
 731                 item.dsize = 0;
 732                 return (item);
 733         }
 734         t = PBLKSIZ;
 735         if (n > 0)
 736                 t = sp[n];
 737         item.dptr = buf+sp[n+1];
 738         item.dsize = t - sp[n+1];
 739         return (item);
 740 }
 741
 742 static int
 743 cmpdatum(datum d1, datum d2)
 744 {
 745         int n;
 746         char *p1, *p2;
 747
 748         n = d1.dsize;
 749         if(n != d2.dsize)
 750                 return(n - d2.dsize);
 751         if(n == 0)
 752                 return(0);
 753         p1 = d1.dptr;
 754         p2 = d2.dptr;
 755         do
 756                 if(*p1++ != *p2++)
 757                         return(*--p1 - *--p2);
 758         while(--n);
 759         return(0);
 760 }
 761
 762 static int
 763 finddatum(char buf[PBLKSIZ], datum item)
 764 {
 765         short *sp;
 766         int i, n, j;
 767
 768         sp = (short *)buf;
 769         n = PBLKSIZ;
 770         for (i=0, j=sp[0]; i<j; i+=2, n = sp[i]) {
 771                 n -= sp[i+1];
 772                 if (n != item.dsize)
 773                         continue;
 774                 if (n == 0 || bcmp(&buf[sp[i+1]], item.dptr, n) == 0)
 775                         return (i);
 776         }
 777         return (-1);
 778 }
 779
 780 static  int hitab[16]
 781  = {    61, 57, 53, 49, 45, 41, 37, 33,
 782         29, 25, 21, 17, 13,  9,  5,  1,
 783 };
 784
 785 static  long hltab[64]
 786  = {
 787         06100151277L,06106161736L,06452611562L,05001724107L,
 788         02614772546L,04120731531L,04665262210L,07347467531L,
 789         06735253126L,06042345173L,03072226605L,01464164730L,
 790         03247435524L,07652510057L,01546775256L,05714532133L,
 791         06173260402L,07517101630L,02431460343L,01743245566L,
 792         00261675137L,02433103631L,03421772437L,04447707466L,
 793         04435620103L,03757017115L,03641531772L,06767633246L,
 794         02673230344L,00260612216L,04133454451L,00615531516L,
 795         06137717526L,02574116560L,02304023373L,07061702261L,
 796         05153031405L,05322056705L,07401116734L,06552375715L,
 797         06165233473L,05311063631L,01212221723L,01052267235L,
 798         06000615237L,01075222665L,06330216006L,04402355630L,
 799         01451177262L,02000133436L,06025467062L,07121076461L,
 800         03123433522L,01010635225L,01716177066L,05161746527L,
 801         01736635071L,06243505026L,03637211610L,01756474365L,
 802         04723077174L,03642763134L,05750130273L,03655541561L,
 803 };
 804
 805 static long
 806 dcalchash(datum item)
 807 {
 808         int s, c, j;
 809         char *cp;
 810         long hashl;
 811         int hashi;
 812
 813         hashl = 0;
 814         hashi = 0;
 815         for (cp = item.dptr, s=item.dsize; --s >= 0; ) {
 816                 c = *cp++;
 817                 for (j=0; j<BYTESIZ; j+=4) {
 818                         hashi += hitab[c&017];
 819                         hashl += hltab[hashi&63];
 820                         c >>= 4;
 821                 }
 822         }
 823         return (hashl);
 824 }
 825
 826 /*
 827  * Delete pairs of items (n & n+1).
 828  */
 829 static int
 830 delitem(char buf[PBLKSIZ], int n)
 831 {
 832         short *sp, *sp1;
 833         int i1, i2;
 834
 835         sp = (short *)buf;
 836         i2 = sp[0];
 837         if ((unsigned)n >= i2 || (n & 1))
 838                 return (0);
 839         if (n == i2-2) {
 840                 sp[0] -= 2;
 841                 return (1);
 842         }
 843         i1 = PBLKSIZ;
 844         if (n > 0)
 845                 i1 = sp[n];
 846         i1 -= sp[n+2];
 847         if (i1 > 0) {
 848                 i2 = sp[i2];
 849                 bcopy(&buf[i2], &buf[i2 + i1], sp[n+2] - i2);
 850         }
 851         sp[0] -= 2;
 852         for (sp1 = sp + sp[0], sp += n+1; sp <= sp1; sp++)
 853                 sp[0] = sp[2] + i1;
 854         return (1);
 855 }
 856
 857 /*
 858  * Add pairs of items (item & item1).
 859  */
 860 static int
 861 additem(char buf[PBLKSIZ], datum item, datum item1)
 862 {
 863         short *sp;
 864         int i1, i2;
 865
 866         sp = (short *)buf;
 867         i1 = PBLKSIZ;
 868         i2 = sp[0];
 869         if (i2 > 0)
 870                 i1 = sp[i2];
 871         i1 -= item.dsize + item1.dsize;
 872         if (i1 <= (i2+3) * sizeof(short))
 873                 return (0);
 874         sp[0] += 2;
 875         sp[++i2] = i1 + item1.dsize;
 876         bcopy(item.dptr, &buf[i1 + item1.dsize], item.dsize);
 877         sp[++i2] = i1;
 878         bcopy(item1.dptr, &buf[i1], item1.dsize);
 879         return (1);
 880 }
 881
 882 #ifdef DEBUG
 883 static int
 884 chkblk(char buf[PBLKSIZ])
 885 {
 886         short *sp;
 887         int t, i;
 888
 889         sp = (short *)buf;
 890         t = PBLKSIZ;
 891         for (i=0; i<sp[0]; i++) {
 892                 if (sp[i+1] > t)
 893                         return (-1);
 894                 t = sp[i+1];
 895         }
 896         if (t < (sp[0]+1)*sizeof(short))
 897                 return (-1);
 898         return (0);
 899 }
 900 #endif