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