1 /*- 2 * Copyright (c) 1990 The Regents of the University of California. 3 * All rights reserved. 4 * 5 * This code is derived from software contributed to Berkeley by 6 * Margo Seltzer. 7 * 8 * %sccs.include.redist.c% 9 */ 10 11 #if defined(LIBC_SCCS) && !defined(lint) 12 static char sccsid[] = "@(#)hash_page.c 5.2 (Berkeley) 02/14/91"; 13 #endif /* LIBC_SCCS and not lint */ 14 15 /****************************************************************************** 16 PACKAGE: hashing 17 18 DESCRIPTION: 19 Page manipulation for hashing package. 20 21 ROUTINES: 22 External 23 __get_page 24 __add_ovflpage 25 Internal 26 overflow_page 27 open_temp 28 ******************************************************************************/ 29 30 #include <sys/param.h> 31 #include <sys/file.h> 32 #include <signal.h> 33 #include <assert.h> 34 #include <errno.h> 35 #include <db.h> 36 #include <stdio.h> 37 #include "hash.h" 38 #include "page.h" 39 40 /* Externals */ 41 /* buf.c */ 42 extern BUFHEAD *__get_buf(); 43 extern void __reclaim_buf(); 44 45 /* big.c */ 46 extern int __big_split(); 47 extern int __big_insert(); 48 extern int __big_delete(); 49 extern int __find_bigpair(); 50 51 /* dynahash.c */ 52 extern int __call_hash(); 53 extern int __expand_table(); 54 55 /* my externals */ 56 extern int __get_page(); 57 extern BUFHEAD *__add_ovflpage(); 58 extern int __split_page(); 59 extern int __addel(); 60 61 /* my internals */ 62 static u_short overflow_page(); 63 static int open_temp(); 64 static void squeeze_key(); 65 static void putpair(); 66 67 #ifdef HASH_STATISTICS 68 extern long hash_accesses, hash_collisions, hash_expansions, hash_overflows; 69 #endif 70 #define PAGE_INIT(P) \ 71 { \ 72 ((u_short *)P)[0] = 0; \ 73 ((u_short *)P)[1] = hashp->BSIZE - 3 * sizeof(u_short); \ 74 ((u_short *)P)[2] = hashp->BSIZE; \ 75 } 76 77 /* 78 This is called AFTER we have verified that there is room on the 79 page for the pair (PAIRFITS has returned true) so we go right 80 ahead and start moving stuff on. 81 */ 82 static void 83 putpair(p, key, val) 84 char *p; 85 DBT *key; 86 DBT *val; 87 { 88 register u_short n; 89 register u_short off; 90 register u_short *bp = (u_short *) p; 91 92 /* enter the key first */ 93 n = bp[0]; 94 95 off = OFFSET(bp) - key->size; 96 bcopy( key->data, p+off, key->size ); 97 bp[++n] = off; 98 99 /* now the data */ 100 off -= val->size; 101 bcopy(val->data, p + off, val->size); 102 bp[++n] = off; 103 104 /* adjust page info */ 105 bp[0] = n; 106 bp[n+1] = off - ((n+3)*sizeof(u_short)); 107 bp[n+2] = off; 108 return; 109 } 110 /* 111 0 OK 112 -1 error 113 */ 114 extern int 115 __delpair(bufp, ndx) 116 BUFHEAD *bufp; 117 register int ndx; 118 { 119 register u_short *bp = (u_short *) bufp->page; 120 register int n = bp[0]; 121 register u_short newoff; 122 u_short pairlen; 123 124 if ( bp[ndx+1] < REAL_KEY ) return ( __big_delete ( bufp, ndx ) ); 125 if ( ndx != 1 ) newoff = bp[ndx-1]; 126 else newoff = hashp->BSIZE; 127 pairlen = newoff - bp[ndx+1]; 128 129 if ( ndx != (n-1) ) { 130 /* Hard Case -- need to shuffle keys */ 131 register int i; 132 register char *src = bufp->page + (int)OFFSET(bp); 133 register char *dst = src + (int)pairlen; 134 bcopy ( src, dst, bp[ndx+1] - OFFSET(bp) ); 135 136 /* Now adjust the pointers */ 137 for ( i = ndx+2; i <= n; i += 2 ) { 138 if ( bp[i+1] == OVFLPAGE ) { 139 bp[i-2] = bp[i]; 140 bp[i-1] = bp[i+1]; 141 } else { 142 bp[i-2] = bp[i] + pairlen; 143 bp[i-1] = bp[i+1] + pairlen; 144 } 145 } 146 } 147 148 /* Finally adjust the page data */ 149 bp[n] = OFFSET(bp) + pairlen; 150 bp[n-1] = bp[n+1] + pairlen + 2 * sizeof(u_short); 151 bp[0] = n-2; 152 hashp->NKEYS--; 153 154 bufp->flags |= BUF_MOD; 155 return (0); 156 } 157 /* 158 -1 ==> Error 159 0 ==> OK 160 */ 161 extern int 162 __split_page(obucket, nbucket) 163 int obucket; 164 int nbucket; 165 { 166 DBT key; 167 DBT val; 168 169 register BUFHEAD *new_bufp; 170 register BUFHEAD *old_bufp; 171 register u_short *ino; 172 register char *np; 173 char *op; 174 175 u_short copyto = (u_short)hashp->BSIZE; 176 u_short off = (u_short)hashp->BSIZE; 177 int n; 178 u_short diff; 179 u_short moved; 180 int ndx; 181 182 old_bufp = __get_buf ( obucket, NULL, 0 ); 183 new_bufp = __get_buf ( nbucket, NULL, 0 ); 184 185 old_bufp->flags |= BUF_MOD; 186 new_bufp->flags |= BUF_MOD; 187 188 ino = (u_short *)(op = old_bufp->page); 189 np = new_bufp->page; 190 191 moved = 0; 192 193 for (n = 1, ndx = 1; n < ino[0]; n+=2) { 194 if ( ino[n+1] < REAL_KEY ) { 195 return ( ugly_split( obucket, old_bufp, new_bufp, 196 copyto, moved ) ); 197 } 198 key.data = op + ino[n]; 199 key.size = off - ino[n]; 200 201 if ( __call_hash ( key.data, key.size ) == obucket ) { 202 /* Don't switch page */ 203 diff = copyto - off; 204 if ( diff ) { 205 copyto = ino[n+1] + diff; 206 bcopy ( op + ino[n+1], op + copyto, off-ino[n+1]); 207 ino[ndx] = copyto + ino[n] - ino[n+1]; 208 ino[ndx+1] = copyto; 209 } else copyto = ino[n+1]; 210 ndx += 2; 211 } else { 212 /* Switch page */ 213 val.data = op + ino[n+1]; 214 val.size = ino[n] - ino[n+1]; 215 putpair( np, &key, &val); 216 moved +=2; 217 } 218 219 off = ino[n+1]; 220 } 221 222 /* Now clean up the page */ 223 ino[0] -= moved; 224 FREESPACE(ino) = copyto - sizeof(u_short) * (ino[0]+3); 225 OFFSET(ino) = copyto; 226 227 #ifdef DEBUG3 228 fprintf(stderr, "split %d/%d\n", 229 ((u_short *) np)[0] / 2, 230 ((u_short *) op)[0] / 2); 231 #endif 232 return(0); 233 } 234 /* 235 0 ==> success 236 -1 ==> failure 237 238 Called when we encounter an overflow page during split handling. 239 this is special cased since we have to begin checking whether 240 the key/data pairs fit on their respective pages and because 241 we may need overflow pages for both the old and new pages 242 */ 243 static int 244 ugly_split( obucket, old_bufp, new_bufp, copyto, moved ) 245 int obucket; /* Same as __split_page */ 246 BUFHEAD *old_bufp; 247 BUFHEAD *new_bufp; 248 u_short copyto; /* First byte on page which contains key/data values */ 249 int moved; /* number of pairs moved to new page */ 250 { 251 register BUFHEAD *bufp = old_bufp; /* Buffer header for ino */ 252 register u_short *ino = (u_short *)old_bufp->page; 253 /* Page keys come off of */ 254 register u_short *np = (u_short *)new_bufp->page; /* New page */ 255 register u_short *op = (u_short *)old_bufp->page; 256 /* Page keys go on to if they 257 aren't moving */ 258 259 char *cino; /* Character value of ino */ 260 BUFHEAD *last_bfp = NULL; /* Last buffer header OVFL which 261 needs to be freed */ 262 u_short ov_addr, last_addr = 0; 263 u_short n; 264 u_short off; 265 266 DBT key, val; 267 SPLIT_RETURN ret; 268 269 n = ino[0]-1; 270 while ( n < ino[0] ) { 271 if ( ino[n+1] == OVFLPAGE ) { 272 ov_addr = ino[n]; 273 /* 274 Fix up the old page -- the extra 2 are the fields which 275 contained the overflow information 276 */ 277 ino[0] -= (moved + 2); 278 FREESPACE(ino) = copyto - sizeof(u_short) * (ino[0]+3); 279 OFFSET(ino) = copyto; 280 281 bufp = __get_buf ( ov_addr, bufp, 0 ); 282 if ( !bufp ) return(-1); 283 284 ino = (u_short *)bufp->page; 285 n = 1; 286 copyto = hashp->BSIZE; 287 moved = 0; 288 289 if ( last_bfp ) { 290 __free_ovflpage( last_bfp); 291 } 292 last_bfp = bufp; 293 } 294 295 if ( (ino[2] < REAL_KEY) && (ino[2] != OVFLPAGE) ) { 296 if (__big_split (old_bufp, 297 new_bufp, bufp, ov_addr, obucket, &ret)) { 298 return(-1); 299 } 300 old_bufp = ret.oldp; 301 if ( !old_bufp ) return(-1); 302 op = (u_short *)old_bufp->page; 303 new_bufp = ret.newp; 304 if ( !new_bufp ) return(-1); 305 np = (u_short *)new_bufp->page; 306 bufp = ret.nextp; 307 if ( !bufp ) return(0); 308 cino = (char *)bufp->page; 309 ino = (u_short *)cino; 310 last_bfp = ret.nextp; 311 } 312 313 314 off = hashp->BSIZE; 315 for ( n = 1; (n < ino[0]) && (ino[n+1] >= REAL_KEY); n += 2 ) { 316 cino = (char *)ino; 317 key.data = cino + ino[n]; 318 key.size = off - ino[n]; 319 val.data = cino + ino[n+1]; 320 val.size = ino[n] - ino[n+1]; 321 off = ino[n+1]; 322 323 if ( __call_hash ( key.data, key.size ) == obucket ) { 324 /* Keep on old page */ 325 if (PAIRFITS(op,(&key),(&val))) putpair((char *)op, &key, &val); 326 else { 327 old_bufp = __add_ovflpage ( old_bufp ); 328 if ( !old_bufp ) return(-1); 329 op = (u_short *)old_bufp->page; 330 putpair ((char *)op, &key, &val); 331 } 332 old_bufp->flags |= BUF_MOD; 333 } else { 334 /* Move to new page */ 335 if (PAIRFITS(np,(&key),(&val))) putpair((char *)np, &key, &val); 336 else { 337 new_bufp = __add_ovflpage ( new_bufp ); 338 if ( !new_bufp )return(-1); 339 np = (u_short *)new_bufp->page; 340 putpair ((char *)np, &key, &val); 341 } 342 new_bufp->flags |= BUF_MOD; 343 } 344 } 345 } 346 if ( last_bfp ) { 347 __free_ovflpage(last_bfp); 348 } 349 350 return (0); 351 } 352 /* 353 Add the given pair to the page 354 1 ==> failure 355 0 ==> OK 356 */ 357 extern int 358 __addel(bufp, key, val) 359 BUFHEAD *bufp; 360 DBT *key; 361 DBT *val; 362 { 363 register u_short *bp = (u_short *)bufp->page; 364 register u_short *sop; 365 int do_expand; 366 367 do_expand = 0; 368 while ( bp[0] && (bp[bp[0]] < REAL_KEY) ) { 369 /* Exception case */ 370 if ( bp[2] < REAL_KEY ) { 371 /* This is a big-keydata pair */ 372 bufp = __add_ovflpage(bufp); 373 if ( !bufp ) { 374 return(-1); 375 } 376 bp = (u_short *)bufp->page; 377 } else { 378 /* Try to squeeze key on this page */ 379 if ( FREESPACE(bp) > PAIRSIZE(key,val) ) { 380 squeeze_key ( bp, key, val ); 381 return(0); 382 } else { 383 bufp = __get_buf ( bp[bp[0]-1], bufp, 0 ); 384 if (!bufp) { 385 return(-1); 386 } 387 bp = (u_short *)bufp->page; 388 } 389 } 390 } 391 392 if ( PAIRFITS(bp,key,val) ) putpair (bufp->page, key, val); 393 else { 394 do_expand = 1; 395 bufp = __add_ovflpage ( bufp ); 396 if (!bufp)return(-1); 397 sop = (u_short *) bufp->page; 398 399 if ( PAIRFITS(sop, key, val) ) putpair ( (char *)sop, key, val ); 400 else if ( __big_insert ( bufp, key, val ) ) { 401 return(-1); 402 } 403 } 404 bufp->flags |= BUF_MOD; 405 /* 406 If the average number of keys per bucket exceeds the fill factor, 407 expand the table 408 */ 409 hashp->NKEYS++; 410 if (do_expand || 411 (hashp->NKEYS / (hashp->MAX_BUCKET+1) > hashp->FFACTOR) ) { 412 return(__expand_table()); 413 } 414 return(0); 415 } 416 417 /* 418 returns a pointer, NULL on error 419 */ 420 extern BUFHEAD * 421 __add_ovflpage ( bufp ) 422 BUFHEAD *bufp; 423 { 424 register u_short *sp = (u_short *)bufp->page; 425 426 u_short ovfl_num; 427 u_short ndx, newoff; 428 char *op; 429 DBT okey, oval; 430 #ifdef DEBUG1 431 int tmp1, tmp2; 432 #endif 433 434 bufp->flags |= BUF_MOD; 435 ovfl_num = overflow_page (); 436 #ifdef DEBUG1 437 tmp1 = bufp->addr; 438 tmp2 = bufp->ovfl?bufp->ovfl->addr:0; 439 #endif 440 if (!ovfl_num || !(bufp->ovfl = __get_buf ( ovfl_num, bufp, 1 ))) { 441 return(NULL); 442 } 443 bufp->ovfl->flags |= BUF_MOD; 444 #ifdef DEBUG1 445 fprintf ( stderr, "ADDOVFLPAGE: %d->ovfl was %d is now %d\n", tmp1, tmp2, 446 bufp->ovfl->addr ); 447 #endif 448 ndx = sp[0]; 449 /* 450 Since a pair is allocated on a page only if there's room 451 to add an overflow page, we know that the OVFL information 452 will fit on the page 453 */ 454 sp[ndx+4] = OFFSET(sp); 455 sp[ndx+3] = FREESPACE(sp) - OVFLSIZE; 456 sp[ndx+1] = ovfl_num; 457 sp[ndx+2] = OVFLPAGE; 458 sp[0] = ndx+2; 459 #ifdef HASH_STATISTICS 460 hash_overflows++; 461 #endif 462 return(bufp->ovfl); 463 } 464 465 /* 466 0 indicates SUCCESS 467 -1 indicates FAILURE 468 */ 469 extern int 470 __get_page ( p, bucket, is_bucket, is_disk, is_bitmap ) 471 char *p; 472 int bucket; 473 int is_bucket; 474 int is_disk; 475 int is_bitmap; 476 { 477 register int size; 478 register int fd; 479 register int page; 480 u_short *bp; 481 int rsize; 482 483 fd = hashp->fp; 484 size = hashp->BSIZE; 485 486 if ( !fd || (hashp->new_file && !is_disk) ) { 487 PAGE_INIT(p); 488 return(0); 489 } 490 491 if ( is_bucket) page = BUCKET_TO_PAGE (bucket); 492 else page = OADDR_TO_PAGE (bucket); 493 if ((lseek ( fd, page << hashp->BSHIFT, L_SET ) == -1) || 494 ((rsize = read ( fd, p, size )) == -1 )) { 495 return(-1); 496 } 497 bp = (u_short *)p; 498 if ( !rsize ) { 499 bp[0] = 0; /* We hit the EOF, so initialize a new page */ 500 } else if ( rsize != size ) { 501 errno = EFTYPE; 502 return(-1); 503 } 504 if (!bp[0]) { 505 PAGE_INIT(p); 506 } else if ( hashp->LORDER != BYTE_ORDER ) { 507 register int i; 508 register int max; 509 510 if ( is_bitmap ) { 511 max = hashp->BSIZE >> 2; /* divide by 4 */ 512 for ( i=0; i < max; i++ ) { 513 BLSWAP(((long *)p)[i]); 514 } 515 } else { 516 BSSWAP(bp[0]); 517 max = bp[0] + 2; 518 for ( i=1; i <= max; i++ ) { 519 BSSWAP(bp[i]); 520 } 521 } 522 } 523 return (0); 524 } 525 526 /* 527 Write page p to disk 528 -1==>failure 529 0==> OK 530 */ 531 extern int 532 __put_page ( p, bucket, is_bucket, is_bitmap ) 533 char *p; 534 int bucket; 535 int is_bucket; 536 int is_bitmap; 537 { 538 register int size; 539 register int fd; 540 register int page; 541 int wsize; 542 543 size = hashp->BSIZE; 544 if ( !hashp->fp && open_temp() ) return (1); 545 fd = hashp->fp; 546 547 if ( hashp->LORDER != BYTE_ORDER ) { 548 register int i; 549 register int max; 550 551 if ( is_bitmap ) { 552 max = hashp->BSIZE >> 2; /* divide by 4 */ 553 for ( i=0; i < max; i++ ) { 554 BLSWAP(((long *)p)[i]); 555 } 556 } else { 557 max = ((u_short *)p)[0] + 2; 558 for ( i=0; i <= max; i++ ) { 559 BSSWAP(((u_short *)p)[i]); 560 } 561 } 562 } 563 if (is_bucket ) page = BUCKET_TO_PAGE (bucket); 564 else page = OADDR_TO_PAGE ( bucket ); 565 if ((lseek ( fd, page << hashp->BSHIFT, L_SET ) == -1) || 566 ((wsize = write ( fd, p, size )) == -1 )) { 567 /* Errno is set */ 568 return(-1); 569 } 570 if ( wsize != size ) { 571 errno = EFTYPE; 572 return(-1); 573 } 574 return(0); 575 } 576 #define BYTE_MASK ((1 << INT_BYTE_SHIFT) -1) 577 /* 578 Initialize a new bitmap page. Bitmap pages are left in memory 579 once they are read in. 580 */ 581 extern u_long * 582 __init_bitmap(pnum, nbits, ndx) 583 u_short pnum; 584 int nbits; 585 int ndx; 586 { 587 u_long *ip; 588 int clearints; 589 int clearbytes; 590 591 if ( !(ip = (u_long *)malloc (hashp->BSIZE)) ) return (NULL); 592 clearints = ((nbits - 1) >> INT_BYTE_SHIFT) + 1; 593 clearbytes = clearints << INT_TO_BYTE; 594 memset ((char *)ip, 0, clearbytes ); 595 memset ( ((char *) ip) + clearbytes, 0xFF, 596 hashp->BSIZE-clearbytes ); 597 ip[clearints-1] = ALL_SET << (nbits & BYTE_MASK); 598 SETBIT(ip, 0); 599 hashp->BITMAPS[ndx] = pnum; 600 hashp->mapp[ndx] = ip; 601 return(ip); 602 } 603 static int 604 first_free ( map ) 605 u_long map; 606 { 607 register u_long mask; 608 register u_long i; 609 610 mask = 0x1; 611 for ( i=0; i < BITS_PER_MAP; i++ ) { 612 if ( !(mask & map) ) return(i); 613 mask = mask << 1; 614 } 615 return ( i ); 616 } 617 618 static u_short 619 overflow_page ( ) 620 { 621 register int max_free; 622 register int splitnum; 623 register u_long *freep; 624 register int offset; 625 u_short addr; 626 int in_use_bits; 627 int free_page, free_bit; 628 int i, j, bit; 629 #ifdef DEBUG2 630 int tmp1, tmp2; 631 #endif 632 633 splitnum = __log2(hashp->MAX_BUCKET); 634 max_free = hashp->SPARES[splitnum]; 635 636 free_page = (max_free-1) >> (hashp->BSHIFT + BYTE_SHIFT); 637 free_bit = (max_free-1) & ((hashp->BSIZE << BYTE_SHIFT) - 1); 638 639 /* Look through all the free maps to find the first free block */ 640 for ( i = 0; i <= free_page; i++ ) { 641 if (!(freep = (u_long *)hashp->mapp[i]) ) return(NULL); 642 if ( i == free_page ) in_use_bits = free_bit; 643 else in_use_bits = (hashp->BSIZE << BYTE_SHIFT) -1; 644 645 for (j = 0, bit = 0; bit <= in_use_bits; j++, bit += BITS_PER_MAP ) { 646 if ( freep[j] != ALL_SET ) goto found; 647 } 648 } 649 /* No Free Page Found */ 650 hashp->SPARES[splitnum]++; 651 offset = hashp->SPARES[splitnum] - 652 (splitnum ? hashp->SPARES[splitnum-1] : 0); 653 654 /* Check if we need to allocate a new bitmap page */ 655 if ( free_bit == (hashp->BSIZE << BYTE_SHIFT) - 1 ) { 656 free_page++; 657 if ( free_page >= NCACHED ) { 658 fprintf ( stderr, 659 "HASH: Out of overflow pages. Increase page size\n" ); 660 return(NULL); 661 } 662 /* 663 This is tricky. The 1 indicates that you want the 664 new page allocated with 1 clear bit. Actually, you 665 are going to allocate 2 pages from this map. The first 666 is going to be the map page, the second is the overflow 667 page we were looking for. The init_bitmap routine 668 automatically, sets the first bit of itself to indicate 669 that the bitmap itself is in use. We would explicitly 670 set the second bit, but don't have to if we tell init_bitmap 671 not to leave it clear in the first place. 672 */ 673 __init_bitmap ( OADDR_OF(splitnum, offset), 1, free_page ); 674 hashp->SPARES[splitnum]++; 675 #ifdef DEBUG2 676 free_bit = 2; 677 #endif 678 offset++; 679 } else { 680 /* 681 Free_bit addresses the last used bit. Bump it to 682 address the first available bit. 683 */ 684 free_bit++; 685 SETBIT ( freep, free_bit ); 686 } 687 688 /* Calculate address of the new overflow page */ 689 if ( offset > SPLITMASK ) { 690 fprintf ( stderr, 691 "HASH: Out of overflow pages. Increase page size\n" ); 692 return(NULL); 693 } 694 addr = OADDR_OF(splitnum, offset); 695 #ifdef DEBUG2 696 fprintf ( stderr, "OVERFLOW_PAGE: ADDR: %d BIT: %d PAGE %d\n", 697 addr, free_bit, free_page ); 698 #endif 699 return(addr); 700 701 found: 702 bit = bit + first_free(freep[j]); 703 SETBIT(freep,bit); 704 #ifdef DEBUG2 705 tmp1 = bit; 706 tmp2 = i; 707 #endif 708 /* 709 Bits are addressed starting with 0, but overflow pages are 710 addressed beginning at 1. Bit is a bit addressnumber, so we 711 need to increment it to convert it to a page number. 712 */ 713 bit = 1 + bit + (i * (hashp->BSIZE << BYTE_SHIFT)); 714 715 /* Calculate the split number for this page */ 716 for ( i = 0; (i < splitnum) && (bit > hashp->SPARES[i]); i++ ); 717 offset =(i ? bit - hashp->SPARES[i-1] : bit ); 718 if ( offset >= SPLITMASK ) return(NULL);/* Out of overflow pages */ 719 addr = OADDR_OF(i, offset); 720 #ifdef DEBUG2 721 fprintf ( stderr, "OVERFLOW_PAGE: ADDR: %d BIT: %d PAGE %d\n", 722 addr, tmp1, tmp2 ); 723 #endif 724 725 /* Allocate and return the overflow page */ 726 return (addr); 727 } 728 729 /* 730 Mark this overflow page as free. 731 */ 732 __free_ovflpage ( obufp ) 733 BUFHEAD *obufp; 734 { 735 register u_short addr = obufp->addr; 736 int free_page, free_bit; 737 int bit_address; 738 u_short ndx; 739 u_long *freep; 740 int j; 741 742 #ifdef DEBUG1 743 fprintf ( stderr, "Freeing %d\n", addr ); 744 #endif 745 ndx = (((u_short)addr) >> SPLITSHIFT); 746 bit_address = (ndx ? hashp->SPARES[ndx-1] : 0) + (addr & SPLITMASK) - 1; 747 free_page = (bit_address >> (hashp->BSHIFT + BYTE_SHIFT)); 748 free_bit = bit_address & ((hashp->BSIZE << BYTE_SHIFT) - 1); 749 750 freep = hashp->mapp[free_page]; 751 assert(freep); 752 CLRBIT(freep, free_bit); 753 #ifdef DEBUG2 754 fprintf ( stderr, "FREE_OVFLPAGE: ADDR: %d BIT: %d PAGE %d\n", 755 obufp->addr, free_bit, free_page ); 756 #endif 757 __reclaim_buf ( obufp ); 758 return; 759 } 760 761 /* 762 0 success 763 -1 failure 764 */ 765 static int 766 open_temp() 767 { 768 sigset_t set, oset; 769 char *namestr = "_hashXXXXXX"; 770 771 /* Block signals; make sure file goes away at process exit. */ 772 sigemptyset(&set); 773 sigaddset(&set, SIGHUP); 774 sigaddset(&set, SIGINT); 775 sigaddset(&set, SIGQUIT); 776 sigaddset(&set, SIGTERM); 777 (void)sigprocmask(SIG_BLOCK, &set, &oset); 778 if ((hashp->fp = mkstemp ( namestr )) != -1) { 779 (void)unlink(namestr); 780 (void)fcntl(hashp->fp, F_SETFD, 1); 781 } 782 (void)sigprocmask(SIG_SETMASK, &oset, (sigset_t *)NULL); 783 return(hashp->fp != -1 ? 0 : -1); 784 } 785 786 /* 787 We have to know that the key will fit, but the 788 last entry on the page is an overflow pair, so we 789 need to shift things. 790 */ 791 static void 792 squeeze_key ( sp, key, val ) 793 u_short *sp; 794 DBT *key; 795 DBT *val; 796 { 797 register char *p = (char *)sp; 798 u_short free_space, off; 799 u_short pageno, n; 800 801 n = sp[0]; 802 free_space = FREESPACE(sp); 803 off = OFFSET(sp); 804 805 pageno = sp[n-1]; 806 off -= key->size; 807 sp[n-1] = off; 808 bcopy ( key->data, p + off, key->size ); 809 off -= val->size; 810 sp[n] = off; 811 bcopy ( val->data, p + off, val->size ); 812 sp[0] = n+2; 813 sp[n+1] = pageno; 814 sp[n+2] = OVFLPAGE; 815 FREESPACE(sp) = free_space - PAIRSIZE(key,val); 816 OFFSET(sp) = off; 817 } 818 819 #ifdef DEBUG4 820 print_chain ( addr ) 821 short addr; 822 { 823 BUFHEAD *bufp; 824 short *bp; 825 short oaddr; 826 827 fprintf ( stderr, "%d ", addr ); 828 bufp = __get_buf ( (int)addr, NULL, 0 ); 829 bp = (short *)bufp->page; 830 while ( bp[0] && 831 ((bp[bp[0]] == OVFLPAGE) || 832 ((bp[0] > 2) && bp[2] < REAL_KEY))) { 833 oaddr = bp[bp[0]-1]; 834 fprintf ( stderr, "%d ", (int)oaddr ); 835 bufp = __get_buf ( (int)oaddr, bufp, 0 ); 836 bp = (short *)bufp->page; 837 } 838 fprintf ( stderr, "\n" ); 839 } 840 #endif 841