1 #pragma ident "%Z%%M% %I% %E% SMI" 2 3 /*- 4 * Copyright (c) 1990, 1993, 1994 5 * The Regents of the University of California. All rights reserved. 6 * 7 * This code is derived from software contributed to Berkeley by 8 * Margo Seltzer. 9 * 10 * Redistribution and use in source and binary forms, with or without 11 * modification, are permitted provided that the following conditions 12 * are met: 13 * 1. Redistributions of source code must retain the above copyright 14 * notice, this list of conditions and the following disclaimer. 15 * 2. Redistributions in binary form must reproduce the above copyright 16 * notice, this list of conditions and the following disclaimer in the 17 * documentation and/or other materials provided with the distribution. 18 * 3. All advertising materials mentioning features or use of this software 19 * must display the following acknowledgement: 20 * This product includes software developed by the University of 21 * California, Berkeley and its contributors. 22 * 4. Neither the name of the University nor the names of its contributors 23 * may be used to endorse or promote products derived from this software 24 * without specific prior written permission. 25 * 26 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 27 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 28 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 29 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 30 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 31 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 32 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 33 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 34 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 35 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 36 * SUCH DAMAGE. 37 */ 38 39 #if defined(LIBC_SCCS) && !defined(lint) 40 static char sccsid[] = "@(#)hash_page.c 8.11 (Berkeley) 11/7/95"; 41 #endif /* LIBC_SCCS and not lint */ 42 43 /* 44 * PACKAGE: hashing 45 * 46 * DESCRIPTION: 47 * Page manipulation for hashing package. 48 * 49 * ROUTINES: 50 * 51 * External 52 * __get_page 53 * __add_ovflpage 54 * Internal 55 * overflow_page 56 * open_temp 57 */ 58 59 #include <sys/types.h> 60 61 #ifdef DEBUG 62 #include <assert.h> 63 #endif 64 #include <stdio.h> 65 #include <stdlib.h> 66 #include <string.h> 67 #include <unistd.h> 68 #include <libintl.h> 69 #include "db-int.h" 70 #include "hash.h" 71 #include "page.h" 72 #include "extern.h" 73 74 static int32_t add_bigptr __P((HTAB *, ITEM_INFO *, indx_t)); 75 static u_int32_t *fetch_bitmap __P((HTAB *, int32_t)); 76 static u_int32_t first_free __P((u_int32_t)); 77 static indx_t next_realkey __P((PAGE16 *, indx_t)); 78 static u_int16_t overflow_page __P((HTAB *)); 79 static void page_init __P((HTAB *, PAGE16 *, db_pgno_t, u_int8_t)); 80 static indx_t prev_realkey __P((PAGE16 *, indx_t)); 81 static void putpair __P((PAGE8 *, const DBT *, const DBT *)); 82 static void swap_page_header_in __P((PAGE16 *)); 83 static void swap_page_header_out __P((PAGE16 *)); 84 85 #ifdef DEBUG_SLOW 86 static void account_page(HTAB *, db_pgno_t, int); 87 #endif 88 89 u_int32_t 90 __get_item(hashp, cursorp, key, val, item_info) 91 HTAB *hashp; 92 CURSOR *cursorp; 93 DBT *key, *val; 94 ITEM_INFO *item_info; 95 { 96 db_pgno_t next_pgno; 97 int32_t i; 98 99 /* Check if we need to get a page. */ 100 if (!cursorp->pagep) { 101 if (cursorp->pgno == INVALID_PGNO) { 102 cursorp->pagep = 103 __get_page(hashp, cursorp->bucket, A_BUCKET); 104 cursorp->pgno = ADDR(cursorp->pagep); 105 cursorp->ndx = 0; 106 cursorp->pgndx = 0; 107 } else 108 cursorp->pagep = 109 __get_page(hashp, cursorp->pgno, A_RAW); 110 if (!cursorp->pagep) { 111 item_info->status = ITEM_ERROR; 112 return (-1); 113 } 114 } 115 if (item_info->seek_size && 116 FREESPACE(cursorp->pagep) > item_info->seek_size) 117 item_info->seek_found_page = cursorp->pgno; 118 119 if (cursorp->pgndx == NUM_ENT(cursorp->pagep)) { 120 /* Fetch next page. */ 121 if (NEXT_PGNO(cursorp->pagep) == INVALID_PGNO) { 122 item_info->status = ITEM_NO_MORE; 123 return (-1); 124 } 125 next_pgno = NEXT_PGNO(cursorp->pagep); 126 cursorp->pgndx = 0; 127 __put_page(hashp, cursorp->pagep, A_RAW, 0); 128 cursorp->pagep = __get_page(hashp, next_pgno, A_RAW); 129 if (!cursorp->pagep) { 130 item_info->status = ITEM_ERROR; 131 return (-1); 132 } 133 cursorp->pgno = next_pgno; 134 } 135 if (KEY_OFF(cursorp->pagep, cursorp->pgndx) != BIGPAIR) { 136 if ((i = prev_realkey(cursorp->pagep, cursorp->pgndx)) == 137 cursorp->pgndx) 138 key->size = hashp->hdr.bsize - 139 KEY_OFF(cursorp->pagep, cursorp->pgndx); 140 else 141 key->size = DATA_OFF(cursorp->pagep, i) - 142 KEY_OFF(cursorp->pagep, cursorp->pgndx); 143 } 144 145 /* 146 * All of this information will be set incorrectly for big keys, but 147 * it will be ignored anyway. 148 */ 149 val->size = KEY_OFF(cursorp->pagep, cursorp->pgndx) - 150 DATA_OFF(cursorp->pagep, cursorp->pgndx); 151 key->data = KEY(cursorp->pagep, cursorp->pgndx); 152 val->data = DATA(cursorp->pagep, cursorp->pgndx); 153 item_info->pgno = cursorp->pgno; 154 item_info->bucket = cursorp->bucket; 155 item_info->ndx = cursorp->ndx; 156 item_info->pgndx = cursorp->pgndx; 157 item_info->key_off = KEY_OFF(cursorp->pagep, cursorp->pgndx); 158 item_info->data_off = DATA_OFF(cursorp->pagep, cursorp->pgndx); 159 item_info->status = ITEM_OK; 160 161 return (0); 162 } 163 164 u_int32_t 165 __get_item_reset(hashp, cursorp) 166 HTAB *hashp; 167 CURSOR *cursorp; 168 { 169 if (cursorp->pagep) 170 __put_page(hashp, cursorp->pagep, A_RAW, 0); 171 cursorp->pagep = NULL; 172 cursorp->bucket = -1; 173 cursorp->ndx = 0; 174 cursorp->pgndx = 0; 175 cursorp->pgno = INVALID_PGNO; 176 return (0); 177 } 178 179 u_int32_t 180 __get_item_done(hashp, cursorp) 181 HTAB *hashp; 182 CURSOR *cursorp; 183 { 184 if (cursorp->pagep) 185 __put_page(hashp, cursorp->pagep, A_RAW, 0); 186 cursorp->pagep = NULL; 187 188 /* 189 * We don't throw out the page number since we might want to 190 * continue getting on this page. 191 */ 192 return (0); 193 } 194 195 u_int32_t 196 __get_item_first(hashp, cursorp, key, val, item_info) 197 HTAB *hashp; 198 CURSOR *cursorp; 199 DBT *key, *val; 200 ITEM_INFO *item_info; 201 { 202 __get_item_reset(hashp, cursorp); 203 cursorp->bucket = 0; 204 return (__get_item_next(hashp, cursorp, key, val, item_info)); 205 } 206 207 /* 208 * Returns a pointer to key/data pair on a page. In the case of bigkeys, 209 * just returns the page number and index of the bigkey pointer pair. 210 */ 211 u_int32_t 212 __get_item_next(hashp, cursorp, key, val, item_info) 213 HTAB *hashp; 214 CURSOR *cursorp; 215 DBT *key, *val; 216 ITEM_INFO *item_info; 217 { 218 int status; 219 220 status = __get_item(hashp, cursorp, key, val, item_info); 221 cursorp->ndx++; 222 cursorp->pgndx++; 223 return (status); 224 } 225 226 /* 227 * Put a non-big pair on a page. 228 */ 229 static void 230 putpair(p, key, val) 231 PAGE8 *p; 232 const DBT *key, *val; 233 { 234 u_int16_t *pagep, n, off; 235 236 pagep = (PAGE16 *)p; 237 238 /* Items on the page are 0-indexed. */ 239 n = NUM_ENT(pagep); 240 off = OFFSET(pagep) - key->size + 1; 241 memmove(p + off, key->data, key->size); 242 KEY_OFF(pagep, n) = off; 243 244 off -= val->size; 245 memmove(p + off, val->data, val->size); 246 DATA_OFF(pagep, n) = off; 247 248 /* Adjust page info. */ 249 NUM_ENT(pagep) = n + 1; 250 OFFSET(pagep) = off - 1; 251 } 252 253 /* 254 * Returns the index of the next non-bigkey pair after n on the page. 255 * Returns -1 if there are no more non-big things on the page. 256 */ 257 static indx_t 258 #ifdef __STDC__ 259 next_realkey(PAGE16 * pagep, indx_t n) 260 #else 261 next_realkey(pagep, n) 262 PAGE16 *pagep; 263 u_int32_t n; 264 #endif 265 { 266 indx_t i; 267 268 for (i = n + 1; i < NUM_ENT(pagep); i++) 269 if (KEY_OFF(pagep, i) != BIGPAIR) 270 return (i); 271 return (-1); 272 } 273 274 /* 275 * Returns the index of the previous non-bigkey pair after n on the page. 276 * Returns n if there are no previous non-big things on the page. 277 */ 278 static indx_t 279 #ifdef __STDC__ 280 prev_realkey(PAGE16 * pagep, indx_t n) 281 #else 282 prev_realkey(pagep, n) 283 PAGE16 *pagep; 284 u_int32_t n; 285 #endif 286 { 287 int32_t i; 288 289 /* Need a signed value to do the compare properly. */ 290 for (i = n - 1; i > -1; i--) 291 if (KEY_OFF(pagep, i) != BIGPAIR) 292 return (i); 293 return (n); 294 } 295 296 /* 297 * Returns: 298 * 0 OK 299 * -1 error 300 */ 301 extern int32_t 302 __delpair(hashp, cursorp, item_info) 303 HTAB *hashp; 304 CURSOR *cursorp; 305 ITEM_INFO *item_info; 306 { 307 PAGE16 *pagep; 308 indx_t ndx; 309 short check_ndx; 310 int16_t delta, len, next_key; 311 int32_t n; 312 u_int8_t *src, *dest; 313 314 ndx = cursorp->pgndx; 315 if (!cursorp->pagep) { 316 pagep = __get_page(hashp, cursorp->pgno, A_RAW); 317 if (!pagep) 318 return (-1); 319 /* 320 * KLUGE: pgndx has gone one too far, because cursor points 321 * to the _next_ item. Use pgndx - 1. 322 */ 323 --ndx; 324 } else 325 pagep = cursorp->pagep; 326 #ifdef DEBUG 327 assert(ADDR(pagep) == cursorp->pgno); 328 #endif 329 330 if (KEY_OFF(pagep, ndx) == BIGPAIR) { 331 delta = 0; 332 __big_delete(hashp, pagep, ndx); 333 } else { 334 /* 335 * Compute "delta", the amount we have to shift all of the 336 * offsets. To find the delta, we need to make sure that 337 * we aren't looking at the DATA_OFF of a big/keydata pair. 338 */ 339 for (check_ndx = (short)(ndx - 1); 340 check_ndx >= 0 && KEY_OFF(pagep, check_ndx) == BIGPAIR; 341 check_ndx--); 342 if (check_ndx < 0) 343 delta = hashp->hdr.bsize - DATA_OFF(pagep, ndx); 344 else 345 delta = 346 DATA_OFF(pagep, check_ndx) - DATA_OFF(pagep, ndx); 347 348 /* 349 * The hard case: we want to remove something other than 350 * the last item on the page. We need to shift data and 351 * offsets down. 352 */ 353 if (ndx != NUM_ENT(pagep) - 1) { 354 /* 355 * Move the data: src is the address of the last data 356 * item on the page. 357 */ 358 src = (u_int8_t *)pagep + OFFSET(pagep) + 1; 359 /* 360 * Length is the distance between where to start 361 * deleting and end of the data on the page. 362 */ 363 len = DATA_OFF(pagep, ndx) - (OFFSET(pagep) + 1); 364 /* 365 * Dest is the location of the to-be-deleted item 366 * occupied - length. 367 */ 368 if (check_ndx < 0) 369 dest = 370 (u_int8_t *)pagep + hashp->hdr.bsize - len; 371 else 372 dest = (u_int8_t *)pagep + 373 DATA_OFF(pagep, (check_ndx)) - len; 374 memmove(dest, src, len); 375 } 376 } 377 378 /* Adjust the offsets. */ 379 for (n = ndx; n < NUM_ENT(pagep) - 1; n++) 380 if (KEY_OFF(pagep, (n + 1)) != BIGPAIR) { 381 next_key = next_realkey(pagep, n); 382 #ifdef DEBUG 383 assert(next_key != -1); 384 #endif 385 KEY_OFF(pagep, n) = KEY_OFF(pagep, (n + 1)) + delta; 386 DATA_OFF(pagep, n) = DATA_OFF(pagep, (n + 1)) + delta; 387 } else { 388 KEY_OFF(pagep, n) = KEY_OFF(pagep, (n + 1)); 389 DATA_OFF(pagep, n) = DATA_OFF(pagep, (n + 1)); 390 } 391 392 /* Adjust page metadata. */ 393 OFFSET(pagep) = OFFSET(pagep) + delta; 394 NUM_ENT(pagep) = NUM_ENT(pagep) - 1; 395 396 --hashp->hdr.nkeys; 397 398 /* Is this page now an empty overflow page? If so, free it. */ 399 if (TYPE(pagep) == HASH_OVFLPAGE && NUM_ENT(pagep) == 0) { 400 PAGE16 *empty_page; 401 db_pgno_t to_find, next_pgno, link_page; 402 403 /* 404 * We need to go back to the first page in the chain and 405 * look for this page so that we can update the previous 406 * page's NEXT_PGNO field. 407 */ 408 to_find = ADDR(pagep); 409 empty_page = pagep; 410 link_page = NEXT_PGNO(empty_page); 411 pagep = __get_page(hashp, item_info->bucket, A_BUCKET); 412 if (!pagep) 413 return (-1); 414 while (NEXT_PGNO(pagep) != to_find) { 415 next_pgno = NEXT_PGNO(pagep); 416 #ifdef DEBUG 417 assert(next_pgno != INVALID_PGNO); 418 #endif 419 __put_page(hashp, pagep, A_RAW, 0); 420 pagep = __get_page(hashp, next_pgno, A_RAW); 421 if (!pagep) 422 return (-1); 423 } 424 425 /* 426 * At this point, pagep should point to the page before the 427 * page to be deleted. 428 */ 429 NEXT_PGNO(pagep) = link_page; 430 if (item_info->pgno == to_find) { 431 item_info->pgno = ADDR(pagep); 432 item_info->pgndx = NUM_ENT(pagep); 433 item_info->seek_found_page = ADDR(pagep); 434 } 435 __delete_page(hashp, empty_page, A_OVFL); 436 } 437 __put_page(hashp, pagep, A_RAW, 1); 438 439 return (0); 440 } 441 442 extern int32_t 443 __split_page(hashp, obucket, nbucket) 444 HTAB *hashp; 445 u_int32_t obucket, nbucket; 446 { 447 DBT key, val; 448 ITEM_INFO old_ii, new_ii; 449 PAGE16 *old_pagep, *temp_pagep; 450 db_pgno_t next_pgno; 451 int32_t off; 452 u_int16_t n; 453 int8_t base_page; 454 455 off = hashp->hdr.bsize; 456 old_pagep = __get_page(hashp, obucket, A_BUCKET); 457 458 base_page = 1; 459 460 temp_pagep = hashp->split_buf; 461 memcpy(temp_pagep, old_pagep, hashp->hdr.bsize); 462 463 page_init(hashp, old_pagep, ADDR(old_pagep), HASH_PAGE); 464 __put_page(hashp, old_pagep, A_RAW, 1); 465 466 old_ii.pgno = BUCKET_TO_PAGE(obucket); 467 new_ii.pgno = BUCKET_TO_PAGE(nbucket); 468 old_ii.bucket = obucket; 469 new_ii.bucket = nbucket; 470 old_ii.seek_found_page = new_ii.seek_found_page = 0; 471 472 while (temp_pagep != 0) { 473 off = hashp->hdr.bsize; 474 for (n = 0; n < NUM_ENT(temp_pagep); n++) { 475 if (KEY_OFF(temp_pagep, n) == BIGPAIR) { 476 __get_bigkey(hashp, temp_pagep, n, &key); 477 if (__call_hash(hashp, 478 key.data, key.size) == obucket) 479 add_bigptr(hashp, &old_ii, 480 DATA_OFF(temp_pagep, n)); 481 else 482 add_bigptr(hashp, &new_ii, 483 DATA_OFF(temp_pagep, n)); 484 } else { 485 key.size = off - KEY_OFF(temp_pagep, n); 486 key.data = KEY(temp_pagep, n); 487 off = KEY_OFF(temp_pagep, n); 488 val.size = off - DATA_OFF(temp_pagep, n); 489 val.data = DATA(temp_pagep, n); 490 if (__call_hash(hashp, 491 key.data, key.size) == obucket) 492 __addel(hashp, &old_ii, &key, &val, 493 NO_EXPAND, 1); 494 else 495 __addel(hashp, &new_ii, &key, &val, 496 NO_EXPAND, 1); 497 off = DATA_OFF(temp_pagep, n); 498 } 499 } 500 next_pgno = NEXT_PGNO(temp_pagep); 501 502 /* Clear temp_page; if it's an overflow page, free it. */ 503 if (!base_page) 504 __delete_page(hashp, temp_pagep, A_OVFL); 505 else 506 base_page = 0; 507 if (next_pgno != INVALID_PGNO) 508 temp_pagep = __get_page(hashp, next_pgno, A_RAW); 509 else 510 break; 511 } 512 return (0); 513 } 514 515 /* 516 * Add the given pair to the page. 517 * 518 * 519 * Returns: 520 * 0 ==> OK 521 * -1 ==> failure 522 */ 523 extern int32_t 524 #ifdef __STDC__ 525 __addel(HTAB *hashp, ITEM_INFO *item_info, const DBT *key, const DBT *val, 526 u_int32_t num_items, const u_int8_t expanding) 527 #else 528 __addel(hashp, item_info, key, val, num_items, expanding) 529 HTAB *hashp; 530 ITEM_INFO *item_info; 531 const DBT *key, *val; 532 u_int32_t num_items; 533 const u_int32_t expanding; 534 #endif 535 { 536 PAGE16 *pagep; 537 int32_t do_expand; 538 db_pgno_t next_pgno; 539 540 do_expand = 0; 541 542 pagep = __get_page(hashp, 543 item_info->seek_found_page != 0 ? 544 item_info->seek_found_page : item_info->pgno, A_RAW); 545 if (!pagep) 546 return (-1); 547 548 /* Advance to first page in chain with room for item. */ 549 while (NUM_ENT(pagep) && NEXT_PGNO(pagep) != INVALID_PGNO) { 550 /* 551 * This may not be the end of the chain, but the pair may fit 552 * anyway. 553 */ 554 if (ISBIG(PAIRSIZE(key, val), hashp) && BIGPAIRFITS(pagep)) 555 break; 556 if (PAIRFITS(pagep, key, val)) 557 break; 558 next_pgno = NEXT_PGNO(pagep); 559 __put_page(hashp, pagep, A_RAW, 0); 560 pagep = (PAGE16 *)__get_page(hashp, next_pgno, A_RAW); 561 if (!pagep) 562 return (-1); 563 } 564 565 if ((ISBIG(PAIRSIZE(key, val), hashp) && 566 !BIGPAIRFITS(pagep)) || 567 (!ISBIG(PAIRSIZE(key, val), hashp) && 568 !PAIRFITS(pagep, key, val))) { 569 do_expand = 1; 570 pagep = __add_ovflpage(hashp, pagep); 571 if (!pagep) 572 return (-1); 573 574 if ((ISBIG(PAIRSIZE(key, val), hashp) && 575 !BIGPAIRFITS(pagep)) || 576 (!ISBIG(PAIRSIZE(key, val), hashp) && 577 !PAIRFITS(pagep, key, val))) { 578 __put_page(hashp, pagep, A_RAW, 0); 579 return (-1); 580 } 581 } 582 583 /* At this point, we know the page fits, so we just add it */ 584 585 if (ISBIG(PAIRSIZE(key, val), hashp)) { 586 if (__big_insert(hashp, pagep, key, val)) 587 return (-1); 588 } else { 589 putpair((PAGE8 *)pagep, key, val); 590 } 591 592 /* 593 * For splits, we are going to update item_info's page number 594 * field, so that we can easily return to the same page the 595 * next time we come in here. For other operations, this shouldn't 596 * matter, since adds are the last thing that happens before we 597 * return to the user program. 598 */ 599 item_info->pgno = ADDR(pagep); 600 601 if (!expanding) 602 hashp->hdr.nkeys++; 603 604 /* Kludge: if this is a big page, then it's already been put. */ 605 if (!ISBIG(PAIRSIZE(key, val), hashp)) 606 __put_page(hashp, pagep, A_RAW, 1); 607 608 if (expanding) 609 item_info->caused_expand = 0; 610 else 611 switch (num_items) { 612 case NO_EXPAND: 613 item_info->caused_expand = 0; 614 break; 615 case UNKNOWN: 616 item_info->caused_expand |= 617 (hashp->hdr.nkeys / hashp->hdr.max_bucket) > 618 hashp->hdr.ffactor || 619 item_info->pgndx > hashp->hdr.ffactor; 620 break; 621 default: 622 item_info->caused_expand = 623 num_items > hashp->hdr.ffactor ? 1 : do_expand; 624 break; 625 } 626 return (0); 627 } 628 629 /* 630 * Special __addel used in big splitting; this one just puts the pointer 631 * to an already-allocated big page in the appropriate bucket. 632 */ 633 static int32_t 634 #ifdef __STDC__ 635 add_bigptr(HTAB * hashp, ITEM_INFO * item_info, indx_t big_pgno) 636 #else 637 add_bigptr(hashp, item_info, big_pgno) 638 HTAB *hashp; 639 ITEM_INFO *item_info; 640 u_int32_t big_pgno; 641 #endif 642 { 643 PAGE16 *pagep; 644 db_pgno_t next_pgno; 645 646 pagep = __get_page(hashp, item_info->bucket, A_BUCKET); 647 if (!pagep) 648 return (-1); 649 650 /* 651 * Note: in __addel(), we used item_info->pgno for the beginning of 652 * our search for space. Now, we use item_info->bucket, since we 653 * know that the space required by a big pair on the base page is 654 * quite small, and we may very well find that space early in the 655 * chain. 656 */ 657 658 /* Find first page in chain that has space for a big pair. */ 659 while (NUM_ENT(pagep) && (NEXT_PGNO(pagep) != INVALID_PGNO)) { 660 if (BIGPAIRFITS(pagep)) 661 break; 662 next_pgno = NEXT_PGNO(pagep); 663 __put_page(hashp, pagep, A_RAW, 0); 664 pagep = __get_page(hashp, next_pgno, A_RAW); 665 if (!pagep) 666 return (-1); 667 } 668 if (!BIGPAIRFITS(pagep)) { 669 pagep = __add_ovflpage(hashp, pagep); 670 if (!pagep) 671 return (-1); 672 #ifdef DEBUG 673 assert(BIGPAIRFITS(pagep)); 674 #endif 675 } 676 KEY_OFF(pagep, NUM_ENT(pagep)) = BIGPAIR; 677 DATA_OFF(pagep, NUM_ENT(pagep)) = big_pgno; 678 NUM_ENT(pagep) = NUM_ENT(pagep) + 1; 679 680 __put_page(hashp, pagep, A_RAW, 1); 681 682 return (0); 683 } 684 685 /* 686 * 687 * Returns: 688 * pointer on success 689 * NULL on error 690 */ 691 extern PAGE16 * 692 __add_ovflpage(hashp, pagep) 693 HTAB *hashp; 694 PAGE16 *pagep; 695 { 696 PAGE16 *new_pagep; 697 u_int16_t ovfl_num; 698 699 /* Check if we are dynamically determining the fill factor. */ 700 if (hashp->hdr.ffactor == DEF_FFACTOR) { 701 hashp->hdr.ffactor = NUM_ENT(pagep) >> 1; 702 if (hashp->hdr.ffactor < MIN_FFACTOR) 703 hashp->hdr.ffactor = MIN_FFACTOR; 704 } 705 ovfl_num = overflow_page(hashp); 706 if (!ovfl_num) 707 return (NULL); 708 709 if (__new_page(hashp, (u_int32_t)ovfl_num, A_OVFL) != 0) 710 return (NULL); 711 712 if (!ovfl_num || !(new_pagep = __get_page(hashp, ovfl_num, A_OVFL))) 713 return (NULL); 714 715 NEXT_PGNO(pagep) = (db_pgno_t)OADDR_TO_PAGE(ovfl_num); 716 TYPE(new_pagep) = HASH_OVFLPAGE; 717 718 __put_page(hashp, pagep, A_RAW, 1); 719 720 #ifdef HASH_STATISTICS 721 hash_overflows++; 722 #endif 723 return (new_pagep); 724 } 725 726 /* 727 * 728 * Returns: 729 * pointer on success 730 * NULL on error 731 */ 732 extern PAGE16 * 733 #ifdef __STDC__ 734 __add_bigpage(HTAB * hashp, PAGE16 * pagep, indx_t ndx, const u_int8_t 735 is_basepage) 736 #else 737 __add_bigpage(hashp, pagep, ndx, is_basepage) 738 HTAB *hashp; 739 PAGE16 *pagep; 740 u_int32_t ndx; 741 const u_int32_t is_basepage; 742 #endif 743 { 744 PAGE16 *new_pagep; 745 u_int16_t ovfl_num; 746 747 ovfl_num = overflow_page(hashp); 748 if (!ovfl_num) 749 return (NULL); 750 751 if (__new_page(hashp, (u_int32_t)ovfl_num, A_OVFL) != 0) 752 return (NULL); 753 754 if (!ovfl_num || !(new_pagep = __get_page(hashp, ovfl_num, A_OVFL))) 755 return (NULL); 756 757 if (is_basepage) { 758 KEY_OFF(pagep, ndx) = BIGPAIR; 759 DATA_OFF(pagep, ndx) = (indx_t)ovfl_num; 760 } else 761 NEXT_PGNO(pagep) = ADDR(new_pagep); 762 763 __put_page(hashp, pagep, A_RAW, 1); 764 765 TYPE(new_pagep) = HASH_BIGPAGE; 766 767 #ifdef HASH_STATISTICS 768 hash_bigpages++; 769 #endif 770 return (new_pagep); 771 } 772 773 static void 774 #ifdef __STDC__ 775 page_init(HTAB * hashp, PAGE16 * pagep, db_pgno_t pgno, u_int8_t type) 776 #else 777 page_init(hashp, pagep, pgno, type) 778 HTAB *hashp; 779 PAGE16 *pagep; 780 db_pgno_t pgno; 781 u_int32_t type; 782 #endif 783 { 784 NUM_ENT(pagep) = 0; 785 PREV_PGNO(pagep) = NEXT_PGNO(pagep) = INVALID_PGNO; 786 TYPE(pagep) = type; 787 OFFSET(pagep) = hashp->hdr.bsize - 1; 788 /* 789 * Note: since in the current version ADDR(pagep) == PREV_PGNO(pagep), 790 * make sure that ADDR(pagep) is set after resetting PREV_PGNO(pagep). 791 * We reset PREV_PGNO(pagep) just in case the macros are changed. 792 */ 793 ADDR(pagep) = pgno; 794 795 return; 796 } 797 798 int32_t 799 __new_page(hashp, addr, addr_type) 800 HTAB *hashp; 801 u_int32_t addr; 802 int32_t addr_type; 803 { 804 db_pgno_t paddr; 805 PAGE16 *pagep; 806 807 switch (addr_type) { /* Convert page number. */ 808 case A_BUCKET: 809 paddr = BUCKET_TO_PAGE(addr); 810 break; 811 case A_OVFL: 812 case A_BITMAP: 813 paddr = OADDR_TO_PAGE(addr); 814 break; 815 default: 816 paddr = addr; 817 break; 818 } 819 pagep = mpool_new(hashp->mp, &paddr, MPOOL_PAGE_REQUEST); 820 if (!pagep) 821 return (-1); 822 #if DEBUG_SLOW 823 account_page(hashp, paddr, 1); 824 #endif 825 826 if (addr_type != A_BITMAP) 827 page_init(hashp, pagep, paddr, HASH_PAGE); 828 829 __put_page(hashp, pagep, addr_type, 1); 830 831 return (0); 832 } 833 834 int32_t 835 __delete_page(hashp, pagep, page_type) 836 HTAB *hashp; 837 PAGE16 *pagep; 838 int32_t page_type; 839 { 840 if (page_type == A_OVFL) 841 __free_ovflpage(hashp, pagep); 842 return (mpool_delete(hashp->mp, pagep)); 843 } 844 845 static u_int8_t 846 is_bitmap_pgno(hashp, pgno) 847 HTAB *hashp; 848 db_pgno_t pgno; 849 { 850 int32_t i; 851 852 for (i = 0; i < hashp->nmaps; i++) 853 if (OADDR_TO_PAGE(hashp->hdr.bitmaps[i]) == pgno) 854 return (1); 855 return (0); 856 } 857 858 void 859 __pgin_routine(pg_cookie, pgno, page) 860 void *pg_cookie; 861 db_pgno_t pgno; 862 void *page; 863 { 864 HTAB *hashp; 865 PAGE16 *pagep; 866 int32_t max, i; 867 868 pagep = (PAGE16 *)page; 869 hashp = (HTAB *)pg_cookie; 870 871 /* 872 * There are the following cases for swapping: 873 * 0) New page that may be unitialized. 874 * 1) Bucket page or overflow page. Either swap 875 * the header or initialize the page. 876 * 2) Bitmap page. Swap the whole page! 877 * 3) Header pages. Not handled here; these are written directly 878 * to the file. 879 */ 880 881 if (NUM_ENT(pagep) == 0 && NEXT_PGNO(pagep) == 0 && 882 !is_bitmap_pgno(hashp, pgno)) { 883 /* XXX check for !0 LSN */ 884 page_init(hashp, pagep, pgno, HASH_PAGE); 885 return; 886 } 887 888 if (hashp->hdr.lorder == DB_BYTE_ORDER) 889 return; 890 if (is_bitmap_pgno(hashp, pgno)) { 891 max = hashp->hdr.bsize >> 2; /* divide by 4 bytes */ 892 for (i = 0; i < max; i++) 893 M_32_SWAP(((int32_t *)pagep)[i]); 894 } else 895 swap_page_header_in(pagep); 896 } 897 898 void 899 __pgout_routine(pg_cookie, pgno, page) 900 void *pg_cookie; 901 db_pgno_t pgno; 902 void *page; 903 { 904 HTAB *hashp; 905 PAGE16 *pagep; 906 int32_t i, max; 907 908 pagep = (PAGE16 *)page; 909 hashp = (HTAB *)pg_cookie; 910 911 /* 912 * There are the following cases for swapping: 913 * 1) Bucket page or overflow page. Just swap the header. 914 * 2) Bitmap page. Swap the whole page! 915 * 3) Header pages. Not handled here; these are written directly 916 * to the file. 917 */ 918 919 if (hashp->hdr.lorder == DB_BYTE_ORDER) 920 return; 921 if (is_bitmap_pgno(hashp, pgno)) { 922 max = hashp->hdr.bsize >> 2; /* divide by 4 bytes */ 923 for (i = 0; i < max; i++) 924 M_32_SWAP(((int32_t *)pagep)[i]); 925 } else 926 swap_page_header_out(pagep); 927 } 928 929 /* 930 * 931 * Returns: 932 * 0 ==> OK 933 * -1 ==>failure 934 */ 935 extern int32_t 936 __put_page(hashp, pagep, addr_type, is_dirty) 937 HTAB *hashp; 938 PAGE16 *pagep; 939 int32_t addr_type, is_dirty; 940 { 941 #if DEBUG_SLOW 942 account_page(hashp, 943 ((BKT *)((char *)pagep - sizeof(BKT)))->pgno, -1); 944 #endif 945 946 return (mpool_put(hashp->mp, pagep, (is_dirty ? MPOOL_DIRTY : 0))); 947 } 948 949 /* 950 * Returns: 951 * 0 indicates SUCCESS 952 * -1 indicates FAILURE 953 */ 954 extern PAGE16 * 955 __get_page(hashp, addr, addr_type) 956 HTAB *hashp; 957 u_int32_t addr; 958 int32_t addr_type; 959 { 960 PAGE16 *pagep; 961 db_pgno_t paddr; 962 963 switch (addr_type) { /* Convert page number. */ 964 case A_BUCKET: 965 paddr = BUCKET_TO_PAGE(addr); 966 break; 967 case A_OVFL: 968 case A_BITMAP: 969 paddr = OADDR_TO_PAGE(addr); 970 break; 971 default: 972 paddr = addr; 973 break; 974 } 975 pagep = (PAGE16 *)mpool_get(hashp->mp, paddr, 0); 976 977 #if DEBUG_SLOW 978 account_page(hashp, paddr, 1); 979 #endif 980 #ifdef DEBUG 981 assert(ADDR(pagep) == paddr || ADDR(pagep) == 0 || 982 addr_type == A_BITMAP || addr_type == A_HEADER); 983 #endif 984 985 return (pagep); 986 } 987 988 static void 989 swap_page_header_in(pagep) 990 PAGE16 *pagep; 991 { 992 u_int32_t i; 993 994 /* can leave type and filler alone, since they're 1-byte quantities */ 995 996 M_32_SWAP(PREV_PGNO(pagep)); 997 M_32_SWAP(NEXT_PGNO(pagep)); 998 M_16_SWAP(NUM_ENT(pagep)); 999 M_16_SWAP(OFFSET(pagep)); 1000 1001 for (i = 0; i < NUM_ENT(pagep); i++) { 1002 M_16_SWAP(KEY_OFF(pagep, i)); 1003 M_16_SWAP(DATA_OFF(pagep, i)); 1004 } 1005 } 1006 1007 static void 1008 swap_page_header_out(pagep) 1009 PAGE16 *pagep; 1010 { 1011 u_int32_t i; 1012 1013 for (i = 0; i < NUM_ENT(pagep); i++) { 1014 M_16_SWAP(KEY_OFF(pagep, i)); 1015 M_16_SWAP(DATA_OFF(pagep, i)) 1016 } 1017 1018 /* can leave type and filler alone, since they're 1-byte quantities */ 1019 1020 M_32_SWAP(PREV_PGNO(pagep)); 1021 M_32_SWAP(NEXT_PGNO(pagep)); 1022 M_16_SWAP(NUM_ENT(pagep)); 1023 M_16_SWAP(OFFSET(pagep)); 1024 } 1025 1026 #define BYTE_MASK ((1 << INT32_T_BYTE_SHIFT) -1) 1027 /* 1028 * Initialize a new bitmap page. Bitmap pages are left in memory 1029 * once they are read in. 1030 */ 1031 extern int32_t 1032 __ibitmap(hashp, pnum, nbits, ndx) 1033 HTAB *hashp; 1034 int32_t pnum, nbits, ndx; 1035 { 1036 u_int32_t *ip; 1037 int32_t clearbytes, clearints; 1038 1039 /* make a new bitmap page */ 1040 if (__new_page(hashp, pnum, A_BITMAP) != 0) 1041 return (1); 1042 if (!(ip = (u_int32_t *)__get_page(hashp, pnum, A_BITMAP))) 1043 return (1); 1044 hashp->nmaps++; 1045 clearints = ((nbits - 1) >> INT32_T_BYTE_SHIFT) + 1; 1046 clearbytes = clearints << INT32_T_TO_BYTE; 1047 (void)memset((int8_t *)ip, 0, clearbytes); 1048 (void)memset((int8_t *)ip + clearbytes, 1049 0xFF, hashp->hdr.bsize - clearbytes); 1050 ip[clearints - 1] = ALL_SET << (nbits & BYTE_MASK); 1051 SETBIT(ip, 0); 1052 hashp->hdr.bitmaps[ndx] = (u_int16_t)pnum; 1053 hashp->mapp[ndx] = ip; 1054 return (0); 1055 } 1056 1057 static u_int32_t 1058 first_free(map) 1059 u_int32_t map; 1060 { 1061 u_int32_t i, mask; 1062 1063 for (mask = 0x1, i = 0; i < BITS_PER_MAP; i++) { 1064 if (!(mask & map)) 1065 return (i); 1066 mask = mask << 1; 1067 } 1068 return (i); 1069 } 1070 1071 /* 1072 * returns 0 on error 1073 */ 1074 static u_int16_t 1075 overflow_page(hashp) 1076 HTAB *hashp; 1077 { 1078 u_int32_t *freep; 1079 int32_t bit, first_page, free_bit, free_page, i, in_use_bits, j; 1080 int32_t max_free, offset, splitnum; 1081 u_int16_t addr; 1082 #ifdef DEBUG2 1083 int32_t tmp1, tmp2; 1084 #endif 1085 1086 splitnum = hashp->hdr.ovfl_point; 1087 max_free = hashp->hdr.spares[splitnum]; 1088 1089 free_page = (max_free - 1) >> (hashp->hdr.bshift + BYTE_SHIFT); 1090 free_bit = (max_free - 1) & ((hashp->hdr.bsize << BYTE_SHIFT) - 1); 1091 1092 /* 1093 * Look through all the free maps to find the first free block. 1094 * The compiler under -Wall will complain that freep may be used 1095 * before being set, however, this loop will ALWAYS get executed 1096 * at least once, so freep is guaranteed to be set. 1097 */ 1098 first_page = hashp->hdr.last_freed >> (hashp->hdr.bshift + BYTE_SHIFT); 1099 for (i = first_page; i <= free_page; i++) { 1100 if (!(freep = fetch_bitmap(hashp, i))) 1101 return (0); 1102 if (i == free_page) 1103 in_use_bits = free_bit; 1104 else 1105 in_use_bits = (hashp->hdr.bsize << BYTE_SHIFT) - 1; 1106 1107 if (i == first_page) { 1108 bit = hashp->hdr.last_freed & 1109 ((hashp->hdr.bsize << BYTE_SHIFT) - 1); 1110 j = bit / BITS_PER_MAP; 1111 bit = bit & ~(BITS_PER_MAP - 1); 1112 } else { 1113 bit = 0; 1114 j = 0; 1115 } 1116 for (; bit <= in_use_bits; j++, bit += BITS_PER_MAP) 1117 if (freep[j] != ALL_SET) 1118 goto found; 1119 } 1120 1121 /* No Free Page Found */ 1122 hashp->hdr.last_freed = hashp->hdr.spares[splitnum]; 1123 hashp->hdr.spares[splitnum]++; 1124 offset = hashp->hdr.spares[splitnum] - 1125 (splitnum ? hashp->hdr.spares[splitnum - 1] : 0); 1126 1127 #define OVMSG "HASH: Out of overflow pages. Increase page size\n" 1128 1129 if (offset > SPLITMASK) { 1130 if (++splitnum >= NCACHED) { 1131 (void)write(STDERR_FILENO, OVMSG, sizeof(OVMSG) - 1); 1132 return (0); 1133 } 1134 hashp->hdr.ovfl_point = splitnum; 1135 hashp->hdr.spares[splitnum] = hashp->hdr.spares[splitnum - 1]; 1136 hashp->hdr.spares[splitnum - 1]--; 1137 offset = 1; 1138 } 1139 /* Check if we need to allocate a new bitmap page. */ 1140 if (free_bit == (hashp->hdr.bsize << BYTE_SHIFT) - 1) { 1141 free_page++; 1142 if (free_page >= NCACHED) { 1143 (void)write(STDERR_FILENO, OVMSG, sizeof(OVMSG) - 1); 1144 return (0); 1145 } 1146 /* 1147 * This is tricky. The 1 indicates that you want the new page 1148 * allocated with 1 clear bit. Actually, you are going to 1149 * allocate 2 pages from this map. The first is going to be 1150 * the map page, the second is the overflow page we were 1151 * looking for. The __ibitmap routine automatically, sets 1152 * the first bit of itself to indicate that the bitmap itself 1153 * is in use. We would explicitly set the second bit, but 1154 * don't have to if we tell __ibitmap not to leave it clear 1155 * in the first place. 1156 */ 1157 if (__ibitmap(hashp, 1158 (int32_t)OADDR_OF(splitnum, offset), 1, free_page)) 1159 return (0); 1160 hashp->hdr.spares[splitnum]++; 1161 #ifdef DEBUG2 1162 free_bit = 2; 1163 #endif 1164 offset++; 1165 if (offset > SPLITMASK) { 1166 if (++splitnum >= NCACHED) { 1167 (void)write(STDERR_FILENO, 1168 OVMSG, sizeof(OVMSG) - 1); 1169 return (0); 1170 } 1171 hashp->hdr.ovfl_point = splitnum; 1172 hashp->hdr.spares[splitnum] = 1173 hashp->hdr.spares[splitnum - 1]; 1174 hashp->hdr.spares[splitnum - 1]--; 1175 offset = 0; 1176 } 1177 } else { 1178 /* 1179 * Free_bit addresses the last used bit. Bump it to address 1180 * the first available bit. 1181 */ 1182 free_bit++; 1183 SETBIT(freep, free_bit); 1184 } 1185 1186 /* Calculate address of the new overflow page */ 1187 addr = OADDR_OF(splitnum, offset); 1188 #ifdef DEBUG2 1189 (void)fprintf(stderr, dgettext(TEXT_DOMAIN, 1190 "OVERFLOW_PAGE: ADDR: %d BIT: %d PAGE %d\n"), 1191 addr, free_bit, free_page); 1192 #endif 1193 1194 if (OADDR_TO_PAGE(addr) > MAX_PAGES(hashp)) { 1195 (void)write(STDERR_FILENO, OVMSG, sizeof(OVMSG) - 1); 1196 return (0); 1197 } 1198 return (addr); 1199 1200 found: 1201 bit = bit + first_free(freep[j]); 1202 SETBIT(freep, bit); 1203 #ifdef DEBUG2 1204 tmp1 = bit; 1205 tmp2 = i; 1206 #endif 1207 /* 1208 * Bits are addressed starting with 0, but overflow pages are addressed 1209 * beginning at 1. Bit is a bit address number, so we need to increment 1210 * it to convert it to a page number. 1211 */ 1212 bit = 1 + bit + (i * (hashp->hdr.bsize << BYTE_SHIFT)); 1213 if (bit >= hashp->hdr.last_freed) 1214 hashp->hdr.last_freed = bit - 1; 1215 1216 /* Calculate the split number for this page */ 1217 for (i = 0; i < splitnum && (bit > hashp->hdr.spares[i]); i++); 1218 offset = (i ? bit - hashp->hdr.spares[i - 1] : bit); 1219 if (offset >= SPLITMASK) 1220 return (0); /* Out of overflow pages */ 1221 addr = OADDR_OF(i, offset); 1222 #ifdef DEBUG2 1223 (void)fprintf(stderr, dgettext(TEXT_DOMAIN, 1224 "OVERFLOW_PAGE: ADDR: %d BIT: %d PAGE %d\n"), 1225 addr, tmp1, tmp2); 1226 #endif 1227 1228 if (OADDR_TO_PAGE(addr) > MAX_PAGES(hashp)) { 1229 (void)write(STDERR_FILENO, OVMSG, sizeof(OVMSG) - 1); 1230 return (0); 1231 } 1232 /* Allocate and return the overflow page */ 1233 return (addr); 1234 } 1235 1236 #ifdef DEBUG 1237 int 1238 bucket_to_page(hashp, n) 1239 HTAB *hashp; 1240 int n; 1241 { 1242 int ret_val; 1243 1244 ret_val = n + hashp->hdr.hdrpages; 1245 if (n != 0) 1246 ret_val += hashp->hdr.spares[__log2(n + 1) - 1]; 1247 return (ret_val); 1248 } 1249 1250 int32_t 1251 oaddr_to_page(hashp, n) 1252 HTAB *hashp; 1253 int n; 1254 { 1255 int ret_val, temp; 1256 1257 temp = (1 << SPLITNUM(n)) - 1; 1258 ret_val = bucket_to_page(hashp, temp); 1259 ret_val += (n & SPLITMASK); 1260 1261 return (ret_val); 1262 } 1263 #endif /* DEBUG */ 1264 1265 static indx_t 1266 page_to_oaddr(hashp, pgno) 1267 HTAB *hashp; 1268 db_pgno_t pgno; 1269 { 1270 int32_t sp, ret_val; 1271 1272 /* 1273 * To convert page number to overflow address: 1274 * 1275 * 1. Find a starting split point -- use 0 since there are only 1276 * 32 split points. 1277 * 2. Find the split point s.t. 2^sp + hdr.spares[sp] < pgno and 1278 * 2^(sp+1) = hdr.spares[sp+1] > pgno. The overflow address will 1279 * be located at sp. 1280 * 3. return... 1281 */ 1282 pgno -= hashp->hdr.hdrpages; 1283 for (sp = 0; sp < NCACHED; sp++) 1284 if (POW2(sp) + hashp->hdr.spares[sp] < pgno && 1285 (POW2(sp + 1) + hashp->hdr.spares[sp + 1]) > pgno) 1286 break; 1287 1288 ret_val = OADDR_OF(sp + 1, 1289 pgno - ((POW2(sp + 1) - 1) + hashp->hdr.spares[sp])); 1290 #ifdef DEBUG 1291 assert(OADDR_TO_PAGE(ret_val) == (pgno + hashp->hdr.hdrpages)); 1292 #endif 1293 return (ret_val); 1294 } 1295 1296 /* 1297 * Mark this overflow page as free. 1298 */ 1299 extern void 1300 __free_ovflpage(hashp, pagep) 1301 HTAB *hashp; 1302 PAGE16 *pagep; 1303 { 1304 u_int32_t *freep; 1305 int32_t bit_address, free_page, free_bit; 1306 u_int16_t addr, ndx; 1307 1308 addr = page_to_oaddr(hashp, ADDR(pagep)); 1309 1310 #ifdef DEBUG2 1311 (void)fprintf(stderr, dgettext(TEXT_DOMAIN, 1312 "Freeing %d\n"), addr); 1313 #endif 1314 ndx = ((u_int16_t)addr) >> SPLITSHIFT; 1315 bit_address = 1316 (ndx ? hashp->hdr.spares[ndx - 1] : 0) + (addr & SPLITMASK) - 1; 1317 if (bit_address < hashp->hdr.last_freed) 1318 hashp->hdr.last_freed = bit_address; 1319 free_page = (bit_address >> (hashp->hdr.bshift + BYTE_SHIFT)); 1320 free_bit = bit_address & ((hashp->hdr.bsize << BYTE_SHIFT) - 1); 1321 1322 freep = fetch_bitmap(hashp, free_page); 1323 #ifdef DEBUG 1324 /* 1325 * This had better never happen. It means we tried to read a bitmap 1326 * that has already had overflow pages allocated off it, and we 1327 * failed to read it from the file. 1328 */ 1329 if (!freep) 1330 assert(0); 1331 #endif 1332 CLRBIT(freep, free_bit); 1333 #ifdef DEBUG2 1334 (void)fprintf(stderr, dgettext(TEXT_DOMAIN, 1335 "FREE_OVFLPAGE: ADDR: %d BIT: %d PAGE %d\n"), 1336 obufp->addr, free_bit, free_page); 1337 #endif 1338 } 1339 1340 static u_int32_t * 1341 fetch_bitmap(hashp, ndx) 1342 HTAB *hashp; 1343 int32_t ndx; 1344 { 1345 if (ndx >= hashp->nmaps) 1346 return (NULL); 1347 if (!hashp->mapp[ndx]) 1348 hashp->mapp[ndx] = (u_int32_t *)__get_page(hashp, 1349 hashp->hdr.bitmaps[ndx], A_BITMAP); 1350 1351 return (hashp->mapp[ndx]); 1352 } 1353 1354 #ifdef DEBUG_SLOW 1355 static void 1356 account_page(hashp, pgno, inout) 1357 HTAB *hashp; 1358 db_pgno_t pgno; 1359 int inout; 1360 { 1361 static struct { 1362 db_pgno_t pgno; 1363 int times; 1364 } list[100]; 1365 static int last; 1366 int i, j; 1367 1368 if (inout == -1) /* XXX: Kluge */ 1369 inout = 0; 1370 1371 /* Find page in list. */ 1372 for (i = 0; i < last; i++) 1373 if (list[i].pgno == pgno) 1374 break; 1375 /* Not found. */ 1376 if (i == last) { 1377 list[last].times = inout; 1378 list[last].pgno = pgno; 1379 last++; 1380 } 1381 list[i].times = inout; 1382 if (list[i].times == 0) { 1383 for (j = i; j < last; j++) 1384 list[j] = list[j + 1]; 1385 last--; 1386 } 1387 for (i = 0; i < last; i++, list[i].times++) 1388 if (list[i].times > 20 && !is_bitmap_pgno(hashp, list[i].pgno)) 1389 (void)fprintf(stderr, 1390 dgettext(TEXT_DOMAIN, 1391 "Warning: pg %d has been out for %d times\n"), 1392 list[i].pgno, list[i].times); 1393 } 1394 #endif /* DEBUG_SLOW */ 1395