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