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