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