1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/security/nss/lib/dbm/src/h_page.c Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,1286 @@
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(unix)
1.39 +#define MY_LSEEK lseek
1.40 +#else
1.41 +#define MY_LSEEK new_lseek
1.42 +extern long new_lseek(int fd, long pos, int start);
1.43 +#endif
1.44 +
1.45 +#if defined(LIBC_SCCS) && !defined(lint)
1.46 +static char sccsid[] = "@(#)hash_page.c 8.7 (Berkeley) 8/16/94";
1.47 +#endif /* LIBC_SCCS and not lint */
1.48 +
1.49 +/*
1.50 + * PACKAGE: hashing
1.51 + *
1.52 + * DESCRIPTION:
1.53 + * Page manipulation for hashing package.
1.54 + *
1.55 + * ROUTINES:
1.56 + *
1.57 + * External
1.58 + * __get_page
1.59 + * __add_ovflpage
1.60 + * Internal
1.61 + * overflow_page
1.62 + * open_temp
1.63 + */
1.64 +#ifndef macintosh
1.65 +#include <sys/types.h>
1.66 +#endif
1.67 +
1.68 +#if defined(macintosh)
1.69 +#include <unistd.h>
1.70 +#endif
1.71 +
1.72 +#include <errno.h>
1.73 +#include <fcntl.h>
1.74 +#if defined(_WIN32) || defined(_WINDOWS)
1.75 +#include <io.h>
1.76 +#endif
1.77 +#include <signal.h>
1.78 +#include <stdio.h>
1.79 +#include <stdlib.h>
1.80 +#include <string.h>
1.81 +
1.82 +#if !defined(_WIN32) && !defined(_WINDOWS) && !defined(macintosh)
1.83 +#include <unistd.h>
1.84 +#endif
1.85 +
1.86 +#include <assert.h>
1.87 +
1.88 +#include "mcom_db.h"
1.89 +#include "hash.h"
1.90 +#include "page.h"
1.91 +/* #include "extern.h" */
1.92 +
1.93 +extern int mkstempflags(char *path, int extraFlags);
1.94 +
1.95 +static uint32 *fetch_bitmap __P((HTAB *, uint32));
1.96 +static uint32 first_free __P((uint32));
1.97 +static int open_temp __P((HTAB *));
1.98 +static uint16 overflow_page __P((HTAB *));
1.99 +static void squeeze_key __P((uint16 *, const DBT *, const DBT *));
1.100 +static int ugly_split
1.101 + __P((HTAB *, uint32, BUFHEAD *, BUFHEAD *, int, int));
1.102 +
1.103 +#define PAGE_INIT(P) { \
1.104 + ((uint16 *)(P))[0] = 0; \
1.105 + ((uint16 *)(P))[1] = hashp->BSIZE - 3 * sizeof(uint16); \
1.106 + ((uint16 *)(P))[2] = hashp->BSIZE; \
1.107 +}
1.108 +
1.109 +/* implement a new lseek using lseek that
1.110 + * writes zero's when extending a file
1.111 + * beyond the end.
1.112 + */
1.113 +long new_lseek(int fd, long offset, int origin)
1.114 +{
1.115 + long cur_pos=0;
1.116 + long end_pos=0;
1.117 + long seek_pos=0;
1.118 +
1.119 + if(origin == SEEK_CUR)
1.120 + {
1.121 + if(offset < 1)
1.122 + return(lseek(fd, offset, SEEK_CUR));
1.123 +
1.124 + cur_pos = lseek(fd, 0, SEEK_CUR);
1.125 +
1.126 + if(cur_pos < 0)
1.127 + return(cur_pos);
1.128 + }
1.129 +
1.130 + end_pos = lseek(fd, 0, SEEK_END);
1.131 + if(end_pos < 0)
1.132 + return(end_pos);
1.133 +
1.134 + if(origin == SEEK_SET)
1.135 + seek_pos = offset;
1.136 + else if(origin == SEEK_CUR)
1.137 + seek_pos = cur_pos + offset;
1.138 + else if(origin == SEEK_END)
1.139 + seek_pos = end_pos + offset;
1.140 + else
1.141 + {
1.142 + assert(0);
1.143 + return(-1);
1.144 + }
1.145 +
1.146 + /* the seek position desired is before the
1.147 + * end of the file. We don't need
1.148 + * to do anything special except the seek.
1.149 + */
1.150 + if(seek_pos <= end_pos)
1.151 + return(lseek(fd, seek_pos, SEEK_SET));
1.152 +
1.153 + /* the seek position is beyond the end of the
1.154 + * file. Write zero's to the end.
1.155 + *
1.156 + * we are already at the end of the file so
1.157 + * we just need to "write()" zeros for the
1.158 + * difference between seek_pos-end_pos and
1.159 + * then seek to the position to finish
1.160 + * the call
1.161 + */
1.162 + {
1.163 + char buffer[1024];
1.164 + long len = seek_pos-end_pos;
1.165 + memset(&buffer, 0, 1024);
1.166 + while(len > 0)
1.167 + {
1.168 + write(fd, (char*)&buffer, (size_t)(1024 > len ? len : 1024));
1.169 + len -= 1024;
1.170 + }
1.171 + return(lseek(fd, seek_pos, SEEK_SET));
1.172 + }
1.173 +
1.174 +}
1.175 +
1.176 +/*
1.177 + * This is called AFTER we have verified that there is room on the page for
1.178 + * the pair (PAIRFITS has returned true) so we go right ahead and start moving
1.179 + * stuff on.
1.180 + */
1.181 +static void
1.182 +putpair(char *p, const DBT *key, DBT * val)
1.183 +{
1.184 + register uint16 *bp, n, off;
1.185 +
1.186 + bp = (uint16 *)p;
1.187 +
1.188 + /* Enter the key first. */
1.189 + n = bp[0];
1.190 +
1.191 + off = OFFSET(bp) - key->size;
1.192 + memmove(p + off, key->data, key->size);
1.193 + bp[++n] = off;
1.194 +
1.195 + /* Now the data. */
1.196 + off -= val->size;
1.197 + memmove(p + off, val->data, val->size);
1.198 + bp[++n] = off;
1.199 +
1.200 + /* Adjust page info. */
1.201 + bp[0] = n;
1.202 + bp[n + 1] = off - ((n + 3) * sizeof(uint16));
1.203 + bp[n + 2] = off;
1.204 +}
1.205 +
1.206 +/*
1.207 + * Returns:
1.208 + * 0 OK
1.209 + * -1 error
1.210 + */
1.211 +extern int
1.212 +__delpair(HTAB *hashp, BUFHEAD *bufp, int ndx)
1.213 +{
1.214 + register uint16 *bp, newoff;
1.215 + register int n;
1.216 + uint16 pairlen;
1.217 +
1.218 + bp = (uint16 *)bufp->page;
1.219 + n = bp[0];
1.220 +
1.221 + if (bp[ndx + 1] < REAL_KEY)
1.222 + return (__big_delete(hashp, bufp));
1.223 + if (ndx != 1)
1.224 + newoff = bp[ndx - 1];
1.225 + else
1.226 + newoff = hashp->BSIZE;
1.227 + pairlen = newoff - bp[ndx + 1];
1.228 +
1.229 + if (ndx != (n - 1)) {
1.230 + /* Hard Case -- need to shuffle keys */
1.231 + register int i;
1.232 + register char *src = bufp->page + (int)OFFSET(bp);
1.233 + uint32 dst_offset = (uint32)OFFSET(bp) + (uint32)pairlen;
1.234 + register char *dst = bufp->page + dst_offset;
1.235 + uint32 length = bp[ndx + 1] - OFFSET(bp);
1.236 +
1.237 + /*
1.238 + * +-----------+XXX+---------+XXX+---------+---------> +infinity
1.239 + * | | | |
1.240 + * 0 src_offset dst_offset BSIZE
1.241 + *
1.242 + * Dst_offset is > src_offset, so if src_offset were bad, dst_offset
1.243 + * would be too, therefore we check only dst_offset.
1.244 + *
1.245 + * If dst_offset is >= BSIZE, either OFFSET(bp), or pairlen, or both
1.246 + * is corrupted.
1.247 + *
1.248 + * Once we know dst_offset is < BSIZE, we can subtract it from BSIZE
1.249 + * to get an upper bound on length.
1.250 + */
1.251 + if(dst_offset > (uint32)hashp->BSIZE)
1.252 + return(DATABASE_CORRUPTED_ERROR);
1.253 +
1.254 + if(length > (uint32)(hashp->BSIZE - dst_offset))
1.255 + return(DATABASE_CORRUPTED_ERROR);
1.256 +
1.257 + memmove(dst, src, length);
1.258 +
1.259 + /* Now adjust the pointers */
1.260 + for (i = ndx + 2; i <= n; i += 2) {
1.261 + if (bp[i + 1] == OVFLPAGE) {
1.262 + bp[i - 2] = bp[i];
1.263 + bp[i - 1] = bp[i + 1];
1.264 + } else {
1.265 + bp[i - 2] = bp[i] + pairlen;
1.266 + bp[i - 1] = bp[i + 1] + pairlen;
1.267 + }
1.268 + }
1.269 + }
1.270 + /* Finally adjust the page data */
1.271 + bp[n] = OFFSET(bp) + pairlen;
1.272 + bp[n - 1] = bp[n + 1] + pairlen + 2 * sizeof(uint16);
1.273 + bp[0] = n - 2;
1.274 + hashp->NKEYS--;
1.275 +
1.276 + bufp->flags |= BUF_MOD;
1.277 + return (0);
1.278 +}
1.279 +/*
1.280 + * Returns:
1.281 + * 0 ==> OK
1.282 + * -1 ==> Error
1.283 + */
1.284 +extern int
1.285 +__split_page(HTAB *hashp, uint32 obucket, uint32 nbucket)
1.286 +{
1.287 + register BUFHEAD *new_bufp, *old_bufp;
1.288 + register uint16 *ino;
1.289 + register uint16 *tmp_uint16_array;
1.290 + register char *np;
1.291 + DBT key, val;
1.292 + uint16 n, ndx;
1.293 + int retval;
1.294 + uint16 copyto, diff, moved;
1.295 + size_t off;
1.296 + char *op;
1.297 +
1.298 + copyto = (uint16)hashp->BSIZE;
1.299 + off = (uint16)hashp->BSIZE;
1.300 + old_bufp = __get_buf(hashp, obucket, NULL, 0);
1.301 + if (old_bufp == NULL)
1.302 + return (-1);
1.303 + new_bufp = __get_buf(hashp, nbucket, NULL, 0);
1.304 + if (new_bufp == NULL)
1.305 + return (-1);
1.306 +
1.307 + old_bufp->flags |= (BUF_MOD | BUF_PIN);
1.308 + new_bufp->flags |= (BUF_MOD | BUF_PIN);
1.309 +
1.310 + ino = (uint16 *)(op = old_bufp->page);
1.311 + np = new_bufp->page;
1.312 +
1.313 + moved = 0;
1.314 +
1.315 + for (n = 1, ndx = 1; n < ino[0]; n += 2) {
1.316 + if (ino[n + 1] < REAL_KEY) {
1.317 + retval = ugly_split(hashp, obucket, old_bufp, new_bufp,
1.318 + (int)copyto, (int)moved);
1.319 + old_bufp->flags &= ~BUF_PIN;
1.320 + new_bufp->flags &= ~BUF_PIN;
1.321 + return (retval);
1.322 +
1.323 + }
1.324 + key.data = (uint8 *)op + ino[n];
1.325 +
1.326 + /* check here for ino[n] being greater than
1.327 + * off. If it is then the database has
1.328 + * been corrupted.
1.329 + */
1.330 + if(ino[n] > off)
1.331 + return(DATABASE_CORRUPTED_ERROR);
1.332 +
1.333 + key.size = off - ino[n];
1.334 +
1.335 +#ifdef DEBUG
1.336 + /* make sure the size is positive */
1.337 + assert(((int)key.size) > -1);
1.338 +#endif
1.339 +
1.340 + if (__call_hash(hashp, (char *)key.data, key.size) == obucket) {
1.341 + /* Don't switch page */
1.342 + diff = copyto - off;
1.343 + if (diff) {
1.344 + copyto = ino[n + 1] + diff;
1.345 + memmove(op + copyto, op + ino[n + 1],
1.346 + off - ino[n + 1]);
1.347 + ino[ndx] = copyto + ino[n] - ino[n + 1];
1.348 + ino[ndx + 1] = copyto;
1.349 + } else
1.350 + copyto = ino[n + 1];
1.351 + ndx += 2;
1.352 + } else {
1.353 + /* Switch page */
1.354 + val.data = (uint8 *)op + ino[n + 1];
1.355 + val.size = ino[n] - ino[n + 1];
1.356 +
1.357 + /* if the pair doesn't fit something is horribly
1.358 + * wrong. LJM
1.359 + */
1.360 + tmp_uint16_array = (uint16*)np;
1.361 + if(!PAIRFITS(tmp_uint16_array, &key, &val))
1.362 + return(DATABASE_CORRUPTED_ERROR);
1.363 +
1.364 + putpair(np, &key, &val);
1.365 + moved += 2;
1.366 + }
1.367 +
1.368 + off = ino[n + 1];
1.369 + }
1.370 +
1.371 + /* Now clean up the page */
1.372 + ino[0] -= moved;
1.373 + FREESPACE(ino) = copyto - sizeof(uint16) * (ino[0] + 3);
1.374 + OFFSET(ino) = copyto;
1.375 +
1.376 +#ifdef DEBUG3
1.377 + (void)fprintf(stderr, "split %d/%d\n",
1.378 + ((uint16 *)np)[0] / 2,
1.379 + ((uint16 *)op)[0] / 2);
1.380 +#endif
1.381 + /* unpin both pages */
1.382 + old_bufp->flags &= ~BUF_PIN;
1.383 + new_bufp->flags &= ~BUF_PIN;
1.384 + return (0);
1.385 +}
1.386 +
1.387 +/*
1.388 + * Called when we encounter an overflow or big key/data page during split
1.389 + * handling. This is special cased since we have to begin checking whether
1.390 + * the key/data pairs fit on their respective pages and because we may need
1.391 + * overflow pages for both the old and new pages.
1.392 + *
1.393 + * The first page might be a page with regular key/data pairs in which case
1.394 + * we have a regular overflow condition and just need to go on to the next
1.395 + * page or it might be a big key/data pair in which case we need to fix the
1.396 + * big key/data pair.
1.397 + *
1.398 + * Returns:
1.399 + * 0 ==> success
1.400 + * -1 ==> failure
1.401 + */
1.402 +
1.403 +/* the maximum number of loops we will allow UGLY split to chew
1.404 + * on before we assume the database is corrupted and throw it
1.405 + * away.
1.406 + */
1.407 +#define MAX_UGLY_SPLIT_LOOPS 10000
1.408 +
1.409 +static int
1.410 +ugly_split(HTAB *hashp, uint32 obucket, BUFHEAD *old_bufp,
1.411 + BUFHEAD *new_bufp,/* Same as __split_page. */ int copyto, int moved)
1.412 + /* int copyto; First byte on page which contains key/data values. */
1.413 + /* int moved; Number of pairs moved to new page. */
1.414 +{
1.415 + register BUFHEAD *bufp; /* Buffer header for ino */
1.416 + register uint16 *ino; /* Page keys come off of */
1.417 + register uint16 *np; /* New page */
1.418 + register uint16 *op; /* Page keys go on to if they aren't moving */
1.419 + uint32 loop_detection=0;
1.420 +
1.421 + BUFHEAD *last_bfp; /* Last buf header OVFL needing to be freed */
1.422 + DBT key, val;
1.423 + SPLIT_RETURN ret;
1.424 + uint16 n, off, ov_addr, scopyto;
1.425 + char *cino; /* Character value of ino */
1.426 + int status;
1.427 +
1.428 + bufp = old_bufp;
1.429 + ino = (uint16 *)old_bufp->page;
1.430 + np = (uint16 *)new_bufp->page;
1.431 + op = (uint16 *)old_bufp->page;
1.432 + last_bfp = NULL;
1.433 + scopyto = (uint16)copyto; /* ANSI */
1.434 +
1.435 + n = ino[0] - 1;
1.436 + while (n < ino[0]) {
1.437 +
1.438 +
1.439 + /* this function goes nuts sometimes and never returns.
1.440 + * I havent found the problem yet but I need a solution
1.441 + * so if we loop too often we assume a database curruption error
1.442 + * :LJM
1.443 + */
1.444 + loop_detection++;
1.445 +
1.446 + if(loop_detection > MAX_UGLY_SPLIT_LOOPS)
1.447 + return DATABASE_CORRUPTED_ERROR;
1.448 +
1.449 + if (ino[2] < REAL_KEY && ino[2] != OVFLPAGE) {
1.450 + if ((status = __big_split(hashp, old_bufp,
1.451 + new_bufp, bufp, bufp->addr, obucket, &ret)))
1.452 + return (status);
1.453 + old_bufp = ret.oldp;
1.454 + if (!old_bufp)
1.455 + return (-1);
1.456 + op = (uint16 *)old_bufp->page;
1.457 + new_bufp = ret.newp;
1.458 + if (!new_bufp)
1.459 + return (-1);
1.460 + np = (uint16 *)new_bufp->page;
1.461 + bufp = ret.nextp;
1.462 + if (!bufp)
1.463 + return (0);
1.464 + cino = (char *)bufp->page;
1.465 + ino = (uint16 *)cino;
1.466 + last_bfp = ret.nextp;
1.467 + } else if (ino[n + 1] == OVFLPAGE) {
1.468 + ov_addr = ino[n];
1.469 + /*
1.470 + * Fix up the old page -- the extra 2 are the fields
1.471 + * which contained the overflow information.
1.472 + */
1.473 + ino[0] -= (moved + 2);
1.474 + FREESPACE(ino) =
1.475 + scopyto - sizeof(uint16) * (ino[0] + 3);
1.476 + OFFSET(ino) = scopyto;
1.477 +
1.478 + bufp = __get_buf(hashp, ov_addr, bufp, 0);
1.479 + if (!bufp)
1.480 + return (-1);
1.481 +
1.482 + ino = (uint16 *)bufp->page;
1.483 + n = 1;
1.484 + scopyto = hashp->BSIZE;
1.485 + moved = 0;
1.486 +
1.487 + if (last_bfp)
1.488 + __free_ovflpage(hashp, last_bfp);
1.489 + last_bfp = bufp;
1.490 + }
1.491 + /* Move regular sized pairs of there are any */
1.492 + off = hashp->BSIZE;
1.493 + for (n = 1; (n < ino[0]) && (ino[n + 1] >= REAL_KEY); n += 2) {
1.494 + cino = (char *)ino;
1.495 + key.data = (uint8 *)cino + ino[n];
1.496 + key.size = off - ino[n];
1.497 + val.data = (uint8 *)cino + ino[n + 1];
1.498 + val.size = ino[n] - ino[n + 1];
1.499 + off = ino[n + 1];
1.500 +
1.501 + if (__call_hash(hashp, (char*)key.data, key.size) == obucket) {
1.502 + /* Keep on old page */
1.503 + if (PAIRFITS(op, (&key), (&val)))
1.504 + putpair((char *)op, &key, &val);
1.505 + else {
1.506 + old_bufp =
1.507 + __add_ovflpage(hashp, old_bufp);
1.508 + if (!old_bufp)
1.509 + return (-1);
1.510 + op = (uint16 *)old_bufp->page;
1.511 + putpair((char *)op, &key, &val);
1.512 + }
1.513 + old_bufp->flags |= BUF_MOD;
1.514 + } else {
1.515 + /* Move to new page */
1.516 + if (PAIRFITS(np, (&key), (&val)))
1.517 + putpair((char *)np, &key, &val);
1.518 + else {
1.519 + new_bufp =
1.520 + __add_ovflpage(hashp, new_bufp);
1.521 + if (!new_bufp)
1.522 + return (-1);
1.523 + np = (uint16 *)new_bufp->page;
1.524 + putpair((char *)np, &key, &val);
1.525 + }
1.526 + new_bufp->flags |= BUF_MOD;
1.527 + }
1.528 + }
1.529 + }
1.530 + if (last_bfp)
1.531 + __free_ovflpage(hashp, last_bfp);
1.532 + return (0);
1.533 +}
1.534 +
1.535 +/*
1.536 + * Add the given pair to the page
1.537 + *
1.538 + * Returns:
1.539 + * 0 ==> OK
1.540 + * 1 ==> failure
1.541 + */
1.542 +extern int
1.543 +__addel(HTAB *hashp, BUFHEAD *bufp, const DBT *key, const DBT * val)
1.544 +{
1.545 + register uint16 *bp, *sop;
1.546 + int do_expand;
1.547 +
1.548 + bp = (uint16 *)bufp->page;
1.549 + do_expand = 0;
1.550 + while (bp[0] && (bp[2] < REAL_KEY || bp[bp[0]] < REAL_KEY))
1.551 + /* Exception case */
1.552 + if (bp[2] == FULL_KEY_DATA && bp[0] == 2)
1.553 + /* This is the last page of a big key/data pair
1.554 + and we need to add another page */
1.555 + break;
1.556 + else if (bp[2] < REAL_KEY && bp[bp[0]] != OVFLPAGE) {
1.557 + bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
1.558 + if (!bufp)
1.559 + {
1.560 +#ifdef DEBUG
1.561 + assert(0);
1.562 +#endif
1.563 + return (-1);
1.564 + }
1.565 + bp = (uint16 *)bufp->page;
1.566 + } else
1.567 + /* Try to squeeze key on this page */
1.568 + if (FREESPACE(bp) > PAIRSIZE(key, val)) {
1.569 + {
1.570 + squeeze_key(bp, key, val);
1.571 +
1.572 + /* LJM: I added this because I think it was
1.573 + * left out on accident.
1.574 + * if this isn't incremented nkeys will not
1.575 + * be the actual number of keys in the db.
1.576 + */
1.577 + hashp->NKEYS++;
1.578 + return (0);
1.579 + }
1.580 + } else {
1.581 + bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
1.582 + if (!bufp)
1.583 + {
1.584 +#ifdef DEBUG
1.585 + assert(0);
1.586 +#endif
1.587 + return (-1);
1.588 + }
1.589 + bp = (uint16 *)bufp->page;
1.590 + }
1.591 +
1.592 + if (PAIRFITS(bp, key, val))
1.593 + putpair(bufp->page, key, (DBT *)val);
1.594 + else {
1.595 + do_expand = 1;
1.596 + bufp = __add_ovflpage(hashp, bufp);
1.597 + if (!bufp)
1.598 + {
1.599 +#ifdef DEBUG
1.600 + assert(0);
1.601 +#endif
1.602 + return (-1);
1.603 + }
1.604 + sop = (uint16 *)bufp->page;
1.605 +
1.606 + if (PAIRFITS(sop, key, val))
1.607 + putpair((char *)sop, key, (DBT *)val);
1.608 + else
1.609 + if (__big_insert(hashp, bufp, key, val))
1.610 + {
1.611 +#ifdef DEBUG
1.612 + assert(0);
1.613 +#endif
1.614 + return (-1);
1.615 + }
1.616 + }
1.617 + bufp->flags |= BUF_MOD;
1.618 + /*
1.619 + * If the average number of keys per bucket exceeds the fill factor,
1.620 + * expand the table.
1.621 + */
1.622 + hashp->NKEYS++;
1.623 + if (do_expand ||
1.624 + (hashp->NKEYS / (hashp->MAX_BUCKET + 1) > hashp->FFACTOR))
1.625 + return (__expand_table(hashp));
1.626 + return (0);
1.627 +}
1.628 +
1.629 +/*
1.630 + *
1.631 + * Returns:
1.632 + * pointer on success
1.633 + * NULL on error
1.634 + */
1.635 +extern BUFHEAD *
1.636 +__add_ovflpage(HTAB *hashp, BUFHEAD *bufp)
1.637 +{
1.638 + register uint16 *sp;
1.639 + uint16 ndx, ovfl_num;
1.640 +#ifdef DEBUG1
1.641 + int tmp1, tmp2;
1.642 +#endif
1.643 + sp = (uint16 *)bufp->page;
1.644 +
1.645 + /* Check if we are dynamically determining the fill factor */
1.646 + if (hashp->FFACTOR == DEF_FFACTOR) {
1.647 + hashp->FFACTOR = sp[0] >> 1;
1.648 + if (hashp->FFACTOR < MIN_FFACTOR)
1.649 + hashp->FFACTOR = MIN_FFACTOR;
1.650 + }
1.651 + bufp->flags |= BUF_MOD;
1.652 + ovfl_num = overflow_page(hashp);
1.653 +#ifdef DEBUG1
1.654 + tmp1 = bufp->addr;
1.655 + tmp2 = bufp->ovfl ? bufp->ovfl->addr : 0;
1.656 +#endif
1.657 + if (!ovfl_num || !(bufp->ovfl = __get_buf(hashp, ovfl_num, bufp, 1)))
1.658 + return (NULL);
1.659 + bufp->ovfl->flags |= BUF_MOD;
1.660 +#ifdef DEBUG1
1.661 + (void)fprintf(stderr, "ADDOVFLPAGE: %d->ovfl was %d is now %d\n",
1.662 + tmp1, tmp2, bufp->ovfl->addr);
1.663 +#endif
1.664 + ndx = sp[0];
1.665 + /*
1.666 + * Since a pair is allocated on a page only if there's room to add
1.667 + * an overflow page, we know that the OVFL information will fit on
1.668 + * the page.
1.669 + */
1.670 + sp[ndx + 4] = OFFSET(sp);
1.671 + sp[ndx + 3] = FREESPACE(sp) - OVFLSIZE;
1.672 + sp[ndx + 1] = ovfl_num;
1.673 + sp[ndx + 2] = OVFLPAGE;
1.674 + sp[0] = ndx + 2;
1.675 +#ifdef HASH_STATISTICS
1.676 + hash_overflows++;
1.677 +#endif
1.678 + return (bufp->ovfl);
1.679 +}
1.680 +
1.681 +/*
1.682 + * Returns:
1.683 + * 0 indicates SUCCESS
1.684 + * -1 indicates FAILURE
1.685 + */
1.686 +extern int
1.687 +__get_page(HTAB *hashp,
1.688 + char * p,
1.689 + uint32 bucket,
1.690 + int is_bucket,
1.691 + int is_disk,
1.692 + int is_bitmap)
1.693 +{
1.694 + register int fd, page;
1.695 + size_t size;
1.696 + int rsize;
1.697 + uint16 *bp;
1.698 +
1.699 + fd = hashp->fp;
1.700 + size = hashp->BSIZE;
1.701 +
1.702 + if ((fd == -1) || !is_disk) {
1.703 + PAGE_INIT(p);
1.704 + return (0);
1.705 + }
1.706 + if (is_bucket)
1.707 + page = BUCKET_TO_PAGE(bucket);
1.708 + else
1.709 + page = OADDR_TO_PAGE(bucket);
1.710 + if ((MY_LSEEK(fd, (off_t)page << hashp->BSHIFT, SEEK_SET) == -1) ||
1.711 + ((rsize = read(fd, p, size)) == -1))
1.712 + return (-1);
1.713 +
1.714 + bp = (uint16 *)p;
1.715 + if (!rsize)
1.716 + bp[0] = 0; /* We hit the EOF, so initialize a new page */
1.717 + else
1.718 + if ((unsigned)rsize != size) {
1.719 + errno = EFTYPE;
1.720 + return (-1);
1.721 + }
1.722 +
1.723 + if (!is_bitmap && !bp[0]) {
1.724 + PAGE_INIT(p);
1.725 + } else {
1.726 +
1.727 +#ifdef DEBUG
1.728 + if(BYTE_ORDER == LITTLE_ENDIAN)
1.729 + {
1.730 + int is_little_endian;
1.731 + is_little_endian = BYTE_ORDER;
1.732 + }
1.733 + else if(BYTE_ORDER == BIG_ENDIAN)
1.734 + {
1.735 + int is_big_endian;
1.736 + is_big_endian = BYTE_ORDER;
1.737 + }
1.738 + else
1.739 + {
1.740 + assert(0);
1.741 + }
1.742 +#endif
1.743 +
1.744 + if (hashp->LORDER != BYTE_ORDER) {
1.745 + register int i, max;
1.746 +
1.747 + if (is_bitmap) {
1.748 + max = hashp->BSIZE >> 2; /* divide by 4 */
1.749 + for (i = 0; i < max; i++)
1.750 + M_32_SWAP(((int *)p)[i]);
1.751 + } else {
1.752 + M_16_SWAP(bp[0]);
1.753 + max = bp[0] + 2;
1.754 +
1.755 + /* bound the size of max by
1.756 + * the maximum number of entries
1.757 + * in the array
1.758 + */
1.759 + if((unsigned)max > (size / sizeof(uint16)))
1.760 + return(DATABASE_CORRUPTED_ERROR);
1.761 +
1.762 + /* do the byte order swap
1.763 + */
1.764 + for (i = 1; i <= max; i++)
1.765 + M_16_SWAP(bp[i]);
1.766 + }
1.767 + }
1.768 +
1.769 + /* check the validity of the page here
1.770 + * (after doing byte order swaping if necessary)
1.771 + */
1.772 + if(!is_bitmap && bp[0] != 0)
1.773 + {
1.774 + uint16 num_keys = bp[0];
1.775 + uint16 offset;
1.776 + uint16 i;
1.777 +
1.778 + /* bp[0] is supposed to be the number of
1.779 + * entries currently in the page. If
1.780 + * bp[0] is too large (larger than the whole
1.781 + * page) then the page is corrupted
1.782 + */
1.783 + if(bp[0] > (size / sizeof(uint16)))
1.784 + return(DATABASE_CORRUPTED_ERROR);
1.785 +
1.786 + /* bound free space */
1.787 + if(FREESPACE(bp) > size)
1.788 + return(DATABASE_CORRUPTED_ERROR);
1.789 +
1.790 + /* check each key and data offset to make
1.791 + * sure they are all within bounds they
1.792 + * should all be less than the previous
1.793 + * offset as well.
1.794 + */
1.795 + offset = size;
1.796 + for(i=1 ; i <= num_keys; i+=2)
1.797 + {
1.798 + /* ignore overflow pages etc. */
1.799 + if(bp[i+1] >= REAL_KEY)
1.800 + {
1.801 +
1.802 + if(bp[i] > offset || bp[i+1] > bp[i])
1.803 + return(DATABASE_CORRUPTED_ERROR);
1.804 +
1.805 + offset = bp[i+1];
1.806 + }
1.807 + else
1.808 + {
1.809 + /* there are no other valid keys after
1.810 + * seeing a non REAL_KEY
1.811 + */
1.812 + break;
1.813 + }
1.814 + }
1.815 + }
1.816 + }
1.817 + return (0);
1.818 +}
1.819 +
1.820 +/*
1.821 + * Write page p to disk
1.822 + *
1.823 + * Returns:
1.824 + * 0 ==> OK
1.825 + * -1 ==>failure
1.826 + */
1.827 +extern int
1.828 +__put_page(HTAB *hashp, char *p, uint32 bucket, int is_bucket, int is_bitmap)
1.829 +{
1.830 + register int fd, page;
1.831 + size_t size;
1.832 + int wsize;
1.833 + off_t offset;
1.834 +
1.835 + size = hashp->BSIZE;
1.836 + if ((hashp->fp == -1) && open_temp(hashp))
1.837 + return (-1);
1.838 + fd = hashp->fp;
1.839 +
1.840 + if (hashp->LORDER != BYTE_ORDER) {
1.841 + register int i;
1.842 + register int max;
1.843 +
1.844 + if (is_bitmap) {
1.845 + max = hashp->BSIZE >> 2; /* divide by 4 */
1.846 + for (i = 0; i < max; i++)
1.847 + M_32_SWAP(((int *)p)[i]);
1.848 + } else {
1.849 + max = ((uint16 *)p)[0] + 2;
1.850 +
1.851 + /* bound the size of max by
1.852 + * the maximum number of entries
1.853 + * in the array
1.854 + */
1.855 + if((unsigned)max > (size / sizeof(uint16)))
1.856 + return(DATABASE_CORRUPTED_ERROR);
1.857 +
1.858 + for (i = 0; i <= max; i++)
1.859 + M_16_SWAP(((uint16 *)p)[i]);
1.860 +
1.861 + }
1.862 + }
1.863 +
1.864 + if (is_bucket)
1.865 + page = BUCKET_TO_PAGE(bucket);
1.866 + else
1.867 + page = OADDR_TO_PAGE(bucket);
1.868 + offset = (off_t)page << hashp->BSHIFT;
1.869 + if ((MY_LSEEK(fd, offset, SEEK_SET) == -1) ||
1.870 + ((wsize = write(fd, p, size)) == -1))
1.871 + /* Errno is set */
1.872 + return (-1);
1.873 + if ((unsigned)wsize != size) {
1.874 + errno = EFTYPE;
1.875 + return (-1);
1.876 + }
1.877 +#if defined(_WIN32) || defined(_WINDOWS)
1.878 + if (offset + size > hashp->file_size) {
1.879 + hashp->updateEOF = 1;
1.880 + }
1.881 +#endif
1.882 + /* put the page back the way it was so that it isn't byteswapped
1.883 + * if it remains in memory - LJM
1.884 + */
1.885 + if (hashp->LORDER != BYTE_ORDER) {
1.886 + register int i;
1.887 + register int max;
1.888 +
1.889 + if (is_bitmap) {
1.890 + max = hashp->BSIZE >> 2; /* divide by 4 */
1.891 + for (i = 0; i < max; i++)
1.892 + M_32_SWAP(((int *)p)[i]);
1.893 + } else {
1.894 + uint16 *bp = (uint16 *)p;
1.895 +
1.896 + M_16_SWAP(bp[0]);
1.897 + max = bp[0] + 2;
1.898 +
1.899 + /* no need to bound the size if max again
1.900 + * since it was done already above
1.901 + */
1.902 +
1.903 + /* do the byte order re-swap
1.904 + */
1.905 + for (i = 1; i <= max; i++)
1.906 + M_16_SWAP(bp[i]);
1.907 + }
1.908 + }
1.909 +
1.910 + return (0);
1.911 +}
1.912 +
1.913 +#define BYTE_MASK ((1 << INT_BYTE_SHIFT) -1)
1.914 +/*
1.915 + * Initialize a new bitmap page. Bitmap pages are left in memory
1.916 + * once they are read in.
1.917 + */
1.918 +extern int
1.919 +__ibitmap(HTAB *hashp, int pnum, int nbits, int ndx)
1.920 +{
1.921 + uint32 *ip;
1.922 + size_t clearbytes, clearints;
1.923 +
1.924 + if ((ip = (uint32 *)malloc((size_t)hashp->BSIZE)) == NULL)
1.925 + return (1);
1.926 + hashp->nmaps++;
1.927 + clearints = ((nbits - 1) >> INT_BYTE_SHIFT) + 1;
1.928 + clearbytes = clearints << INT_TO_BYTE;
1.929 + (void)memset((char *)ip, 0, clearbytes);
1.930 + (void)memset(((char *)ip) + clearbytes, 0xFF,
1.931 + hashp->BSIZE - clearbytes);
1.932 + ip[clearints - 1] = ALL_SET << (nbits & BYTE_MASK);
1.933 + SETBIT(ip, 0);
1.934 + hashp->BITMAPS[ndx] = (uint16)pnum;
1.935 + hashp->mapp[ndx] = ip;
1.936 + return (0);
1.937 +}
1.938 +
1.939 +static uint32
1.940 +first_free(uint32 map)
1.941 +{
1.942 + register uint32 i, mask;
1.943 +
1.944 + mask = 0x1;
1.945 + for (i = 0; i < BITS_PER_MAP; i++) {
1.946 + if (!(mask & map))
1.947 + return (i);
1.948 + mask = mask << 1;
1.949 + }
1.950 + return (i);
1.951 +}
1.952 +
1.953 +static uint16
1.954 +overflow_page(HTAB *hashp)
1.955 +{
1.956 + register uint32 *freep=NULL;
1.957 + register int max_free, offset, splitnum;
1.958 + uint16 addr;
1.959 + uint32 i;
1.960 + int bit, first_page, free_bit, free_page, in_use_bits, j;
1.961 +#ifdef DEBUG2
1.962 + int tmp1, tmp2;
1.963 +#endif
1.964 + splitnum = hashp->OVFL_POINT;
1.965 + max_free = hashp->SPARES[splitnum];
1.966 +
1.967 + free_page = (max_free - 1) >> (hashp->BSHIFT + BYTE_SHIFT);
1.968 + free_bit = (max_free - 1) & ((hashp->BSIZE << BYTE_SHIFT) - 1);
1.969 +
1.970 + /* Look through all the free maps to find the first free block */
1.971 + first_page = hashp->LAST_FREED >>(hashp->BSHIFT + BYTE_SHIFT);
1.972 + for ( i = first_page; i <= (unsigned)free_page; i++ ) {
1.973 + if (!(freep = (uint32 *)hashp->mapp[i]) &&
1.974 + !(freep = fetch_bitmap(hashp, i)))
1.975 + return (0);
1.976 + if (i == (unsigned)free_page)
1.977 + in_use_bits = free_bit;
1.978 + else
1.979 + in_use_bits = (hashp->BSIZE << BYTE_SHIFT) - 1;
1.980 +
1.981 + if (i == (unsigned)first_page) {
1.982 + bit = hashp->LAST_FREED &
1.983 + ((hashp->BSIZE << BYTE_SHIFT) - 1);
1.984 + j = bit / BITS_PER_MAP;
1.985 + bit = bit & ~(BITS_PER_MAP - 1);
1.986 + } else {
1.987 + bit = 0;
1.988 + j = 0;
1.989 + }
1.990 + for (; bit <= in_use_bits; j++, bit += BITS_PER_MAP)
1.991 + if (freep[j] != ALL_SET)
1.992 + goto found;
1.993 + }
1.994 +
1.995 + /* No Free Page Found */
1.996 + hashp->LAST_FREED = hashp->SPARES[splitnum];
1.997 + hashp->SPARES[splitnum]++;
1.998 + offset = hashp->SPARES[splitnum] -
1.999 + (splitnum ? hashp->SPARES[splitnum - 1] : 0);
1.1000 +
1.1001 +#define OVMSG "HASH: Out of overflow pages. Increase page size\n"
1.1002 + if (offset > SPLITMASK) {
1.1003 + if (++splitnum >= NCACHED) {
1.1004 +#ifndef macintosh
1.1005 + (void)write(STDERR_FILENO, OVMSG, sizeof(OVMSG) - 1);
1.1006 +#endif
1.1007 + return (0);
1.1008 + }
1.1009 + hashp->OVFL_POINT = splitnum;
1.1010 + hashp->SPARES[splitnum] = hashp->SPARES[splitnum-1];
1.1011 + hashp->SPARES[splitnum-1]--;
1.1012 + offset = 1;
1.1013 + }
1.1014 +
1.1015 + /* Check if we need to allocate a new bitmap page */
1.1016 + if (free_bit == (hashp->BSIZE << BYTE_SHIFT) - 1) {
1.1017 + free_page++;
1.1018 + if (free_page >= NCACHED) {
1.1019 +#ifndef macintosh
1.1020 + (void)write(STDERR_FILENO, OVMSG, sizeof(OVMSG) - 1);
1.1021 +#endif
1.1022 + return (0);
1.1023 + }
1.1024 + /*
1.1025 + * This is tricky. The 1 indicates that you want the new page
1.1026 + * allocated with 1 clear bit. Actually, you are going to
1.1027 + * allocate 2 pages from this map. The first is going to be
1.1028 + * the map page, the second is the overflow page we were
1.1029 + * looking for. The init_bitmap routine automatically, sets
1.1030 + * the first bit of itself to indicate that the bitmap itself
1.1031 + * is in use. We would explicitly set the second bit, but
1.1032 + * don't have to if we tell init_bitmap not to leave it clear
1.1033 + * in the first place.
1.1034 + */
1.1035 + if (__ibitmap(hashp,
1.1036 + (int)OADDR_OF(splitnum, offset), 1, free_page))
1.1037 + return (0);
1.1038 + hashp->SPARES[splitnum]++;
1.1039 +#ifdef DEBUG2
1.1040 + free_bit = 2;
1.1041 +#endif
1.1042 + offset++;
1.1043 + if (offset > SPLITMASK) {
1.1044 + if (++splitnum >= NCACHED) {
1.1045 +#ifndef macintosh
1.1046 + (void)write(STDERR_FILENO, OVMSG,
1.1047 + sizeof(OVMSG) - 1);
1.1048 +#endif
1.1049 + return (0);
1.1050 + }
1.1051 + hashp->OVFL_POINT = splitnum;
1.1052 + hashp->SPARES[splitnum] = hashp->SPARES[splitnum-1];
1.1053 + hashp->SPARES[splitnum-1]--;
1.1054 + offset = 0;
1.1055 + }
1.1056 + } else {
1.1057 + /*
1.1058 + * Free_bit addresses the last used bit. Bump it to address
1.1059 + * the first available bit.
1.1060 + */
1.1061 + free_bit++;
1.1062 + SETBIT(freep, free_bit);
1.1063 + }
1.1064 +
1.1065 + /* Calculate address of the new overflow page */
1.1066 + addr = OADDR_OF(splitnum, offset);
1.1067 +#ifdef DEBUG2
1.1068 + (void)fprintf(stderr, "OVERFLOW_PAGE: ADDR: %d BIT: %d PAGE %d\n",
1.1069 + addr, free_bit, free_page);
1.1070 +#endif
1.1071 + return (addr);
1.1072 +
1.1073 +found:
1.1074 + bit = bit + first_free(freep[j]);
1.1075 + SETBIT(freep, bit);
1.1076 +#ifdef DEBUG2
1.1077 + tmp1 = bit;
1.1078 + tmp2 = i;
1.1079 +#endif
1.1080 + /*
1.1081 + * Bits are addressed starting with 0, but overflow pages are addressed
1.1082 + * beginning at 1. Bit is a bit addressnumber, so we need to increment
1.1083 + * it to convert it to a page number.
1.1084 + */
1.1085 + bit = 1 + bit + (i * (hashp->BSIZE << BYTE_SHIFT));
1.1086 + if (bit >= hashp->LAST_FREED)
1.1087 + hashp->LAST_FREED = bit - 1;
1.1088 +
1.1089 + /* Calculate the split number for this page */
1.1090 + for (i = 0; (i < (unsigned)splitnum) && (bit > hashp->SPARES[i]); i++) {}
1.1091 + offset = (i ? bit - hashp->SPARES[i - 1] : bit);
1.1092 + if (offset >= SPLITMASK)
1.1093 + return (0); /* Out of overflow pages */
1.1094 + addr = OADDR_OF(i, offset);
1.1095 +#ifdef DEBUG2
1.1096 + (void)fprintf(stderr, "OVERFLOW_PAGE: ADDR: %d BIT: %d PAGE %d\n",
1.1097 + addr, tmp1, tmp2);
1.1098 +#endif
1.1099 +
1.1100 + /* Allocate and return the overflow page */
1.1101 + return (addr);
1.1102 +}
1.1103 +
1.1104 +/*
1.1105 + * Mark this overflow page as free.
1.1106 + */
1.1107 +extern void
1.1108 +__free_ovflpage(HTAB *hashp, BUFHEAD *obufp)
1.1109 +{
1.1110 + uint16 addr;
1.1111 + uint32 *freep;
1.1112 + uint32 bit_address, free_page, free_bit;
1.1113 + uint16 ndx;
1.1114 +
1.1115 + if(!obufp || !obufp->addr)
1.1116 + return;
1.1117 +
1.1118 + addr = obufp->addr;
1.1119 +#ifdef DEBUG1
1.1120 + (void)fprintf(stderr, "Freeing %d\n", addr);
1.1121 +#endif
1.1122 + ndx = (((uint16)addr) >> SPLITSHIFT);
1.1123 + bit_address =
1.1124 + (ndx ? hashp->SPARES[ndx - 1] : 0) + (addr & SPLITMASK) - 1;
1.1125 + if (bit_address < (uint32)hashp->LAST_FREED)
1.1126 + hashp->LAST_FREED = bit_address;
1.1127 + free_page = (bit_address >> (hashp->BSHIFT + BYTE_SHIFT));
1.1128 + free_bit = bit_address & ((hashp->BSIZE << BYTE_SHIFT) - 1);
1.1129 +
1.1130 + if (!(freep = hashp->mapp[free_page]))
1.1131 + freep = fetch_bitmap(hashp, free_page);
1.1132 +
1.1133 +#ifdef DEBUG
1.1134 + /*
1.1135 + * This had better never happen. It means we tried to read a bitmap
1.1136 + * that has already had overflow pages allocated off it, and we
1.1137 + * failed to read it from the file.
1.1138 + */
1.1139 + if (!freep)
1.1140 + {
1.1141 + assert(0);
1.1142 + return;
1.1143 + }
1.1144 +#endif
1.1145 + CLRBIT(freep, free_bit);
1.1146 +#ifdef DEBUG2
1.1147 + (void)fprintf(stderr, "FREE_OVFLPAGE: ADDR: %d BIT: %d PAGE %d\n",
1.1148 + obufp->addr, free_bit, free_page);
1.1149 +#endif
1.1150 + __reclaim_buf(hashp, obufp);
1.1151 +}
1.1152 +
1.1153 +/*
1.1154 + * Returns:
1.1155 + * 0 success
1.1156 + * -1 failure
1.1157 + */
1.1158 +static int
1.1159 +open_temp(HTAB *hashp)
1.1160 +{
1.1161 +#ifdef XP_OS2
1.1162 + hashp->fp = mkstemp(NULL);
1.1163 +#else
1.1164 +#if !defined(_WIN32) && !defined(_WINDOWS) && !defined(macintosh)
1.1165 + sigset_t set, oset;
1.1166 +#endif
1.1167 +#if !defined(macintosh)
1.1168 + char * tmpdir;
1.1169 + size_t len;
1.1170 + char last;
1.1171 +#endif
1.1172 + static const char namestr[] = "/_hashXXXXXX";
1.1173 + char filename[1024];
1.1174 +
1.1175 +#if !defined(_WIN32) && !defined(_WINDOWS) && !defined(macintosh)
1.1176 + /* Block signals; make sure file goes away at process exit. */
1.1177 + (void)sigfillset(&set);
1.1178 + (void)sigprocmask(SIG_BLOCK, &set, &oset);
1.1179 +#endif
1.1180 +
1.1181 + filename[0] = 0;
1.1182 +#if defined(macintosh)
1.1183 + strcat(filename, namestr + 1);
1.1184 +#else
1.1185 + tmpdir = getenv("TMP");
1.1186 + if (!tmpdir)
1.1187 + tmpdir = getenv("TMPDIR");
1.1188 + if (!tmpdir)
1.1189 + tmpdir = getenv("TEMP");
1.1190 + if (!tmpdir)
1.1191 + tmpdir = ".";
1.1192 + len = strlen(tmpdir);
1.1193 + if (len && len < (sizeof filename - sizeof namestr)) {
1.1194 + strcpy(filename, tmpdir);
1.1195 + }
1.1196 + len = strlen(filename);
1.1197 + last = tmpdir[len - 1];
1.1198 + strcat(filename, (last == '/' || last == '\\') ? namestr + 1 : namestr);
1.1199 +#endif
1.1200 +
1.1201 +#if defined(_WIN32) || defined(_WINDOWS)
1.1202 + if ((hashp->fp = mkstempflags(filename, _O_BINARY|_O_TEMPORARY)) != -1) {
1.1203 + if (hashp->filename) {
1.1204 + free(hashp->filename);
1.1205 + }
1.1206 + hashp->filename = strdup(filename);
1.1207 + hashp->is_temp = 1;
1.1208 + }
1.1209 +#else
1.1210 + if ((hashp->fp = mkstemp(filename)) != -1) {
1.1211 + (void)unlink(filename);
1.1212 +#if !defined(macintosh)
1.1213 + (void)fcntl(hashp->fp, F_SETFD, 1);
1.1214 +#endif
1.1215 + }
1.1216 +#endif
1.1217 +
1.1218 +#if !defined(_WIN32) && !defined(_WINDOWS) && !defined(macintosh)
1.1219 + (void)sigprocmask(SIG_SETMASK, &oset, (sigset_t *)NULL);
1.1220 +#endif
1.1221 +#endif /* !OS2 */
1.1222 + return (hashp->fp != -1 ? 0 : -1);
1.1223 +}
1.1224 +
1.1225 +/*
1.1226 + * We have to know that the key will fit, but the last entry on the page is
1.1227 + * an overflow pair, so we need to shift things.
1.1228 + */
1.1229 +static void
1.1230 +squeeze_key(uint16 *sp, const DBT * key, const DBT * val)
1.1231 +{
1.1232 + register char *p;
1.1233 + uint16 free_space, n, off, pageno;
1.1234 +
1.1235 + p = (char *)sp;
1.1236 + n = sp[0];
1.1237 + free_space = FREESPACE(sp);
1.1238 + off = OFFSET(sp);
1.1239 +
1.1240 + pageno = sp[n - 1];
1.1241 + off -= key->size;
1.1242 + sp[n - 1] = off;
1.1243 + memmove(p + off, key->data, key->size);
1.1244 + off -= val->size;
1.1245 + sp[n] = off;
1.1246 + memmove(p + off, val->data, val->size);
1.1247 + sp[0] = n + 2;
1.1248 + sp[n + 1] = pageno;
1.1249 + sp[n + 2] = OVFLPAGE;
1.1250 + FREESPACE(sp) = free_space - PAIRSIZE(key, val);
1.1251 + OFFSET(sp) = off;
1.1252 +}
1.1253 +
1.1254 +static uint32 *
1.1255 +fetch_bitmap(HTAB *hashp, uint32 ndx)
1.1256 +{
1.1257 + if (ndx >= (unsigned)hashp->nmaps)
1.1258 + return (NULL);
1.1259 + if ((hashp->mapp[ndx] = (uint32 *)malloc((size_t)hashp->BSIZE)) == NULL)
1.1260 + return (NULL);
1.1261 + if (__get_page(hashp,
1.1262 + (char *)hashp->mapp[ndx], hashp->BITMAPS[ndx], 0, 1, 1)) {
1.1263 + free(hashp->mapp[ndx]);
1.1264 + hashp->mapp[ndx] = NULL; /* NEW: 9-11-95 */
1.1265 + return (NULL);
1.1266 + }
1.1267 + return (hashp->mapp[ndx]);
1.1268 +}
1.1269 +
1.1270 +#ifdef DEBUG4
1.1271 +int
1.1272 +print_chain(int addr)
1.1273 +{
1.1274 + BUFHEAD *bufp;
1.1275 + short *bp, oaddr;
1.1276 +
1.1277 + (void)fprintf(stderr, "%d ", addr);
1.1278 + bufp = __get_buf(hashp, addr, NULL, 0);
1.1279 + bp = (short *)bufp->page;
1.1280 + while (bp[0] && ((bp[bp[0]] == OVFLPAGE) ||
1.1281 + ((bp[0] > 2) && bp[2] < REAL_KEY))) {
1.1282 + oaddr = bp[bp[0] - 1];
1.1283 + (void)fprintf(stderr, "%d ", (int)oaddr);
1.1284 + bufp = __get_buf(hashp, (int)oaddr, bufp, 0);
1.1285 + bp = (short *)bufp->page;
1.1286 + }
1.1287 + (void)fprintf(stderr, "\n");
1.1288 +}
1.1289 +#endif
