1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/security/nss/lib/dbm/src/h_bigkey.c Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,709 @@
1.4 +/*-
1.5 + * Copyright (c) 1990, 1993, 1994
1.6 + * The Regents of the University of California. All rights reserved.
1.7 + *
1.8 + * This code is derived from software contributed to Berkeley by
1.9 + * Margo Seltzer.
1.10 + *
1.11 + * Redistribution and use in source and binary forms, with or without
1.12 + * modification, are permitted provided that the following conditions
1.13 + * are met:
1.14 + * 1. Redistributions of source code must retain the above copyright
1.15 + * notice, this list of conditions and the following disclaimer.
1.16 + * 2. Redistributions in binary form must reproduce the above copyright
1.17 + * notice, this list of conditions and the following disclaimer in the
1.18 + * documentation and/or other materials provided with the distribution.
1.19 + * 3. ***REMOVED*** - see
1.20 + * ftp://ftp.cs.berkeley.edu/pub/4bsd/README.Impt.License.Change
1.21 + * 4. Neither the name of the University nor the names of its contributors
1.22 + * may be used to endorse or promote products derived from this software
1.23 + * without specific prior written permission.
1.24 + *
1.25 + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
1.26 + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
1.27 + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
1.28 + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
1.29 + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
1.30 + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
1.31 + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
1.32 + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
1.33 + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
1.34 + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
1.35 + * SUCH DAMAGE.
1.36 + */
1.37 +
1.38 +#if defined(LIBC_SCCS) && !defined(lint)
1.39 +static char sccsid[] = "@(#)hash_bigkey.c 8.3 (Berkeley) 5/31/94";
1.40 +#endif /* LIBC_SCCS and not lint */
1.41 +
1.42 +/*
1.43 + * PACKAGE: hash
1.44 + * DESCRIPTION:
1.45 + * Big key/data handling for the hashing package.
1.46 + *
1.47 + * ROUTINES:
1.48 + * External
1.49 + * __big_keydata
1.50 + * __big_split
1.51 + * __big_insert
1.52 + * __big_return
1.53 + * __big_delete
1.54 + * __find_last_page
1.55 + * Internal
1.56 + * collect_key
1.57 + * collect_data
1.58 + */
1.59 +
1.60 +#if !defined(_WIN32) && !defined(_WINDOWS) && !defined(macintosh)
1.61 +#include <sys/param.h>
1.62 +#endif
1.63 +
1.64 +#include <errno.h>
1.65 +#include <stdio.h>
1.66 +#include <stdlib.h>
1.67 +#include <string.h>
1.68 +
1.69 +#ifdef DEBUG
1.70 +#include <assert.h>
1.71 +#endif
1.72 +
1.73 +#include "mcom_db.h"
1.74 +#include "hash.h"
1.75 +#include "page.h"
1.76 +/* #include "extern.h" */
1.77 +
1.78 +static int collect_key __P((HTAB *, BUFHEAD *, int, DBT *, int));
1.79 +static int collect_data __P((HTAB *, BUFHEAD *, int, int));
1.80 +
1.81 +/*
1.82 + * Big_insert
1.83 + *
1.84 + * You need to do an insert and the key/data pair is too big
1.85 + *
1.86 + * Returns:
1.87 + * 0 ==> OK
1.88 + *-1 ==> ERROR
1.89 + */
1.90 +extern int
1.91 +__big_insert(HTAB *hashp, BUFHEAD *bufp, const DBT *key, const DBT *val)
1.92 +{
1.93 + register uint16 *p;
1.94 + uint key_size, n, val_size;
1.95 + uint16 space, move_bytes, off;
1.96 + char *cp, *key_data, *val_data;
1.97 +
1.98 + cp = bufp->page; /* Character pointer of p. */
1.99 + p = (uint16 *)cp;
1.100 +
1.101 + key_data = (char *)key->data;
1.102 + key_size = key->size;
1.103 + val_data = (char *)val->data;
1.104 + val_size = val->size;
1.105 +
1.106 + /* First move the Key */
1.107 + for (space = FREESPACE(p) - BIGOVERHEAD; key_size;
1.108 + space = FREESPACE(p) - BIGOVERHEAD) {
1.109 + move_bytes = PR_MIN(space, key_size);
1.110 + off = OFFSET(p) - move_bytes;
1.111 + memmove(cp + off, key_data, move_bytes);
1.112 + key_size -= move_bytes;
1.113 + key_data += move_bytes;
1.114 + n = p[0];
1.115 + p[++n] = off;
1.116 + p[0] = ++n;
1.117 + FREESPACE(p) = off - PAGE_META(n);
1.118 + OFFSET(p) = off;
1.119 + p[n] = PARTIAL_KEY;
1.120 + bufp = __add_ovflpage(hashp, bufp);
1.121 + if (!bufp)
1.122 + return (-1);
1.123 + n = p[0];
1.124 + if (!key_size) {
1.125 + if (FREESPACE(p)) {
1.126 + move_bytes = PR_MIN(FREESPACE(p), val_size);
1.127 + off = OFFSET(p) - move_bytes;
1.128 + p[n] = off;
1.129 + memmove(cp + off, val_data, move_bytes);
1.130 + val_data += move_bytes;
1.131 + val_size -= move_bytes;
1.132 + p[n - 2] = FULL_KEY_DATA;
1.133 + FREESPACE(p) = FREESPACE(p) - move_bytes;
1.134 + OFFSET(p) = off;
1.135 + } else
1.136 + p[n - 2] = FULL_KEY;
1.137 + }
1.138 + p = (uint16 *)bufp->page;
1.139 + cp = bufp->page;
1.140 + bufp->flags |= BUF_MOD;
1.141 + }
1.142 +
1.143 + /* Now move the data */
1.144 + for (space = FREESPACE(p) - BIGOVERHEAD; val_size;
1.145 + space = FREESPACE(p) - BIGOVERHEAD) {
1.146 + move_bytes = PR_MIN(space, val_size);
1.147 + /*
1.148 + * Here's the hack to make sure that if the data ends on the
1.149 + * same page as the key ends, FREESPACE is at least one.
1.150 + */
1.151 + if (space == val_size && val_size == val->size)
1.152 + move_bytes--;
1.153 + off = OFFSET(p) - move_bytes;
1.154 + memmove(cp + off, val_data, move_bytes);
1.155 + val_size -= move_bytes;
1.156 + val_data += move_bytes;
1.157 + n = p[0];
1.158 + p[++n] = off;
1.159 + p[0] = ++n;
1.160 + FREESPACE(p) = off - PAGE_META(n);
1.161 + OFFSET(p) = off;
1.162 + if (val_size) {
1.163 + p[n] = FULL_KEY;
1.164 + bufp = __add_ovflpage(hashp, bufp);
1.165 + if (!bufp)
1.166 + return (-1);
1.167 + cp = bufp->page;
1.168 + p = (uint16 *)cp;
1.169 + } else
1.170 + p[n] = FULL_KEY_DATA;
1.171 + bufp->flags |= BUF_MOD;
1.172 + }
1.173 + return (0);
1.174 +}
1.175 +
1.176 +/*
1.177 + * Called when bufp's page contains a partial key (index should be 1)
1.178 + *
1.179 + * All pages in the big key/data pair except bufp are freed. We cannot
1.180 + * free bufp because the page pointing to it is lost and we can't get rid
1.181 + * of its pointer.
1.182 + *
1.183 + * Returns:
1.184 + * 0 => OK
1.185 + *-1 => ERROR
1.186 + */
1.187 +extern int
1.188 +__big_delete(HTAB *hashp, BUFHEAD *bufp)
1.189 +{
1.190 + register BUFHEAD *last_bfp, *rbufp;
1.191 + uint16 *bp, pageno;
1.192 + int key_done, n;
1.193 +
1.194 + rbufp = bufp;
1.195 + last_bfp = NULL;
1.196 + bp = (uint16 *)bufp->page;
1.197 + pageno = 0;
1.198 + key_done = 0;
1.199 +
1.200 + while (!key_done || (bp[2] != FULL_KEY_DATA)) {
1.201 + if (bp[2] == FULL_KEY || bp[2] == FULL_KEY_DATA)
1.202 + key_done = 1;
1.203 +
1.204 + /*
1.205 + * If there is freespace left on a FULL_KEY_DATA page, then
1.206 + * the data is short and fits entirely on this page, and this
1.207 + * is the last page.
1.208 + */
1.209 + if (bp[2] == FULL_KEY_DATA && FREESPACE(bp))
1.210 + break;
1.211 + pageno = bp[bp[0] - 1];
1.212 + rbufp->flags |= BUF_MOD;
1.213 + rbufp = __get_buf(hashp, pageno, rbufp, 0);
1.214 + if (last_bfp)
1.215 + __free_ovflpage(hashp, last_bfp);
1.216 + last_bfp = rbufp;
1.217 + if (!rbufp)
1.218 + return (-1); /* Error. */
1.219 + bp = (uint16 *)rbufp->page;
1.220 + }
1.221 +
1.222 + /*
1.223 + * If we get here then rbufp points to the last page of the big
1.224 + * key/data pair. Bufp points to the first one -- it should now be
1.225 + * empty pointing to the next page after this pair. Can't free it
1.226 + * because we don't have the page pointing to it.
1.227 + */
1.228 +
1.229 + /* This is information from the last page of the pair. */
1.230 + n = bp[0];
1.231 + pageno = bp[n - 1];
1.232 +
1.233 + /* Now, bp is the first page of the pair. */
1.234 + bp = (uint16 *)bufp->page;
1.235 + if (n > 2) {
1.236 + /* There is an overflow page. */
1.237 + bp[1] = pageno;
1.238 + bp[2] = OVFLPAGE;
1.239 + bufp->ovfl = rbufp->ovfl;
1.240 + } else
1.241 + /* This is the last page. */
1.242 + bufp->ovfl = NULL;
1.243 + n -= 2;
1.244 + bp[0] = n;
1.245 + FREESPACE(bp) = hashp->BSIZE - PAGE_META(n);
1.246 + OFFSET(bp) = hashp->BSIZE - 1;
1.247 +
1.248 + bufp->flags |= BUF_MOD;
1.249 + if (rbufp)
1.250 + __free_ovflpage(hashp, rbufp);
1.251 + if (last_bfp != rbufp)
1.252 + __free_ovflpage(hashp, last_bfp);
1.253 +
1.254 + hashp->NKEYS--;
1.255 + return (0);
1.256 +}
1.257 +/*
1.258 + * Returns:
1.259 + * 0 = key not found
1.260 + * -1 = get next overflow page
1.261 + * -2 means key not found and this is big key/data
1.262 + * -3 error
1.263 + */
1.264 +extern int
1.265 +__find_bigpair(HTAB *hashp, BUFHEAD *bufp, int ndx, char *key, int size)
1.266 +{
1.267 + register uint16 *bp;
1.268 + register char *p;
1.269 + int ksize;
1.270 + uint16 bytes;
1.271 + char *kkey;
1.272 +
1.273 + bp = (uint16 *)bufp->page;
1.274 + p = bufp->page;
1.275 + ksize = size;
1.276 + kkey = key;
1.277 +
1.278 + for (bytes = hashp->BSIZE - bp[ndx];
1.279 + bytes <= size && bp[ndx + 1] == PARTIAL_KEY;
1.280 + bytes = hashp->BSIZE - bp[ndx]) {
1.281 + if (memcmp(p + bp[ndx], kkey, bytes))
1.282 + return (-2);
1.283 + kkey += bytes;
1.284 + ksize -= bytes;
1.285 + bufp = __get_buf(hashp, bp[ndx + 2], bufp, 0);
1.286 + if (!bufp)
1.287 + return (-3);
1.288 + p = bufp->page;
1.289 + bp = (uint16 *)p;
1.290 + ndx = 1;
1.291 + }
1.292 +
1.293 + if (bytes != ksize || memcmp(p + bp[ndx], kkey, bytes)) {
1.294 +#ifdef HASH_STATISTICS
1.295 + ++hash_collisions;
1.296 +#endif
1.297 + return (-2);
1.298 + } else
1.299 + return (ndx);
1.300 +}
1.301 +
1.302 +/*
1.303 + * Given the buffer pointer of the first overflow page of a big pair,
1.304 + * find the end of the big pair
1.305 + *
1.306 + * This will set bpp to the buffer header of the last page of the big pair.
1.307 + * It will return the pageno of the overflow page following the last page
1.308 + * of the pair; 0 if there isn't any (i.e. big pair is the last key in the
1.309 + * bucket)
1.310 + */
1.311 +extern uint16
1.312 +__find_last_page(HTAB *hashp, BUFHEAD **bpp)
1.313 +{
1.314 + BUFHEAD *bufp;
1.315 + uint16 *bp, pageno;
1.316 + uint n;
1.317 +
1.318 + bufp = *bpp;
1.319 + bp = (uint16 *)bufp->page;
1.320 + for (;;) {
1.321 + n = bp[0];
1.322 +
1.323 + /*
1.324 + * This is the last page if: the tag is FULL_KEY_DATA and
1.325 + * either only 2 entries OVFLPAGE marker is explicit there
1.326 + * is freespace on the page.
1.327 + */
1.328 + if (bp[2] == FULL_KEY_DATA &&
1.329 + ((n == 2) || (bp[n] == OVFLPAGE) || (FREESPACE(bp))))
1.330 + break;
1.331 +
1.332 + /* LJM bound the size of n to reasonable limits
1.333 + */
1.334 + if(n > hashp->BSIZE/sizeof(uint16))
1.335 + return(0);
1.336 +
1.337 + pageno = bp[n - 1];
1.338 + bufp = __get_buf(hashp, pageno, bufp, 0);
1.339 + if (!bufp)
1.340 + return (0); /* Need to indicate an error! */
1.341 + bp = (uint16 *)bufp->page;
1.342 + }
1.343 +
1.344 + *bpp = bufp;
1.345 + if (bp[0] > 2)
1.346 + return (bp[3]);
1.347 + else
1.348 + return (0);
1.349 +}
1.350 +
1.351 +/*
1.352 + * Return the data for the key/data pair that begins on this page at this
1.353 + * index (index should always be 1).
1.354 + */
1.355 +extern int
1.356 +__big_return(
1.357 + HTAB *hashp,
1.358 + BUFHEAD *bufp,
1.359 + int ndx,
1.360 + DBT *val,
1.361 + int set_current)
1.362 +{
1.363 + BUFHEAD *save_p;
1.364 + uint16 *bp, len, off, save_addr;
1.365 + char *tp;
1.366 + int save_flags;
1.367 +
1.368 + bp = (uint16 *)bufp->page;
1.369 + while (bp[ndx + 1] == PARTIAL_KEY) {
1.370 + bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
1.371 + if (!bufp)
1.372 + return (-1);
1.373 + bp = (uint16 *)bufp->page;
1.374 + ndx = 1;
1.375 + }
1.376 +
1.377 + if (bp[ndx + 1] == FULL_KEY) {
1.378 + bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
1.379 + if (!bufp)
1.380 + return (-1);
1.381 + bp = (uint16 *)bufp->page;
1.382 + save_p = bufp;
1.383 + save_addr = save_p->addr;
1.384 + off = bp[1];
1.385 + len = 0;
1.386 + } else
1.387 + if (!FREESPACE(bp)) {
1.388 + /*
1.389 + * This is a hack. We can't distinguish between
1.390 + * FULL_KEY_DATA that contains complete data or
1.391 + * incomplete data, so we require that if the data
1.392 + * is complete, there is at least 1 byte of free
1.393 + * space left.
1.394 + */
1.395 + off = bp[bp[0]];
1.396 + len = bp[1] - off;
1.397 + save_p = bufp;
1.398 + save_addr = bufp->addr;
1.399 + bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
1.400 + if (!bufp)
1.401 + return (-1);
1.402 + bp = (uint16 *)bufp->page;
1.403 + } else {
1.404 + /* The data is all on one page. */
1.405 + tp = (char *)bp;
1.406 + off = bp[bp[0]];
1.407 + val->data = (uint8 *)tp + off;
1.408 + val->size = bp[1] - off;
1.409 + if (set_current) {
1.410 + if (bp[0] == 2) { /* No more buckets in
1.411 + * chain */
1.412 + hashp->cpage = NULL;
1.413 + hashp->cbucket++;
1.414 + hashp->cndx = 1;
1.415 + } else {
1.416 + hashp->cpage = __get_buf(hashp,
1.417 + bp[bp[0] - 1], bufp, 0);
1.418 + if (!hashp->cpage)
1.419 + return (-1);
1.420 + hashp->cndx = 1;
1.421 + if (!((uint16 *)
1.422 + hashp->cpage->page)[0]) {
1.423 + hashp->cbucket++;
1.424 + hashp->cpage = NULL;
1.425 + }
1.426 + }
1.427 + }
1.428 + return (0);
1.429 + }
1.430 +
1.431 + /* pin our saved buf so that we don't lose if
1.432 + * we run out of buffers */
1.433 + save_flags = save_p->flags;
1.434 + save_p->flags |= BUF_PIN;
1.435 + val->size = collect_data(hashp, bufp, (int)len, set_current);
1.436 + save_p->flags = save_flags;
1.437 + if (val->size == (size_t)-1)
1.438 + return (-1);
1.439 + if (save_p->addr != save_addr) {
1.440 + /* We are pretty short on buffers. */
1.441 + errno = EINVAL; /* OUT OF BUFFERS */
1.442 + return (-1);
1.443 + }
1.444 + memmove(hashp->tmp_buf, (save_p->page) + off, len);
1.445 + val->data = (uint8 *)hashp->tmp_buf;
1.446 + return (0);
1.447 +}
1.448 +
1.449 +
1.450 +/*
1.451 + * Count how big the total datasize is by looping through the pages. Then
1.452 + * allocate a buffer and copy the data in the second loop. NOTE: Our caller
1.453 + * may already have a bp which it is holding onto. The caller is
1.454 + * responsible for copying that bp into our temp buffer. 'len' is how much
1.455 + * space to reserve for that buffer.
1.456 + */
1.457 +static int
1.458 +collect_data(
1.459 + HTAB *hashp,
1.460 + BUFHEAD *bufp,
1.461 + int len, int set)
1.462 +{
1.463 + register uint16 *bp;
1.464 + BUFHEAD *save_bufp;
1.465 + int save_flags;
1.466 + int mylen, totlen;
1.467 +
1.468 + /*
1.469 + * save the input buf head because we need to walk the list twice.
1.470 + * pin it to make sure it doesn't leave the buffer pool.
1.471 + * This has the effect of growing the buffer pool if necessary.
1.472 + */
1.473 + save_bufp = bufp;
1.474 + save_flags = save_bufp->flags;
1.475 + save_bufp->flags |= BUF_PIN;
1.476 +
1.477 + /* read the length of the buffer */
1.478 + for (totlen = len; bufp ; bufp = __get_buf(hashp, bp[bp[0]-1], bufp, 0)) {
1.479 + bp = (uint16 *)bufp->page;
1.480 + mylen = hashp->BSIZE - bp[1];
1.481 +
1.482 + /* if mylen ever goes negative it means that the
1.483 + * page is screwed up.
1.484 + */
1.485 + if (mylen < 0) {
1.486 + save_bufp->flags = save_flags;
1.487 + return (-1);
1.488 + }
1.489 + totlen += mylen;
1.490 + if (bp[2] == FULL_KEY_DATA) { /* End of Data */
1.491 + break;
1.492 + }
1.493 + }
1.494 +
1.495 + if (!bufp) {
1.496 + save_bufp->flags = save_flags;
1.497 + return (-1);
1.498 + }
1.499 +
1.500 + /* allocate a temp buf */
1.501 + if (hashp->tmp_buf)
1.502 + free(hashp->tmp_buf);
1.503 + if ((hashp->tmp_buf = (char *)malloc((size_t)totlen)) == NULL) {
1.504 + save_bufp->flags = save_flags;
1.505 + return (-1);
1.506 + }
1.507 +
1.508 + /* copy the buffers back into temp buf */
1.509 + for (bufp = save_bufp; bufp ;
1.510 + bufp = __get_buf(hashp, bp[bp[0]-1], bufp, 0)) {
1.511 + bp = (uint16 *)bufp->page;
1.512 + mylen = hashp->BSIZE - bp[1];
1.513 + memmove(&hashp->tmp_buf[len], (bufp->page) + bp[1], (size_t)mylen);
1.514 + len += mylen;
1.515 + if (bp[2] == FULL_KEY_DATA) {
1.516 + break;
1.517 + }
1.518 + }
1.519 +
1.520 + /* 'clear' the pin flags */
1.521 + save_bufp->flags = save_flags;
1.522 +
1.523 + /* update the database cursor */
1.524 + if (set) {
1.525 + hashp->cndx = 1;
1.526 + if (bp[0] == 2) { /* No more buckets in chain */
1.527 + hashp->cpage = NULL;
1.528 + hashp->cbucket++;
1.529 + } else {
1.530 + hashp->cpage = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
1.531 + if (!hashp->cpage)
1.532 + return (-1);
1.533 + else if (!((uint16 *)hashp->cpage->page)[0]) {
1.534 + hashp->cbucket++;
1.535 + hashp->cpage = NULL;
1.536 + }
1.537 + }
1.538 + }
1.539 + return (totlen);
1.540 +}
1.541 +
1.542 +/*
1.543 + * Fill in the key and data for this big pair.
1.544 + */
1.545 +extern int
1.546 +__big_keydata(
1.547 + HTAB *hashp,
1.548 + BUFHEAD *bufp,
1.549 + DBT *key, DBT *val,
1.550 + int set)
1.551 +{
1.552 + key->size = collect_key(hashp, bufp, 0, val, set);
1.553 + if (key->size == (size_t)-1)
1.554 + return (-1);
1.555 + key->data = (uint8 *)hashp->tmp_key;
1.556 + return (0);
1.557 +}
1.558 +
1.559 +/*
1.560 + * Count how big the total key size is by recursing through the pages. Then
1.561 + * collect the data, allocate a buffer and copy the key as you recurse up.
1.562 + */
1.563 +static int
1.564 +collect_key(
1.565 + HTAB *hashp,
1.566 + BUFHEAD *bufp,
1.567 + int len,
1.568 + DBT *val,
1.569 + int set)
1.570 +{
1.571 + BUFHEAD *xbp;
1.572 + char *p;
1.573 + int mylen, totlen;
1.574 + uint16 *bp, save_addr;
1.575 +
1.576 + p = bufp->page;
1.577 + bp = (uint16 *)p;
1.578 + mylen = hashp->BSIZE - bp[1];
1.579 +
1.580 + save_addr = bufp->addr;
1.581 + totlen = len + mylen;
1.582 + if (bp[2] == FULL_KEY || bp[2] == FULL_KEY_DATA) { /* End of Key. */
1.583 + if (hashp->tmp_key != NULL)
1.584 + free(hashp->tmp_key);
1.585 + if ((hashp->tmp_key = (char *)malloc((size_t)totlen)) == NULL)
1.586 + return (-1);
1.587 + if (__big_return(hashp, bufp, 1, val, set))
1.588 + return (-1);
1.589 + } else {
1.590 + xbp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
1.591 + if (!xbp || ((totlen =
1.592 + collect_key(hashp, xbp, totlen, val, set)) < 1))
1.593 + return (-1);
1.594 + }
1.595 + if (bufp->addr != save_addr) {
1.596 + errno = EINVAL; /* MIS -- OUT OF BUFFERS */
1.597 + return (-1);
1.598 + }
1.599 + memmove(&hashp->tmp_key[len], (bufp->page) + bp[1], (size_t)mylen);
1.600 + return (totlen);
1.601 +}
1.602 +
1.603 +/*
1.604 + * Returns:
1.605 + * 0 => OK
1.606 + * -1 => error
1.607 + */
1.608 +extern int
1.609 +__big_split(
1.610 + HTAB *hashp,
1.611 + BUFHEAD *op, /* Pointer to where to put keys that go in old bucket */
1.612 + BUFHEAD *np, /* Pointer to new bucket page */
1.613 + /* Pointer to first page containing the big key/data */
1.614 + BUFHEAD *big_keyp,
1.615 + uint32 addr, /* Address of big_keyp */
1.616 + uint32 obucket,/* Old Bucket */
1.617 + SPLIT_RETURN *ret)
1.618 +{
1.619 + register BUFHEAD *tmpp;
1.620 + register uint16 *tp;
1.621 + BUFHEAD *bp;
1.622 + DBT key, val;
1.623 + uint32 change;
1.624 + uint16 free_space, n, off;
1.625 +
1.626 + bp = big_keyp;
1.627 +
1.628 + /* Now figure out where the big key/data goes */
1.629 + if (__big_keydata(hashp, big_keyp, &key, &val, 0))
1.630 + return (-1);
1.631 + change = (__call_hash(hashp,(char*) key.data, key.size) != obucket);
1.632 +
1.633 + if ((ret->next_addr = __find_last_page(hashp, &big_keyp))) {
1.634 + if (!(ret->nextp =
1.635 + __get_buf(hashp, ret->next_addr, big_keyp, 0)))
1.636 + return (-1);;
1.637 + } else
1.638 + ret->nextp = NULL;
1.639 +
1.640 + /* Now make one of np/op point to the big key/data pair */
1.641 +#ifdef DEBUG
1.642 + assert(np->ovfl == NULL);
1.643 +#endif
1.644 + if (change)
1.645 + tmpp = np;
1.646 + else
1.647 + tmpp = op;
1.648 +
1.649 + tmpp->flags |= BUF_MOD;
1.650 +#ifdef DEBUG1
1.651 + (void)fprintf(stderr,
1.652 + "BIG_SPLIT: %d->ovfl was %d is now %d\n", tmpp->addr,
1.653 + (tmpp->ovfl ? tmpp->ovfl->addr : 0), (bp ? bp->addr : 0));
1.654 +#endif
1.655 + tmpp->ovfl = bp; /* one of op/np point to big_keyp */
1.656 + tp = (uint16 *)tmpp->page;
1.657 +
1.658 +
1.659 +#if 0 /* this get's tripped on database corrupted error */
1.660 + assert(FREESPACE(tp) >= OVFLSIZE);
1.661 +#endif
1.662 + if(FREESPACE(tp) < OVFLSIZE)
1.663 + return(DATABASE_CORRUPTED_ERROR);
1.664 +
1.665 + n = tp[0];
1.666 + off = OFFSET(tp);
1.667 + free_space = FREESPACE(tp);
1.668 + tp[++n] = (uint16)addr;
1.669 + tp[++n] = OVFLPAGE;
1.670 + tp[0] = n;
1.671 + OFFSET(tp) = off;
1.672 + FREESPACE(tp) = free_space - OVFLSIZE;
1.673 +
1.674 + /*
1.675 + * Finally, set the new and old return values. BIG_KEYP contains a
1.676 + * pointer to the last page of the big key_data pair. Make sure that
1.677 + * big_keyp has no following page (2 elements) or create an empty
1.678 + * following page.
1.679 + */
1.680 +
1.681 + ret->newp = np;
1.682 + ret->oldp = op;
1.683 +
1.684 + tp = (uint16 *)big_keyp->page;
1.685 + big_keyp->flags |= BUF_MOD;
1.686 + if (tp[0] > 2) {
1.687 + /*
1.688 + * There may be either one or two offsets on this page. If
1.689 + * there is one, then the overflow page is linked on normally
1.690 + * and tp[4] is OVFLPAGE. If there are two, tp[4] contains
1.691 + * the second offset and needs to get stuffed in after the
1.692 + * next overflow page is added.
1.693 + */
1.694 + n = tp[4];
1.695 + free_space = FREESPACE(tp);
1.696 + off = OFFSET(tp);
1.697 + tp[0] -= 2;
1.698 + FREESPACE(tp) = free_space + OVFLSIZE;
1.699 + OFFSET(tp) = off;
1.700 + tmpp = __add_ovflpage(hashp, big_keyp);
1.701 + if (!tmpp)
1.702 + return (-1);
1.703 + tp[4] = n;
1.704 + } else
1.705 + tmpp = big_keyp;
1.706 +
1.707 + if (change)
1.708 + ret->newp = tmpp;
1.709 + else
1.710 + ret->oldp = tmpp;
1.711 + return (0);
1.712 +}
