hash_page.c revision 14287
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 */ 401573Srgrimes 411573Srgrimes/* 421573Srgrimes * PACKAGE: hashing 431573Srgrimes * 441573Srgrimes * DESCRIPTION: 451573Srgrimes * Page manipulation for hashing package. 461573Srgrimes * 471573Srgrimes * ROUTINES: 481573Srgrimes * 491573Srgrimes * External 501573Srgrimes * __get_page 511573Srgrimes * __add_ovflpage 521573Srgrimes * Internal 531573Srgrimes * overflow_page 541573Srgrimes * open_temp 551573Srgrimes */ 561573Srgrimes 571573Srgrimes#include <sys/types.h> 581573Srgrimes 591573Srgrimes#include <errno.h> 601573Srgrimes#include <fcntl.h> 611573Srgrimes#include <signal.h> 621573Srgrimes#include <stdio.h> 631573Srgrimes#include <stdlib.h> 641573Srgrimes#include <string.h> 651573Srgrimes#include <unistd.h> 661573Srgrimes#ifdef DEBUG 671573Srgrimes#include <assert.h> 681573Srgrimes#endif 691573Srgrimes 701573Srgrimes#include <db.h> 711573Srgrimes#include "hash.h" 721573Srgrimes#include "page.h" 731573Srgrimes#include "extern.h" 741573Srgrimes 7514287Spststatic u_int32_t *fetch_bitmap __P((HTAB *, int)); 7614287Spststatic u_int32_t first_free __P((u_int32_t)); 771573Srgrimesstatic int open_temp __P((HTAB *)); 7814287Spststatic u_int16_t overflow_page __P((HTAB *)); 791573Srgrimesstatic void putpair __P((char *, const DBT *, const DBT *)); 8014287Spststatic void squeeze_key __P((u_int16_t *, const DBT *, const DBT *)); 811573Srgrimesstatic int ugly_split 8214287Spst __P((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 961573Srgrimesputpair(p, key, val) 971573Srgrimes char *p; 981573Srgrimes const DBT *key, *val; 991573Srgrimes{ 10014287Spst register u_int16_t *bp, n, off; 1011573Srgrimes 10214287Spst bp = (u_int16_t *)p; 1031573Srgrimes 1041573Srgrimes /* Enter the key first. */ 1051573Srgrimes n = bp[0]; 1061573Srgrimes 1071573Srgrimes off = OFFSET(bp) - key->size; 1081573Srgrimes memmove(p + off, key->data, key->size); 1091573Srgrimes bp[++n] = off; 1101573Srgrimes 1111573Srgrimes /* Now the data. */ 1121573Srgrimes off -= val->size; 1131573Srgrimes memmove(p + off, val->data, val->size); 1141573Srgrimes bp[++n] = off; 1151573Srgrimes 1161573Srgrimes /* Adjust page info. */ 1171573Srgrimes bp[0] = n; 11814287Spst bp[n + 1] = off - ((n + 3) * sizeof(u_int16_t)); 1191573Srgrimes bp[n + 2] = off; 1201573Srgrimes} 1211573Srgrimes 1221573Srgrimes/* 1231573Srgrimes * Returns: 1241573Srgrimes * 0 OK 1251573Srgrimes * -1 error 1261573Srgrimes */ 1271573Srgrimesextern int 1281573Srgrimes__delpair(hashp, bufp, ndx) 1291573Srgrimes HTAB *hashp; 1301573Srgrimes BUFHEAD *bufp; 1311573Srgrimes register int ndx; 1321573Srgrimes{ 13314287Spst register u_int16_t *bp, newoff; 1341573Srgrimes register int n; 13514287Spst u_int16_t pairlen; 1361573Srgrimes 13714287Spst bp = (u_int16_t *)bufp->page; 1381573Srgrimes n = bp[0]; 1391573Srgrimes 1401573Srgrimes if (bp[ndx + 1] < REAL_KEY) 1411573Srgrimes return (__big_delete(hashp, bufp)); 1421573Srgrimes if (ndx != 1) 1431573Srgrimes newoff = bp[ndx - 1]; 1441573Srgrimes else 1451573Srgrimes newoff = hashp->BSIZE; 1461573Srgrimes pairlen = newoff - bp[ndx + 1]; 1471573Srgrimes 1481573Srgrimes if (ndx != (n - 1)) { 1491573Srgrimes /* Hard Case -- need to shuffle keys */ 1501573Srgrimes register int i; 1511573Srgrimes register char *src = bufp->page + (int)OFFSET(bp); 1521573Srgrimes register char *dst = src + (int)pairlen; 1531573Srgrimes memmove(dst, src, bp[ndx + 1] - OFFSET(bp)); 1541573Srgrimes 1551573Srgrimes /* Now adjust the pointers */ 1561573Srgrimes for (i = ndx + 2; i <= n; i += 2) { 1571573Srgrimes if (bp[i + 1] == OVFLPAGE) { 1581573Srgrimes bp[i - 2] = bp[i]; 1591573Srgrimes bp[i - 1] = bp[i + 1]; 1601573Srgrimes } else { 1611573Srgrimes bp[i - 2] = bp[i] + pairlen; 1621573Srgrimes bp[i - 1] = bp[i + 1] + pairlen; 1631573Srgrimes } 1641573Srgrimes } 1651573Srgrimes } 1661573Srgrimes /* Finally adjust the page data */ 1671573Srgrimes bp[n] = OFFSET(bp) + pairlen; 16814287Spst bp[n - 1] = bp[n + 1] + pairlen + 2 * sizeof(u_int16_t); 1691573Srgrimes bp[0] = n - 2; 1701573Srgrimes hashp->NKEYS--; 1711573Srgrimes 1721573Srgrimes bufp->flags |= BUF_MOD; 1731573Srgrimes return (0); 1741573Srgrimes} 1751573Srgrimes/* 1761573Srgrimes * Returns: 1771573Srgrimes * 0 ==> OK 1781573Srgrimes * -1 ==> Error 1791573Srgrimes */ 1801573Srgrimesextern int 1811573Srgrimes__split_page(hashp, obucket, nbucket) 1821573Srgrimes HTAB *hashp; 18314287Spst u_int32_t obucket, nbucket; 1841573Srgrimes{ 1851573Srgrimes register BUFHEAD *new_bufp, *old_bufp; 18614287Spst register u_int16_t *ino; 1871573Srgrimes register 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 2771573Srgrimesugly_split(hashp, obucket, old_bufp, new_bufp, copyto, moved) 2781573Srgrimes HTAB *hashp; 27914287Spst u_int32_t obucket; /* Same as __split_page. */ 2801573Srgrimes BUFHEAD *old_bufp, *new_bufp; 2811573Srgrimes int copyto; /* First byte on page which contains key/data values. */ 2821573Srgrimes int moved; /* Number of pairs moved to new page. */ 2831573Srgrimes{ 2841573Srgrimes register BUFHEAD *bufp; /* Buffer header for ino */ 28514287Spst register u_int16_t *ino; /* Page keys come off of */ 28614287Spst register u_int16_t *np; /* New page */ 28714287Spst register 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 */ 3971573Srgrimesextern int 3981573Srgrimes__addel(hashp, bufp, key, val) 3991573Srgrimes HTAB *hashp; 4001573Srgrimes BUFHEAD *bufp; 4011573Srgrimes const DBT *key, *val; 4021573Srgrimes{ 40314287Spst register u_int16_t *bp, *sop; 4041573Srgrimes int do_expand; 4051573Srgrimes 40614287Spst bp = (u_int16_t *)bufp->page; 4071573Srgrimes do_expand = 0; 4081573Srgrimes while (bp[0] && (bp[2] < REAL_KEY || bp[bp[0]] < REAL_KEY)) 4091573Srgrimes /* Exception case */ 4101573Srgrimes if (bp[2] == FULL_KEY_DATA && bp[0] == 2) 4111573Srgrimes /* This is the last page of a big key/data pair 4121573Srgrimes and we need to add another page */ 4131573Srgrimes break; 4141573Srgrimes else if (bp[2] < REAL_KEY && bp[bp[0]] != OVFLPAGE) { 4151573Srgrimes bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0); 4161573Srgrimes if (!bufp) 4171573Srgrimes return (-1); 41814287Spst bp = (u_int16_t *)bufp->page; 4191573Srgrimes } else 4201573Srgrimes /* Try to squeeze key on this page */ 4211573Srgrimes if (FREESPACE(bp) > PAIRSIZE(key, val)) { 4221573Srgrimes squeeze_key(bp, key, val); 4231573Srgrimes return (0); 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 } 4301573Srgrimes 4311573Srgrimes if (PAIRFITS(bp, key, val)) 4321573Srgrimes putpair(bufp->page, key, val); 4331573Srgrimes else { 4341573Srgrimes do_expand = 1; 4351573Srgrimes bufp = __add_ovflpage(hashp, bufp); 4361573Srgrimes if (!bufp) 4371573Srgrimes return (-1); 43814287Spst sop = (u_int16_t *)bufp->page; 4391573Srgrimes 4401573Srgrimes if (PAIRFITS(sop, key, val)) 4411573Srgrimes putpair((char *)sop, key, val); 4421573Srgrimes else 4431573Srgrimes if (__big_insert(hashp, bufp, key, val)) 4441573Srgrimes return (-1); 4451573Srgrimes } 4461573Srgrimes bufp->flags |= BUF_MOD; 4471573Srgrimes /* 4481573Srgrimes * If the average number of keys per bucket exceeds the fill factor, 4491573Srgrimes * expand the table. 4501573Srgrimes */ 4511573Srgrimes hashp->NKEYS++; 4521573Srgrimes if (do_expand || 4531573Srgrimes (hashp->NKEYS / (hashp->MAX_BUCKET + 1) > hashp->FFACTOR)) 4541573Srgrimes return (__expand_table(hashp)); 4551573Srgrimes return (0); 4561573Srgrimes} 4571573Srgrimes 4581573Srgrimes/* 4591573Srgrimes * 4601573Srgrimes * Returns: 4611573Srgrimes * pointer on success 4621573Srgrimes * NULL on error 4631573Srgrimes */ 4641573Srgrimesextern BUFHEAD * 4651573Srgrimes__add_ovflpage(hashp, bufp) 4661573Srgrimes HTAB *hashp; 4671573Srgrimes BUFHEAD *bufp; 4681573Srgrimes{ 46914287Spst register u_int16_t *sp; 47014287Spst u_int16_t 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 */ 5171573Srgrimesextern int 5181573Srgrimes__get_page(hashp, p, bucket, is_bucket, is_disk, is_bitmap) 5191573Srgrimes HTAB *hashp; 5201573Srgrimes char *p; 52114287Spst u_int32_t bucket; 5221573Srgrimes int is_bucket, is_disk, is_bitmap; 5231573Srgrimes{ 5241573Srgrimes register int fd, page, size; 5251573Srgrimes int rsize; 52614287Spst u_int16_t *bp; 5271573Srgrimes 5281573Srgrimes fd = hashp->fp; 5291573Srgrimes size = hashp->BSIZE; 5301573Srgrimes 5311573Srgrimes if ((fd == -1) || !is_disk) { 5321573Srgrimes PAGE_INIT(p); 5331573Srgrimes return (0); 5341573Srgrimes } 5351573Srgrimes if (is_bucket) 5361573Srgrimes page = BUCKET_TO_PAGE(bucket); 5371573Srgrimes else 5381573Srgrimes page = OADDR_TO_PAGE(bucket); 5391573Srgrimes if ((lseek(fd, (off_t)page << hashp->BSHIFT, SEEK_SET) == -1) || 5401573Srgrimes ((rsize = read(fd, p, size)) == -1)) 5411573Srgrimes return (-1); 54214287Spst bp = (u_int16_t *)p; 5431573Srgrimes if (!rsize) 5441573Srgrimes bp[0] = 0; /* We hit the EOF, so initialize a new page */ 5451573Srgrimes else 5461573Srgrimes if (rsize != size) { 5471573Srgrimes errno = EFTYPE; 5481573Srgrimes return (-1); 5491573Srgrimes } 5501573Srgrimes if (!is_bitmap && !bp[0]) { 5511573Srgrimes PAGE_INIT(p); 5521573Srgrimes } else 5531573Srgrimes if (hashp->LORDER != BYTE_ORDER) { 5541573Srgrimes register int i, max; 5551573Srgrimes 5561573Srgrimes if (is_bitmap) { 5571573Srgrimes max = hashp->BSIZE >> 2; /* divide by 4 */ 5581573Srgrimes for (i = 0; i < max; i++) 55914287Spst M_32_SWAP(((int *)p)[i]); 5601573Srgrimes } else { 5611573Srgrimes M_16_SWAP(bp[0]); 5621573Srgrimes max = bp[0] + 2; 5631573Srgrimes for (i = 1; i <= max; i++) 5641573Srgrimes M_16_SWAP(bp[i]); 5651573Srgrimes } 5661573Srgrimes } 5671573Srgrimes return (0); 5681573Srgrimes} 5691573Srgrimes 5701573Srgrimes/* 5711573Srgrimes * Write page p to disk 5721573Srgrimes * 5731573Srgrimes * Returns: 5741573Srgrimes * 0 ==> OK 5751573Srgrimes * -1 ==>failure 5761573Srgrimes */ 5771573Srgrimesextern int 5781573Srgrimes__put_page(hashp, p, bucket, is_bucket, is_bitmap) 5791573Srgrimes HTAB *hashp; 5801573Srgrimes char *p; 58114287Spst u_int32_t bucket; 5821573Srgrimes int is_bucket, is_bitmap; 5831573Srgrimes{ 5841573Srgrimes register int fd, page, size; 5851573Srgrimes int wsize; 5861573Srgrimes 5871573Srgrimes size = hashp->BSIZE; 5881573Srgrimes if ((hashp->fp == -1) && open_temp(hashp)) 5891573Srgrimes return (-1); 5901573Srgrimes fd = hashp->fp; 5911573Srgrimes 5921573Srgrimes if (hashp->LORDER != BYTE_ORDER) { 5931573Srgrimes register int i; 5941573Srgrimes register int max; 5951573Srgrimes 5961573Srgrimes if (is_bitmap) { 5971573Srgrimes max = hashp->BSIZE >> 2; /* divide by 4 */ 5981573Srgrimes for (i = 0; i < max; i++) 59914287Spst M_32_SWAP(((int *)p)[i]); 6001573Srgrimes } else { 60114287Spst max = ((u_int16_t *)p)[0] + 2; 6021573Srgrimes for (i = 0; i <= max; i++) 60314287Spst M_16_SWAP(((u_int16_t *)p)[i]); 6041573Srgrimes } 6051573Srgrimes } 6061573Srgrimes if (is_bucket) 6071573Srgrimes page = BUCKET_TO_PAGE(bucket); 6081573Srgrimes else 6091573Srgrimes page = OADDR_TO_PAGE(bucket); 6101573Srgrimes if ((lseek(fd, (off_t)page << hashp->BSHIFT, SEEK_SET) == -1) || 6111573Srgrimes ((wsize = write(fd, p, size)) == -1)) 6121573Srgrimes /* Errno is set */ 6131573Srgrimes return (-1); 6141573Srgrimes if (wsize != size) { 6151573Srgrimes errno = EFTYPE; 6161573Srgrimes return (-1); 6171573Srgrimes } 6181573Srgrimes return (0); 6191573Srgrimes} 6201573Srgrimes 6211573Srgrimes#define BYTE_MASK ((1 << INT_BYTE_SHIFT) -1) 6221573Srgrimes/* 6231573Srgrimes * Initialize a new bitmap page. Bitmap pages are left in memory 6241573Srgrimes * once they are read in. 6251573Srgrimes */ 6261573Srgrimesextern int 62714287Spst__ibitmap(hashp, pnum, nbits, ndx) 6281573Srgrimes HTAB *hashp; 6291573Srgrimes int pnum, nbits, ndx; 6301573Srgrimes{ 63114287Spst u_int32_t *ip; 6321573Srgrimes int clearbytes, clearints; 6331573Srgrimes 63414287Spst if ((ip = (u_int32_t *)malloc(hashp->BSIZE)) == NULL) 6351573Srgrimes return (1); 6361573Srgrimes hashp->nmaps++; 6371573Srgrimes clearints = ((nbits - 1) >> INT_BYTE_SHIFT) + 1; 6381573Srgrimes clearbytes = clearints << INT_TO_BYTE; 6391573Srgrimes (void)memset((char *)ip, 0, clearbytes); 6401573Srgrimes (void)memset(((char *)ip) + clearbytes, 0xFF, 6411573Srgrimes hashp->BSIZE - clearbytes); 6421573Srgrimes ip[clearints - 1] = ALL_SET << (nbits & BYTE_MASK); 6431573Srgrimes SETBIT(ip, 0); 64414287Spst hashp->BITMAPS[ndx] = (u_int16_t)pnum; 6451573Srgrimes hashp->mapp[ndx] = ip; 6461573Srgrimes return (0); 6471573Srgrimes} 6481573Srgrimes 64914287Spststatic u_int32_t 6501573Srgrimesfirst_free(map) 65114287Spst u_int32_t map; 6521573Srgrimes{ 65314287Spst register u_int32_t i, mask; 6541573Srgrimes 6551573Srgrimes mask = 0x1; 6561573Srgrimes for (i = 0; i < BITS_PER_MAP; i++) { 6571573Srgrimes if (!(mask & map)) 6581573Srgrimes return (i); 6591573Srgrimes mask = mask << 1; 6601573Srgrimes } 6611573Srgrimes return (i); 6621573Srgrimes} 6631573Srgrimes 66414287Spststatic u_int16_t 6651573Srgrimesoverflow_page(hashp) 6661573Srgrimes HTAB *hashp; 6671573Srgrimes{ 66814287Spst register u_int32_t *freep; 6691573Srgrimes register int max_free, offset, splitnum; 67014287Spst u_int16_t addr; 6711573Srgrimes int bit, first_page, free_bit, free_page, i, in_use_bits, j; 6721573Srgrimes#ifdef DEBUG2 6731573Srgrimes int tmp1, tmp2; 6741573Srgrimes#endif 6751573Srgrimes splitnum = hashp->OVFL_POINT; 6761573Srgrimes max_free = hashp->SPARES[splitnum]; 6771573Srgrimes 6781573Srgrimes free_page = (max_free - 1) >> (hashp->BSHIFT + BYTE_SHIFT); 6791573Srgrimes free_bit = (max_free - 1) & ((hashp->BSIZE << BYTE_SHIFT) - 1); 6801573Srgrimes 6811573Srgrimes /* Look through all the free maps to find the first free block */ 6821573Srgrimes first_page = hashp->LAST_FREED >>(hashp->BSHIFT + BYTE_SHIFT); 6831573Srgrimes for ( i = first_page; i <= free_page; i++ ) { 68414287Spst if (!(freep = (u_int32_t *)hashp->mapp[i]) && 6851573Srgrimes !(freep = fetch_bitmap(hashp, i))) 68614287Spst return (0); 6871573Srgrimes if (i == free_page) 6881573Srgrimes in_use_bits = free_bit; 6891573Srgrimes else 6901573Srgrimes in_use_bits = (hashp->BSIZE << BYTE_SHIFT) - 1; 6918870Srgrimes 6921573Srgrimes if (i == first_page) { 6931573Srgrimes bit = hashp->LAST_FREED & 6941573Srgrimes ((hashp->BSIZE << BYTE_SHIFT) - 1); 6951573Srgrimes j = bit / BITS_PER_MAP; 6961573Srgrimes bit = bit & ~(BITS_PER_MAP - 1); 6971573Srgrimes } else { 6981573Srgrimes bit = 0; 6991573Srgrimes j = 0; 7001573Srgrimes } 7011573Srgrimes for (; bit <= in_use_bits; j++, bit += BITS_PER_MAP) 7021573Srgrimes if (freep[j] != ALL_SET) 7031573Srgrimes goto found; 7041573Srgrimes } 7051573Srgrimes 7061573Srgrimes /* No Free Page Found */ 7071573Srgrimes hashp->LAST_FREED = hashp->SPARES[splitnum]; 7081573Srgrimes hashp->SPARES[splitnum]++; 7091573Srgrimes offset = hashp->SPARES[splitnum] - 7101573Srgrimes (splitnum ? hashp->SPARES[splitnum - 1] : 0); 7111573Srgrimes 7121573Srgrimes#define OVMSG "HASH: Out of overflow pages. Increase page size\n" 7131573Srgrimes if (offset > SPLITMASK) { 7141573Srgrimes if (++splitnum >= NCACHED) { 7151573Srgrimes (void)write(STDERR_FILENO, OVMSG, sizeof(OVMSG) - 1); 71614287Spst return (0); 7171573Srgrimes } 7181573Srgrimes hashp->OVFL_POINT = splitnum; 7191573Srgrimes hashp->SPARES[splitnum] = hashp->SPARES[splitnum-1]; 7201573Srgrimes hashp->SPARES[splitnum-1]--; 7211573Srgrimes offset = 1; 7221573Srgrimes } 7231573Srgrimes 7241573Srgrimes /* Check if we need to allocate a new bitmap page */ 7251573Srgrimes if (free_bit == (hashp->BSIZE << BYTE_SHIFT) - 1) { 7261573Srgrimes free_page++; 7271573Srgrimes if (free_page >= NCACHED) { 7281573Srgrimes (void)write(STDERR_FILENO, OVMSG, sizeof(OVMSG) - 1); 72914287Spst return (0); 7301573Srgrimes } 7311573Srgrimes /* 7321573Srgrimes * This is tricky. The 1 indicates that you want the new page 7331573Srgrimes * allocated with 1 clear bit. Actually, you are going to 7341573Srgrimes * allocate 2 pages from this map. The first is going to be 7351573Srgrimes * the map page, the second is the overflow page we were 7361573Srgrimes * looking for. The init_bitmap routine automatically, sets 7371573Srgrimes * the first bit of itself to indicate that the bitmap itself 7381573Srgrimes * is in use. We would explicitly set the second bit, but 7391573Srgrimes * don't have to if we tell init_bitmap not to leave it clear 7401573Srgrimes * in the first place. 7411573Srgrimes */ 74214287Spst if (__ibitmap(hashp, 74314287Spst (int)OADDR_OF(splitnum, offset), 1, free_page)) 74414287Spst return (0); 7451573Srgrimes hashp->SPARES[splitnum]++; 7461573Srgrimes#ifdef DEBUG2 7471573Srgrimes free_bit = 2; 7481573Srgrimes#endif 7491573Srgrimes offset++; 7501573Srgrimes if (offset > SPLITMASK) { 7511573Srgrimes if (++splitnum >= NCACHED) { 7521573Srgrimes (void)write(STDERR_FILENO, OVMSG, 7531573Srgrimes sizeof(OVMSG) - 1); 75414287Spst return (0); 7551573Srgrimes } 7561573Srgrimes hashp->OVFL_POINT = splitnum; 7571573Srgrimes hashp->SPARES[splitnum] = hashp->SPARES[splitnum-1]; 7581573Srgrimes hashp->SPARES[splitnum-1]--; 7591573Srgrimes offset = 0; 7601573Srgrimes } 7611573Srgrimes } else { 7621573Srgrimes /* 7631573Srgrimes * Free_bit addresses the last used bit. Bump it to address 7641573Srgrimes * the first available bit. 7651573Srgrimes */ 7661573Srgrimes free_bit++; 7671573Srgrimes SETBIT(freep, free_bit); 7681573Srgrimes } 7691573Srgrimes 7701573Srgrimes /* Calculate address of the new overflow page */ 7711573Srgrimes addr = OADDR_OF(splitnum, offset); 7721573Srgrimes#ifdef DEBUG2 7731573Srgrimes (void)fprintf(stderr, "OVERFLOW_PAGE: ADDR: %d BIT: %d PAGE %d\n", 7741573Srgrimes addr, free_bit, free_page); 7751573Srgrimes#endif 7761573Srgrimes return (addr); 7771573Srgrimes 7781573Srgrimesfound: 7791573Srgrimes bit = bit + first_free(freep[j]); 7801573Srgrimes SETBIT(freep, bit); 7811573Srgrimes#ifdef DEBUG2 7821573Srgrimes tmp1 = bit; 7831573Srgrimes tmp2 = i; 7841573Srgrimes#endif 7851573Srgrimes /* 7861573Srgrimes * Bits are addressed starting with 0, but overflow pages are addressed 7871573Srgrimes * beginning at 1. Bit is a bit addressnumber, so we need to increment 7881573Srgrimes * it to convert it to a page number. 7891573Srgrimes */ 7901573Srgrimes bit = 1 + bit + (i * (hashp->BSIZE << BYTE_SHIFT)); 7911573Srgrimes if (bit >= hashp->LAST_FREED) 7921573Srgrimes hashp->LAST_FREED = bit - 1; 7931573Srgrimes 7941573Srgrimes /* Calculate the split number for this page */ 7951573Srgrimes for (i = 0; (i < splitnum) && (bit > hashp->SPARES[i]); i++); 7961573Srgrimes offset = (i ? bit - hashp->SPARES[i - 1] : bit); 7971573Srgrimes if (offset >= SPLITMASK) 79814287Spst return (0); /* Out of overflow pages */ 7991573Srgrimes addr = OADDR_OF(i, offset); 8001573Srgrimes#ifdef DEBUG2 8011573Srgrimes (void)fprintf(stderr, "OVERFLOW_PAGE: ADDR: %d BIT: %d PAGE %d\n", 8021573Srgrimes addr, tmp1, tmp2); 8031573Srgrimes#endif 8041573Srgrimes 8051573Srgrimes /* Allocate and return the overflow page */ 8061573Srgrimes return (addr); 8071573Srgrimes} 8081573Srgrimes 8091573Srgrimes/* 8101573Srgrimes * Mark this overflow page as free. 8111573Srgrimes */ 8121573Srgrimesextern void 8131573Srgrimes__free_ovflpage(hashp, obufp) 8141573Srgrimes HTAB *hashp; 8151573Srgrimes BUFHEAD *obufp; 8161573Srgrimes{ 81714287Spst register u_int16_t addr; 81814287Spst u_int32_t *freep; 8191573Srgrimes int bit_address, free_page, free_bit; 82014287Spst u_int16_t ndx; 8211573Srgrimes 8221573Srgrimes addr = obufp->addr; 8231573Srgrimes#ifdef DEBUG1 8241573Srgrimes (void)fprintf(stderr, "Freeing %d\n", addr); 8251573Srgrimes#endif 82614287Spst ndx = (((u_int16_t)addr) >> SPLITSHIFT); 8271573Srgrimes bit_address = 8281573Srgrimes (ndx ? hashp->SPARES[ndx - 1] : 0) + (addr & SPLITMASK) - 1; 8291573Srgrimes if (bit_address < hashp->LAST_FREED) 8301573Srgrimes hashp->LAST_FREED = bit_address; 8311573Srgrimes free_page = (bit_address >> (hashp->BSHIFT + BYTE_SHIFT)); 8321573Srgrimes free_bit = bit_address & ((hashp->BSIZE << BYTE_SHIFT) - 1); 8331573Srgrimes 8341573Srgrimes if (!(freep = hashp->mapp[free_page])) 8351573Srgrimes freep = fetch_bitmap(hashp, free_page); 8361573Srgrimes#ifdef DEBUG 8371573Srgrimes /* 8381573Srgrimes * This had better never happen. It means we tried to read a bitmap 8391573Srgrimes * that has already had overflow pages allocated off it, and we 8401573Srgrimes * failed to read it from the file. 8411573Srgrimes */ 8421573Srgrimes if (!freep) 8431573Srgrimes assert(0); 8441573Srgrimes#endif 8451573Srgrimes CLRBIT(freep, free_bit); 8461573Srgrimes#ifdef DEBUG2 8471573Srgrimes (void)fprintf(stderr, "FREE_OVFLPAGE: ADDR: %d BIT: %d PAGE %d\n", 8481573Srgrimes obufp->addr, free_bit, free_page); 8491573Srgrimes#endif 8501573Srgrimes __reclaim_buf(hashp, obufp); 8511573Srgrimes} 8521573Srgrimes 8531573Srgrimes/* 8541573Srgrimes * Returns: 8551573Srgrimes * 0 success 8561573Srgrimes * -1 failure 8571573Srgrimes */ 8581573Srgrimesstatic int 8591573Srgrimesopen_temp(hashp) 8601573Srgrimes HTAB *hashp; 8611573Srgrimes{ 8621573Srgrimes sigset_t set, oset; 8631573Srgrimes static char namestr[] = "_hashXXXXXX"; 8641573Srgrimes 8651573Srgrimes /* Block signals; make sure file goes away at process exit. */ 8661573Srgrimes (void)sigfillset(&set); 8671573Srgrimes (void)sigprocmask(SIG_BLOCK, &set, &oset); 8681573Srgrimes if ((hashp->fp = mkstemp(namestr)) != -1) { 8691573Srgrimes (void)unlink(namestr); 8701573Srgrimes (void)fcntl(hashp->fp, F_SETFD, 1); 8711573Srgrimes } 8721573Srgrimes (void)sigprocmask(SIG_SETMASK, &oset, (sigset_t *)NULL); 8731573Srgrimes return (hashp->fp != -1 ? 0 : -1); 8741573Srgrimes} 8751573Srgrimes 8761573Srgrimes/* 8771573Srgrimes * We have to know that the key will fit, but the last entry on the page is 8781573Srgrimes * an overflow pair, so we need to shift things. 8791573Srgrimes */ 8801573Srgrimesstatic void 8811573Srgrimessqueeze_key(sp, key, val) 88214287Spst u_int16_t *sp; 8831573Srgrimes const DBT *key, *val; 8841573Srgrimes{ 8851573Srgrimes register char *p; 88614287Spst u_int16_t free_space, n, off, pageno; 8871573Srgrimes 8881573Srgrimes p = (char *)sp; 8891573Srgrimes n = sp[0]; 8901573Srgrimes free_space = FREESPACE(sp); 8911573Srgrimes off = OFFSET(sp); 8921573Srgrimes 8931573Srgrimes pageno = sp[n - 1]; 8941573Srgrimes off -= key->size; 8951573Srgrimes sp[n - 1] = off; 8961573Srgrimes memmove(p + off, key->data, key->size); 8971573Srgrimes off -= val->size; 8981573Srgrimes sp[n] = off; 8991573Srgrimes memmove(p + off, val->data, val->size); 9001573Srgrimes sp[0] = n + 2; 9011573Srgrimes sp[n + 1] = pageno; 9021573Srgrimes sp[n + 2] = OVFLPAGE; 9031573Srgrimes FREESPACE(sp) = free_space - PAIRSIZE(key, val); 9041573Srgrimes OFFSET(sp) = off; 9051573Srgrimes} 9061573Srgrimes 90714287Spststatic u_int32_t * 9081573Srgrimesfetch_bitmap(hashp, ndx) 9091573Srgrimes HTAB *hashp; 9101573Srgrimes int ndx; 9111573Srgrimes{ 9121573Srgrimes if (ndx >= hashp->nmaps) 9131573Srgrimes return (NULL); 91414287Spst if ((hashp->mapp[ndx] = (u_int32_t *)malloc(hashp->BSIZE)) == NULL) 9151573Srgrimes return (NULL); 9161573Srgrimes if (__get_page(hashp, 9171573Srgrimes (char *)hashp->mapp[ndx], hashp->BITMAPS[ndx], 0, 1, 1)) { 9181573Srgrimes free(hashp->mapp[ndx]); 9191573Srgrimes return (NULL); 9201573Srgrimes } 9211573Srgrimes return (hashp->mapp[ndx]); 9221573Srgrimes} 9231573Srgrimes 9241573Srgrimes#ifdef DEBUG4 9251573Srgrimesint 9261573Srgrimesprint_chain(addr) 9271573Srgrimes int addr; 9281573Srgrimes{ 9291573Srgrimes BUFHEAD *bufp; 9301573Srgrimes short *bp, oaddr; 9311573Srgrimes 9321573Srgrimes (void)fprintf(stderr, "%d ", addr); 9331573Srgrimes bufp = __get_buf(hashp, addr, NULL, 0); 9341573Srgrimes bp = (short *)bufp->page; 9351573Srgrimes while (bp[0] && ((bp[bp[0]] == OVFLPAGE) || 9361573Srgrimes ((bp[0] > 2) && bp[2] < REAL_KEY))) { 9371573Srgrimes oaddr = bp[bp[0] - 1]; 9381573Srgrimes (void)fprintf(stderr, "%d ", (int)oaddr); 9391573Srgrimes bufp = __get_buf(hashp, (int)oaddr, bufp, 0); 9401573Srgrimes bp = (short *)bufp->page; 9411573Srgrimes } 9421573Srgrimes (void)fprintf(stderr, "\n"); 9431573Srgrimes} 9441573Srgrimes#endif 945