11573Srgrimes/*- 214287Spst * Copyright (c) 1990, 1993, 1994 31573Srgrimes * The Regents of the University of California. All rights reserved. 41573Srgrimes * 51573Srgrimes * This code is derived from software contributed to Berkeley by 61573Srgrimes * Margo Seltzer. 71573Srgrimes * 81573Srgrimes * Redistribution and use in source and binary forms, with or without 91573Srgrimes * modification, are permitted provided that the following conditions 101573Srgrimes * are met: 111573Srgrimes * 1. Redistributions of source code must retain the above copyright 121573Srgrimes * notice, this list of conditions and the following disclaimer. 131573Srgrimes * 2. Redistributions in binary form must reproduce the above copyright 141573Srgrimes * notice, this list of conditions and the following disclaimer in the 151573Srgrimes * documentation and/or other materials provided with the distribution. 161573Srgrimes * 4. Neither the name of the University nor the names of its contributors 171573Srgrimes * may be used to endorse or promote products derived from this software 181573Srgrimes * without specific prior written permission. 191573Srgrimes * 201573Srgrimes * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 211573Srgrimes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 221573Srgrimes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 231573Srgrimes * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 241573Srgrimes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 251573Srgrimes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 261573Srgrimes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 271573Srgrimes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 281573Srgrimes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 291573Srgrimes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 301573Srgrimes * SUCH DAMAGE. 311573Srgrimes */ 321573Srgrimes 331573Srgrimes#if defined(LIBC_SCCS) && !defined(lint) 3414287Spststatic char sccsid[] = "@(#)hash_page.c 8.7 (Berkeley) 8/16/94"; 351573Srgrimes#endif /* LIBC_SCCS and not lint */ 3692889Sobrien#include <sys/cdefs.h> 3792889Sobrien__FBSDID("$FreeBSD: releng/11.0/lib/libc/db/hash/hash_page.c 298323 2016-04-20 01:21:39Z pfg $"); 381573Srgrimes 391573Srgrimes/* 401573Srgrimes * PACKAGE: hashing 411573Srgrimes * 421573Srgrimes * DESCRIPTION: 431573Srgrimes * Page manipulation for hashing package. 441573Srgrimes * 451573Srgrimes * ROUTINES: 461573Srgrimes * 471573Srgrimes * External 481573Srgrimes * __get_page 491573Srgrimes * __add_ovflpage 501573Srgrimes * Internal 511573Srgrimes * overflow_page 521573Srgrimes * open_temp 531573Srgrimes */ 541573Srgrimes 5571579Sdeischen#include "namespace.h" 56190485Sdelphij#include <sys/param.h> 571573Srgrimes 581573Srgrimes#include <errno.h> 591573Srgrimes#include <fcntl.h> 601573Srgrimes#include <signal.h> 611573Srgrimes#include <stdio.h> 621573Srgrimes#include <stdlib.h> 631573Srgrimes#include <string.h> 641573Srgrimes#include <unistd.h> 651573Srgrimes#ifdef DEBUG 661573Srgrimes#include <assert.h> 671573Srgrimes#endif 6871579Sdeischen#include "un-namespace.h" 69287292Skib#include "libc_private.h" 701573Srgrimes 711573Srgrimes#include <db.h> 721573Srgrimes#include "hash.h" 731573Srgrimes#include "page.h" 741573Srgrimes#include "extern.h" 751573Srgrimes 76189291Sdelphijstatic u_int32_t *fetch_bitmap(HTAB *, int); 77189291Sdelphijstatic u_int32_t first_free(u_int32_t); 78189291Sdelphijstatic int open_temp(HTAB *); 79189291Sdelphijstatic u_int16_t overflow_page(HTAB *); 80189291Sdelphijstatic void putpair(char *, const DBT *, const DBT *); 81189291Sdelphijstatic void squeeze_key(u_int16_t *, const DBT *, const DBT *); 82189291Sdelphijstatic int ugly_split(HTAB *, u_int32_t, BUFHEAD *, BUFHEAD *, int, int); 831573Srgrimes 841573Srgrimes#define PAGE_INIT(P) { \ 8514287Spst ((u_int16_t *)(P))[0] = 0; \ 8614287Spst ((u_int16_t *)(P))[1] = hashp->BSIZE - 3 * sizeof(u_int16_t); \ 8714287Spst ((u_int16_t *)(P))[2] = hashp->BSIZE; \ 881573Srgrimes} 891573Srgrimes 901573Srgrimes/* 911573Srgrimes * This is called AFTER we have verified that there is room on the page for 921573Srgrimes * the pair (PAIRFITS has returned true) so we go right ahead and start moving 931573Srgrimes * stuff on. 941573Srgrimes */ 951573Srgrimesstatic void 96189291Sdelphijputpair(char *p, const DBT *key, const DBT *val) 971573Srgrimes{ 9892889Sobrien u_int16_t *bp, n, off; 991573Srgrimes 10014287Spst bp = (u_int16_t *)p; 1011573Srgrimes 1021573Srgrimes /* Enter the key first. */ 1031573Srgrimes n = bp[0]; 1041573Srgrimes 1051573Srgrimes off = OFFSET(bp) - key->size; 1061573Srgrimes memmove(p + off, key->data, key->size); 1071573Srgrimes bp[++n] = off; 1081573Srgrimes 1091573Srgrimes /* Now the data. */ 1101573Srgrimes off -= val->size; 1111573Srgrimes memmove(p + off, val->data, val->size); 1121573Srgrimes bp[++n] = off; 1131573Srgrimes 1141573Srgrimes /* Adjust page info. */ 1151573Srgrimes bp[0] = n; 11614287Spst bp[n + 1] = off - ((n + 3) * sizeof(u_int16_t)); 1171573Srgrimes bp[n + 2] = off; 1181573Srgrimes} 1191573Srgrimes 1201573Srgrimes/* 1211573Srgrimes * Returns: 1221573Srgrimes * 0 OK 1231573Srgrimes * -1 error 1241573Srgrimes */ 125189291Sdelphijint 126189291Sdelphij__delpair(HTAB *hashp, BUFHEAD *bufp, int ndx) 1271573Srgrimes{ 128190489Sdelphij u_int16_t *bp, newoff, pairlen; 12992889Sobrien int n; 1301573Srgrimes 13114287Spst bp = (u_int16_t *)bufp->page; 1321573Srgrimes n = bp[0]; 1331573Srgrimes 1341573Srgrimes if (bp[ndx + 1] < REAL_KEY) 1351573Srgrimes return (__big_delete(hashp, bufp)); 1361573Srgrimes if (ndx != 1) 1371573Srgrimes newoff = bp[ndx - 1]; 1381573Srgrimes else 1391573Srgrimes newoff = hashp->BSIZE; 1401573Srgrimes pairlen = newoff - bp[ndx + 1]; 1411573Srgrimes 1421573Srgrimes if (ndx != (n - 1)) { 1431573Srgrimes /* Hard Case -- need to shuffle keys */ 14492889Sobrien int i; 14592889Sobrien char *src = bufp->page + (int)OFFSET(bp); 14692889Sobrien char *dst = src + (int)pairlen; 1471573Srgrimes memmove(dst, src, bp[ndx + 1] - OFFSET(bp)); 1481573Srgrimes 1491573Srgrimes /* Now adjust the pointers */ 1501573Srgrimes for (i = ndx + 2; i <= n; i += 2) { 1511573Srgrimes if (bp[i + 1] == OVFLPAGE) { 1521573Srgrimes bp[i - 2] = bp[i]; 1531573Srgrimes bp[i - 1] = bp[i + 1]; 1541573Srgrimes } else { 1551573Srgrimes bp[i - 2] = bp[i] + pairlen; 1561573Srgrimes bp[i - 1] = bp[i + 1] + pairlen; 1571573Srgrimes } 1581573Srgrimes } 159190491Sdelphij if (ndx == hashp->cndx) { 160190491Sdelphij /* 161190491Sdelphij * We just removed pair we were "pointing" to. 162190491Sdelphij * By moving back the cndx we ensure subsequent 163190491Sdelphij * hash_seq() calls won't skip over any entries. 164190491Sdelphij */ 165190491Sdelphij hashp->cndx -= 2; 166190491Sdelphij } 1671573Srgrimes } 1681573Srgrimes /* Finally adjust the page data */ 1691573Srgrimes bp[n] = OFFSET(bp) + pairlen; 17014287Spst bp[n - 1] = bp[n + 1] + pairlen + 2 * sizeof(u_int16_t); 1711573Srgrimes bp[0] = n - 2; 1721573Srgrimes hashp->NKEYS--; 1731573Srgrimes 1741573Srgrimes bufp->flags |= BUF_MOD; 1751573Srgrimes return (0); 1761573Srgrimes} 1771573Srgrimes/* 1781573Srgrimes * Returns: 1791573Srgrimes * 0 ==> OK 1801573Srgrimes * -1 ==> Error 1811573Srgrimes */ 182189291Sdelphijint 183189291Sdelphij__split_page(HTAB *hashp, u_int32_t obucket, u_int32_t nbucket) 1841573Srgrimes{ 18592889Sobrien BUFHEAD *new_bufp, *old_bufp; 18692889Sobrien u_int16_t *ino; 18792889Sobrien char *np; 1881573Srgrimes DBT key, val; 1891573Srgrimes int n, ndx, retval; 19014287Spst u_int16_t copyto, diff, off, moved; 1911573Srgrimes char *op; 1921573Srgrimes 19314287Spst copyto = (u_int16_t)hashp->BSIZE; 19414287Spst off = (u_int16_t)hashp->BSIZE; 1951573Srgrimes old_bufp = __get_buf(hashp, obucket, NULL, 0); 1961573Srgrimes if (old_bufp == NULL) 1971573Srgrimes return (-1); 1981573Srgrimes new_bufp = __get_buf(hashp, nbucket, NULL, 0); 1991573Srgrimes if (new_bufp == NULL) 2001573Srgrimes return (-1); 2011573Srgrimes 2021573Srgrimes old_bufp->flags |= (BUF_MOD | BUF_PIN); 2031573Srgrimes new_bufp->flags |= (BUF_MOD | BUF_PIN); 2041573Srgrimes 20514287Spst ino = (u_int16_t *)(op = old_bufp->page); 2061573Srgrimes np = new_bufp->page; 2071573Srgrimes 2081573Srgrimes moved = 0; 2091573Srgrimes 2101573Srgrimes for (n = 1, ndx = 1; n < ino[0]; n += 2) { 2111573Srgrimes if (ino[n + 1] < REAL_KEY) { 2121573Srgrimes retval = ugly_split(hashp, obucket, old_bufp, new_bufp, 2131573Srgrimes (int)copyto, (int)moved); 2141573Srgrimes old_bufp->flags &= ~BUF_PIN; 2151573Srgrimes new_bufp->flags &= ~BUF_PIN; 2161573Srgrimes return (retval); 2171573Srgrimes 2181573Srgrimes } 2191573Srgrimes key.data = (u_char *)op + ino[n]; 2201573Srgrimes key.size = off - ino[n]; 2211573Srgrimes 2221573Srgrimes if (__call_hash(hashp, key.data, key.size) == obucket) { 2231573Srgrimes /* Don't switch page */ 2241573Srgrimes diff = copyto - off; 2251573Srgrimes if (diff) { 2261573Srgrimes copyto = ino[n + 1] + diff; 2271573Srgrimes memmove(op + copyto, op + ino[n + 1], 2281573Srgrimes off - ino[n + 1]); 2291573Srgrimes ino[ndx] = copyto + ino[n] - ino[n + 1]; 2301573Srgrimes ino[ndx + 1] = copyto; 2311573Srgrimes } else 2321573Srgrimes copyto = ino[n + 1]; 2331573Srgrimes ndx += 2; 2341573Srgrimes } else { 2351573Srgrimes /* Switch page */ 2361573Srgrimes val.data = (u_char *)op + ino[n + 1]; 2371573Srgrimes val.size = ino[n] - ino[n + 1]; 2381573Srgrimes putpair(np, &key, &val); 2391573Srgrimes moved += 2; 2401573Srgrimes } 2411573Srgrimes 2421573Srgrimes off = ino[n + 1]; 2431573Srgrimes } 2441573Srgrimes 2451573Srgrimes /* Now clean up the page */ 2461573Srgrimes ino[0] -= moved; 24714287Spst FREESPACE(ino) = copyto - sizeof(u_int16_t) * (ino[0] + 3); 2481573Srgrimes OFFSET(ino) = copyto; 2491573Srgrimes 2501573Srgrimes#ifdef DEBUG3 2511573Srgrimes (void)fprintf(stderr, "split %d/%d\n", 25214287Spst ((u_int16_t *)np)[0] / 2, 25314287Spst ((u_int16_t *)op)[0] / 2); 2541573Srgrimes#endif 2551573Srgrimes /* unpin both pages */ 2561573Srgrimes old_bufp->flags &= ~BUF_PIN; 2571573Srgrimes new_bufp->flags &= ~BUF_PIN; 2581573Srgrimes return (0); 2591573Srgrimes} 2601573Srgrimes 2611573Srgrimes/* 2621573Srgrimes * Called when we encounter an overflow or big key/data page during split 2631573Srgrimes * handling. This is special cased since we have to begin checking whether 2641573Srgrimes * the key/data pairs fit on their respective pages and because we may need 2651573Srgrimes * overflow pages for both the old and new pages. 2661573Srgrimes * 2671573Srgrimes * The first page might be a page with regular key/data pairs in which case 2681573Srgrimes * we have a regular overflow condition and just need to go on to the next 2691573Srgrimes * page or it might be a big key/data pair in which case we need to fix the 2701573Srgrimes * big key/data pair. 2711573Srgrimes * 2721573Srgrimes * Returns: 2731573Srgrimes * 0 ==> success 2741573Srgrimes * -1 ==> failure 2751573Srgrimes */ 2761573Srgrimesstatic int 277189291Sdelphijugly_split(HTAB *hashp, 278189291Sdelphij u_int32_t obucket, /* Same as __split_page. */ 279189291Sdelphij BUFHEAD *old_bufp, 280189291Sdelphij BUFHEAD *new_bufp, 281189291Sdelphij int copyto, /* First byte on page which contains key/data values. */ 282189291Sdelphij int moved) /* Number of pairs moved to new page. */ 2831573Srgrimes{ 284189291Sdelphij BUFHEAD *bufp; /* Buffer header for ino */ 285189291Sdelphij u_int16_t *ino; /* Page keys come off of */ 286189291Sdelphij u_int16_t *np; /* New page */ 287189291Sdelphij u_int16_t *op; /* Page keys go on to if they aren't moving */ 2881573Srgrimes 2891573Srgrimes BUFHEAD *last_bfp; /* Last buf header OVFL needing to be freed */ 2901573Srgrimes DBT key, val; 2911573Srgrimes SPLIT_RETURN ret; 29214287Spst u_int16_t n, off, ov_addr, scopyto; 2931573Srgrimes char *cino; /* Character value of ino */ 2941573Srgrimes 2951573Srgrimes bufp = old_bufp; 29614287Spst ino = (u_int16_t *)old_bufp->page; 29714287Spst np = (u_int16_t *)new_bufp->page; 29814287Spst op = (u_int16_t *)old_bufp->page; 2991573Srgrimes last_bfp = NULL; 30014287Spst scopyto = (u_int16_t)copyto; /* ANSI */ 3011573Srgrimes 3021573Srgrimes n = ino[0] - 1; 3031573Srgrimes while (n < ino[0]) { 3041573Srgrimes if (ino[2] < REAL_KEY && ino[2] != OVFLPAGE) { 3051573Srgrimes if (__big_split(hashp, old_bufp, 3061573Srgrimes new_bufp, bufp, bufp->addr, obucket, &ret)) 3071573Srgrimes return (-1); 3081573Srgrimes old_bufp = ret.oldp; 3091573Srgrimes if (!old_bufp) 3101573Srgrimes return (-1); 31114287Spst op = (u_int16_t *)old_bufp->page; 3121573Srgrimes new_bufp = ret.newp; 3131573Srgrimes if (!new_bufp) 3141573Srgrimes return (-1); 31514287Spst np = (u_int16_t *)new_bufp->page; 3161573Srgrimes bufp = ret.nextp; 3171573Srgrimes if (!bufp) 3181573Srgrimes return (0); 3191573Srgrimes cino = (char *)bufp->page; 32014287Spst ino = (u_int16_t *)cino; 3211573Srgrimes last_bfp = ret.nextp; 3221573Srgrimes } else if (ino[n + 1] == OVFLPAGE) { 3231573Srgrimes ov_addr = ino[n]; 3241573Srgrimes /* 3251573Srgrimes * Fix up the old page -- the extra 2 are the fields 3261573Srgrimes * which contained the overflow information. 3271573Srgrimes */ 3281573Srgrimes ino[0] -= (moved + 2); 3291573Srgrimes FREESPACE(ino) = 33014287Spst scopyto - sizeof(u_int16_t) * (ino[0] + 3); 3311573Srgrimes OFFSET(ino) = scopyto; 3321573Srgrimes 3331573Srgrimes bufp = __get_buf(hashp, ov_addr, bufp, 0); 3341573Srgrimes if (!bufp) 3351573Srgrimes return (-1); 3361573Srgrimes 33714287Spst ino = (u_int16_t *)bufp->page; 3381573Srgrimes n = 1; 3391573Srgrimes scopyto = hashp->BSIZE; 3401573Srgrimes moved = 0; 3411573Srgrimes 3421573Srgrimes if (last_bfp) 3431573Srgrimes __free_ovflpage(hashp, last_bfp); 3441573Srgrimes last_bfp = bufp; 3451573Srgrimes } 3461573Srgrimes /* Move regular sized pairs of there are any */ 3471573Srgrimes off = hashp->BSIZE; 3481573Srgrimes for (n = 1; (n < ino[0]) && (ino[n + 1] >= REAL_KEY); n += 2) { 3491573Srgrimes cino = (char *)ino; 3501573Srgrimes key.data = (u_char *)cino + ino[n]; 3511573Srgrimes key.size = off - ino[n]; 3521573Srgrimes val.data = (u_char *)cino + ino[n + 1]; 3531573Srgrimes val.size = ino[n] - ino[n + 1]; 3541573Srgrimes off = ino[n + 1]; 3551573Srgrimes 3561573Srgrimes if (__call_hash(hashp, key.data, key.size) == obucket) { 3571573Srgrimes /* Keep on old page */ 3581573Srgrimes if (PAIRFITS(op, (&key), (&val))) 3591573Srgrimes putpair((char *)op, &key, &val); 3601573Srgrimes else { 3611573Srgrimes old_bufp = 3621573Srgrimes __add_ovflpage(hashp, old_bufp); 3631573Srgrimes if (!old_bufp) 3641573Srgrimes return (-1); 36514287Spst op = (u_int16_t *)old_bufp->page; 3661573Srgrimes putpair((char *)op, &key, &val); 3671573Srgrimes } 3681573Srgrimes old_bufp->flags |= BUF_MOD; 3691573Srgrimes } else { 3701573Srgrimes /* Move to new page */ 3711573Srgrimes if (PAIRFITS(np, (&key), (&val))) 3721573Srgrimes putpair((char *)np, &key, &val); 3731573Srgrimes else { 3741573Srgrimes new_bufp = 3751573Srgrimes __add_ovflpage(hashp, new_bufp); 3761573Srgrimes if (!new_bufp) 3771573Srgrimes return (-1); 37814287Spst np = (u_int16_t *)new_bufp->page; 3791573Srgrimes putpair((char *)np, &key, &val); 3801573Srgrimes } 3811573Srgrimes new_bufp->flags |= BUF_MOD; 3821573Srgrimes } 3831573Srgrimes } 3841573Srgrimes } 3851573Srgrimes if (last_bfp) 3861573Srgrimes __free_ovflpage(hashp, last_bfp); 3871573Srgrimes return (0); 3881573Srgrimes} 3891573Srgrimes 3901573Srgrimes/* 3911573Srgrimes * Add the given pair to the page 3921573Srgrimes * 3931573Srgrimes * Returns: 3941573Srgrimes * 0 ==> OK 3951573Srgrimes * 1 ==> failure 3961573Srgrimes */ 397189291Sdelphijint 398189291Sdelphij__addel(HTAB *hashp, BUFHEAD *bufp, const DBT *key, const DBT *val) 3991573Srgrimes{ 40092889Sobrien u_int16_t *bp, *sop; 4011573Srgrimes int do_expand; 4021573Srgrimes 40314287Spst bp = (u_int16_t *)bufp->page; 4041573Srgrimes do_expand = 0; 4051573Srgrimes while (bp[0] && (bp[2] < REAL_KEY || bp[bp[0]] < REAL_KEY)) 4061573Srgrimes /* Exception case */ 4071573Srgrimes if (bp[2] == FULL_KEY_DATA && bp[0] == 2) 4081573Srgrimes /* This is the last page of a big key/data pair 4091573Srgrimes and we need to add another page */ 4101573Srgrimes break; 4111573Srgrimes else if (bp[2] < REAL_KEY && bp[bp[0]] != OVFLPAGE) { 4121573Srgrimes bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0); 4131573Srgrimes if (!bufp) 4141573Srgrimes return (-1); 41514287Spst bp = (u_int16_t *)bufp->page; 416190490Sdelphij } else if (bp[bp[0]] != OVFLPAGE) { 417190490Sdelphij /* Short key/data pairs, no more pages */ 418190490Sdelphij break; 419190490Sdelphij } else { 4201573Srgrimes /* Try to squeeze key on this page */ 421190490Sdelphij if (bp[2] >= REAL_KEY && 422190490Sdelphij FREESPACE(bp) >= PAIRSIZE(key, val)) { 4231573Srgrimes squeeze_key(bp, key, val); 424190490Sdelphij goto stats; 4251573Srgrimes } else { 4261573Srgrimes bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0); 4271573Srgrimes if (!bufp) 4281573Srgrimes return (-1); 42914287Spst bp = (u_int16_t *)bufp->page; 4301573Srgrimes } 431190490Sdelphij } 4321573Srgrimes 4331573Srgrimes if (PAIRFITS(bp, key, val)) 4341573Srgrimes putpair(bufp->page, key, val); 4351573Srgrimes else { 4361573Srgrimes do_expand = 1; 4371573Srgrimes bufp = __add_ovflpage(hashp, bufp); 4381573Srgrimes if (!bufp) 4391573Srgrimes return (-1); 44014287Spst sop = (u_int16_t *)bufp->page; 4411573Srgrimes 4421573Srgrimes if (PAIRFITS(sop, key, val)) 4431573Srgrimes putpair((char *)sop, key, val); 4441573Srgrimes else 4451573Srgrimes if (__big_insert(hashp, bufp, key, val)) 4461573Srgrimes return (-1); 4471573Srgrimes } 448190490Sdelphijstats: 4491573Srgrimes bufp->flags |= BUF_MOD; 4501573Srgrimes /* 4511573Srgrimes * If the average number of keys per bucket exceeds the fill factor, 4521573Srgrimes * expand the table. 4531573Srgrimes */ 4541573Srgrimes hashp->NKEYS++; 4551573Srgrimes if (do_expand || 4561573Srgrimes (hashp->NKEYS / (hashp->MAX_BUCKET + 1) > hashp->FFACTOR)) 4571573Srgrimes return (__expand_table(hashp)); 4581573Srgrimes return (0); 4591573Srgrimes} 4601573Srgrimes 4611573Srgrimes/* 4621573Srgrimes * 4631573Srgrimes * Returns: 4641573Srgrimes * pointer on success 4651573Srgrimes * NULL on error 4661573Srgrimes */ 467189291SdelphijBUFHEAD * 468189291Sdelphij__add_ovflpage(HTAB *hashp, BUFHEAD *bufp) 4691573Srgrimes{ 470190489Sdelphij u_int16_t *sp, ndx, ovfl_num; 4711573Srgrimes#ifdef DEBUG1 4721573Srgrimes int tmp1, tmp2; 4731573Srgrimes#endif 47414287Spst sp = (u_int16_t *)bufp->page; 4751573Srgrimes 4761573Srgrimes /* Check if we are dynamically determining the fill factor */ 4771573Srgrimes if (hashp->FFACTOR == DEF_FFACTOR) { 4781573Srgrimes hashp->FFACTOR = sp[0] >> 1; 4791573Srgrimes if (hashp->FFACTOR < MIN_FFACTOR) 4801573Srgrimes hashp->FFACTOR = MIN_FFACTOR; 4811573Srgrimes } 4821573Srgrimes bufp->flags |= BUF_MOD; 4831573Srgrimes ovfl_num = overflow_page(hashp); 4841573Srgrimes#ifdef DEBUG1 4851573Srgrimes tmp1 = bufp->addr; 4861573Srgrimes tmp2 = bufp->ovfl ? bufp->ovfl->addr : 0; 4871573Srgrimes#endif 4881573Srgrimes if (!ovfl_num || !(bufp->ovfl = __get_buf(hashp, ovfl_num, bufp, 1))) 4891573Srgrimes return (NULL); 4901573Srgrimes bufp->ovfl->flags |= BUF_MOD; 4911573Srgrimes#ifdef DEBUG1 4921573Srgrimes (void)fprintf(stderr, "ADDOVFLPAGE: %d->ovfl was %d is now %d\n", 4931573Srgrimes tmp1, tmp2, bufp->ovfl->addr); 4941573Srgrimes#endif 4951573Srgrimes ndx = sp[0]; 4961573Srgrimes /* 4971573Srgrimes * Since a pair is allocated on a page only if there's room to add 4981573Srgrimes * an overflow page, we know that the OVFL information will fit on 4991573Srgrimes * the page. 5001573Srgrimes */ 5011573Srgrimes sp[ndx + 4] = OFFSET(sp); 5021573Srgrimes sp[ndx + 3] = FREESPACE(sp) - OVFLSIZE; 5031573Srgrimes sp[ndx + 1] = ovfl_num; 5041573Srgrimes sp[ndx + 2] = OVFLPAGE; 5051573Srgrimes sp[0] = ndx + 2; 5061573Srgrimes#ifdef HASH_STATISTICS 5071573Srgrimes hash_overflows++; 5081573Srgrimes#endif 5091573Srgrimes return (bufp->ovfl); 5101573Srgrimes} 5111573Srgrimes 5121573Srgrimes/* 5131573Srgrimes * Returns: 5141573Srgrimes * 0 indicates SUCCESS 5151573Srgrimes * -1 indicates FAILURE 5161573Srgrimes */ 517189291Sdelphijint 518189291Sdelphij__get_page(HTAB *hashp, char *p, u_int32_t bucket, int is_bucket, int is_disk, 519189291Sdelphij int is_bitmap) 5201573Srgrimes{ 521190489Sdelphij int fd, page, size, rsize; 52214287Spst u_int16_t *bp; 5231573Srgrimes 5241573Srgrimes fd = hashp->fp; 5251573Srgrimes size = hashp->BSIZE; 5261573Srgrimes 5271573Srgrimes if ((fd == -1) || !is_disk) { 5281573Srgrimes PAGE_INIT(p); 5291573Srgrimes return (0); 5301573Srgrimes } 5311573Srgrimes if (is_bucket) 5321573Srgrimes page = BUCKET_TO_PAGE(bucket); 5331573Srgrimes else 5341573Srgrimes page = OADDR_TO_PAGE(bucket); 535190486Sdelphij if ((rsize = pread(fd, p, size, (off_t)page << hashp->BSHIFT)) == -1) 5361573Srgrimes return (-1); 53714287Spst bp = (u_int16_t *)p; 5381573Srgrimes if (!rsize) 5391573Srgrimes bp[0] = 0; /* We hit the EOF, so initialize a new page */ 5401573Srgrimes else 5411573Srgrimes if (rsize != size) { 5421573Srgrimes errno = EFTYPE; 5431573Srgrimes return (-1); 5441573Srgrimes } 5451573Srgrimes if (!is_bitmap && !bp[0]) { 5461573Srgrimes PAGE_INIT(p); 5471573Srgrimes } else 5481573Srgrimes if (hashp->LORDER != BYTE_ORDER) { 54992889Sobrien int i, max; 5501573Srgrimes 5511573Srgrimes if (is_bitmap) { 5521573Srgrimes max = hashp->BSIZE >> 2; /* divide by 4 */ 5531573Srgrimes for (i = 0; i < max; i++) 55414287Spst M_32_SWAP(((int *)p)[i]); 5551573Srgrimes } else { 5561573Srgrimes M_16_SWAP(bp[0]); 5571573Srgrimes max = bp[0] + 2; 5581573Srgrimes for (i = 1; i <= max; i++) 5591573Srgrimes M_16_SWAP(bp[i]); 5601573Srgrimes } 5611573Srgrimes } 5621573Srgrimes return (0); 5631573Srgrimes} 5641573Srgrimes 5651573Srgrimes/* 5661573Srgrimes * Write page p to disk 5671573Srgrimes * 5681573Srgrimes * Returns: 5691573Srgrimes * 0 ==> OK 5701573Srgrimes * -1 ==>failure 5711573Srgrimes */ 572189291Sdelphijint 573189291Sdelphij__put_page(HTAB *hashp, char *p, u_int32_t bucket, int is_bucket, int is_bitmap) 5741573Srgrimes{ 575190489Sdelphij int fd, page, size, wsize; 5761573Srgrimes 5771573Srgrimes size = hashp->BSIZE; 5781573Srgrimes if ((hashp->fp == -1) && open_temp(hashp)) 5791573Srgrimes return (-1); 5801573Srgrimes fd = hashp->fp; 5811573Srgrimes 5821573Srgrimes if (hashp->LORDER != BYTE_ORDER) { 583190489Sdelphij int i, max; 5841573Srgrimes 5851573Srgrimes if (is_bitmap) { 5861573Srgrimes max = hashp->BSIZE >> 2; /* divide by 4 */ 5871573Srgrimes for (i = 0; i < max; i++) 58814287Spst M_32_SWAP(((int *)p)[i]); 5891573Srgrimes } else { 59014287Spst max = ((u_int16_t *)p)[0] + 2; 5911573Srgrimes for (i = 0; i <= max; i++) 59214287Spst M_16_SWAP(((u_int16_t *)p)[i]); 5931573Srgrimes } 5941573Srgrimes } 5951573Srgrimes if (is_bucket) 5961573Srgrimes page = BUCKET_TO_PAGE(bucket); 5971573Srgrimes else 5981573Srgrimes page = OADDR_TO_PAGE(bucket); 599190486Sdelphij if ((wsize = pwrite(fd, p, size, (off_t)page << hashp->BSHIFT)) == -1) 6001573Srgrimes /* Errno is set */ 6011573Srgrimes return (-1); 6021573Srgrimes if (wsize != size) { 6031573Srgrimes errno = EFTYPE; 6041573Srgrimes return (-1); 6051573Srgrimes } 6061573Srgrimes return (0); 6071573Srgrimes} 6081573Srgrimes 6091573Srgrimes#define BYTE_MASK ((1 << INT_BYTE_SHIFT) -1) 6101573Srgrimes/* 6111573Srgrimes * Initialize a new bitmap page. Bitmap pages are left in memory 6121573Srgrimes * once they are read in. 6131573Srgrimes */ 614189291Sdelphijint 615189291Sdelphij__ibitmap(HTAB *hashp, int pnum, int nbits, int ndx) 6161573Srgrimes{ 61714287Spst u_int32_t *ip; 6181573Srgrimes int clearbytes, clearints; 6191573Srgrimes 62014287Spst if ((ip = (u_int32_t *)malloc(hashp->BSIZE)) == NULL) 6211573Srgrimes return (1); 6221573Srgrimes hashp->nmaps++; 6231573Srgrimes clearints = ((nbits - 1) >> INT_BYTE_SHIFT) + 1; 6241573Srgrimes clearbytes = clearints << INT_TO_BYTE; 6251573Srgrimes (void)memset((char *)ip, 0, clearbytes); 6261573Srgrimes (void)memset(((char *)ip) + clearbytes, 0xFF, 6271573Srgrimes hashp->BSIZE - clearbytes); 6281573Srgrimes ip[clearints - 1] = ALL_SET << (nbits & BYTE_MASK); 6291573Srgrimes SETBIT(ip, 0); 63014287Spst hashp->BITMAPS[ndx] = (u_int16_t)pnum; 6311573Srgrimes hashp->mapp[ndx] = ip; 6321573Srgrimes return (0); 6331573Srgrimes} 6341573Srgrimes 63514287Spststatic u_int32_t 636189291Sdelphijfirst_free(u_int32_t map) 6371573Srgrimes{ 63892889Sobrien u_int32_t i, mask; 6391573Srgrimes 6401573Srgrimes mask = 0x1; 6411573Srgrimes for (i = 0; i < BITS_PER_MAP; i++) { 6421573Srgrimes if (!(mask & map)) 6431573Srgrimes return (i); 6441573Srgrimes mask = mask << 1; 6451573Srgrimes } 6461573Srgrimes return (i); 6471573Srgrimes} 6481573Srgrimes 64914287Spststatic u_int16_t 650189291Sdelphijoverflow_page(HTAB *hashp) 6511573Srgrimes{ 65292889Sobrien u_int32_t *freep; 65392889Sobrien int max_free, offset, splitnum; 65414287Spst u_int16_t addr; 6551573Srgrimes int bit, first_page, free_bit, free_page, i, in_use_bits, j; 6561573Srgrimes#ifdef DEBUG2 6571573Srgrimes int tmp1, tmp2; 6581573Srgrimes#endif 6591573Srgrimes splitnum = hashp->OVFL_POINT; 6601573Srgrimes max_free = hashp->SPARES[splitnum]; 6611573Srgrimes 6621573Srgrimes free_page = (max_free - 1) >> (hashp->BSHIFT + BYTE_SHIFT); 6631573Srgrimes free_bit = (max_free - 1) & ((hashp->BSIZE << BYTE_SHIFT) - 1); 6641573Srgrimes 6651573Srgrimes /* Look through all the free maps to find the first free block */ 6661573Srgrimes first_page = hashp->LAST_FREED >>(hashp->BSHIFT + BYTE_SHIFT); 6671573Srgrimes for ( i = first_page; i <= free_page; i++ ) { 66814287Spst if (!(freep = (u_int32_t *)hashp->mapp[i]) && 6691573Srgrimes !(freep = fetch_bitmap(hashp, i))) 67014287Spst return (0); 6711573Srgrimes if (i == free_page) 6721573Srgrimes in_use_bits = free_bit; 6731573Srgrimes else 6741573Srgrimes in_use_bits = (hashp->BSIZE << BYTE_SHIFT) - 1; 6758870Srgrimes 6761573Srgrimes if (i == first_page) { 6771573Srgrimes bit = hashp->LAST_FREED & 6781573Srgrimes ((hashp->BSIZE << BYTE_SHIFT) - 1); 6791573Srgrimes j = bit / BITS_PER_MAP; 680298323Spfg bit = rounddown2(bit, BITS_PER_MAP); 6811573Srgrimes } else { 6821573Srgrimes bit = 0; 6831573Srgrimes j = 0; 6841573Srgrimes } 6851573Srgrimes for (; bit <= in_use_bits; j++, bit += BITS_PER_MAP) 6861573Srgrimes if (freep[j] != ALL_SET) 6871573Srgrimes goto found; 6881573Srgrimes } 6891573Srgrimes 6901573Srgrimes /* No Free Page Found */ 6911573Srgrimes hashp->LAST_FREED = hashp->SPARES[splitnum]; 6921573Srgrimes hashp->SPARES[splitnum]++; 6931573Srgrimes offset = hashp->SPARES[splitnum] - 6941573Srgrimes (splitnum ? hashp->SPARES[splitnum - 1] : 0); 6951573Srgrimes 6961573Srgrimes#define OVMSG "HASH: Out of overflow pages. Increase page size\n" 6971573Srgrimes if (offset > SPLITMASK) { 6981573Srgrimes if (++splitnum >= NCACHED) { 69956698Sjasone (void)_write(STDERR_FILENO, OVMSG, sizeof(OVMSG) - 1); 700190487Sdelphij errno = EFBIG; 70114287Spst return (0); 7021573Srgrimes } 7031573Srgrimes hashp->OVFL_POINT = splitnum; 7041573Srgrimes hashp->SPARES[splitnum] = hashp->SPARES[splitnum-1]; 7051573Srgrimes hashp->SPARES[splitnum-1]--; 7061573Srgrimes offset = 1; 7071573Srgrimes } 7081573Srgrimes 7091573Srgrimes /* Check if we need to allocate a new bitmap page */ 7101573Srgrimes if (free_bit == (hashp->BSIZE << BYTE_SHIFT) - 1) { 7111573Srgrimes free_page++; 7121573Srgrimes if (free_page >= NCACHED) { 71356698Sjasone (void)_write(STDERR_FILENO, OVMSG, sizeof(OVMSG) - 1); 714190487Sdelphij errno = EFBIG; 71514287Spst return (0); 7161573Srgrimes } 7171573Srgrimes /* 7181573Srgrimes * This is tricky. The 1 indicates that you want the new page 7191573Srgrimes * allocated with 1 clear bit. Actually, you are going to 7201573Srgrimes * allocate 2 pages from this map. The first is going to be 7211573Srgrimes * the map page, the second is the overflow page we were 7221573Srgrimes * looking for. The init_bitmap routine automatically, sets 7231573Srgrimes * the first bit of itself to indicate that the bitmap itself 7241573Srgrimes * is in use. We would explicitly set the second bit, but 7251573Srgrimes * don't have to if we tell init_bitmap not to leave it clear 7261573Srgrimes * in the first place. 7271573Srgrimes */ 72814287Spst if (__ibitmap(hashp, 72914287Spst (int)OADDR_OF(splitnum, offset), 1, free_page)) 73014287Spst return (0); 7311573Srgrimes hashp->SPARES[splitnum]++; 7321573Srgrimes#ifdef DEBUG2 7331573Srgrimes free_bit = 2; 7341573Srgrimes#endif 7351573Srgrimes offset++; 7361573Srgrimes if (offset > SPLITMASK) { 7371573Srgrimes if (++splitnum >= NCACHED) { 73856698Sjasone (void)_write(STDERR_FILENO, OVMSG, 7391573Srgrimes sizeof(OVMSG) - 1); 740190487Sdelphij errno = EFBIG; 74114287Spst return (0); 7421573Srgrimes } 7431573Srgrimes hashp->OVFL_POINT = splitnum; 7441573Srgrimes hashp->SPARES[splitnum] = hashp->SPARES[splitnum-1]; 7451573Srgrimes hashp->SPARES[splitnum-1]--; 7461573Srgrimes offset = 0; 7471573Srgrimes } 7481573Srgrimes } else { 7491573Srgrimes /* 7501573Srgrimes * Free_bit addresses the last used bit. Bump it to address 7511573Srgrimes * the first available bit. 7521573Srgrimes */ 7531573Srgrimes free_bit++; 7541573Srgrimes SETBIT(freep, free_bit); 7551573Srgrimes } 7561573Srgrimes 7571573Srgrimes /* Calculate address of the new overflow page */ 7581573Srgrimes addr = OADDR_OF(splitnum, offset); 7591573Srgrimes#ifdef DEBUG2 7601573Srgrimes (void)fprintf(stderr, "OVERFLOW_PAGE: ADDR: %d BIT: %d PAGE %d\n", 7611573Srgrimes addr, free_bit, free_page); 7621573Srgrimes#endif 7631573Srgrimes return (addr); 7641573Srgrimes 7651573Srgrimesfound: 7661573Srgrimes bit = bit + first_free(freep[j]); 7671573Srgrimes SETBIT(freep, bit); 7681573Srgrimes#ifdef DEBUG2 7691573Srgrimes tmp1 = bit; 7701573Srgrimes tmp2 = i; 7711573Srgrimes#endif 7721573Srgrimes /* 7731573Srgrimes * Bits are addressed starting with 0, but overflow pages are addressed 7741573Srgrimes * beginning at 1. Bit is a bit addressnumber, so we need to increment 7751573Srgrimes * it to convert it to a page number. 7761573Srgrimes */ 7771573Srgrimes bit = 1 + bit + (i * (hashp->BSIZE << BYTE_SHIFT)); 7781573Srgrimes if (bit >= hashp->LAST_FREED) 7791573Srgrimes hashp->LAST_FREED = bit - 1; 7801573Srgrimes 7811573Srgrimes /* Calculate the split number for this page */ 7821573Srgrimes for (i = 0; (i < splitnum) && (bit > hashp->SPARES[i]); i++); 7831573Srgrimes offset = (i ? bit - hashp->SPARES[i - 1] : bit); 784190487Sdelphij if (offset >= SPLITMASK) { 785190487Sdelphij (void)_write(STDERR_FILENO, OVMSG, sizeof(OVMSG) - 1); 786190487Sdelphij errno = EFBIG; 78714287Spst return (0); /* Out of overflow pages */ 788190487Sdelphij } 7891573Srgrimes addr = OADDR_OF(i, offset); 7901573Srgrimes#ifdef DEBUG2 7911573Srgrimes (void)fprintf(stderr, "OVERFLOW_PAGE: ADDR: %d BIT: %d PAGE %d\n", 7921573Srgrimes addr, tmp1, tmp2); 7931573Srgrimes#endif 7941573Srgrimes 7951573Srgrimes /* Allocate and return the overflow page */ 7961573Srgrimes return (addr); 7971573Srgrimes} 7981573Srgrimes 7991573Srgrimes/* 8001573Srgrimes * Mark this overflow page as free. 8011573Srgrimes */ 802189291Sdelphijvoid 803189291Sdelphij__free_ovflpage(HTAB *hashp, BUFHEAD *obufp) 8041573Srgrimes{ 80592889Sobrien u_int16_t addr; 80614287Spst u_int32_t *freep; 8071573Srgrimes int bit_address, free_page, free_bit; 80814287Spst u_int16_t ndx; 8091573Srgrimes 8101573Srgrimes addr = obufp->addr; 8111573Srgrimes#ifdef DEBUG1 8121573Srgrimes (void)fprintf(stderr, "Freeing %d\n", addr); 8131573Srgrimes#endif 81414287Spst ndx = (((u_int16_t)addr) >> SPLITSHIFT); 8151573Srgrimes bit_address = 8161573Srgrimes (ndx ? hashp->SPARES[ndx - 1] : 0) + (addr & SPLITMASK) - 1; 8171573Srgrimes if (bit_address < hashp->LAST_FREED) 8181573Srgrimes hashp->LAST_FREED = bit_address; 8191573Srgrimes free_page = (bit_address >> (hashp->BSHIFT + BYTE_SHIFT)); 8201573Srgrimes free_bit = bit_address & ((hashp->BSIZE << BYTE_SHIFT) - 1); 8211573Srgrimes 8221573Srgrimes if (!(freep = hashp->mapp[free_page])) 8231573Srgrimes freep = fetch_bitmap(hashp, free_page); 8241573Srgrimes#ifdef DEBUG 8251573Srgrimes /* 8261573Srgrimes * This had better never happen. It means we tried to read a bitmap 8271573Srgrimes * that has already had overflow pages allocated off it, and we 8281573Srgrimes * failed to read it from the file. 8291573Srgrimes */ 8301573Srgrimes if (!freep) 8311573Srgrimes assert(0); 8321573Srgrimes#endif 8331573Srgrimes CLRBIT(freep, free_bit); 8341573Srgrimes#ifdef DEBUG2 8351573Srgrimes (void)fprintf(stderr, "FREE_OVFLPAGE: ADDR: %d BIT: %d PAGE %d\n", 8361573Srgrimes obufp->addr, free_bit, free_page); 8371573Srgrimes#endif 8381573Srgrimes __reclaim_buf(hashp, obufp); 8391573Srgrimes} 8401573Srgrimes 8411573Srgrimes/* 8421573Srgrimes * Returns: 8431573Srgrimes * 0 success 8441573Srgrimes * -1 failure 8451573Srgrimes */ 8461573Srgrimesstatic int 847189291Sdelphijopen_temp(HTAB *hashp) 8481573Srgrimes{ 8491573Srgrimes sigset_t set, oset; 850190485Sdelphij int len; 851190485Sdelphij char *envtmp = NULL; 852190485Sdelphij char path[MAXPATHLEN]; 8531573Srgrimes 854190485Sdelphij if (issetugid() == 0) 855190485Sdelphij envtmp = getenv("TMPDIR"); 856190485Sdelphij len = snprintf(path, 857190485Sdelphij sizeof(path), "%s/_hash.XXXXXX", envtmp ? envtmp : "/tmp"); 858190500Sdelphij if (len < 0 || len >= (int)sizeof(path)) { 859190485Sdelphij errno = ENAMETOOLONG; 860190485Sdelphij return (-1); 861190485Sdelphij } 862190485Sdelphij 8631573Srgrimes /* Block signals; make sure file goes away at process exit. */ 8641573Srgrimes (void)sigfillset(&set); 865287292Skib (void)__libc_sigprocmask(SIG_BLOCK, &set, &oset); 866254289Sjilles if ((hashp->fp = mkostemp(path, O_CLOEXEC)) != -1) 867190485Sdelphij (void)unlink(path); 868287292Skib (void)__libc_sigprocmask(SIG_SETMASK, &oset, (sigset_t *)NULL); 8691573Srgrimes return (hashp->fp != -1 ? 0 : -1); 8701573Srgrimes} 8711573Srgrimes 8721573Srgrimes/* 8731573Srgrimes * We have to know that the key will fit, but the last entry on the page is 8741573Srgrimes * an overflow pair, so we need to shift things. 8751573Srgrimes */ 8761573Srgrimesstatic void 877189291Sdelphijsqueeze_key(u_int16_t *sp, const DBT *key, const DBT *val) 8781573Srgrimes{ 87992889Sobrien char *p; 88014287Spst u_int16_t free_space, n, off, pageno; 8811573Srgrimes 8821573Srgrimes p = (char *)sp; 8831573Srgrimes n = sp[0]; 8841573Srgrimes free_space = FREESPACE(sp); 8851573Srgrimes off = OFFSET(sp); 8861573Srgrimes 8871573Srgrimes pageno = sp[n - 1]; 8881573Srgrimes off -= key->size; 8891573Srgrimes sp[n - 1] = off; 8901573Srgrimes memmove(p + off, key->data, key->size); 8911573Srgrimes off -= val->size; 8921573Srgrimes sp[n] = off; 8931573Srgrimes memmove(p + off, val->data, val->size); 8941573Srgrimes sp[0] = n + 2; 8951573Srgrimes sp[n + 1] = pageno; 8961573Srgrimes sp[n + 2] = OVFLPAGE; 8971573Srgrimes FREESPACE(sp) = free_space - PAIRSIZE(key, val); 8981573Srgrimes OFFSET(sp) = off; 8991573Srgrimes} 9001573Srgrimes 90114287Spststatic u_int32_t * 902189291Sdelphijfetch_bitmap(HTAB *hashp, int ndx) 9031573Srgrimes{ 9041573Srgrimes if (ndx >= hashp->nmaps) 9051573Srgrimes return (NULL); 90614287Spst if ((hashp->mapp[ndx] = (u_int32_t *)malloc(hashp->BSIZE)) == NULL) 9071573Srgrimes return (NULL); 9081573Srgrimes if (__get_page(hashp, 9091573Srgrimes (char *)hashp->mapp[ndx], hashp->BITMAPS[ndx], 0, 1, 1)) { 9101573Srgrimes free(hashp->mapp[ndx]); 9111573Srgrimes return (NULL); 9121573Srgrimes } 9131573Srgrimes return (hashp->mapp[ndx]); 9141573Srgrimes} 9151573Srgrimes 9161573Srgrimes#ifdef DEBUG4 9171573Srgrimesint 918189291Sdelphijprint_chain(int addr) 9191573Srgrimes{ 9201573Srgrimes BUFHEAD *bufp; 9211573Srgrimes short *bp, oaddr; 9221573Srgrimes 9231573Srgrimes (void)fprintf(stderr, "%d ", addr); 9241573Srgrimes bufp = __get_buf(hashp, addr, NULL, 0); 9251573Srgrimes bp = (short *)bufp->page; 9261573Srgrimes while (bp[0] && ((bp[bp[0]] == OVFLPAGE) || 9271573Srgrimes ((bp[0] > 2) && bp[2] < REAL_KEY))) { 9281573Srgrimes oaddr = bp[bp[0] - 1]; 9291573Srgrimes (void)fprintf(stderr, "%d ", (int)oaddr); 9301573Srgrimes bufp = __get_buf(hashp, (int)oaddr, bufp, 0); 9311573Srgrimes bp = (short *)bufp->page; 9321573Srgrimes } 9331573Srgrimes (void)fprintf(stderr, "\n"); 9341573Srgrimes} 9351573Srgrimes#endif 936