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