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