11573Srgrimes/*- 214272Spst * 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) 3414272Spststatic char sccsid[] = "@(#)hash_bigkey.c 8.3 (Berkeley) 5/31/94"; 351573Srgrimes#endif /* LIBC_SCCS and not lint */ 3692889Sobrien#include <sys/cdefs.h> 3792889Sobrien__FBSDID("$FreeBSD$"); 381573Srgrimes 391573Srgrimes/* 401573Srgrimes * PACKAGE: hash 411573Srgrimes * DESCRIPTION: 421573Srgrimes * Big key/data handling for the hashing package. 431573Srgrimes * 441573Srgrimes * ROUTINES: 451573Srgrimes * External 461573Srgrimes * __big_keydata 471573Srgrimes * __big_split 481573Srgrimes * __big_insert 491573Srgrimes * __big_return 501573Srgrimes * __big_delete 511573Srgrimes * __find_last_page 521573Srgrimes * Internal 531573Srgrimes * collect_key 541573Srgrimes * collect_data 551573Srgrimes */ 561573Srgrimes 571573Srgrimes#include <sys/param.h> 581573Srgrimes 591573Srgrimes#include <errno.h> 601573Srgrimes#include <stdio.h> 611573Srgrimes#include <stdlib.h> 621573Srgrimes#include <string.h> 631573Srgrimes 641573Srgrimes#ifdef DEBUG 651573Srgrimes#include <assert.h> 661573Srgrimes#endif 671573Srgrimes 681573Srgrimes#include <db.h> 691573Srgrimes#include "hash.h" 701573Srgrimes#include "page.h" 711573Srgrimes#include "extern.h" 721573Srgrimes 7392905Sobrienstatic int collect_key(HTAB *, BUFHEAD *, int, DBT *, int); 7492905Sobrienstatic int collect_data(HTAB *, BUFHEAD *, int, int); 751573Srgrimes 761573Srgrimes/* 771573Srgrimes * Big_insert 781573Srgrimes * 791573Srgrimes * You need to do an insert and the key/data pair is too big 801573Srgrimes * 811573Srgrimes * Returns: 821573Srgrimes * 0 ==> OK 831573Srgrimes *-1 ==> ERROR 841573Srgrimes */ 85189291Sdelphijint 86189291Sdelphij__big_insert(HTAB *hashp, BUFHEAD *bufp, const DBT *key, const DBT *val) 871573Srgrimes{ 8892889Sobrien u_int16_t *p; 89190484Sdelphij int key_size, n; 90190484Sdelphij unsigned int val_size; 9114272Spst u_int16_t space, move_bytes, off; 921573Srgrimes char *cp, *key_data, *val_data; 931573Srgrimes 941573Srgrimes cp = bufp->page; /* Character pointer of p. */ 9514272Spst p = (u_int16_t *)cp; 961573Srgrimes 971573Srgrimes key_data = (char *)key->data; 981573Srgrimes key_size = key->size; 991573Srgrimes val_data = (char *)val->data; 1001573Srgrimes val_size = val->size; 1011573Srgrimes 1021573Srgrimes /* First move the Key */ 1031573Srgrimes for (space = FREESPACE(p) - BIGOVERHEAD; key_size; 1041573Srgrimes space = FREESPACE(p) - BIGOVERHEAD) { 1051573Srgrimes move_bytes = MIN(space, key_size); 1061573Srgrimes off = OFFSET(p) - move_bytes; 1071573Srgrimes memmove(cp + off, key_data, move_bytes); 1081573Srgrimes key_size -= move_bytes; 1091573Srgrimes key_data += move_bytes; 1101573Srgrimes n = p[0]; 1111573Srgrimes p[++n] = off; 1121573Srgrimes p[0] = ++n; 1131573Srgrimes FREESPACE(p) = off - PAGE_META(n); 1141573Srgrimes OFFSET(p) = off; 1151573Srgrimes p[n] = PARTIAL_KEY; 1161573Srgrimes bufp = __add_ovflpage(hashp, bufp); 1171573Srgrimes if (!bufp) 1181573Srgrimes return (-1); 1191573Srgrimes n = p[0]; 120111010Snectar if (!key_size) { 121190494Sdelphij space = FREESPACE(p); 122190494Sdelphij if (space) { 123190494Sdelphij move_bytes = MIN(space, val_size); 124190494Sdelphij /* 125190494Sdelphij * If the data would fit exactly in the 126190494Sdelphij * remaining space, we must overflow it to the 127190494Sdelphij * next page; otherwise the invariant that the 128190494Sdelphij * data must end on a page with FREESPACE 129190494Sdelphij * non-zero would fail. 130190494Sdelphij */ 131190494Sdelphij if (space == val_size && val_size == val->size) 132190494Sdelphij goto toolarge; 1331573Srgrimes off = OFFSET(p) - move_bytes; 1341573Srgrimes memmove(cp + off, val_data, move_bytes); 1351573Srgrimes val_data += move_bytes; 1361573Srgrimes val_size -= move_bytes; 137190494Sdelphij p[n] = off; 1381573Srgrimes p[n - 2] = FULL_KEY_DATA; 1391573Srgrimes FREESPACE(p) = FREESPACE(p) - move_bytes; 1401573Srgrimes OFFSET(p) = off; 141190494Sdelphij } else { 142190494Sdelphij toolarge: 1431573Srgrimes p[n - 2] = FULL_KEY; 144190494Sdelphij } 145111010Snectar } 14614272Spst p = (u_int16_t *)bufp->page; 1471573Srgrimes cp = bufp->page; 1481573Srgrimes bufp->flags |= BUF_MOD; 1491573Srgrimes } 1501573Srgrimes 1511573Srgrimes /* Now move the data */ 1521573Srgrimes for (space = FREESPACE(p) - BIGOVERHEAD; val_size; 1531573Srgrimes space = FREESPACE(p) - BIGOVERHEAD) { 1541573Srgrimes move_bytes = MIN(space, val_size); 1551573Srgrimes /* 1561573Srgrimes * Here's the hack to make sure that if the data ends on the 1571573Srgrimes * same page as the key ends, FREESPACE is at least one. 1581573Srgrimes */ 1591573Srgrimes if (space == val_size && val_size == val->size) 1601573Srgrimes move_bytes--; 1611573Srgrimes off = OFFSET(p) - move_bytes; 1621573Srgrimes memmove(cp + off, val_data, move_bytes); 1631573Srgrimes val_size -= move_bytes; 1641573Srgrimes val_data += move_bytes; 1651573Srgrimes n = p[0]; 1661573Srgrimes p[++n] = off; 1671573Srgrimes p[0] = ++n; 1681573Srgrimes FREESPACE(p) = off - PAGE_META(n); 1691573Srgrimes OFFSET(p) = off; 1701573Srgrimes if (val_size) { 1711573Srgrimes p[n] = FULL_KEY; 1721573Srgrimes bufp = __add_ovflpage(hashp, bufp); 1731573Srgrimes if (!bufp) 1741573Srgrimes return (-1); 1751573Srgrimes cp = bufp->page; 17614272Spst p = (u_int16_t *)cp; 1771573Srgrimes } else 1781573Srgrimes p[n] = FULL_KEY_DATA; 1791573Srgrimes bufp->flags |= BUF_MOD; 1801573Srgrimes } 1811573Srgrimes return (0); 1821573Srgrimes} 1831573Srgrimes 1841573Srgrimes/* 1851573Srgrimes * Called when bufp's page contains a partial key (index should be 1) 1861573Srgrimes * 1871573Srgrimes * All pages in the big key/data pair except bufp are freed. We cannot 1881573Srgrimes * free bufp because the page pointing to it is lost and we can't get rid 1891573Srgrimes * of its pointer. 1901573Srgrimes * 1911573Srgrimes * Returns: 1921573Srgrimes * 0 => OK 1931573Srgrimes *-1 => ERROR 1941573Srgrimes */ 195189291Sdelphijint 196189291Sdelphij__big_delete(HTAB *hashp, BUFHEAD *bufp) 1971573Srgrimes{ 19892889Sobrien BUFHEAD *last_bfp, *rbufp; 19914272Spst u_int16_t *bp, pageno; 2001573Srgrimes int key_done, n; 2011573Srgrimes 2021573Srgrimes rbufp = bufp; 2031573Srgrimes last_bfp = NULL; 20414272Spst bp = (u_int16_t *)bufp->page; 2051573Srgrimes pageno = 0; 2061573Srgrimes key_done = 0; 2071573Srgrimes 2081573Srgrimes while (!key_done || (bp[2] != FULL_KEY_DATA)) { 2091573Srgrimes if (bp[2] == FULL_KEY || bp[2] == FULL_KEY_DATA) 2101573Srgrimes key_done = 1; 2111573Srgrimes 2121573Srgrimes /* 2131573Srgrimes * If there is freespace left on a FULL_KEY_DATA page, then 2141573Srgrimes * the data is short and fits entirely on this page, and this 2151573Srgrimes * is the last page. 2161573Srgrimes */ 2171573Srgrimes if (bp[2] == FULL_KEY_DATA && FREESPACE(bp)) 2181573Srgrimes break; 2191573Srgrimes pageno = bp[bp[0] - 1]; 2201573Srgrimes rbufp->flags |= BUF_MOD; 2211573Srgrimes rbufp = __get_buf(hashp, pageno, rbufp, 0); 2221573Srgrimes if (last_bfp) 2231573Srgrimes __free_ovflpage(hashp, last_bfp); 2241573Srgrimes last_bfp = rbufp; 2251573Srgrimes if (!rbufp) 2261573Srgrimes return (-1); /* Error. */ 22714272Spst bp = (u_int16_t *)rbufp->page; 2281573Srgrimes } 2291573Srgrimes 2301573Srgrimes /* 2311573Srgrimes * If we get here then rbufp points to the last page of the big 2321573Srgrimes * key/data pair. Bufp points to the first one -- it should now be 2331573Srgrimes * empty pointing to the next page after this pair. Can't free it 2341573Srgrimes * because we don't have the page pointing to it. 2351573Srgrimes */ 2361573Srgrimes 2371573Srgrimes /* This is information from the last page of the pair. */ 2381573Srgrimes n = bp[0]; 2391573Srgrimes pageno = bp[n - 1]; 2401573Srgrimes 2411573Srgrimes /* Now, bp is the first page of the pair. */ 24214272Spst bp = (u_int16_t *)bufp->page; 2431573Srgrimes if (n > 2) { 2441573Srgrimes /* There is an overflow page. */ 2451573Srgrimes bp[1] = pageno; 2461573Srgrimes bp[2] = OVFLPAGE; 2471573Srgrimes bufp->ovfl = rbufp->ovfl; 2481573Srgrimes } else 2491573Srgrimes /* This is the last page. */ 2501573Srgrimes bufp->ovfl = NULL; 2511573Srgrimes n -= 2; 2521573Srgrimes bp[0] = n; 2531573Srgrimes FREESPACE(bp) = hashp->BSIZE - PAGE_META(n); 254190494Sdelphij OFFSET(bp) = hashp->BSIZE; 2551573Srgrimes 2561573Srgrimes bufp->flags |= BUF_MOD; 2571573Srgrimes if (rbufp) 2581573Srgrimes __free_ovflpage(hashp, rbufp); 259190494Sdelphij if (last_bfp && last_bfp != rbufp) 2601573Srgrimes __free_ovflpage(hashp, last_bfp); 2611573Srgrimes 2621573Srgrimes hashp->NKEYS--; 2631573Srgrimes return (0); 2641573Srgrimes} 2651573Srgrimes/* 2661573Srgrimes * Returns: 2671573Srgrimes * 0 = key not found 2681573Srgrimes * -1 = get next overflow page 2691573Srgrimes * -2 means key not found and this is big key/data 2701573Srgrimes * -3 error 2711573Srgrimes */ 272189291Sdelphijint 273189291Sdelphij__find_bigpair(HTAB *hashp, BUFHEAD *bufp, int ndx, char *key, int size) 2741573Srgrimes{ 27592889Sobrien u_int16_t *bp; 27692889Sobrien char *p; 2771573Srgrimes int ksize; 27814272Spst u_int16_t bytes; 2791573Srgrimes char *kkey; 2801573Srgrimes 28114272Spst bp = (u_int16_t *)bufp->page; 2821573Srgrimes p = bufp->page; 2831573Srgrimes ksize = size; 2841573Srgrimes kkey = key; 2851573Srgrimes 2861573Srgrimes for (bytes = hashp->BSIZE - bp[ndx]; 2871573Srgrimes bytes <= size && bp[ndx + 1] == PARTIAL_KEY; 2881573Srgrimes bytes = hashp->BSIZE - bp[ndx]) { 2891573Srgrimes if (memcmp(p + bp[ndx], kkey, bytes)) 2901573Srgrimes return (-2); 2911573Srgrimes kkey += bytes; 2921573Srgrimes ksize -= bytes; 2931573Srgrimes bufp = __get_buf(hashp, bp[ndx + 2], bufp, 0); 2941573Srgrimes if (!bufp) 2951573Srgrimes return (-3); 2961573Srgrimes p = bufp->page; 29714272Spst bp = (u_int16_t *)p; 2981573Srgrimes ndx = 1; 2991573Srgrimes } 3001573Srgrimes 3011573Srgrimes if (bytes != ksize || memcmp(p + bp[ndx], kkey, bytes)) { 3021573Srgrimes#ifdef HASH_STATISTICS 3031573Srgrimes ++hash_collisions; 3041573Srgrimes#endif 3051573Srgrimes return (-2); 3061573Srgrimes } else 3071573Srgrimes return (ndx); 3081573Srgrimes} 3091573Srgrimes 3101573Srgrimes/* 3111573Srgrimes * Given the buffer pointer of the first overflow page of a big pair, 3121573Srgrimes * find the end of the big pair 3131573Srgrimes * 3141573Srgrimes * This will set bpp to the buffer header of the last page of the big pair. 3151573Srgrimes * It will return the pageno of the overflow page following the last page 3161573Srgrimes * of the pair; 0 if there isn't any (i.e. big pair is the last key in the 3171573Srgrimes * bucket) 3181573Srgrimes */ 319189291Sdelphiju_int16_t 320189291Sdelphij__find_last_page(HTAB *hashp, BUFHEAD **bpp) 3211573Srgrimes{ 3221573Srgrimes BUFHEAD *bufp; 32314272Spst u_int16_t *bp, pageno; 3241573Srgrimes int n; 3251573Srgrimes 3261573Srgrimes bufp = *bpp; 32714272Spst bp = (u_int16_t *)bufp->page; 3281573Srgrimes for (;;) { 3291573Srgrimes n = bp[0]; 3301573Srgrimes 3311573Srgrimes /* 3321573Srgrimes * This is the last page if: the tag is FULL_KEY_DATA and 3331573Srgrimes * either only 2 entries OVFLPAGE marker is explicit there 3341573Srgrimes * is freespace on the page. 3351573Srgrimes */ 3361573Srgrimes if (bp[2] == FULL_KEY_DATA && 3371573Srgrimes ((n == 2) || (bp[n] == OVFLPAGE) || (FREESPACE(bp)))) 3381573Srgrimes break; 3391573Srgrimes 3401573Srgrimes pageno = bp[n - 1]; 3411573Srgrimes bufp = __get_buf(hashp, pageno, bufp, 0); 3421573Srgrimes if (!bufp) 3431573Srgrimes return (0); /* Need to indicate an error! */ 34414272Spst bp = (u_int16_t *)bufp->page; 3451573Srgrimes } 3461573Srgrimes 3471573Srgrimes *bpp = bufp; 3481573Srgrimes if (bp[0] > 2) 3491573Srgrimes return (bp[3]); 3501573Srgrimes else 3511573Srgrimes return (0); 3521573Srgrimes} 3531573Srgrimes 3541573Srgrimes/* 3551573Srgrimes * Return the data for the key/data pair that begins on this page at this 3561573Srgrimes * index (index should always be 1). 3571573Srgrimes */ 358189291Sdelphijint 359189291Sdelphij__big_return(HTAB *hashp, BUFHEAD *bufp, int ndx, DBT *val, int set_current) 3601573Srgrimes{ 3611573Srgrimes BUFHEAD *save_p; 36214272Spst u_int16_t *bp, len, off, save_addr; 3631573Srgrimes char *tp; 3641573Srgrimes 36514272Spst bp = (u_int16_t *)bufp->page; 3661573Srgrimes while (bp[ndx + 1] == PARTIAL_KEY) { 3671573Srgrimes bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0); 3681573Srgrimes if (!bufp) 3691573Srgrimes return (-1); 37014272Spst bp = (u_int16_t *)bufp->page; 3711573Srgrimes ndx = 1; 3721573Srgrimes } 3731573Srgrimes 3741573Srgrimes if (bp[ndx + 1] == FULL_KEY) { 3751573Srgrimes bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0); 3761573Srgrimes if (!bufp) 3771573Srgrimes return (-1); 37814272Spst bp = (u_int16_t *)bufp->page; 3791573Srgrimes save_p = bufp; 3801573Srgrimes save_addr = save_p->addr; 3811573Srgrimes off = bp[1]; 3821573Srgrimes len = 0; 3831573Srgrimes } else 3841573Srgrimes if (!FREESPACE(bp)) { 3851573Srgrimes /* 3861573Srgrimes * This is a hack. We can't distinguish between 3871573Srgrimes * FULL_KEY_DATA that contains complete data or 3881573Srgrimes * incomplete data, so we require that if the data 3891573Srgrimes * is complete, there is at least 1 byte of free 3901573Srgrimes * space left. 3911573Srgrimes */ 3921573Srgrimes off = bp[bp[0]]; 3931573Srgrimes len = bp[1] - off; 3941573Srgrimes save_p = bufp; 3951573Srgrimes save_addr = bufp->addr; 3961573Srgrimes bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0); 3971573Srgrimes if (!bufp) 3981573Srgrimes return (-1); 39914272Spst bp = (u_int16_t *)bufp->page; 4001573Srgrimes } else { 4011573Srgrimes /* The data is all on one page. */ 4021573Srgrimes tp = (char *)bp; 4031573Srgrimes off = bp[bp[0]]; 4041573Srgrimes val->data = (u_char *)tp + off; 4051573Srgrimes val->size = bp[1] - off; 4061573Srgrimes if (set_current) { 4071573Srgrimes if (bp[0] == 2) { /* No more buckets in 4081573Srgrimes * chain */ 4091573Srgrimes hashp->cpage = NULL; 4101573Srgrimes hashp->cbucket++; 4111573Srgrimes hashp->cndx = 1; 4121573Srgrimes } else { 4131573Srgrimes hashp->cpage = __get_buf(hashp, 4141573Srgrimes bp[bp[0] - 1], bufp, 0); 4151573Srgrimes if (!hashp->cpage) 4161573Srgrimes return (-1); 4171573Srgrimes hashp->cndx = 1; 41814272Spst if (!((u_int16_t *) 4191573Srgrimes hashp->cpage->page)[0]) { 4201573Srgrimes hashp->cbucket++; 4211573Srgrimes hashp->cpage = NULL; 4221573Srgrimes } 4231573Srgrimes } 4241573Srgrimes } 4251573Srgrimes return (0); 4261573Srgrimes } 4271573Srgrimes 428189327Sdelphij val->size = (size_t)collect_data(hashp, bufp, (int)len, set_current); 429189327Sdelphij if (val->size == (size_t)-1) 4301573Srgrimes return (-1); 4311573Srgrimes if (save_p->addr != save_addr) { 4321573Srgrimes /* We are pretty short on buffers. */ 4331573Srgrimes errno = EINVAL; /* OUT OF BUFFERS */ 4341573Srgrimes return (-1); 4351573Srgrimes } 4361573Srgrimes memmove(hashp->tmp_buf, (save_p->page) + off, len); 4371573Srgrimes val->data = (u_char *)hashp->tmp_buf; 4381573Srgrimes return (0); 4391573Srgrimes} 4401573Srgrimes/* 4411573Srgrimes * Count how big the total datasize is by recursing through the pages. Then 4421573Srgrimes * allocate a buffer and copy the data as you recurse up. 4431573Srgrimes */ 4441573Srgrimesstatic int 445189291Sdelphijcollect_data(HTAB *hashp, BUFHEAD *bufp, int len, int set) 4461573Srgrimes{ 44792889Sobrien u_int16_t *bp; 44892889Sobrien char *p; 4491573Srgrimes BUFHEAD *xbp; 45014272Spst u_int16_t save_addr; 4511573Srgrimes int mylen, totlen; 4521573Srgrimes 4531573Srgrimes p = bufp->page; 45414272Spst bp = (u_int16_t *)p; 4551573Srgrimes mylen = hashp->BSIZE - bp[1]; 4561573Srgrimes save_addr = bufp->addr; 4571573Srgrimes 4581573Srgrimes if (bp[2] == FULL_KEY_DATA) { /* End of Data */ 4591573Srgrimes totlen = len + mylen; 4601573Srgrimes if (hashp->tmp_buf) 4611573Srgrimes free(hashp->tmp_buf); 4621573Srgrimes if ((hashp->tmp_buf = (char *)malloc(totlen)) == NULL) 4631573Srgrimes return (-1); 4641573Srgrimes if (set) { 4651573Srgrimes hashp->cndx = 1; 4661573Srgrimes if (bp[0] == 2) { /* No more buckets in chain */ 4671573Srgrimes hashp->cpage = NULL; 4681573Srgrimes hashp->cbucket++; 4691573Srgrimes } else { 4701573Srgrimes hashp->cpage = 4711573Srgrimes __get_buf(hashp, bp[bp[0] - 1], bufp, 0); 4721573Srgrimes if (!hashp->cpage) 4731573Srgrimes return (-1); 47414272Spst else if (!((u_int16_t *)hashp->cpage->page)[0]) { 4751573Srgrimes hashp->cbucket++; 4761573Srgrimes hashp->cpage = NULL; 4771573Srgrimes } 4781573Srgrimes } 4791573Srgrimes } 4801573Srgrimes } else { 4811573Srgrimes xbp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0); 4821573Srgrimes if (!xbp || ((totlen = 4831573Srgrimes collect_data(hashp, xbp, len + mylen, set)) < 1)) 4841573Srgrimes return (-1); 4851573Srgrimes } 4861573Srgrimes if (bufp->addr != save_addr) { 4871573Srgrimes errno = EINVAL; /* Out of buffers. */ 4881573Srgrimes return (-1); 4891573Srgrimes } 4901573Srgrimes memmove(&hashp->tmp_buf[len], (bufp->page) + bp[1], mylen); 4911573Srgrimes return (totlen); 4921573Srgrimes} 4931573Srgrimes 4941573Srgrimes/* 4951573Srgrimes * Fill in the key and data for this big pair. 4961573Srgrimes */ 497189291Sdelphijint 498189291Sdelphij__big_keydata(HTAB *hashp, BUFHEAD *bufp, DBT *key, DBT *val, int set) 4991573Srgrimes{ 500189327Sdelphij key->size = (size_t)collect_key(hashp, bufp, 0, val, set); 501189327Sdelphij if (key->size == (size_t)-1) 5021573Srgrimes return (-1); 5031573Srgrimes key->data = (u_char *)hashp->tmp_key; 5041573Srgrimes return (0); 5051573Srgrimes} 5061573Srgrimes 5071573Srgrimes/* 5081573Srgrimes * Count how big the total key size is by recursing through the pages. Then 5091573Srgrimes * collect the data, allocate a buffer and copy the key as you recurse up. 5101573Srgrimes */ 5111573Srgrimesstatic int 512189291Sdelphijcollect_key(HTAB *hashp, BUFHEAD *bufp, int len, DBT *val, int set) 5131573Srgrimes{ 5141573Srgrimes BUFHEAD *xbp; 5151573Srgrimes char *p; 5161573Srgrimes int mylen, totlen; 51714272Spst u_int16_t *bp, save_addr; 5181573Srgrimes 5191573Srgrimes p = bufp->page; 52014272Spst bp = (u_int16_t *)p; 5211573Srgrimes mylen = hashp->BSIZE - bp[1]; 5221573Srgrimes 5231573Srgrimes save_addr = bufp->addr; 5241573Srgrimes totlen = len + mylen; 5251573Srgrimes if (bp[2] == FULL_KEY || bp[2] == FULL_KEY_DATA) { /* End of Key. */ 5261573Srgrimes if (hashp->tmp_key != NULL) 5271573Srgrimes free(hashp->tmp_key); 5281573Srgrimes if ((hashp->tmp_key = (char *)malloc(totlen)) == NULL) 5291573Srgrimes return (-1); 5301573Srgrimes if (__big_return(hashp, bufp, 1, val, set)) 5311573Srgrimes return (-1); 5321573Srgrimes } else { 5331573Srgrimes xbp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0); 5341573Srgrimes if (!xbp || ((totlen = 5351573Srgrimes collect_key(hashp, xbp, totlen, val, set)) < 1)) 5361573Srgrimes return (-1); 5371573Srgrimes } 5381573Srgrimes if (bufp->addr != save_addr) { 5391573Srgrimes errno = EINVAL; /* MIS -- OUT OF BUFFERS */ 5401573Srgrimes return (-1); 5411573Srgrimes } 5421573Srgrimes memmove(&hashp->tmp_key[len], (bufp->page) + bp[1], mylen); 5431573Srgrimes return (totlen); 5441573Srgrimes} 5451573Srgrimes 5461573Srgrimes/* 5471573Srgrimes * Returns: 5481573Srgrimes * 0 => OK 5491573Srgrimes * -1 => error 5501573Srgrimes */ 551189291Sdelphijint 552189291Sdelphij__big_split(HTAB *hashp, 553189291Sdelphij BUFHEAD *op, /* Pointer to where to put keys that go in old bucket */ 554189291Sdelphij BUFHEAD *np, /* Pointer to new bucket page */ 555189291Sdelphij BUFHEAD *big_keyp, /* Pointer to first page containing the big key/data */ 556189291Sdelphij int addr, /* Address of big_keyp */ 557189291Sdelphij u_int32_t obucket, /* Old Bucket */ 558189291Sdelphij SPLIT_RETURN *ret) 5591573Srgrimes{ 560189327Sdelphij BUFHEAD *bp, *tmpp; 5611573Srgrimes DBT key, val; 56214272Spst u_int32_t change; 563189327Sdelphij u_int16_t free_space, n, off, *tp; 5641573Srgrimes 5651573Srgrimes bp = big_keyp; 5661573Srgrimes 5671573Srgrimes /* Now figure out where the big key/data goes */ 5681573Srgrimes if (__big_keydata(hashp, big_keyp, &key, &val, 0)) 5691573Srgrimes return (-1); 5701573Srgrimes change = (__call_hash(hashp, key.data, key.size) != obucket); 5711573Srgrimes 57217141Sjkh if ( (ret->next_addr = __find_last_page(hashp, &big_keyp)) ) { 5731573Srgrimes if (!(ret->nextp = 5741573Srgrimes __get_buf(hashp, ret->next_addr, big_keyp, 0))) 575189327Sdelphij return (-1); 5761573Srgrimes } else 5771573Srgrimes ret->nextp = NULL; 5781573Srgrimes 5791573Srgrimes /* Now make one of np/op point to the big key/data pair */ 5801573Srgrimes#ifdef DEBUG 5811573Srgrimes assert(np->ovfl == NULL); 5821573Srgrimes#endif 5831573Srgrimes if (change) 5841573Srgrimes tmpp = np; 5851573Srgrimes else 5861573Srgrimes tmpp = op; 5871573Srgrimes 5881573Srgrimes tmpp->flags |= BUF_MOD; 5891573Srgrimes#ifdef DEBUG1 5901573Srgrimes (void)fprintf(stderr, 5911573Srgrimes "BIG_SPLIT: %d->ovfl was %d is now %d\n", tmpp->addr, 5921573Srgrimes (tmpp->ovfl ? tmpp->ovfl->addr : 0), (bp ? bp->addr : 0)); 5931573Srgrimes#endif 5941573Srgrimes tmpp->ovfl = bp; /* one of op/np point to big_keyp */ 59514272Spst tp = (u_int16_t *)tmpp->page; 5961573Srgrimes#ifdef DEBUG 5971573Srgrimes assert(FREESPACE(tp) >= OVFLSIZE); 5981573Srgrimes#endif 5991573Srgrimes n = tp[0]; 6001573Srgrimes off = OFFSET(tp); 6011573Srgrimes free_space = FREESPACE(tp); 60214272Spst tp[++n] = (u_int16_t)addr; 6031573Srgrimes tp[++n] = OVFLPAGE; 6041573Srgrimes tp[0] = n; 6051573Srgrimes OFFSET(tp) = off; 6061573Srgrimes FREESPACE(tp) = free_space - OVFLSIZE; 6071573Srgrimes 6081573Srgrimes /* 6091573Srgrimes * Finally, set the new and old return values. BIG_KEYP contains a 6101573Srgrimes * pointer to the last page of the big key_data pair. Make sure that 6111573Srgrimes * big_keyp has no following page (2 elements) or create an empty 6121573Srgrimes * following page. 6131573Srgrimes */ 6141573Srgrimes 6151573Srgrimes ret->newp = np; 6161573Srgrimes ret->oldp = op; 6171573Srgrimes 61814272Spst tp = (u_int16_t *)big_keyp->page; 6191573Srgrimes big_keyp->flags |= BUF_MOD; 6201573Srgrimes if (tp[0] > 2) { 6211573Srgrimes /* 6221573Srgrimes * There may be either one or two offsets on this page. If 6231573Srgrimes * there is one, then the overflow page is linked on normally 6241573Srgrimes * and tp[4] is OVFLPAGE. If there are two, tp[4] contains 6251573Srgrimes * the second offset and needs to get stuffed in after the 6261573Srgrimes * next overflow page is added. 6271573Srgrimes */ 6281573Srgrimes n = tp[4]; 6291573Srgrimes free_space = FREESPACE(tp); 6301573Srgrimes off = OFFSET(tp); 6311573Srgrimes tp[0] -= 2; 6321573Srgrimes FREESPACE(tp) = free_space + OVFLSIZE; 6331573Srgrimes OFFSET(tp) = off; 6341573Srgrimes tmpp = __add_ovflpage(hashp, big_keyp); 6351573Srgrimes if (!tmpp) 6361573Srgrimes return (-1); 6371573Srgrimes tp[4] = n; 6381573Srgrimes } else 6391573Srgrimes tmpp = big_keyp; 6401573Srgrimes 6411573Srgrimes if (change) 6421573Srgrimes ret->newp = tmpp; 6431573Srgrimes else 6441573Srgrimes ret->oldp = tmpp; 6451573Srgrimes return (0); 6461573Srgrimes} 647