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