hash_page.c revision 92889
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 * 3. All advertising materials mentioning features or use of this software 171573Srgrimes * must display the following acknowledgement: 181573Srgrimes * This product includes software developed by the University of 191573Srgrimes * California, Berkeley and its contributors. 201573Srgrimes * 4. Neither the name of the University nor the names of its contributors 211573Srgrimes * may be used to endorse or promote products derived from this software 221573Srgrimes * without specific prior written permission. 231573Srgrimes * 241573Srgrimes * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 251573Srgrimes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 261573Srgrimes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 271573Srgrimes * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 281573Srgrimes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 291573Srgrimes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 301573Srgrimes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 311573Srgrimes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 321573Srgrimes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 331573Srgrimes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 341573Srgrimes * SUCH DAMAGE. 351573Srgrimes */ 361573Srgrimes 371573Srgrimes#if defined(LIBC_SCCS) && !defined(lint) 3814287Spststatic char sccsid[] = "@(#)hash_page.c 8.7 (Berkeley) 8/16/94"; 391573Srgrimes#endif /* LIBC_SCCS and not lint */ 4092889Sobrien#include <sys/cdefs.h> 4192889Sobrien__FBSDID("$FreeBSD: head/lib/libc/db/hash/hash_page.c 92889 2002-03-21 18:49:23Z obrien $"); 421573Srgrimes 431573Srgrimes/* 441573Srgrimes * PACKAGE: hashing 451573Srgrimes * 461573Srgrimes * DESCRIPTION: 471573Srgrimes * Page manipulation for hashing package. 481573Srgrimes * 491573Srgrimes * ROUTINES: 501573Srgrimes * 511573Srgrimes * External 521573Srgrimes * __get_page 531573Srgrimes * __add_ovflpage 541573Srgrimes * Internal 551573Srgrimes * overflow_page 561573Srgrimes * open_temp 571573Srgrimes */ 581573Srgrimes 5971579Sdeischen#include "namespace.h" 601573Srgrimes#include <sys/types.h> 611573Srgrimes 621573Srgrimes#include <errno.h> 631573Srgrimes#include <fcntl.h> 641573Srgrimes#include <signal.h> 651573Srgrimes#include <stdio.h> 661573Srgrimes#include <stdlib.h> 671573Srgrimes#include <string.h> 681573Srgrimes#include <unistd.h> 691573Srgrimes#ifdef DEBUG 701573Srgrimes#include <assert.h> 711573Srgrimes#endif 7271579Sdeischen#include "un-namespace.h" 731573Srgrimes 741573Srgrimes#include <db.h> 751573Srgrimes#include "hash.h" 761573Srgrimes#include "page.h" 771573Srgrimes#include "extern.h" 781573Srgrimes 7914287Spststatic u_int32_t *fetch_bitmap __P((HTAB *, int)); 8014287Spststatic u_int32_t first_free __P((u_int32_t)); 811573Srgrimesstatic int open_temp __P((HTAB *)); 8214287Spststatic u_int16_t overflow_page __P((HTAB *)); 831573Srgrimesstatic void putpair __P((char *, const DBT *, const DBT *)); 8414287Spststatic void squeeze_key __P((u_int16_t *, const DBT *, const DBT *)); 851573Srgrimesstatic int ugly_split 8614287Spst __P((HTAB *, u_int32_t, BUFHEAD *, BUFHEAD *, int, int)); 871573Srgrimes 881573Srgrimes#define PAGE_INIT(P) { \ 8914287Spst ((u_int16_t *)(P))[0] = 0; \ 9014287Spst ((u_int16_t *)(P))[1] = hashp->BSIZE - 3 * sizeof(u_int16_t); \ 9114287Spst ((u_int16_t *)(P))[2] = hashp->BSIZE; \ 921573Srgrimes} 931573Srgrimes 941573Srgrimes/* 951573Srgrimes * This is called AFTER we have verified that there is room on the page for 961573Srgrimes * the pair (PAIRFITS has returned true) so we go right ahead and start moving 971573Srgrimes * stuff on. 981573Srgrimes */ 991573Srgrimesstatic void 1001573Srgrimesputpair(p, key, val) 1011573Srgrimes char *p; 1021573Srgrimes const DBT *key, *val; 1031573Srgrimes{ 10492889Sobrien u_int16_t *bp, n, off; 1051573Srgrimes 10614287Spst bp = (u_int16_t *)p; 1071573Srgrimes 1081573Srgrimes /* Enter the key first. */ 1091573Srgrimes n = bp[0]; 1101573Srgrimes 1111573Srgrimes off = OFFSET(bp) - key->size; 1121573Srgrimes memmove(p + off, key->data, key->size); 1131573Srgrimes bp[++n] = off; 1141573Srgrimes 1151573Srgrimes /* Now the data. */ 1161573Srgrimes off -= val->size; 1171573Srgrimes memmove(p + off, val->data, val->size); 1181573Srgrimes bp[++n] = off; 1191573Srgrimes 1201573Srgrimes /* Adjust page info. */ 1211573Srgrimes bp[0] = n; 12214287Spst bp[n + 1] = off - ((n + 3) * sizeof(u_int16_t)); 1231573Srgrimes bp[n + 2] = off; 1241573Srgrimes} 1251573Srgrimes 1261573Srgrimes/* 1271573Srgrimes * Returns: 1281573Srgrimes * 0 OK 1291573Srgrimes * -1 error 1301573Srgrimes */ 1311573Srgrimesextern int 1321573Srgrimes__delpair(hashp, bufp, ndx) 1331573Srgrimes HTAB *hashp; 1341573Srgrimes BUFHEAD *bufp; 13592889Sobrien int ndx; 1361573Srgrimes{ 13792889Sobrien u_int16_t *bp, newoff; 13892889Sobrien int n; 13914287Spst u_int16_t pairlen; 1401573Srgrimes 14114287Spst bp = (u_int16_t *)bufp->page; 1421573Srgrimes n = bp[0]; 1431573Srgrimes 1441573Srgrimes if (bp[ndx + 1] < REAL_KEY) 1451573Srgrimes return (__big_delete(hashp, bufp)); 1461573Srgrimes if (ndx != 1) 1471573Srgrimes newoff = bp[ndx - 1]; 1481573Srgrimes else 1491573Srgrimes newoff = hashp->BSIZE; 1501573Srgrimes pairlen = newoff - bp[ndx + 1]; 1511573Srgrimes 1521573Srgrimes if (ndx != (n - 1)) { 1531573Srgrimes /* Hard Case -- need to shuffle keys */ 15492889Sobrien int i; 15592889Sobrien char *src = bufp->page + (int)OFFSET(bp); 15692889Sobrien char *dst = src + (int)pairlen; 1571573Srgrimes memmove(dst, src, bp[ndx + 1] - OFFSET(bp)); 1581573Srgrimes 1591573Srgrimes /* Now adjust the pointers */ 1601573Srgrimes for (i = ndx + 2; i <= n; i += 2) { 1611573Srgrimes if (bp[i + 1] == OVFLPAGE) { 1621573Srgrimes bp[i - 2] = bp[i]; 1631573Srgrimes bp[i - 1] = bp[i + 1]; 1641573Srgrimes } else { 1651573Srgrimes bp[i - 2] = bp[i] + pairlen; 1661573Srgrimes bp[i - 1] = bp[i + 1] + pairlen; 1671573Srgrimes } 1681573Srgrimes } 1691573Srgrimes } 1701573Srgrimes /* Finally adjust the page data */ 1711573Srgrimes bp[n] = OFFSET(bp) + pairlen; 17214287Spst bp[n - 1] = bp[n + 1] + pairlen + 2 * sizeof(u_int16_t); 1731573Srgrimes bp[0] = n - 2; 1741573Srgrimes hashp->NKEYS--; 1751573Srgrimes 1761573Srgrimes bufp->flags |= BUF_MOD; 1771573Srgrimes return (0); 1781573Srgrimes} 1791573Srgrimes/* 1801573Srgrimes * Returns: 1811573Srgrimes * 0 ==> OK 1821573Srgrimes * -1 ==> Error 1831573Srgrimes */ 1841573Srgrimesextern int 1851573Srgrimes__split_page(hashp, obucket, nbucket) 1861573Srgrimes HTAB *hashp; 18714287Spst u_int32_t obucket, nbucket; 1881573Srgrimes{ 18992889Sobrien BUFHEAD *new_bufp, *old_bufp; 19092889Sobrien u_int16_t *ino; 19192889Sobrien char *np; 1921573Srgrimes DBT key, val; 1931573Srgrimes int n, ndx, retval; 19414287Spst u_int16_t copyto, diff, off, moved; 1951573Srgrimes char *op; 1961573Srgrimes 19714287Spst copyto = (u_int16_t)hashp->BSIZE; 19814287Spst off = (u_int16_t)hashp->BSIZE; 1991573Srgrimes old_bufp = __get_buf(hashp, obucket, NULL, 0); 2001573Srgrimes if (old_bufp == NULL) 2011573Srgrimes return (-1); 2021573Srgrimes new_bufp = __get_buf(hashp, nbucket, NULL, 0); 2031573Srgrimes if (new_bufp == NULL) 2041573Srgrimes return (-1); 2051573Srgrimes 2061573Srgrimes old_bufp->flags |= (BUF_MOD | BUF_PIN); 2071573Srgrimes new_bufp->flags |= (BUF_MOD | BUF_PIN); 2081573Srgrimes 20914287Spst ino = (u_int16_t *)(op = old_bufp->page); 2101573Srgrimes np = new_bufp->page; 2111573Srgrimes 2121573Srgrimes moved = 0; 2131573Srgrimes 2141573Srgrimes for (n = 1, ndx = 1; n < ino[0]; n += 2) { 2151573Srgrimes if (ino[n + 1] < REAL_KEY) { 2161573Srgrimes retval = ugly_split(hashp, obucket, old_bufp, new_bufp, 2171573Srgrimes (int)copyto, (int)moved); 2181573Srgrimes old_bufp->flags &= ~BUF_PIN; 2191573Srgrimes new_bufp->flags &= ~BUF_PIN; 2201573Srgrimes return (retval); 2211573Srgrimes 2221573Srgrimes } 2231573Srgrimes key.data = (u_char *)op + ino[n]; 2241573Srgrimes key.size = off - ino[n]; 2251573Srgrimes 2261573Srgrimes if (__call_hash(hashp, key.data, key.size) == obucket) { 2271573Srgrimes /* Don't switch page */ 2281573Srgrimes diff = copyto - off; 2291573Srgrimes if (diff) { 2301573Srgrimes copyto = ino[n + 1] + diff; 2311573Srgrimes memmove(op + copyto, op + ino[n + 1], 2321573Srgrimes off - ino[n + 1]); 2331573Srgrimes ino[ndx] = copyto + ino[n] - ino[n + 1]; 2341573Srgrimes ino[ndx + 1] = copyto; 2351573Srgrimes } else 2361573Srgrimes copyto = ino[n + 1]; 2371573Srgrimes ndx += 2; 2381573Srgrimes } else { 2391573Srgrimes /* Switch page */ 2401573Srgrimes val.data = (u_char *)op + ino[n + 1]; 2411573Srgrimes val.size = ino[n] - ino[n + 1]; 2421573Srgrimes putpair(np, &key, &val); 2431573Srgrimes moved += 2; 2441573Srgrimes } 2451573Srgrimes 2461573Srgrimes off = ino[n + 1]; 2471573Srgrimes } 2481573Srgrimes 2491573Srgrimes /* Now clean up the page */ 2501573Srgrimes ino[0] -= moved; 25114287Spst FREESPACE(ino) = copyto - sizeof(u_int16_t) * (ino[0] + 3); 2521573Srgrimes OFFSET(ino) = copyto; 2531573Srgrimes 2541573Srgrimes#ifdef DEBUG3 2551573Srgrimes (void)fprintf(stderr, "split %d/%d\n", 25614287Spst ((u_int16_t *)np)[0] / 2, 25714287Spst ((u_int16_t *)op)[0] / 2); 2581573Srgrimes#endif 2591573Srgrimes /* unpin both pages */ 2601573Srgrimes old_bufp->flags &= ~BUF_PIN; 2611573Srgrimes new_bufp->flags &= ~BUF_PIN; 2621573Srgrimes return (0); 2631573Srgrimes} 2641573Srgrimes 2651573Srgrimes/* 2661573Srgrimes * Called when we encounter an overflow or big key/data page during split 2671573Srgrimes * handling. This is special cased since we have to begin checking whether 2681573Srgrimes * the key/data pairs fit on their respective pages and because we may need 2691573Srgrimes * overflow pages for both the old and new pages. 2701573Srgrimes * 2711573Srgrimes * The first page might be a page with regular key/data pairs in which case 2721573Srgrimes * we have a regular overflow condition and just need to go on to the next 2731573Srgrimes * page or it might be a big key/data pair in which case we need to fix the 2741573Srgrimes * big key/data pair. 2751573Srgrimes * 2761573Srgrimes * Returns: 2771573Srgrimes * 0 ==> success 2781573Srgrimes * -1 ==> failure 2791573Srgrimes */ 2801573Srgrimesstatic int 2811573Srgrimesugly_split(hashp, obucket, old_bufp, new_bufp, copyto, moved) 2821573Srgrimes HTAB *hashp; 28314287Spst u_int32_t obucket; /* Same as __split_page. */ 2841573Srgrimes BUFHEAD *old_bufp, *new_bufp; 2851573Srgrimes int copyto; /* First byte on page which contains key/data values. */ 28692889Sobrien int moved; /* Number of pairs moved to new page. */ 2871573Srgrimes{ 28892889Sobrien BUFHEAD *bufp; /* Buffer header for ino */ 28992889Sobrien u_int16_t *ino; /* Page keys come off of */ 29092889Sobrien u_int16_t *np; /* New page */ 29192889Sobrien u_int16_t *op; /* Page keys go on to if they aren't moving */ 2921573Srgrimes 2931573Srgrimes BUFHEAD *last_bfp; /* Last buf header OVFL needing to be freed */ 2941573Srgrimes DBT key, val; 2951573Srgrimes SPLIT_RETURN ret; 29614287Spst u_int16_t n, off, ov_addr, scopyto; 2971573Srgrimes char *cino; /* Character value of ino */ 2981573Srgrimes 2991573Srgrimes bufp = old_bufp; 30014287Spst ino = (u_int16_t *)old_bufp->page; 30114287Spst np = (u_int16_t *)new_bufp->page; 30214287Spst op = (u_int16_t *)old_bufp->page; 3031573Srgrimes last_bfp = NULL; 30414287Spst scopyto = (u_int16_t)copyto; /* ANSI */ 3051573Srgrimes 3061573Srgrimes n = ino[0] - 1; 3071573Srgrimes while (n < ino[0]) { 3081573Srgrimes if (ino[2] < REAL_KEY && ino[2] != OVFLPAGE) { 3091573Srgrimes if (__big_split(hashp, old_bufp, 3101573Srgrimes new_bufp, bufp, bufp->addr, obucket, &ret)) 3111573Srgrimes return (-1); 3121573Srgrimes old_bufp = ret.oldp; 3131573Srgrimes if (!old_bufp) 3141573Srgrimes return (-1); 31514287Spst op = (u_int16_t *)old_bufp->page; 3161573Srgrimes new_bufp = ret.newp; 3171573Srgrimes if (!new_bufp) 3181573Srgrimes return (-1); 31914287Spst np = (u_int16_t *)new_bufp->page; 3201573Srgrimes bufp = ret.nextp; 3211573Srgrimes if (!bufp) 3221573Srgrimes return (0); 3231573Srgrimes cino = (char *)bufp->page; 32414287Spst ino = (u_int16_t *)cino; 3251573Srgrimes last_bfp = ret.nextp; 3261573Srgrimes } else if (ino[n + 1] == OVFLPAGE) { 3271573Srgrimes ov_addr = ino[n]; 3281573Srgrimes /* 3291573Srgrimes * Fix up the old page -- the extra 2 are the fields 3301573Srgrimes * which contained the overflow information. 3311573Srgrimes */ 3321573Srgrimes ino[0] -= (moved + 2); 3331573Srgrimes FREESPACE(ino) = 33414287Spst scopyto - sizeof(u_int16_t) * (ino[0] + 3); 3351573Srgrimes OFFSET(ino) = scopyto; 3361573Srgrimes 3371573Srgrimes bufp = __get_buf(hashp, ov_addr, bufp, 0); 3381573Srgrimes if (!bufp) 3391573Srgrimes return (-1); 3401573Srgrimes 34114287Spst ino = (u_int16_t *)bufp->page; 3421573Srgrimes n = 1; 3431573Srgrimes scopyto = hashp->BSIZE; 3441573Srgrimes moved = 0; 3451573Srgrimes 3461573Srgrimes if (last_bfp) 3471573Srgrimes __free_ovflpage(hashp, last_bfp); 3481573Srgrimes last_bfp = bufp; 3491573Srgrimes } 3501573Srgrimes /* Move regular sized pairs of there are any */ 3511573Srgrimes off = hashp->BSIZE; 3521573Srgrimes for (n = 1; (n < ino[0]) && (ino[n + 1] >= REAL_KEY); n += 2) { 3531573Srgrimes cino = (char *)ino; 3541573Srgrimes key.data = (u_char *)cino + ino[n]; 3551573Srgrimes key.size = off - ino[n]; 3561573Srgrimes val.data = (u_char *)cino + ino[n + 1]; 3571573Srgrimes val.size = ino[n] - ino[n + 1]; 3581573Srgrimes off = ino[n + 1]; 3591573Srgrimes 3601573Srgrimes if (__call_hash(hashp, key.data, key.size) == obucket) { 3611573Srgrimes /* Keep on old page */ 3621573Srgrimes if (PAIRFITS(op, (&key), (&val))) 3631573Srgrimes putpair((char *)op, &key, &val); 3641573Srgrimes else { 3651573Srgrimes old_bufp = 3661573Srgrimes __add_ovflpage(hashp, old_bufp); 3671573Srgrimes if (!old_bufp) 3681573Srgrimes return (-1); 36914287Spst op = (u_int16_t *)old_bufp->page; 3701573Srgrimes putpair((char *)op, &key, &val); 3711573Srgrimes } 3721573Srgrimes old_bufp->flags |= BUF_MOD; 3731573Srgrimes } else { 3741573Srgrimes /* Move to new page */ 3751573Srgrimes if (PAIRFITS(np, (&key), (&val))) 3761573Srgrimes putpair((char *)np, &key, &val); 3771573Srgrimes else { 3781573Srgrimes new_bufp = 3791573Srgrimes __add_ovflpage(hashp, new_bufp); 3801573Srgrimes if (!new_bufp) 3811573Srgrimes return (-1); 38214287Spst np = (u_int16_t *)new_bufp->page; 3831573Srgrimes putpair((char *)np, &key, &val); 3841573Srgrimes } 3851573Srgrimes new_bufp->flags |= BUF_MOD; 3861573Srgrimes } 3871573Srgrimes } 3881573Srgrimes } 3891573Srgrimes if (last_bfp) 3901573Srgrimes __free_ovflpage(hashp, last_bfp); 3911573Srgrimes return (0); 3921573Srgrimes} 3931573Srgrimes 3941573Srgrimes/* 3951573Srgrimes * Add the given pair to the page 3961573Srgrimes * 3971573Srgrimes * Returns: 3981573Srgrimes * 0 ==> OK 3991573Srgrimes * 1 ==> failure 4001573Srgrimes */ 4011573Srgrimesextern int 4021573Srgrimes__addel(hashp, bufp, key, val) 4031573Srgrimes HTAB *hashp; 4041573Srgrimes BUFHEAD *bufp; 4051573Srgrimes const DBT *key, *val; 4061573Srgrimes{ 40792889Sobrien u_int16_t *bp, *sop; 4081573Srgrimes int do_expand; 4091573Srgrimes 41014287Spst bp = (u_int16_t *)bufp->page; 4111573Srgrimes do_expand = 0; 4121573Srgrimes while (bp[0] && (bp[2] < REAL_KEY || bp[bp[0]] < REAL_KEY)) 4131573Srgrimes /* Exception case */ 4141573Srgrimes if (bp[2] == FULL_KEY_DATA && bp[0] == 2) 4151573Srgrimes /* This is the last page of a big key/data pair 4161573Srgrimes and we need to add another page */ 4171573Srgrimes break; 4181573Srgrimes else if (bp[2] < REAL_KEY && bp[bp[0]] != OVFLPAGE) { 4191573Srgrimes bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0); 4201573Srgrimes if (!bufp) 4211573Srgrimes return (-1); 42214287Spst bp = (u_int16_t *)bufp->page; 4231573Srgrimes } else 4241573Srgrimes /* Try to squeeze key on this page */ 4251573Srgrimes if (FREESPACE(bp) > PAIRSIZE(key, val)) { 4261573Srgrimes squeeze_key(bp, key, val); 4271573Srgrimes return (0); 4281573Srgrimes } else { 4291573Srgrimes bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0); 4301573Srgrimes if (!bufp) 4311573Srgrimes return (-1); 43214287Spst bp = (u_int16_t *)bufp->page; 4331573Srgrimes } 4341573Srgrimes 4351573Srgrimes if (PAIRFITS(bp, key, val)) 4361573Srgrimes putpair(bufp->page, key, val); 4371573Srgrimes else { 4381573Srgrimes do_expand = 1; 4391573Srgrimes bufp = __add_ovflpage(hashp, bufp); 4401573Srgrimes if (!bufp) 4411573Srgrimes return (-1); 44214287Spst sop = (u_int16_t *)bufp->page; 4431573Srgrimes 4441573Srgrimes if (PAIRFITS(sop, key, val)) 4451573Srgrimes putpair((char *)sop, key, val); 4461573Srgrimes else 4471573Srgrimes if (__big_insert(hashp, bufp, key, val)) 4481573Srgrimes return (-1); 4491573Srgrimes } 4501573Srgrimes bufp->flags |= BUF_MOD; 4511573Srgrimes /* 4521573Srgrimes * If the average number of keys per bucket exceeds the fill factor, 4531573Srgrimes * expand the table. 4541573Srgrimes */ 4551573Srgrimes hashp->NKEYS++; 4561573Srgrimes if (do_expand || 4571573Srgrimes (hashp->NKEYS / (hashp->MAX_BUCKET + 1) > hashp->FFACTOR)) 4581573Srgrimes return (__expand_table(hashp)); 4591573Srgrimes return (0); 4601573Srgrimes} 4611573Srgrimes 4621573Srgrimes/* 4631573Srgrimes * 4641573Srgrimes * Returns: 4651573Srgrimes * pointer on success 4661573Srgrimes * NULL on error 4671573Srgrimes */ 4681573Srgrimesextern BUFHEAD * 4691573Srgrimes__add_ovflpage(hashp, bufp) 4701573Srgrimes HTAB *hashp; 4711573Srgrimes BUFHEAD *bufp; 4721573Srgrimes{ 47392889Sobrien u_int16_t *sp; 47414287Spst u_int16_t ndx, ovfl_num; 4751573Srgrimes#ifdef DEBUG1 4761573Srgrimes int tmp1, tmp2; 4771573Srgrimes#endif 47814287Spst sp = (u_int16_t *)bufp->page; 4791573Srgrimes 4801573Srgrimes /* Check if we are dynamically determining the fill factor */ 4811573Srgrimes if (hashp->FFACTOR == DEF_FFACTOR) { 4821573Srgrimes hashp->FFACTOR = sp[0] >> 1; 4831573Srgrimes if (hashp->FFACTOR < MIN_FFACTOR) 4841573Srgrimes hashp->FFACTOR = MIN_FFACTOR; 4851573Srgrimes } 4861573Srgrimes bufp->flags |= BUF_MOD; 4871573Srgrimes ovfl_num = overflow_page(hashp); 4881573Srgrimes#ifdef DEBUG1 4891573Srgrimes tmp1 = bufp->addr; 4901573Srgrimes tmp2 = bufp->ovfl ? bufp->ovfl->addr : 0; 4911573Srgrimes#endif 4921573Srgrimes if (!ovfl_num || !(bufp->ovfl = __get_buf(hashp, ovfl_num, bufp, 1))) 4931573Srgrimes return (NULL); 4941573Srgrimes bufp->ovfl->flags |= BUF_MOD; 4951573Srgrimes#ifdef DEBUG1 4961573Srgrimes (void)fprintf(stderr, "ADDOVFLPAGE: %d->ovfl was %d is now %d\n", 4971573Srgrimes tmp1, tmp2, bufp->ovfl->addr); 4981573Srgrimes#endif 4991573Srgrimes ndx = sp[0]; 5001573Srgrimes /* 5011573Srgrimes * Since a pair is allocated on a page only if there's room to add 5021573Srgrimes * an overflow page, we know that the OVFL information will fit on 5031573Srgrimes * the page. 5041573Srgrimes */ 5051573Srgrimes sp[ndx + 4] = OFFSET(sp); 5061573Srgrimes sp[ndx + 3] = FREESPACE(sp) - OVFLSIZE; 5071573Srgrimes sp[ndx + 1] = ovfl_num; 5081573Srgrimes sp[ndx + 2] = OVFLPAGE; 5091573Srgrimes sp[0] = ndx + 2; 5101573Srgrimes#ifdef HASH_STATISTICS 5111573Srgrimes hash_overflows++; 5121573Srgrimes#endif 5131573Srgrimes return (bufp->ovfl); 5141573Srgrimes} 5151573Srgrimes 5161573Srgrimes/* 5171573Srgrimes * Returns: 5181573Srgrimes * 0 indicates SUCCESS 5191573Srgrimes * -1 indicates FAILURE 5201573Srgrimes */ 5211573Srgrimesextern int 5221573Srgrimes__get_page(hashp, p, bucket, is_bucket, is_disk, is_bitmap) 5231573Srgrimes HTAB *hashp; 5241573Srgrimes char *p; 52514287Spst u_int32_t bucket; 5261573Srgrimes int is_bucket, is_disk, is_bitmap; 5271573Srgrimes{ 52892889Sobrien int fd, page, size; 5291573Srgrimes int rsize; 53014287Spst u_int16_t *bp; 5311573Srgrimes 5321573Srgrimes fd = hashp->fp; 5331573Srgrimes size = hashp->BSIZE; 5341573Srgrimes 5351573Srgrimes if ((fd == -1) || !is_disk) { 5361573Srgrimes PAGE_INIT(p); 5371573Srgrimes return (0); 5381573Srgrimes } 5391573Srgrimes if (is_bucket) 5401573Srgrimes page = BUCKET_TO_PAGE(bucket); 5411573Srgrimes else 5421573Srgrimes page = OADDR_TO_PAGE(bucket); 5431573Srgrimes if ((lseek(fd, (off_t)page << hashp->BSHIFT, SEEK_SET) == -1) || 54456698Sjasone ((rsize = _read(fd, p, size)) == -1)) 5451573Srgrimes return (-1); 54614287Spst bp = (u_int16_t *)p; 5471573Srgrimes if (!rsize) 5481573Srgrimes bp[0] = 0; /* We hit the EOF, so initialize a new page */ 5491573Srgrimes else 5501573Srgrimes if (rsize != size) { 5511573Srgrimes errno = EFTYPE; 5521573Srgrimes return (-1); 5531573Srgrimes } 5541573Srgrimes if (!is_bitmap && !bp[0]) { 5551573Srgrimes PAGE_INIT(p); 5561573Srgrimes } else 5571573Srgrimes if (hashp->LORDER != BYTE_ORDER) { 55892889Sobrien int i, max; 5591573Srgrimes 5601573Srgrimes if (is_bitmap) { 5611573Srgrimes max = hashp->BSIZE >> 2; /* divide by 4 */ 5621573Srgrimes for (i = 0; i < max; i++) 56314287Spst M_32_SWAP(((int *)p)[i]); 5641573Srgrimes } else { 5651573Srgrimes M_16_SWAP(bp[0]); 5661573Srgrimes max = bp[0] + 2; 5671573Srgrimes for (i = 1; i <= max; i++) 5681573Srgrimes M_16_SWAP(bp[i]); 5691573Srgrimes } 5701573Srgrimes } 5711573Srgrimes return (0); 5721573Srgrimes} 5731573Srgrimes 5741573Srgrimes/* 5751573Srgrimes * Write page p to disk 5761573Srgrimes * 5771573Srgrimes * Returns: 5781573Srgrimes * 0 ==> OK 5791573Srgrimes * -1 ==>failure 5801573Srgrimes */ 5811573Srgrimesextern int 5821573Srgrimes__put_page(hashp, p, bucket, is_bucket, is_bitmap) 5831573Srgrimes HTAB *hashp; 5841573Srgrimes char *p; 58514287Spst u_int32_t bucket; 5861573Srgrimes int is_bucket, is_bitmap; 5871573Srgrimes{ 58892889Sobrien int fd, page, size; 5891573Srgrimes int wsize; 5901573Srgrimes 5911573Srgrimes size = hashp->BSIZE; 5921573Srgrimes if ((hashp->fp == -1) && open_temp(hashp)) 5931573Srgrimes return (-1); 5941573Srgrimes fd = hashp->fp; 5951573Srgrimes 5961573Srgrimes if (hashp->LORDER != BYTE_ORDER) { 59792889Sobrien int i; 59892889Sobrien int max; 5991573Srgrimes 6001573Srgrimes if (is_bitmap) { 6011573Srgrimes max = hashp->BSIZE >> 2; /* divide by 4 */ 6021573Srgrimes for (i = 0; i < max; i++) 60314287Spst M_32_SWAP(((int *)p)[i]); 6041573Srgrimes } else { 60514287Spst max = ((u_int16_t *)p)[0] + 2; 6061573Srgrimes for (i = 0; i <= max; i++) 60714287Spst M_16_SWAP(((u_int16_t *)p)[i]); 6081573Srgrimes } 6091573Srgrimes } 6101573Srgrimes if (is_bucket) 6111573Srgrimes page = BUCKET_TO_PAGE(bucket); 6121573Srgrimes else 6131573Srgrimes page = OADDR_TO_PAGE(bucket); 6141573Srgrimes if ((lseek(fd, (off_t)page << hashp->BSHIFT, SEEK_SET) == -1) || 61556698Sjasone ((wsize = _write(fd, p, size)) == -1)) 6161573Srgrimes /* Errno is set */ 6171573Srgrimes return (-1); 6181573Srgrimes if (wsize != size) { 6191573Srgrimes errno = EFTYPE; 6201573Srgrimes return (-1); 6211573Srgrimes } 6221573Srgrimes return (0); 6231573Srgrimes} 6241573Srgrimes 6251573Srgrimes#define BYTE_MASK ((1 << INT_BYTE_SHIFT) -1) 6261573Srgrimes/* 6271573Srgrimes * Initialize a new bitmap page. Bitmap pages are left in memory 6281573Srgrimes * once they are read in. 6291573Srgrimes */ 6301573Srgrimesextern int 63114287Spst__ibitmap(hashp, pnum, nbits, ndx) 6321573Srgrimes HTAB *hashp; 6331573Srgrimes int pnum, nbits, ndx; 6341573Srgrimes{ 63514287Spst u_int32_t *ip; 6361573Srgrimes int clearbytes, clearints; 6371573Srgrimes 63814287Spst if ((ip = (u_int32_t *)malloc(hashp->BSIZE)) == NULL) 6391573Srgrimes return (1); 6401573Srgrimes hashp->nmaps++; 6411573Srgrimes clearints = ((nbits - 1) >> INT_BYTE_SHIFT) + 1; 6421573Srgrimes clearbytes = clearints << INT_TO_BYTE; 6431573Srgrimes (void)memset((char *)ip, 0, clearbytes); 6441573Srgrimes (void)memset(((char *)ip) + clearbytes, 0xFF, 6451573Srgrimes hashp->BSIZE - clearbytes); 6461573Srgrimes ip[clearints - 1] = ALL_SET << (nbits & BYTE_MASK); 6471573Srgrimes SETBIT(ip, 0); 64814287Spst hashp->BITMAPS[ndx] = (u_int16_t)pnum; 6491573Srgrimes hashp->mapp[ndx] = ip; 6501573Srgrimes return (0); 6511573Srgrimes} 6521573Srgrimes 65314287Spststatic u_int32_t 6541573Srgrimesfirst_free(map) 65514287Spst u_int32_t map; 6561573Srgrimes{ 65792889Sobrien u_int32_t i, mask; 6581573Srgrimes 6591573Srgrimes mask = 0x1; 6601573Srgrimes for (i = 0; i < BITS_PER_MAP; i++) { 6611573Srgrimes if (!(mask & map)) 6621573Srgrimes return (i); 6631573Srgrimes mask = mask << 1; 6641573Srgrimes } 6651573Srgrimes return (i); 6661573Srgrimes} 6671573Srgrimes 66814287Spststatic u_int16_t 6691573Srgrimesoverflow_page(hashp) 6701573Srgrimes HTAB *hashp; 6711573Srgrimes{ 67292889Sobrien u_int32_t *freep; 67392889Sobrien int max_free, offset, splitnum; 67414287Spst u_int16_t addr; 6751573Srgrimes int bit, first_page, free_bit, free_page, i, in_use_bits, j; 6761573Srgrimes#ifdef DEBUG2 6771573Srgrimes int tmp1, tmp2; 6781573Srgrimes#endif 6791573Srgrimes splitnum = hashp->OVFL_POINT; 6801573Srgrimes max_free = hashp->SPARES[splitnum]; 6811573Srgrimes 6821573Srgrimes free_page = (max_free - 1) >> (hashp->BSHIFT + BYTE_SHIFT); 6831573Srgrimes free_bit = (max_free - 1) & ((hashp->BSIZE << BYTE_SHIFT) - 1); 6841573Srgrimes 6851573Srgrimes /* Look through all the free maps to find the first free block */ 6861573Srgrimes first_page = hashp->LAST_FREED >>(hashp->BSHIFT + BYTE_SHIFT); 6871573Srgrimes for ( i = first_page; i <= free_page; i++ ) { 68814287Spst if (!(freep = (u_int32_t *)hashp->mapp[i]) && 6891573Srgrimes !(freep = fetch_bitmap(hashp, i))) 69014287Spst return (0); 6911573Srgrimes if (i == free_page) 6921573Srgrimes in_use_bits = free_bit; 6931573Srgrimes else 6941573Srgrimes in_use_bits = (hashp->BSIZE << BYTE_SHIFT) - 1; 6958870Srgrimes 6961573Srgrimes if (i == first_page) { 6971573Srgrimes bit = hashp->LAST_FREED & 6981573Srgrimes ((hashp->BSIZE << BYTE_SHIFT) - 1); 6991573Srgrimes j = bit / BITS_PER_MAP; 7001573Srgrimes bit = bit & ~(BITS_PER_MAP - 1); 7011573Srgrimes } else { 7021573Srgrimes bit = 0; 7031573Srgrimes j = 0; 7041573Srgrimes } 7051573Srgrimes for (; bit <= in_use_bits; j++, bit += BITS_PER_MAP) 7061573Srgrimes if (freep[j] != ALL_SET) 7071573Srgrimes goto found; 7081573Srgrimes } 7091573Srgrimes 7101573Srgrimes /* No Free Page Found */ 7111573Srgrimes hashp->LAST_FREED = hashp->SPARES[splitnum]; 7121573Srgrimes hashp->SPARES[splitnum]++; 7131573Srgrimes offset = hashp->SPARES[splitnum] - 7141573Srgrimes (splitnum ? hashp->SPARES[splitnum - 1] : 0); 7151573Srgrimes 7161573Srgrimes#define OVMSG "HASH: Out of overflow pages. Increase page size\n" 7171573Srgrimes if (offset > SPLITMASK) { 7181573Srgrimes if (++splitnum >= NCACHED) { 71956698Sjasone (void)_write(STDERR_FILENO, OVMSG, sizeof(OVMSG) - 1); 72014287Spst return (0); 7211573Srgrimes } 7221573Srgrimes hashp->OVFL_POINT = splitnum; 7231573Srgrimes hashp->SPARES[splitnum] = hashp->SPARES[splitnum-1]; 7241573Srgrimes hashp->SPARES[splitnum-1]--; 7251573Srgrimes offset = 1; 7261573Srgrimes } 7271573Srgrimes 7281573Srgrimes /* Check if we need to allocate a new bitmap page */ 7291573Srgrimes if (free_bit == (hashp->BSIZE << BYTE_SHIFT) - 1) { 7301573Srgrimes free_page++; 7311573Srgrimes if (free_page >= NCACHED) { 73256698Sjasone (void)_write(STDERR_FILENO, OVMSG, sizeof(OVMSG) - 1); 73314287Spst return (0); 7341573Srgrimes } 7351573Srgrimes /* 7361573Srgrimes * This is tricky. The 1 indicates that you want the new page 7371573Srgrimes * allocated with 1 clear bit. Actually, you are going to 7381573Srgrimes * allocate 2 pages from this map. The first is going to be 7391573Srgrimes * the map page, the second is the overflow page we were 7401573Srgrimes * looking for. The init_bitmap routine automatically, sets 7411573Srgrimes * the first bit of itself to indicate that the bitmap itself 7421573Srgrimes * is in use. We would explicitly set the second bit, but 7431573Srgrimes * don't have to if we tell init_bitmap not to leave it clear 7441573Srgrimes * in the first place. 7451573Srgrimes */ 74614287Spst if (__ibitmap(hashp, 74714287Spst (int)OADDR_OF(splitnum, offset), 1, free_page)) 74814287Spst return (0); 7491573Srgrimes hashp->SPARES[splitnum]++; 7501573Srgrimes#ifdef DEBUG2 7511573Srgrimes free_bit = 2; 7521573Srgrimes#endif 7531573Srgrimes offset++; 7541573Srgrimes if (offset > SPLITMASK) { 7551573Srgrimes if (++splitnum >= NCACHED) { 75656698Sjasone (void)_write(STDERR_FILENO, OVMSG, 7571573Srgrimes sizeof(OVMSG) - 1); 75814287Spst return (0); 7591573Srgrimes } 7601573Srgrimes hashp->OVFL_POINT = splitnum; 7611573Srgrimes hashp->SPARES[splitnum] = hashp->SPARES[splitnum-1]; 7621573Srgrimes hashp->SPARES[splitnum-1]--; 7631573Srgrimes offset = 0; 7641573Srgrimes } 7651573Srgrimes } else { 7661573Srgrimes /* 7671573Srgrimes * Free_bit addresses the last used bit. Bump it to address 7681573Srgrimes * the first available bit. 7691573Srgrimes */ 7701573Srgrimes free_bit++; 7711573Srgrimes SETBIT(freep, free_bit); 7721573Srgrimes } 7731573Srgrimes 7741573Srgrimes /* Calculate address of the new overflow page */ 7751573Srgrimes addr = OADDR_OF(splitnum, offset); 7761573Srgrimes#ifdef DEBUG2 7771573Srgrimes (void)fprintf(stderr, "OVERFLOW_PAGE: ADDR: %d BIT: %d PAGE %d\n", 7781573Srgrimes addr, free_bit, free_page); 7791573Srgrimes#endif 7801573Srgrimes return (addr); 7811573Srgrimes 7821573Srgrimesfound: 7831573Srgrimes bit = bit + first_free(freep[j]); 7841573Srgrimes SETBIT(freep, bit); 7851573Srgrimes#ifdef DEBUG2 7861573Srgrimes tmp1 = bit; 7871573Srgrimes tmp2 = i; 7881573Srgrimes#endif 7891573Srgrimes /* 7901573Srgrimes * Bits are addressed starting with 0, but overflow pages are addressed 7911573Srgrimes * beginning at 1. Bit is a bit addressnumber, so we need to increment 7921573Srgrimes * it to convert it to a page number. 7931573Srgrimes */ 7941573Srgrimes bit = 1 + bit + (i * (hashp->BSIZE << BYTE_SHIFT)); 7951573Srgrimes if (bit >= hashp->LAST_FREED) 7961573Srgrimes hashp->LAST_FREED = bit - 1; 7971573Srgrimes 7981573Srgrimes /* Calculate the split number for this page */ 7991573Srgrimes for (i = 0; (i < splitnum) && (bit > hashp->SPARES[i]); i++); 8001573Srgrimes offset = (i ? bit - hashp->SPARES[i - 1] : bit); 8011573Srgrimes if (offset >= SPLITMASK) 80214287Spst return (0); /* Out of overflow pages */ 8031573Srgrimes addr = OADDR_OF(i, offset); 8041573Srgrimes#ifdef DEBUG2 8051573Srgrimes (void)fprintf(stderr, "OVERFLOW_PAGE: ADDR: %d BIT: %d PAGE %d\n", 8061573Srgrimes addr, tmp1, tmp2); 8071573Srgrimes#endif 8081573Srgrimes 8091573Srgrimes /* Allocate and return the overflow page */ 8101573Srgrimes return (addr); 8111573Srgrimes} 8121573Srgrimes 8131573Srgrimes/* 8141573Srgrimes * Mark this overflow page as free. 8151573Srgrimes */ 8161573Srgrimesextern void 8171573Srgrimes__free_ovflpage(hashp, obufp) 8181573Srgrimes HTAB *hashp; 8191573Srgrimes BUFHEAD *obufp; 8201573Srgrimes{ 82192889Sobrien u_int16_t addr; 82214287Spst u_int32_t *freep; 8231573Srgrimes int bit_address, free_page, free_bit; 82414287Spst u_int16_t ndx; 8251573Srgrimes 8261573Srgrimes addr = obufp->addr; 8271573Srgrimes#ifdef DEBUG1 8281573Srgrimes (void)fprintf(stderr, "Freeing %d\n", addr); 8291573Srgrimes#endif 83014287Spst ndx = (((u_int16_t)addr) >> SPLITSHIFT); 8311573Srgrimes bit_address = 8321573Srgrimes (ndx ? hashp->SPARES[ndx - 1] : 0) + (addr & SPLITMASK) - 1; 8331573Srgrimes if (bit_address < hashp->LAST_FREED) 8341573Srgrimes hashp->LAST_FREED = bit_address; 8351573Srgrimes free_page = (bit_address >> (hashp->BSHIFT + BYTE_SHIFT)); 8361573Srgrimes free_bit = bit_address & ((hashp->BSIZE << BYTE_SHIFT) - 1); 8371573Srgrimes 8381573Srgrimes if (!(freep = hashp->mapp[free_page])) 8391573Srgrimes freep = fetch_bitmap(hashp, free_page); 8401573Srgrimes#ifdef DEBUG 8411573Srgrimes /* 8421573Srgrimes * This had better never happen. It means we tried to read a bitmap 8431573Srgrimes * that has already had overflow pages allocated off it, and we 8441573Srgrimes * failed to read it from the file. 8451573Srgrimes */ 8461573Srgrimes if (!freep) 8471573Srgrimes assert(0); 8481573Srgrimes#endif 8491573Srgrimes CLRBIT(freep, free_bit); 8501573Srgrimes#ifdef DEBUG2 8511573Srgrimes (void)fprintf(stderr, "FREE_OVFLPAGE: ADDR: %d BIT: %d PAGE %d\n", 8521573Srgrimes obufp->addr, free_bit, free_page); 8531573Srgrimes#endif 8541573Srgrimes __reclaim_buf(hashp, obufp); 8551573Srgrimes} 8561573Srgrimes 8571573Srgrimes/* 8581573Srgrimes * Returns: 8591573Srgrimes * 0 success 8601573Srgrimes * -1 failure 8611573Srgrimes */ 8621573Srgrimesstatic int 8631573Srgrimesopen_temp(hashp) 8641573Srgrimes HTAB *hashp; 8651573Srgrimes{ 8661573Srgrimes sigset_t set, oset; 8671573Srgrimes static char namestr[] = "_hashXXXXXX"; 8681573Srgrimes 8691573Srgrimes /* Block signals; make sure file goes away at process exit. */ 8701573Srgrimes (void)sigfillset(&set); 87171579Sdeischen (void)_sigprocmask(SIG_BLOCK, &set, &oset); 8721573Srgrimes if ((hashp->fp = mkstemp(namestr)) != -1) { 8731573Srgrimes (void)unlink(namestr); 87456698Sjasone (void)_fcntl(hashp->fp, F_SETFD, 1); 8751573Srgrimes } 87671579Sdeischen (void)_sigprocmask(SIG_SETMASK, &oset, (sigset_t *)NULL); 8771573Srgrimes return (hashp->fp != -1 ? 0 : -1); 8781573Srgrimes} 8791573Srgrimes 8801573Srgrimes/* 8811573Srgrimes * We have to know that the key will fit, but the last entry on the page is 8821573Srgrimes * an overflow pair, so we need to shift things. 8831573Srgrimes */ 8841573Srgrimesstatic void 8851573Srgrimessqueeze_key(sp, key, val) 88614287Spst u_int16_t *sp; 8871573Srgrimes const DBT *key, *val; 8881573Srgrimes{ 88992889Sobrien char *p; 89014287Spst u_int16_t free_space, n, off, pageno; 8911573Srgrimes 8921573Srgrimes p = (char *)sp; 8931573Srgrimes n = sp[0]; 8941573Srgrimes free_space = FREESPACE(sp); 8951573Srgrimes off = OFFSET(sp); 8961573Srgrimes 8971573Srgrimes pageno = sp[n - 1]; 8981573Srgrimes off -= key->size; 8991573Srgrimes sp[n - 1] = off; 9001573Srgrimes memmove(p + off, key->data, key->size); 9011573Srgrimes off -= val->size; 9021573Srgrimes sp[n] = off; 9031573Srgrimes memmove(p + off, val->data, val->size); 9041573Srgrimes sp[0] = n + 2; 9051573Srgrimes sp[n + 1] = pageno; 9061573Srgrimes sp[n + 2] = OVFLPAGE; 9071573Srgrimes FREESPACE(sp) = free_space - PAIRSIZE(key, val); 9081573Srgrimes OFFSET(sp) = off; 9091573Srgrimes} 9101573Srgrimes 91114287Spststatic u_int32_t * 9121573Srgrimesfetch_bitmap(hashp, ndx) 9131573Srgrimes HTAB *hashp; 9141573Srgrimes int ndx; 9151573Srgrimes{ 9161573Srgrimes if (ndx >= hashp->nmaps) 9171573Srgrimes return (NULL); 91814287Spst if ((hashp->mapp[ndx] = (u_int32_t *)malloc(hashp->BSIZE)) == NULL) 9191573Srgrimes return (NULL); 9201573Srgrimes if (__get_page(hashp, 9211573Srgrimes (char *)hashp->mapp[ndx], hashp->BITMAPS[ndx], 0, 1, 1)) { 9221573Srgrimes free(hashp->mapp[ndx]); 9231573Srgrimes return (NULL); 9241573Srgrimes } 9251573Srgrimes return (hashp->mapp[ndx]); 9261573Srgrimes} 9271573Srgrimes 9281573Srgrimes#ifdef DEBUG4 9291573Srgrimesint 9301573Srgrimesprint_chain(addr) 9311573Srgrimes int addr; 9321573Srgrimes{ 9331573Srgrimes BUFHEAD *bufp; 9341573Srgrimes short *bp, oaddr; 9351573Srgrimes 9361573Srgrimes (void)fprintf(stderr, "%d ", addr); 9371573Srgrimes bufp = __get_buf(hashp, addr, NULL, 0); 9381573Srgrimes bp = (short *)bufp->page; 9391573Srgrimes while (bp[0] && ((bp[bp[0]] == OVFLPAGE) || 9401573Srgrimes ((bp[0] > 2) && bp[2] < REAL_KEY))) { 9411573Srgrimes oaddr = bp[bp[0] - 1]; 9421573Srgrimes (void)fprintf(stderr, "%d ", (int)oaddr); 9431573Srgrimes bufp = __get_buf(hashp, (int)oaddr, bufp, 0); 9441573Srgrimes bp = (short *)bufp->page; 9451573Srgrimes } 9461573Srgrimes (void)fprintf(stderr, "\n"); 9471573Srgrimes} 9481573Srgrimes#endif 949