hash_page.c revision 190500
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: head/lib/libc/db/hash/hash_page.c 190500 2009-03-28 07:44:08Z delphij $"); 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" 691573Srgrimes 701573Srgrimes#include <db.h> 711573Srgrimes#include "hash.h" 721573Srgrimes#include "page.h" 731573Srgrimes#include "extern.h" 741573Srgrimes 75189291Sdelphijstatic u_int32_t *fetch_bitmap(HTAB *, int); 76189291Sdelphijstatic u_int32_t first_free(u_int32_t); 77189291Sdelphijstatic int open_temp(HTAB *); 78189291Sdelphijstatic u_int16_t overflow_page(HTAB *); 79189291Sdelphijstatic void putpair(char *, const DBT *, const DBT *); 80189291Sdelphijstatic void squeeze_key(u_int16_t *, const DBT *, const DBT *); 81189291Sdelphijstatic int ugly_split(HTAB *, u_int32_t, BUFHEAD *, BUFHEAD *, int, int); 821573Srgrimes 831573Srgrimes#define PAGE_INIT(P) { \ 8414287Spst ((u_int16_t *)(P))[0] = 0; \ 8514287Spst ((u_int16_t *)(P))[1] = hashp->BSIZE - 3 * sizeof(u_int16_t); \ 8614287Spst ((u_int16_t *)(P))[2] = hashp->BSIZE; \ 871573Srgrimes} 881573Srgrimes 891573Srgrimes/* 901573Srgrimes * This is called AFTER we have verified that there is room on the page for 911573Srgrimes * the pair (PAIRFITS has returned true) so we go right ahead and start moving 921573Srgrimes * stuff on. 931573Srgrimes */ 941573Srgrimesstatic void 95189291Sdelphijputpair(char *p, const DBT *key, const DBT *val) 961573Srgrimes{ 9792889Sobrien u_int16_t *bp, n, off; 981573Srgrimes 9914287Spst bp = (u_int16_t *)p; 1001573Srgrimes 1011573Srgrimes /* Enter the key first. */ 1021573Srgrimes n = bp[0]; 1031573Srgrimes 1041573Srgrimes off = OFFSET(bp) - key->size; 1051573Srgrimes memmove(p + off, key->data, key->size); 1061573Srgrimes bp[++n] = off; 1071573Srgrimes 1081573Srgrimes /* Now the data. */ 1091573Srgrimes off -= val->size; 1101573Srgrimes memmove(p + off, val->data, val->size); 1111573Srgrimes bp[++n] = off; 1121573Srgrimes 1131573Srgrimes /* Adjust page info. */ 1141573Srgrimes bp[0] = n; 11514287Spst bp[n + 1] = off - ((n + 3) * sizeof(u_int16_t)); 1161573Srgrimes bp[n + 2] = off; 1171573Srgrimes} 1181573Srgrimes 1191573Srgrimes/* 1201573Srgrimes * Returns: 1211573Srgrimes * 0 OK 1221573Srgrimes * -1 error 1231573Srgrimes */ 124189291Sdelphijint 125189291Sdelphij__delpair(HTAB *hashp, BUFHEAD *bufp, int ndx) 1261573Srgrimes{ 127190489Sdelphij u_int16_t *bp, newoff, pairlen; 12892889Sobrien int n; 1291573Srgrimes 13014287Spst bp = (u_int16_t *)bufp->page; 1311573Srgrimes n = bp[0]; 1321573Srgrimes 1331573Srgrimes if (bp[ndx + 1] < REAL_KEY) 1341573Srgrimes return (__big_delete(hashp, bufp)); 1351573Srgrimes if (ndx != 1) 1361573Srgrimes newoff = bp[ndx - 1]; 1371573Srgrimes else 1381573Srgrimes newoff = hashp->BSIZE; 1391573Srgrimes pairlen = newoff - bp[ndx + 1]; 1401573Srgrimes 1411573Srgrimes if (ndx != (n - 1)) { 1421573Srgrimes /* Hard Case -- need to shuffle keys */ 14392889Sobrien int i; 14492889Sobrien char *src = bufp->page + (int)OFFSET(bp); 14592889Sobrien char *dst = src + (int)pairlen; 1461573Srgrimes memmove(dst, src, bp[ndx + 1] - OFFSET(bp)); 1471573Srgrimes 1481573Srgrimes /* Now adjust the pointers */ 1491573Srgrimes for (i = ndx + 2; i <= n; i += 2) { 1501573Srgrimes if (bp[i + 1] == OVFLPAGE) { 1511573Srgrimes bp[i - 2] = bp[i]; 1521573Srgrimes bp[i - 1] = bp[i + 1]; 1531573Srgrimes } else { 1541573Srgrimes bp[i - 2] = bp[i] + pairlen; 1551573Srgrimes bp[i - 1] = bp[i + 1] + pairlen; 1561573Srgrimes } 1571573Srgrimes } 158190491Sdelphij if (ndx == hashp->cndx) { 159190491Sdelphij /* 160190491Sdelphij * We just removed pair we were "pointing" to. 161190491Sdelphij * By moving back the cndx we ensure subsequent 162190491Sdelphij * hash_seq() calls won't skip over any entries. 163190491Sdelphij */ 164190491Sdelphij hashp->cndx -= 2; 165190491Sdelphij } 1661573Srgrimes } 1671573Srgrimes /* Finally adjust the page data */ 1681573Srgrimes bp[n] = OFFSET(bp) + pairlen; 16914287Spst bp[n - 1] = bp[n + 1] + pairlen + 2 * sizeof(u_int16_t); 1701573Srgrimes bp[0] = n - 2; 1711573Srgrimes hashp->NKEYS--; 1721573Srgrimes 1731573Srgrimes bufp->flags |= BUF_MOD; 1741573Srgrimes return (0); 1751573Srgrimes} 1761573Srgrimes/* 1771573Srgrimes * Returns: 1781573Srgrimes * 0 ==> OK 1791573Srgrimes * -1 ==> Error 1801573Srgrimes */ 181189291Sdelphijint 182189291Sdelphij__split_page(HTAB *hashp, u_int32_t obucket, u_int32_t nbucket) 1831573Srgrimes{ 18492889Sobrien BUFHEAD *new_bufp, *old_bufp; 18592889Sobrien u_int16_t *ino; 18692889Sobrien char *np; 1871573Srgrimes DBT key, val; 1881573Srgrimes int n, ndx, retval; 18914287Spst u_int16_t copyto, diff, off, moved; 1901573Srgrimes char *op; 1911573Srgrimes 19214287Spst copyto = (u_int16_t)hashp->BSIZE; 19314287Spst off = (u_int16_t)hashp->BSIZE; 1941573Srgrimes old_bufp = __get_buf(hashp, obucket, NULL, 0); 1951573Srgrimes if (old_bufp == NULL) 1961573Srgrimes return (-1); 1971573Srgrimes new_bufp = __get_buf(hashp, nbucket, NULL, 0); 1981573Srgrimes if (new_bufp == NULL) 1991573Srgrimes return (-1); 2001573Srgrimes 2011573Srgrimes old_bufp->flags |= (BUF_MOD | BUF_PIN); 2021573Srgrimes new_bufp->flags |= (BUF_MOD | BUF_PIN); 2031573Srgrimes 20414287Spst ino = (u_int16_t *)(op = old_bufp->page); 2051573Srgrimes np = new_bufp->page; 2061573Srgrimes 2071573Srgrimes moved = 0; 2081573Srgrimes 2091573Srgrimes for (n = 1, ndx = 1; n < ino[0]; n += 2) { 2101573Srgrimes if (ino[n + 1] < REAL_KEY) { 2111573Srgrimes retval = ugly_split(hashp, obucket, old_bufp, new_bufp, 2121573Srgrimes (int)copyto, (int)moved); 2131573Srgrimes old_bufp->flags &= ~BUF_PIN; 2141573Srgrimes new_bufp->flags &= ~BUF_PIN; 2151573Srgrimes return (retval); 2161573Srgrimes 2171573Srgrimes } 2181573Srgrimes key.data = (u_char *)op + ino[n]; 2191573Srgrimes key.size = off - ino[n]; 2201573Srgrimes 2211573Srgrimes if (__call_hash(hashp, key.data, key.size) == obucket) { 2221573Srgrimes /* Don't switch page */ 2231573Srgrimes diff = copyto - off; 2241573Srgrimes if (diff) { 2251573Srgrimes copyto = ino[n + 1] + diff; 2261573Srgrimes memmove(op + copyto, op + ino[n + 1], 2271573Srgrimes off - ino[n + 1]); 2281573Srgrimes ino[ndx] = copyto + ino[n] - ino[n + 1]; 2291573Srgrimes ino[ndx + 1] = copyto; 2301573Srgrimes } else 2311573Srgrimes copyto = ino[n + 1]; 2321573Srgrimes ndx += 2; 2331573Srgrimes } else { 2341573Srgrimes /* Switch page */ 2351573Srgrimes val.data = (u_char *)op + ino[n + 1]; 2361573Srgrimes val.size = ino[n] - ino[n + 1]; 2371573Srgrimes putpair(np, &key, &val); 2381573Srgrimes moved += 2; 2391573Srgrimes } 2401573Srgrimes 2411573Srgrimes off = ino[n + 1]; 2421573Srgrimes } 2431573Srgrimes 2441573Srgrimes /* Now clean up the page */ 2451573Srgrimes ino[0] -= moved; 24614287Spst FREESPACE(ino) = copyto - sizeof(u_int16_t) * (ino[0] + 3); 2471573Srgrimes OFFSET(ino) = copyto; 2481573Srgrimes 2491573Srgrimes#ifdef DEBUG3 2501573Srgrimes (void)fprintf(stderr, "split %d/%d\n", 25114287Spst ((u_int16_t *)np)[0] / 2, 25214287Spst ((u_int16_t *)op)[0] / 2); 2531573Srgrimes#endif 2541573Srgrimes /* unpin both pages */ 2551573Srgrimes old_bufp->flags &= ~BUF_PIN; 2561573Srgrimes new_bufp->flags &= ~BUF_PIN; 2571573Srgrimes return (0); 2581573Srgrimes} 2591573Srgrimes 2601573Srgrimes/* 2611573Srgrimes * Called when we encounter an overflow or big key/data page during split 2621573Srgrimes * handling. This is special cased since we have to begin checking whether 2631573Srgrimes * the key/data pairs fit on their respective pages and because we may need 2641573Srgrimes * overflow pages for both the old and new pages. 2651573Srgrimes * 2661573Srgrimes * The first page might be a page with regular key/data pairs in which case 2671573Srgrimes * we have a regular overflow condition and just need to go on to the next 2681573Srgrimes * page or it might be a big key/data pair in which case we need to fix the 2691573Srgrimes * big key/data pair. 2701573Srgrimes * 2711573Srgrimes * Returns: 2721573Srgrimes * 0 ==> success 2731573Srgrimes * -1 ==> failure 2741573Srgrimes */ 2751573Srgrimesstatic int 276189291Sdelphijugly_split(HTAB *hashp, 277189291Sdelphij u_int32_t obucket, /* Same as __split_page. */ 278189291Sdelphij BUFHEAD *old_bufp, 279189291Sdelphij BUFHEAD *new_bufp, 280189291Sdelphij int copyto, /* First byte on page which contains key/data values. */ 281189291Sdelphij int moved) /* Number of pairs moved to new page. */ 2821573Srgrimes{ 283189291Sdelphij BUFHEAD *bufp; /* Buffer header for ino */ 284189291Sdelphij u_int16_t *ino; /* Page keys come off of */ 285189291Sdelphij u_int16_t *np; /* New page */ 286189291Sdelphij u_int16_t *op; /* Page keys go on to if they aren't moving */ 2871573Srgrimes 2881573Srgrimes BUFHEAD *last_bfp; /* Last buf header OVFL needing to be freed */ 2891573Srgrimes DBT key, val; 2901573Srgrimes SPLIT_RETURN ret; 29114287Spst u_int16_t n, off, ov_addr, scopyto; 2921573Srgrimes char *cino; /* Character value of ino */ 2931573Srgrimes 2941573Srgrimes bufp = old_bufp; 29514287Spst ino = (u_int16_t *)old_bufp->page; 29614287Spst np = (u_int16_t *)new_bufp->page; 29714287Spst op = (u_int16_t *)old_bufp->page; 2981573Srgrimes last_bfp = NULL; 29914287Spst scopyto = (u_int16_t)copyto; /* ANSI */ 3001573Srgrimes 3011573Srgrimes n = ino[0] - 1; 3021573Srgrimes while (n < ino[0]) { 3031573Srgrimes if (ino[2] < REAL_KEY && ino[2] != OVFLPAGE) { 3041573Srgrimes if (__big_split(hashp, old_bufp, 3051573Srgrimes new_bufp, bufp, bufp->addr, obucket, &ret)) 3061573Srgrimes return (-1); 3071573Srgrimes old_bufp = ret.oldp; 3081573Srgrimes if (!old_bufp) 3091573Srgrimes return (-1); 31014287Spst op = (u_int16_t *)old_bufp->page; 3111573Srgrimes new_bufp = ret.newp; 3121573Srgrimes if (!new_bufp) 3131573Srgrimes return (-1); 31414287Spst np = (u_int16_t *)new_bufp->page; 3151573Srgrimes bufp = ret.nextp; 3161573Srgrimes if (!bufp) 3171573Srgrimes return (0); 3181573Srgrimes cino = (char *)bufp->page; 31914287Spst ino = (u_int16_t *)cino; 3201573Srgrimes last_bfp = ret.nextp; 3211573Srgrimes } else if (ino[n + 1] == OVFLPAGE) { 3221573Srgrimes ov_addr = ino[n]; 3231573Srgrimes /* 3241573Srgrimes * Fix up the old page -- the extra 2 are the fields 3251573Srgrimes * which contained the overflow information. 3261573Srgrimes */ 3271573Srgrimes ino[0] -= (moved + 2); 3281573Srgrimes FREESPACE(ino) = 32914287Spst scopyto - sizeof(u_int16_t) * (ino[0] + 3); 3301573Srgrimes OFFSET(ino) = scopyto; 3311573Srgrimes 3321573Srgrimes bufp = __get_buf(hashp, ov_addr, bufp, 0); 3331573Srgrimes if (!bufp) 3341573Srgrimes return (-1); 3351573Srgrimes 33614287Spst ino = (u_int16_t *)bufp->page; 3371573Srgrimes n = 1; 3381573Srgrimes scopyto = hashp->BSIZE; 3391573Srgrimes moved = 0; 3401573Srgrimes 3411573Srgrimes if (last_bfp) 3421573Srgrimes __free_ovflpage(hashp, last_bfp); 3431573Srgrimes last_bfp = bufp; 3441573Srgrimes } 3451573Srgrimes /* Move regular sized pairs of there are any */ 3461573Srgrimes off = hashp->BSIZE; 3471573Srgrimes for (n = 1; (n < ino[0]) && (ino[n + 1] >= REAL_KEY); n += 2) { 3481573Srgrimes cino = (char *)ino; 3491573Srgrimes key.data = (u_char *)cino + ino[n]; 3501573Srgrimes key.size = off - ino[n]; 3511573Srgrimes val.data = (u_char *)cino + ino[n + 1]; 3521573Srgrimes val.size = ino[n] - ino[n + 1]; 3531573Srgrimes off = ino[n + 1]; 3541573Srgrimes 3551573Srgrimes if (__call_hash(hashp, key.data, key.size) == obucket) { 3561573Srgrimes /* Keep on old page */ 3571573Srgrimes if (PAIRFITS(op, (&key), (&val))) 3581573Srgrimes putpair((char *)op, &key, &val); 3591573Srgrimes else { 3601573Srgrimes old_bufp = 3611573Srgrimes __add_ovflpage(hashp, old_bufp); 3621573Srgrimes if (!old_bufp) 3631573Srgrimes return (-1); 36414287Spst op = (u_int16_t *)old_bufp->page; 3651573Srgrimes putpair((char *)op, &key, &val); 3661573Srgrimes } 3671573Srgrimes old_bufp->flags |= BUF_MOD; 3681573Srgrimes } else { 3691573Srgrimes /* Move to new page */ 3701573Srgrimes if (PAIRFITS(np, (&key), (&val))) 3711573Srgrimes putpair((char *)np, &key, &val); 3721573Srgrimes else { 3731573Srgrimes new_bufp = 3741573Srgrimes __add_ovflpage(hashp, new_bufp); 3751573Srgrimes if (!new_bufp) 3761573Srgrimes return (-1); 37714287Spst np = (u_int16_t *)new_bufp->page; 3781573Srgrimes putpair((char *)np, &key, &val); 3791573Srgrimes } 3801573Srgrimes new_bufp->flags |= BUF_MOD; 3811573Srgrimes } 3821573Srgrimes } 3831573Srgrimes } 3841573Srgrimes if (last_bfp) 3851573Srgrimes __free_ovflpage(hashp, last_bfp); 3861573Srgrimes return (0); 3871573Srgrimes} 3881573Srgrimes 3891573Srgrimes/* 3901573Srgrimes * Add the given pair to the page 3911573Srgrimes * 3921573Srgrimes * Returns: 3931573Srgrimes * 0 ==> OK 3941573Srgrimes * 1 ==> failure 3951573Srgrimes */ 396189291Sdelphijint 397189291Sdelphij__addel(HTAB *hashp, BUFHEAD *bufp, const DBT *key, const DBT *val) 3981573Srgrimes{ 39992889Sobrien u_int16_t *bp, *sop; 4001573Srgrimes int do_expand; 4011573Srgrimes 40214287Spst bp = (u_int16_t *)bufp->page; 4031573Srgrimes do_expand = 0; 4041573Srgrimes while (bp[0] && (bp[2] < REAL_KEY || bp[bp[0]] < REAL_KEY)) 4051573Srgrimes /* Exception case */ 4061573Srgrimes if (bp[2] == FULL_KEY_DATA && bp[0] == 2) 4071573Srgrimes /* This is the last page of a big key/data pair 4081573Srgrimes and we need to add another page */ 4091573Srgrimes break; 4101573Srgrimes else if (bp[2] < REAL_KEY && bp[bp[0]] != OVFLPAGE) { 4111573Srgrimes bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0); 4121573Srgrimes if (!bufp) 4131573Srgrimes return (-1); 41414287Spst bp = (u_int16_t *)bufp->page; 415190490Sdelphij } else if (bp[bp[0]] != OVFLPAGE) { 416190490Sdelphij /* Short key/data pairs, no more pages */ 417190490Sdelphij break; 418190490Sdelphij } else { 4191573Srgrimes /* Try to squeeze key on this page */ 420190490Sdelphij if (bp[2] >= REAL_KEY && 421190490Sdelphij FREESPACE(bp) >= PAIRSIZE(key, val)) { 4221573Srgrimes squeeze_key(bp, key, val); 423190490Sdelphij goto stats; 4241573Srgrimes } else { 4251573Srgrimes bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0); 4261573Srgrimes if (!bufp) 4271573Srgrimes return (-1); 42814287Spst bp = (u_int16_t *)bufp->page; 4291573Srgrimes } 430190490Sdelphij } 4311573Srgrimes 4321573Srgrimes if (PAIRFITS(bp, key, val)) 4331573Srgrimes putpair(bufp->page, key, val); 4341573Srgrimes else { 4351573Srgrimes do_expand = 1; 4361573Srgrimes bufp = __add_ovflpage(hashp, bufp); 4371573Srgrimes if (!bufp) 4381573Srgrimes return (-1); 43914287Spst sop = (u_int16_t *)bufp->page; 4401573Srgrimes 4411573Srgrimes if (PAIRFITS(sop, key, val)) 4421573Srgrimes putpair((char *)sop, key, val); 4431573Srgrimes else 4441573Srgrimes if (__big_insert(hashp, bufp, key, val)) 4451573Srgrimes return (-1); 4461573Srgrimes } 447190490Sdelphijstats: 4481573Srgrimes bufp->flags |= BUF_MOD; 4491573Srgrimes /* 4501573Srgrimes * If the average number of keys per bucket exceeds the fill factor, 4511573Srgrimes * expand the table. 4521573Srgrimes */ 4531573Srgrimes hashp->NKEYS++; 4541573Srgrimes if (do_expand || 4551573Srgrimes (hashp->NKEYS / (hashp->MAX_BUCKET + 1) > hashp->FFACTOR)) 4561573Srgrimes return (__expand_table(hashp)); 4571573Srgrimes return (0); 4581573Srgrimes} 4591573Srgrimes 4601573Srgrimes/* 4611573Srgrimes * 4621573Srgrimes * Returns: 4631573Srgrimes * pointer on success 4641573Srgrimes * NULL on error 4651573Srgrimes */ 466189291SdelphijBUFHEAD * 467189291Sdelphij__add_ovflpage(HTAB *hashp, BUFHEAD *bufp) 4681573Srgrimes{ 469190489Sdelphij u_int16_t *sp, ndx, ovfl_num; 4701573Srgrimes#ifdef DEBUG1 4711573Srgrimes int tmp1, tmp2; 4721573Srgrimes#endif 47314287Spst sp = (u_int16_t *)bufp->page; 4741573Srgrimes 4751573Srgrimes /* Check if we are dynamically determining the fill factor */ 4761573Srgrimes if (hashp->FFACTOR == DEF_FFACTOR) { 4771573Srgrimes hashp->FFACTOR = sp[0] >> 1; 4781573Srgrimes if (hashp->FFACTOR < MIN_FFACTOR) 4791573Srgrimes hashp->FFACTOR = MIN_FFACTOR; 4801573Srgrimes } 4811573Srgrimes bufp->flags |= BUF_MOD; 4821573Srgrimes ovfl_num = overflow_page(hashp); 4831573Srgrimes#ifdef DEBUG1 4841573Srgrimes tmp1 = bufp->addr; 4851573Srgrimes tmp2 = bufp->ovfl ? bufp->ovfl->addr : 0; 4861573Srgrimes#endif 4871573Srgrimes if (!ovfl_num || !(bufp->ovfl = __get_buf(hashp, ovfl_num, bufp, 1))) 4881573Srgrimes return (NULL); 4891573Srgrimes bufp->ovfl->flags |= BUF_MOD; 4901573Srgrimes#ifdef DEBUG1 4911573Srgrimes (void)fprintf(stderr, "ADDOVFLPAGE: %d->ovfl was %d is now %d\n", 4921573Srgrimes tmp1, tmp2, bufp->ovfl->addr); 4931573Srgrimes#endif 4941573Srgrimes ndx = sp[0]; 4951573Srgrimes /* 4961573Srgrimes * Since a pair is allocated on a page only if there's room to add 4971573Srgrimes * an overflow page, we know that the OVFL information will fit on 4981573Srgrimes * the page. 4991573Srgrimes */ 5001573Srgrimes sp[ndx + 4] = OFFSET(sp); 5011573Srgrimes sp[ndx + 3] = FREESPACE(sp) - OVFLSIZE; 5021573Srgrimes sp[ndx + 1] = ovfl_num; 5031573Srgrimes sp[ndx + 2] = OVFLPAGE; 5041573Srgrimes sp[0] = ndx + 2; 5051573Srgrimes#ifdef HASH_STATISTICS 5061573Srgrimes hash_overflows++; 5071573Srgrimes#endif 5081573Srgrimes return (bufp->ovfl); 5091573Srgrimes} 5101573Srgrimes 5111573Srgrimes/* 5121573Srgrimes * Returns: 5131573Srgrimes * 0 indicates SUCCESS 5141573Srgrimes * -1 indicates FAILURE 5151573Srgrimes */ 516189291Sdelphijint 517189291Sdelphij__get_page(HTAB *hashp, char *p, u_int32_t bucket, int is_bucket, int is_disk, 518189291Sdelphij int is_bitmap) 5191573Srgrimes{ 520190489Sdelphij int fd, page, size, rsize; 52114287Spst u_int16_t *bp; 5221573Srgrimes 5231573Srgrimes fd = hashp->fp; 5241573Srgrimes size = hashp->BSIZE; 5251573Srgrimes 5261573Srgrimes if ((fd == -1) || !is_disk) { 5271573Srgrimes PAGE_INIT(p); 5281573Srgrimes return (0); 5291573Srgrimes } 5301573Srgrimes if (is_bucket) 5311573Srgrimes page = BUCKET_TO_PAGE(bucket); 5321573Srgrimes else 5331573Srgrimes page = OADDR_TO_PAGE(bucket); 534190486Sdelphij if ((rsize = pread(fd, p, size, (off_t)page << hashp->BSHIFT)) == -1) 5351573Srgrimes return (-1); 53614287Spst bp = (u_int16_t *)p; 5371573Srgrimes if (!rsize) 5381573Srgrimes bp[0] = 0; /* We hit the EOF, so initialize a new page */ 5391573Srgrimes else 5401573Srgrimes if (rsize != size) { 5411573Srgrimes errno = EFTYPE; 5421573Srgrimes return (-1); 5431573Srgrimes } 5441573Srgrimes if (!is_bitmap && !bp[0]) { 5451573Srgrimes PAGE_INIT(p); 5461573Srgrimes } else 5471573Srgrimes if (hashp->LORDER != BYTE_ORDER) { 54892889Sobrien int i, max; 5491573Srgrimes 5501573Srgrimes if (is_bitmap) { 5511573Srgrimes max = hashp->BSIZE >> 2; /* divide by 4 */ 5521573Srgrimes for (i = 0; i < max; i++) 55314287Spst M_32_SWAP(((int *)p)[i]); 5541573Srgrimes } else { 5551573Srgrimes M_16_SWAP(bp[0]); 5561573Srgrimes max = bp[0] + 2; 5571573Srgrimes for (i = 1; i <= max; i++) 5581573Srgrimes M_16_SWAP(bp[i]); 5591573Srgrimes } 5601573Srgrimes } 5611573Srgrimes return (0); 5621573Srgrimes} 5631573Srgrimes 5641573Srgrimes/* 5651573Srgrimes * Write page p to disk 5661573Srgrimes * 5671573Srgrimes * Returns: 5681573Srgrimes * 0 ==> OK 5691573Srgrimes * -1 ==>failure 5701573Srgrimes */ 571189291Sdelphijint 572189291Sdelphij__put_page(HTAB *hashp, char *p, u_int32_t bucket, int is_bucket, int is_bitmap) 5731573Srgrimes{ 574190489Sdelphij int fd, page, size, wsize; 5751573Srgrimes 5761573Srgrimes size = hashp->BSIZE; 5771573Srgrimes if ((hashp->fp == -1) && open_temp(hashp)) 5781573Srgrimes return (-1); 5791573Srgrimes fd = hashp->fp; 5801573Srgrimes 5811573Srgrimes if (hashp->LORDER != BYTE_ORDER) { 582190489Sdelphij int i, max; 5831573Srgrimes 5841573Srgrimes if (is_bitmap) { 5851573Srgrimes max = hashp->BSIZE >> 2; /* divide by 4 */ 5861573Srgrimes for (i = 0; i < max; i++) 58714287Spst M_32_SWAP(((int *)p)[i]); 5881573Srgrimes } else { 58914287Spst max = ((u_int16_t *)p)[0] + 2; 5901573Srgrimes for (i = 0; i <= max; i++) 59114287Spst M_16_SWAP(((u_int16_t *)p)[i]); 5921573Srgrimes } 5931573Srgrimes } 5941573Srgrimes if (is_bucket) 5951573Srgrimes page = BUCKET_TO_PAGE(bucket); 5961573Srgrimes else 5971573Srgrimes page = OADDR_TO_PAGE(bucket); 598190486Sdelphij if ((wsize = pwrite(fd, p, size, (off_t)page << hashp->BSHIFT)) == -1) 5991573Srgrimes /* Errno is set */ 6001573Srgrimes return (-1); 6011573Srgrimes if (wsize != size) { 6021573Srgrimes errno = EFTYPE; 6031573Srgrimes return (-1); 6041573Srgrimes } 6051573Srgrimes return (0); 6061573Srgrimes} 6071573Srgrimes 6081573Srgrimes#define BYTE_MASK ((1 << INT_BYTE_SHIFT) -1) 6091573Srgrimes/* 6101573Srgrimes * Initialize a new bitmap page. Bitmap pages are left in memory 6111573Srgrimes * once they are read in. 6121573Srgrimes */ 613189291Sdelphijint 614189291Sdelphij__ibitmap(HTAB *hashp, int pnum, int nbits, int ndx) 6151573Srgrimes{ 61614287Spst u_int32_t *ip; 6171573Srgrimes int clearbytes, clearints; 6181573Srgrimes 61914287Spst if ((ip = (u_int32_t *)malloc(hashp->BSIZE)) == NULL) 6201573Srgrimes return (1); 6211573Srgrimes hashp->nmaps++; 6221573Srgrimes clearints = ((nbits - 1) >> INT_BYTE_SHIFT) + 1; 6231573Srgrimes clearbytes = clearints << INT_TO_BYTE; 6241573Srgrimes (void)memset((char *)ip, 0, clearbytes); 6251573Srgrimes (void)memset(((char *)ip) + clearbytes, 0xFF, 6261573Srgrimes hashp->BSIZE - clearbytes); 6271573Srgrimes ip[clearints - 1] = ALL_SET << (nbits & BYTE_MASK); 6281573Srgrimes SETBIT(ip, 0); 62914287Spst hashp->BITMAPS[ndx] = (u_int16_t)pnum; 6301573Srgrimes hashp->mapp[ndx] = ip; 6311573Srgrimes return (0); 6321573Srgrimes} 6331573Srgrimes 63414287Spststatic u_int32_t 635189291Sdelphijfirst_free(u_int32_t map) 6361573Srgrimes{ 63792889Sobrien u_int32_t i, mask; 6381573Srgrimes 6391573Srgrimes mask = 0x1; 6401573Srgrimes for (i = 0; i < BITS_PER_MAP; i++) { 6411573Srgrimes if (!(mask & map)) 6421573Srgrimes return (i); 6431573Srgrimes mask = mask << 1; 6441573Srgrimes } 6451573Srgrimes return (i); 6461573Srgrimes} 6471573Srgrimes 64814287Spststatic u_int16_t 649189291Sdelphijoverflow_page(HTAB *hashp) 6501573Srgrimes{ 65192889Sobrien u_int32_t *freep; 65292889Sobrien int max_free, offset, splitnum; 65314287Spst u_int16_t addr; 6541573Srgrimes int bit, first_page, free_bit, free_page, i, in_use_bits, j; 6551573Srgrimes#ifdef DEBUG2 6561573Srgrimes int tmp1, tmp2; 6571573Srgrimes#endif 6581573Srgrimes splitnum = hashp->OVFL_POINT; 6591573Srgrimes max_free = hashp->SPARES[splitnum]; 6601573Srgrimes 6611573Srgrimes free_page = (max_free - 1) >> (hashp->BSHIFT + BYTE_SHIFT); 6621573Srgrimes free_bit = (max_free - 1) & ((hashp->BSIZE << BYTE_SHIFT) - 1); 6631573Srgrimes 6641573Srgrimes /* Look through all the free maps to find the first free block */ 6651573Srgrimes first_page = hashp->LAST_FREED >>(hashp->BSHIFT + BYTE_SHIFT); 6661573Srgrimes for ( i = first_page; i <= free_page; i++ ) { 66714287Spst if (!(freep = (u_int32_t *)hashp->mapp[i]) && 6681573Srgrimes !(freep = fetch_bitmap(hashp, i))) 66914287Spst return (0); 6701573Srgrimes if (i == free_page) 6711573Srgrimes in_use_bits = free_bit; 6721573Srgrimes else 6731573Srgrimes in_use_bits = (hashp->BSIZE << BYTE_SHIFT) - 1; 6748870Srgrimes 6751573Srgrimes if (i == first_page) { 6761573Srgrimes bit = hashp->LAST_FREED & 6771573Srgrimes ((hashp->BSIZE << BYTE_SHIFT) - 1); 6781573Srgrimes j = bit / BITS_PER_MAP; 6791573Srgrimes bit = bit & ~(BITS_PER_MAP - 1); 6801573Srgrimes } else { 6811573Srgrimes bit = 0; 6821573Srgrimes j = 0; 6831573Srgrimes } 6841573Srgrimes for (; bit <= in_use_bits; j++, bit += BITS_PER_MAP) 6851573Srgrimes if (freep[j] != ALL_SET) 6861573Srgrimes goto found; 6871573Srgrimes } 6881573Srgrimes 6891573Srgrimes /* No Free Page Found */ 6901573Srgrimes hashp->LAST_FREED = hashp->SPARES[splitnum]; 6911573Srgrimes hashp->SPARES[splitnum]++; 6921573Srgrimes offset = hashp->SPARES[splitnum] - 6931573Srgrimes (splitnum ? hashp->SPARES[splitnum - 1] : 0); 6941573Srgrimes 6951573Srgrimes#define OVMSG "HASH: Out of overflow pages. Increase page size\n" 6961573Srgrimes if (offset > SPLITMASK) { 6971573Srgrimes if (++splitnum >= NCACHED) { 69856698Sjasone (void)_write(STDERR_FILENO, OVMSG, sizeof(OVMSG) - 1); 699190487Sdelphij errno = EFBIG; 70014287Spst return (0); 7011573Srgrimes } 7021573Srgrimes hashp->OVFL_POINT = splitnum; 7031573Srgrimes hashp->SPARES[splitnum] = hashp->SPARES[splitnum-1]; 7041573Srgrimes hashp->SPARES[splitnum-1]--; 7051573Srgrimes offset = 1; 7061573Srgrimes } 7071573Srgrimes 7081573Srgrimes /* Check if we need to allocate a new bitmap page */ 7091573Srgrimes if (free_bit == (hashp->BSIZE << BYTE_SHIFT) - 1) { 7101573Srgrimes free_page++; 7111573Srgrimes if (free_page >= NCACHED) { 71256698Sjasone (void)_write(STDERR_FILENO, OVMSG, sizeof(OVMSG) - 1); 713190487Sdelphij errno = EFBIG; 71414287Spst return (0); 7151573Srgrimes } 7161573Srgrimes /* 7171573Srgrimes * This is tricky. The 1 indicates that you want the new page 7181573Srgrimes * allocated with 1 clear bit. Actually, you are going to 7191573Srgrimes * allocate 2 pages from this map. The first is going to be 7201573Srgrimes * the map page, the second is the overflow page we were 7211573Srgrimes * looking for. The init_bitmap routine automatically, sets 7221573Srgrimes * the first bit of itself to indicate that the bitmap itself 7231573Srgrimes * is in use. We would explicitly set the second bit, but 7241573Srgrimes * don't have to if we tell init_bitmap not to leave it clear 7251573Srgrimes * in the first place. 7261573Srgrimes */ 72714287Spst if (__ibitmap(hashp, 72814287Spst (int)OADDR_OF(splitnum, offset), 1, free_page)) 72914287Spst return (0); 7301573Srgrimes hashp->SPARES[splitnum]++; 7311573Srgrimes#ifdef DEBUG2 7321573Srgrimes free_bit = 2; 7331573Srgrimes#endif 7341573Srgrimes offset++; 7351573Srgrimes if (offset > SPLITMASK) { 7361573Srgrimes if (++splitnum >= NCACHED) { 73756698Sjasone (void)_write(STDERR_FILENO, OVMSG, 7381573Srgrimes sizeof(OVMSG) - 1); 739190487Sdelphij errno = EFBIG; 74014287Spst return (0); 7411573Srgrimes } 7421573Srgrimes hashp->OVFL_POINT = splitnum; 7431573Srgrimes hashp->SPARES[splitnum] = hashp->SPARES[splitnum-1]; 7441573Srgrimes hashp->SPARES[splitnum-1]--; 7451573Srgrimes offset = 0; 7461573Srgrimes } 7471573Srgrimes } else { 7481573Srgrimes /* 7491573Srgrimes * Free_bit addresses the last used bit. Bump it to address 7501573Srgrimes * the first available bit. 7511573Srgrimes */ 7521573Srgrimes free_bit++; 7531573Srgrimes SETBIT(freep, free_bit); 7541573Srgrimes } 7551573Srgrimes 7561573Srgrimes /* Calculate address of the new overflow page */ 7571573Srgrimes addr = OADDR_OF(splitnum, offset); 7581573Srgrimes#ifdef DEBUG2 7591573Srgrimes (void)fprintf(stderr, "OVERFLOW_PAGE: ADDR: %d BIT: %d PAGE %d\n", 7601573Srgrimes addr, free_bit, free_page); 7611573Srgrimes#endif 7621573Srgrimes return (addr); 7631573Srgrimes 7641573Srgrimesfound: 7651573Srgrimes bit = bit + first_free(freep[j]); 7661573Srgrimes SETBIT(freep, bit); 7671573Srgrimes#ifdef DEBUG2 7681573Srgrimes tmp1 = bit; 7691573Srgrimes tmp2 = i; 7701573Srgrimes#endif 7711573Srgrimes /* 7721573Srgrimes * Bits are addressed starting with 0, but overflow pages are addressed 7731573Srgrimes * beginning at 1. Bit is a bit addressnumber, so we need to increment 7741573Srgrimes * it to convert it to a page number. 7751573Srgrimes */ 7761573Srgrimes bit = 1 + bit + (i * (hashp->BSIZE << BYTE_SHIFT)); 7771573Srgrimes if (bit >= hashp->LAST_FREED) 7781573Srgrimes hashp->LAST_FREED = bit - 1; 7791573Srgrimes 7801573Srgrimes /* Calculate the split number for this page */ 7811573Srgrimes for (i = 0; (i < splitnum) && (bit > hashp->SPARES[i]); i++); 7821573Srgrimes offset = (i ? bit - hashp->SPARES[i - 1] : bit); 783190487Sdelphij if (offset >= SPLITMASK) { 784190487Sdelphij (void)_write(STDERR_FILENO, OVMSG, sizeof(OVMSG) - 1); 785190487Sdelphij errno = EFBIG; 78614287Spst return (0); /* Out of overflow pages */ 787190487Sdelphij } 7881573Srgrimes addr = OADDR_OF(i, offset); 7891573Srgrimes#ifdef DEBUG2 7901573Srgrimes (void)fprintf(stderr, "OVERFLOW_PAGE: ADDR: %d BIT: %d PAGE %d\n", 7911573Srgrimes addr, tmp1, tmp2); 7921573Srgrimes#endif 7931573Srgrimes 7941573Srgrimes /* Allocate and return the overflow page */ 7951573Srgrimes return (addr); 7961573Srgrimes} 7971573Srgrimes 7981573Srgrimes/* 7991573Srgrimes * Mark this overflow page as free. 8001573Srgrimes */ 801189291Sdelphijvoid 802189291Sdelphij__free_ovflpage(HTAB *hashp, BUFHEAD *obufp) 8031573Srgrimes{ 80492889Sobrien u_int16_t addr; 80514287Spst u_int32_t *freep; 8061573Srgrimes int bit_address, free_page, free_bit; 80714287Spst u_int16_t ndx; 8081573Srgrimes 8091573Srgrimes addr = obufp->addr; 8101573Srgrimes#ifdef DEBUG1 8111573Srgrimes (void)fprintf(stderr, "Freeing %d\n", addr); 8121573Srgrimes#endif 81314287Spst ndx = (((u_int16_t)addr) >> SPLITSHIFT); 8141573Srgrimes bit_address = 8151573Srgrimes (ndx ? hashp->SPARES[ndx - 1] : 0) + (addr & SPLITMASK) - 1; 8161573Srgrimes if (bit_address < hashp->LAST_FREED) 8171573Srgrimes hashp->LAST_FREED = bit_address; 8181573Srgrimes free_page = (bit_address >> (hashp->BSHIFT + BYTE_SHIFT)); 8191573Srgrimes free_bit = bit_address & ((hashp->BSIZE << BYTE_SHIFT) - 1); 8201573Srgrimes 8211573Srgrimes if (!(freep = hashp->mapp[free_page])) 8221573Srgrimes freep = fetch_bitmap(hashp, free_page); 8231573Srgrimes#ifdef DEBUG 8241573Srgrimes /* 8251573Srgrimes * This had better never happen. It means we tried to read a bitmap 8261573Srgrimes * that has already had overflow pages allocated off it, and we 8271573Srgrimes * failed to read it from the file. 8281573Srgrimes */ 8291573Srgrimes if (!freep) 8301573Srgrimes assert(0); 8311573Srgrimes#endif 8321573Srgrimes CLRBIT(freep, free_bit); 8331573Srgrimes#ifdef DEBUG2 8341573Srgrimes (void)fprintf(stderr, "FREE_OVFLPAGE: ADDR: %d BIT: %d PAGE %d\n", 8351573Srgrimes obufp->addr, free_bit, free_page); 8361573Srgrimes#endif 8371573Srgrimes __reclaim_buf(hashp, obufp); 8381573Srgrimes} 8391573Srgrimes 8401573Srgrimes/* 8411573Srgrimes * Returns: 8421573Srgrimes * 0 success 8431573Srgrimes * -1 failure 8441573Srgrimes */ 8451573Srgrimesstatic int 846189291Sdelphijopen_temp(HTAB *hashp) 8471573Srgrimes{ 8481573Srgrimes sigset_t set, oset; 849190485Sdelphij int len; 850190485Sdelphij char *envtmp = NULL; 851190485Sdelphij char path[MAXPATHLEN]; 8521573Srgrimes 853190485Sdelphij if (issetugid() == 0) 854190485Sdelphij envtmp = getenv("TMPDIR"); 855190485Sdelphij len = snprintf(path, 856190485Sdelphij sizeof(path), "%s/_hash.XXXXXX", envtmp ? envtmp : "/tmp"); 857190500Sdelphij if (len < 0 || len >= (int)sizeof(path)) { 858190485Sdelphij errno = ENAMETOOLONG; 859190485Sdelphij return (-1); 860190485Sdelphij } 861190485Sdelphij 8621573Srgrimes /* Block signals; make sure file goes away at process exit. */ 8631573Srgrimes (void)sigfillset(&set); 86471579Sdeischen (void)_sigprocmask(SIG_BLOCK, &set, &oset); 865190485Sdelphij if ((hashp->fp = mkstemp(path)) != -1) { 866190485Sdelphij (void)unlink(path); 86756698Sjasone (void)_fcntl(hashp->fp, F_SETFD, 1); 8681573Srgrimes } 86971579Sdeischen (void)_sigprocmask(SIG_SETMASK, &oset, (sigset_t *)NULL); 8701573Srgrimes return (hashp->fp != -1 ? 0 : -1); 8711573Srgrimes} 8721573Srgrimes 8731573Srgrimes/* 8741573Srgrimes * We have to know that the key will fit, but the last entry on the page is 8751573Srgrimes * an overflow pair, so we need to shift things. 8761573Srgrimes */ 8771573Srgrimesstatic void 878189291Sdelphijsqueeze_key(u_int16_t *sp, const DBT *key, const DBT *val) 8791573Srgrimes{ 88092889Sobrien char *p; 88114287Spst u_int16_t free_space, n, off, pageno; 8821573Srgrimes 8831573Srgrimes p = (char *)sp; 8841573Srgrimes n = sp[0]; 8851573Srgrimes free_space = FREESPACE(sp); 8861573Srgrimes off = OFFSET(sp); 8871573Srgrimes 8881573Srgrimes pageno = sp[n - 1]; 8891573Srgrimes off -= key->size; 8901573Srgrimes sp[n - 1] = off; 8911573Srgrimes memmove(p + off, key->data, key->size); 8921573Srgrimes off -= val->size; 8931573Srgrimes sp[n] = off; 8941573Srgrimes memmove(p + off, val->data, val->size); 8951573Srgrimes sp[0] = n + 2; 8961573Srgrimes sp[n + 1] = pageno; 8971573Srgrimes sp[n + 2] = OVFLPAGE; 8981573Srgrimes FREESPACE(sp) = free_space - PAIRSIZE(key, val); 8991573Srgrimes OFFSET(sp) = off; 9001573Srgrimes} 9011573Srgrimes 90214287Spststatic u_int32_t * 903189291Sdelphijfetch_bitmap(HTAB *hashp, int ndx) 9041573Srgrimes{ 9051573Srgrimes if (ndx >= hashp->nmaps) 9061573Srgrimes return (NULL); 90714287Spst if ((hashp->mapp[ndx] = (u_int32_t *)malloc(hashp->BSIZE)) == NULL) 9081573Srgrimes return (NULL); 9091573Srgrimes if (__get_page(hashp, 9101573Srgrimes (char *)hashp->mapp[ndx], hashp->BITMAPS[ndx], 0, 1, 1)) { 9111573Srgrimes free(hashp->mapp[ndx]); 9121573Srgrimes return (NULL); 9131573Srgrimes } 9141573Srgrimes return (hashp->mapp[ndx]); 9151573Srgrimes} 9161573Srgrimes 9171573Srgrimes#ifdef DEBUG4 9181573Srgrimesint 919189291Sdelphijprint_chain(int addr) 9201573Srgrimes{ 9211573Srgrimes BUFHEAD *bufp; 9221573Srgrimes short *bp, oaddr; 9231573Srgrimes 9241573Srgrimes (void)fprintf(stderr, "%d ", addr); 9251573Srgrimes bufp = __get_buf(hashp, addr, NULL, 0); 9261573Srgrimes bp = (short *)bufp->page; 9271573Srgrimes while (bp[0] && ((bp[bp[0]] == OVFLPAGE) || 9281573Srgrimes ((bp[0] > 2) && bp[2] < REAL_KEY))) { 9291573Srgrimes oaddr = bp[bp[0] - 1]; 9301573Srgrimes (void)fprintf(stderr, "%d ", (int)oaddr); 9311573Srgrimes bufp = __get_buf(hashp, (int)oaddr, bufp, 0); 9321573Srgrimes bp = (short *)bufp->page; 9331573Srgrimes } 9341573Srgrimes (void)fprintf(stderr, "\n"); 9351573Srgrimes} 9361573Srgrimes#endif 937