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