home *** CD-ROM | disk | FTP | other *** search
/ Geek Gadgets 1 / ADE-1.bin / ade-dist / ixemul-45.0-src.tgz / tar.out / contrib / ixemul / db / hash / hash_page.c < prev    next >
C/C++ Source or Header  |  1996-09-28  |  24KB  |  951 lines
  1. /*    $NetBSD: hash_page.c,v 1.7 1995/02/27 13:22:34 cgd Exp $    */
  2.  
  3. /*-
  4.  * Copyright (c) 1990, 1993, 1994
  5.  *    The Regents of the University of California.  All rights reserved.
  6.  *
  7.  * This code is derived from software contributed to Berkeley by
  8.  * Margo Seltzer.
  9.  *
  10.  * Redistribution and use in source and binary forms, with or without
  11.  * modification, are permitted provided that the following conditions
  12.  * are met:
  13.  * 1. Redistributions of source code must retain the above copyright
  14.  *    notice, this list of conditions and the following disclaimer.
  15.  * 2. Redistributions in binary form must reproduce the above copyright
  16.  *    notice, this list of conditions and the following disclaimer in the
  17.  *    documentation and/or other materials provided with the distribution.
  18.  * 3. All advertising materials mentioning features or use of this software
  19.  *    must display the following acknowledgement:
  20.  *    This product includes software developed by the University of
  21.  *    California, Berkeley and its contributors.
  22.  * 4. Neither the name of the University nor the names of its contributors
  23.  *    may be used to endorse or promote products derived from this software
  24.  *    without specific prior written permission.
  25.  *
  26.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  27.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  28.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  29.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  30.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  31.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  32.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  33.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  34.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  35.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  36.  * SUCH DAMAGE.
  37.  */
  38.  
  39. #if defined(LIBC_SCCS) && !defined(lint)
  40. #if 0
  41. static char sccsid[] = "@(#)hash_page.c    8.6 (Berkeley) 6/16/94";
  42. #else
  43. static char rcsid[] = "$NetBSD: hash_page.c,v 1.7 1995/02/27 13:22:34 cgd Exp $";
  44. #endif
  45. #endif /* LIBC_SCCS and not lint */
  46.  
  47. /*
  48.  * PACKAGE:  hashing
  49.  *
  50.  * DESCRIPTION:
  51.  *    Page manipulation for hashing package.
  52.  *
  53.  * ROUTINES:
  54.  *
  55.  * External
  56.  *    __get_page
  57.  *    __add_ovflpage
  58.  * Internal
  59.  *    overflow_page
  60.  *    open_temp
  61.  */
  62.  
  63. #include <sys/types.h>
  64.  
  65. #include <errno.h>
  66. #include <fcntl.h>
  67. #include <signal.h>
  68. #include <stdio.h>
  69. #include <stdlib.h>
  70. #include <string.h>
  71. #include <unistd.h>
  72. #ifdef DEBUG
  73. #include <assert.h>
  74. #endif
  75.  
  76. #include <db.h>
  77. #include "hash.h"
  78. #include "page.h"
  79. #include "extern.h"
  80.  
  81. static u_int32_t    *fetch_bitmap __P((HTAB *, int));
  82. static u_int32_t     first_free __P((u_int32_t));
  83. static int     open_temp __P((HTAB *));
  84. static u_int16_t     overflow_page __P((HTAB *));
  85. static void     putpair __P((char *, const DBT *, const DBT *));
  86. static void     squeeze_key __P((u_int16_t *, const DBT *, const DBT *));
  87. static int     ugly_split
  88.             __P((HTAB *, u_int32_t, BUFHEAD *, BUFHEAD *, int, int));
  89.  
  90. #define    PAGE_INIT(P) { \
  91.     ((u_int16_t *)(P))[0] = 0; \
  92.     ((u_int16_t *)(P))[1] = hashp->BSIZE - 3 * sizeof(u_int16_t); \
  93.     ((u_int16_t *)(P))[2] = hashp->BSIZE; \
  94. }
  95.  
  96. /*
  97.  * This is called AFTER we have verified that there is room on the page for
  98.  * the pair (PAIRFITS has returned true) so we go right ahead and start moving
  99.  * stuff on.
  100.  */
  101. static void
  102. putpair(p, key, val)
  103.     char *p;
  104.     const DBT *key, *val;
  105. {
  106.     register u_int16_t *bp, n, off;
  107.  
  108.     bp = (u_int16_t *)p;
  109.  
  110.     /* Enter the key first. */
  111.     n = bp[0];
  112.  
  113.     off = OFFSET(bp) - key->size;
  114.     memmove(p + off, key->data, key->size);
  115.     bp[++n] = off;
  116.  
  117.     /* Now the data. */
  118.     off -= val->size;
  119.     memmove(p + off, val->data, val->size);
  120.     bp[++n] = off;
  121.  
  122.     /* Adjust page info. */
  123.     bp[0] = n;
  124.     bp[n + 1] = off - ((n + 3) * sizeof(u_int16_t));
  125.     bp[n + 2] = off;
  126. }
  127.  
  128. /*
  129.  * Returns:
  130.  *     0 OK
  131.  *    -1 error
  132.  */
  133. extern int
  134. __delpair(hashp, bufp, ndx)
  135.     HTAB *hashp;
  136.     BUFHEAD *bufp;
  137.     register int ndx;
  138. {
  139.     register u_int16_t *bp, newoff;
  140.     register int n;
  141.     u_int16_t pairlen;
  142.  
  143.     bp = (u_int16_t *)bufp->page;
  144.     n = bp[0];
  145.  
  146.     if (bp[ndx + 1] < REAL_KEY)
  147.         return (__big_delete(hashp, bufp));
  148.     if (ndx != 1)
  149.         newoff = bp[ndx - 1];
  150.     else
  151.         newoff = hashp->BSIZE;
  152.     pairlen = newoff - bp[ndx + 1];
  153.  
  154.     if (ndx != (n - 1)) {
  155.         /* Hard Case -- need to shuffle keys */
  156.         register int i;
  157.         register char *src = bufp->page + (int)OFFSET(bp);
  158.         register char *dst = src + (int)pairlen;
  159.         memmove(dst, src, bp[ndx + 1] - OFFSET(bp));
  160.  
  161.         /* Now adjust the pointers */
  162.         for (i = ndx + 2; i <= n; i += 2) {
  163.             if (bp[i + 1] == OVFLPAGE) {
  164.                 bp[i - 2] = bp[i];
  165.                 bp[i - 1] = bp[i + 1];
  166.             } else {
  167.                 bp[i - 2] = bp[i] + pairlen;
  168.                 bp[i - 1] = bp[i + 1] + pairlen;
  169.             }
  170.         }
  171.     }
  172.     /* Finally adjust the page data */
  173.     bp[n] = OFFSET(bp) + pairlen;
  174.     bp[n - 1] = bp[n + 1] + pairlen + 2 * sizeof(u_int16_t);
  175.     bp[0] = n - 2;
  176.     hashp->NKEYS--;
  177.  
  178.     bufp->flags |= BUF_MOD;
  179.     return (0);
  180. }
  181. /*
  182.  * Returns:
  183.  *     0 ==> OK
  184.  *    -1 ==> Error
  185.  */
  186. extern int
  187. __split_page(hashp, obucket, nbucket)
  188.     HTAB *hashp;
  189.     u_int32_t obucket, nbucket;
  190. {
  191.     register BUFHEAD *new_bufp, *old_bufp;
  192.     register u_int16_t *ino;
  193.     register char *np;
  194.     DBT key, val;
  195.     int n, ndx, retval;
  196.     u_int16_t copyto, diff, off, moved;
  197.     char *op;
  198.  
  199.     copyto = (u_int16_t)hashp->BSIZE;
  200.     off = (u_int16_t)hashp->BSIZE;
  201.     old_bufp = __get_buf(hashp, obucket, NULL, 0);
  202.     if (old_bufp == NULL)
  203.         return (-1);
  204.     new_bufp = __get_buf(hashp, nbucket, NULL, 0);
  205.     if (new_bufp == NULL)
  206.         return (-1);
  207.  
  208.     old_bufp->flags |= (BUF_MOD | BUF_PIN);
  209.     new_bufp->flags |= (BUF_MOD | BUF_PIN);
  210.  
  211.     ino = (u_int16_t *)(op = old_bufp->page);
  212.     np = new_bufp->page;
  213.  
  214.     moved = 0;
  215.  
  216.     for (n = 1, ndx = 1; n < ino[0]; n += 2) {
  217.         if (ino[n + 1] < REAL_KEY) {
  218.             retval = ugly_split(hashp, obucket, old_bufp, new_bufp,
  219.                 (int)copyto, (int)moved);
  220.             old_bufp->flags &= ~BUF_PIN;
  221.             new_bufp->flags &= ~BUF_PIN;
  222.             return (retval);
  223.  
  224.         }
  225.         key.data = (u_char *)op + ino[n];
  226.         key.size = off - ino[n];
  227.  
  228.         if (__call_hash(hashp, key.data, key.size) == obucket) {
  229.             /* Don't switch page */
  230.             diff = copyto - off;
  231.             if (diff) {
  232.                 copyto = ino[n + 1] + diff;
  233.                 memmove(op + copyto, op + ino[n + 1],
  234.                     off - ino[n + 1]);
  235.                 ino[ndx] = copyto + ino[n] - ino[n + 1];
  236.                 ino[ndx + 1] = copyto;
  237.             } else
  238.                 copyto = ino[n + 1];
  239.             ndx += 2;
  240.         } else {
  241.             /* Switch page */
  242.             val.data = (u_char *)op + ino[n + 1];
  243.             val.size = ino[n] - ino[n + 1];
  244.             putpair(np, &key, &val);
  245.             moved += 2;
  246.         }
  247.  
  248.         off = ino[n + 1];
  249.     }
  250.  
  251.     /* Now clean up the page */
  252.     ino[0] -= moved;
  253.     FREESPACE(ino) = copyto - sizeof(u_int16_t) * (ino[0] + 3);
  254.     OFFSET(ino) = copyto;
  255.  
  256. #ifdef DEBUG3
  257.     (void)fprintf(stderr, "split %d/%d\n",
  258.         ((u_int16_t *)np)[0] / 2,
  259.         ((u_int16_t *)op)[0] / 2);
  260. #endif
  261.     /* unpin both pages */
  262.     old_bufp->flags &= ~BUF_PIN;
  263.     new_bufp->flags &= ~BUF_PIN;
  264.     return (0);
  265. }
  266.  
  267. /*
  268.  * Called when we encounter an overflow or big key/data page during split
  269.  * handling.  This is special cased since we have to begin checking whether
  270.  * the key/data pairs fit on their respective pages and because we may need
  271.  * overflow pages for both the old and new pages.
  272.  *
  273.  * The first page might be a page with regular key/data pairs in which case
  274.  * we have a regular overflow condition and just need to go on to the next
  275.  * page or it might be a big key/data pair in which case we need to fix the
  276.  * big key/data pair.
  277.  *
  278.  * Returns:
  279.  *     0 ==> success
  280.  *    -1 ==> failure
  281.  */
  282. static int
  283. ugly_split(hashp, obucket, old_bufp, new_bufp, copyto, moved)
  284.     HTAB *hashp;
  285.     u_int32_t obucket;    /* Same as __split_page. */
  286.     BUFHEAD *old_bufp, *new_bufp;
  287.     int copyto;    /* First byte on page which contains key/data values. */
  288.     int moved;    /* Number of pairs moved to new page. */
  289. {
  290.     register BUFHEAD *bufp;    /* Buffer header for ino */
  291.     register u_int16_t *ino;    /* Page keys come off of */
  292.     register u_int16_t *np;    /* New page */
  293.     register u_int16_t *op;    /* Page keys go on to if they aren't moving */
  294.  
  295.     BUFHEAD *last_bfp;    /* Last buf header OVFL needing to be freed */
  296.     DBT key, val;
  297.     SPLIT_RETURN ret;
  298.     u_int16_t n, off, ov_addr, scopyto;
  299.     char *cino;        /* Character value of ino */
  300.  
  301.     bufp = old_bufp;
  302.     ino = (u_int16_t *)old_bufp->page;
  303.     np = (u_int16_t *)new_bufp->page;
  304.     op = (u_int16_t *)old_bufp->page;
  305.     last_bfp = NULL;
  306.     scopyto = (u_int16_t)copyto;    /* ANSI */
  307.  
  308.     n = ino[0] - 1;
  309.     while (n < ino[0]) {
  310.         if (ino[2] < REAL_KEY && ino[2] != OVFLPAGE) {
  311.             if (__big_split(hashp, old_bufp,
  312.                 new_bufp, bufp, bufp->addr, obucket, &ret))
  313.                 return (-1);
  314.             old_bufp = ret.oldp;
  315.             if (!old_bufp)
  316.                 return (-1);
  317.             op = (u_int16_t *)old_bufp->page;
  318.             new_bufp = ret.newp;
  319.             if (!new_bufp)
  320.                 return (-1);
  321.             np = (u_int16_t *)new_bufp->page;
  322.             bufp = ret.nextp;
  323.             if (!bufp)
  324.                 return (0);
  325.             cino = (char *)bufp->page;
  326.             ino = (u_int16_t *)cino;
  327.             last_bfp = ret.nextp;
  328.         } else if (ino[n + 1] == OVFLPAGE) {
  329.             ov_addr = ino[n];
  330.             /*
  331.              * Fix up the old page -- the extra 2 are the fields
  332.              * which contained the overflow information.
  333.              */
  334.             ino[0] -= (moved + 2);
  335.             FREESPACE(ino) =
  336.                 scopyto - sizeof(u_int16_t) * (ino[0] + 3);
  337.             OFFSET(ino) = scopyto;
  338.  
  339.             bufp = __get_buf(hashp, ov_addr, bufp, 0);
  340.             if (!bufp)
  341.                 return (-1);
  342.  
  343.             ino = (u_int16_t *)bufp->page;
  344.             n = 1;
  345.             scopyto = hashp->BSIZE;
  346.             moved = 0;
  347.  
  348.             if (last_bfp)
  349.                 __free_ovflpage(hashp, last_bfp);
  350.             last_bfp = bufp;
  351.         }
  352.         /* Move regular sized pairs of there are any */
  353.         off = hashp->BSIZE;
  354.         for (n = 1; (n < ino[0]) && (ino[n + 1] >= REAL_KEY); n += 2) {
  355.             cino = (char *)ino;
  356.             key.data = (u_char *)cino + ino[n];
  357.             key.size = off - ino[n];
  358.             val.data = (u_char *)cino + ino[n + 1];
  359.             val.size = ino[n] - ino[n + 1];
  360.             off = ino[n + 1];
  361.  
  362.             if (__call_hash(hashp, key.data, key.size) == obucket) {
  363.                 /* Keep on old page */
  364.                 if (PAIRFITS(op, (&key), (&val)))
  365.                     putpair((char *)op, &key, &val);
  366.                 else {
  367.                     old_bufp =
  368.                         __add_ovflpage(hashp, old_bufp);
  369.                     if (!old_bufp)
  370.                         return (-1);
  371.                     op = (u_int16_t *)old_bufp->page;
  372.                     putpair((char *)op, &key, &val);
  373.                 }
  374.                 old_bufp->flags |= BUF_MOD;
  375.             } else {
  376.                 /* Move to new page */
  377.                 if (PAIRFITS(np, (&key), (&val)))
  378.                     putpair((char *)np, &key, &val);
  379.                 else {
  380.                     new_bufp =
  381.                         __add_ovflpage(hashp, new_bufp);
  382.                     if (!new_bufp)
  383.                         return (-1);
  384.                     np = (u_int16_t *)new_bufp->page;
  385.                     putpair((char *)np, &key, &val);
  386.                 }
  387.                 new_bufp->flags |= BUF_MOD;
  388.             }
  389.         }
  390.     }
  391.     if (last_bfp)
  392.         __free_ovflpage(hashp, last_bfp);
  393.     return (0);
  394. }
  395.  
  396. /*
  397.  * Add the given pair to the page
  398.  *
  399.  * Returns:
  400.  *    0 ==> OK
  401.  *    1 ==> failure
  402.  */
  403. extern int
  404. __addel(hashp, bufp, key, val)
  405.     HTAB *hashp;
  406.     BUFHEAD *bufp;
  407.     const DBT *key, *val;
  408. {
  409.     register u_int16_t *bp, *sop;
  410.     int do_expand;
  411.  
  412.     bp = (u_int16_t *)bufp->page;
  413.     do_expand = 0;
  414.     while (bp[0] && (bp[2] < REAL_KEY || bp[bp[0]] < REAL_KEY))
  415.         /* Exception case */
  416.         if (bp[2] == FULL_KEY_DATA && bp[0] == 2)
  417.             /* This is the last page of a big key/data pair
  418.                and we need to add another page */
  419.             break;
  420.         else if (bp[2] < REAL_KEY && bp[bp[0]] != OVFLPAGE) {
  421.             bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
  422.             if (!bufp)
  423.                 return (-1);
  424.             bp = (u_int16_t *)bufp->page;
  425.         } else
  426.             /* Try to squeeze key on this page */
  427.             if (FREESPACE(bp) > PAIRSIZE(key, val)) {
  428.                 squeeze_key(bp, key, val);
  429.                 return (0);
  430.             } else {
  431.                 bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
  432.                 if (!bufp)
  433.                     return (-1);
  434.                 bp = (u_int16_t *)bufp->page;
  435.             }
  436.  
  437.     if (PAIRFITS(bp, key, val))
  438.         putpair(bufp->page, key, val);
  439.     else {
  440.         do_expand = 1;
  441.         bufp = __add_ovflpage(hashp, bufp);
  442.         if (!bufp)
  443.             return (-1);
  444.         sop = (u_int16_t *)bufp->page;
  445.  
  446.         if (PAIRFITS(sop, key, val))
  447.             putpair((char *)sop, key, val);
  448.         else
  449.             if (__big_insert(hashp, bufp, key, val))
  450.                 return (-1);
  451.     }
  452.     bufp->flags |= BUF_MOD;
  453.     /*
  454.      * If the average number of keys per bucket exceeds the fill factor,
  455.      * expand the table.
  456.      */
  457.     hashp->NKEYS++;
  458.     if (do_expand ||
  459.         (hashp->NKEYS / (hashp->MAX_BUCKET + 1) > hashp->FFACTOR))
  460.         return (__expand_table(hashp));
  461.     return (0);
  462. }
  463.  
  464. /*
  465.  *
  466.  * Returns:
  467.  *    pointer on success
  468.  *    NULL on error
  469.  */
  470. extern BUFHEAD *
  471. __add_ovflpage(hashp, bufp)
  472.     HTAB *hashp;
  473.     BUFHEAD *bufp;
  474. {
  475.     register u_int16_t *sp;
  476.     u_int16_t ndx, ovfl_num;
  477. #ifdef DEBUG1
  478.     int tmp1, tmp2;
  479. #endif
  480.     sp = (u_int16_t *)bufp->page;
  481.  
  482.     /* Check if we are dynamically determining the fill factor */
  483.     if (hashp->FFACTOR == DEF_FFACTOR) {
  484.         hashp->FFACTOR = sp[0] >> 1;
  485.         if (hashp->FFACTOR < MIN_FFACTOR)
  486.             hashp->FFACTOR = MIN_FFACTOR;
  487.     }
  488.     bufp->flags |= BUF_MOD;
  489.     ovfl_num = overflow_page(hashp);
  490. #ifdef DEBUG1
  491.     tmp1 = bufp->addr;
  492.     tmp2 = bufp->ovfl ? bufp->ovfl->addr : 0;
  493. #endif
  494.     if (!ovfl_num || !(bufp->ovfl = __get_buf(hashp, ovfl_num, bufp, 1)))
  495.         return (NULL);
  496.     bufp->ovfl->flags |= BUF_MOD;
  497. #ifdef DEBUG1
  498.     (void)fprintf(stderr, "ADDOVFLPAGE: %d->ovfl was %d is now %d\n",
  499.         tmp1, tmp2, bufp->ovfl->addr);
  500. #endif
  501.     ndx = sp[0];
  502.     /*
  503.      * Since a pair is allocated on a page only if there's room to add
  504.      * an overflow page, we know that the OVFL information will fit on
  505.      * the page.
  506.      */
  507.     sp[ndx + 4] = OFFSET(sp);
  508.     sp[ndx + 3] = FREESPACE(sp) - OVFLSIZE;
  509.     sp[ndx + 1] = ovfl_num;
  510.     sp[ndx + 2] = OVFLPAGE;
  511.     sp[0] = ndx + 2;
  512. #ifdef HASH_STATISTICS
  513.     hash_overflows++;
  514. #endif
  515.     return (bufp->ovfl);
  516. }
  517.  
  518. /*
  519.  * Returns:
  520.  *     0 indicates SUCCESS
  521.  *    -1 indicates FAILURE
  522.  */
  523. extern int
  524. __get_page(hashp, p, bucket, is_bucket, is_disk, is_bitmap)
  525.     HTAB *hashp;
  526.     char *p;
  527.     u_int32_t bucket;
  528.     int is_bucket, is_disk, is_bitmap;
  529. {
  530.     register int fd, page, size;
  531.     int rsize;
  532.     u_int16_t *bp;
  533.  
  534.     fd = hashp->fp;
  535.     size = hashp->BSIZE;
  536.  
  537.     if ((fd == -1) || !is_disk) {
  538.         PAGE_INIT(p);
  539.         return (0);
  540.     }
  541.     if (is_bucket)
  542.         page = BUCKET_TO_PAGE(bucket);
  543.     else
  544.         page = OADDR_TO_PAGE(bucket);
  545.     if ((lseek(fd, (off_t)page << hashp->BSHIFT, SEEK_SET) == -1) ||
  546.         ((rsize = read(fd, p, size)) == -1))
  547.         return (-1);
  548.     bp = (u_int16_t *)p;
  549.     if (!rsize)
  550.         bp[0] = 0;    /* We hit the EOF, so initialize a new page */
  551.     else
  552.         if (rsize != size) {
  553.             errno = EFTYPE;
  554.             return (-1);
  555.         }
  556.     if (!is_bitmap && !bp[0]) {
  557.         PAGE_INIT(p);
  558.     } else
  559.         if (hashp->LORDER != BYTE_ORDER) {
  560.             register int i, max;
  561.  
  562.             if (is_bitmap) {
  563.                 max = hashp->BSIZE >> 2; /* divide by 4 */
  564.                 for (i = 0; i < max; i++)
  565.                     M_32_SWAP(((int *)p)[i]);
  566.             } else {
  567.                 M_16_SWAP(bp[0]);
  568.                 max = bp[0] + 2;
  569.                 for (i = 1; i <= max; i++)
  570.                     M_16_SWAP(bp[i]);
  571.             }
  572.         }
  573.     return (0);
  574. }
  575.  
  576. /*
  577.  * Write page p to disk
  578.  *
  579.  * Returns:
  580.  *     0 ==> OK
  581.  *    -1 ==>failure
  582.  */
  583. extern int
  584. __put_page(hashp, p, bucket, is_bucket, is_bitmap)
  585.     HTAB *hashp;
  586.     char *p;
  587.     u_int32_t bucket;
  588.     int is_bucket, is_bitmap;
  589. {
  590.     register int fd, page, size;
  591.     int wsize;
  592.  
  593.     size = hashp->BSIZE;
  594.     if ((hashp->fp == -1) && open_temp(hashp))
  595.         return (-1);
  596.     fd = hashp->fp;
  597.  
  598.     if (hashp->LORDER != BYTE_ORDER) {
  599.         register int i;
  600.         register int max;
  601.  
  602.         if (is_bitmap) {
  603.             max = hashp->BSIZE >> 2;    /* divide by 4 */
  604.             for (i = 0; i < max; i++)
  605.                 M_32_SWAP(((int *)p)[i]);
  606.         } else {
  607.             max = ((u_int16_t *)p)[0] + 2;
  608.             for (i = 0; i <= max; i++)
  609.                 M_16_SWAP(((u_int16_t *)p)[i]);
  610.         }
  611.     }
  612.     if (is_bucket)
  613.         page = BUCKET_TO_PAGE(bucket);
  614.     else
  615.         page = OADDR_TO_PAGE(bucket);
  616.     if ((lseek(fd, (off_t)page << hashp->BSHIFT, SEEK_SET) == -1) ||
  617.         ((wsize = write(fd, p, size)) == -1))
  618.         /* Errno is set */
  619.         return (-1);
  620.     if (wsize != size) {
  621.         errno = EFTYPE;
  622.         return (-1);
  623.     }
  624.     return (0);
  625. }
  626.  
  627. #define BYTE_MASK    ((1 << INT_BYTE_SHIFT) -1)
  628. /*
  629.  * Initialize a new bitmap page.  Bitmap pages are left in memory
  630.  * once they are read in.
  631.  */
  632. extern int
  633. __ibitmap(hashp, pnum, nbits, ndx)
  634.     HTAB *hashp;
  635.     int pnum, nbits, ndx;
  636. {
  637.     u_int32_t *ip;
  638.     int clearbytes, clearints;
  639.  
  640.     if ((ip = (u_int32_t *)malloc(hashp->BSIZE)) == NULL)
  641.         return (1);
  642.     hashp->nmaps++;
  643.     clearints = ((nbits - 1) >> INT_BYTE_SHIFT) + 1;
  644.     clearbytes = clearints << INT_TO_BYTE;
  645.     (void)memset((char *)ip, 0, clearbytes);
  646.     (void)memset(((char *)ip) + clearbytes, 0xFF,
  647.         hashp->BSIZE - clearbytes);
  648.     ip[clearints - 1] = ALL_SET << (nbits & BYTE_MASK);
  649.     SETBIT(ip, 0);
  650.     hashp->BITMAPS[ndx] = (u_int16_t)pnum;
  651.     hashp->mapp[ndx] = ip;
  652.     return (0);
  653. }
  654.  
  655. static u_int32_t
  656. first_free(map)
  657.     u_int32_t map;
  658. {
  659.     register u_int32_t i, mask;
  660.  
  661.     mask = 0x1;
  662.     for (i = 0; i < BITS_PER_MAP; i++) {
  663.         if (!(mask & map))
  664.             return (i);
  665.         mask = mask << 1;
  666.     }
  667.     return (i);
  668. }
  669.  
  670. static u_int16_t
  671. overflow_page(hashp)
  672.     HTAB *hashp;
  673. {
  674.     register u_int32_t *freep = NULL;
  675.     register int max_free, offset, splitnum;
  676.     u_int16_t addr;
  677.     int bit, first_page, free_bit, free_page, i, in_use_bits, j;
  678. #ifdef DEBUG2
  679.     int tmp1, tmp2;
  680. #endif
  681.     splitnum = hashp->OVFL_POINT;
  682.     max_free = hashp->SPARES[splitnum];
  683.  
  684.     free_page = (max_free - 1) >> (hashp->BSHIFT + BYTE_SHIFT);
  685.     free_bit = (max_free - 1) & ((hashp->BSIZE << BYTE_SHIFT) - 1);
  686.  
  687.     /* Look through all the free maps to find the first free block */
  688.     first_page = hashp->LAST_FREED >>(hashp->BSHIFT + BYTE_SHIFT);
  689.     for ( i = first_page; i <= free_page; i++ ) {
  690.         if (!(freep = (u_int32_t *)hashp->mapp[i]) &&
  691.             !(freep = fetch_bitmap(hashp, i)))
  692.             return (NULL);
  693.         if (i == free_page)
  694.             in_use_bits = free_bit;
  695.         else
  696.             in_use_bits = (hashp->BSIZE << BYTE_SHIFT) - 1;
  697.         
  698.         if (i == first_page) {
  699.             bit = hashp->LAST_FREED &
  700.                 ((hashp->BSIZE << BYTE_SHIFT) - 1);
  701.             j = bit / BITS_PER_MAP;
  702.             bit = bit & ~(BITS_PER_MAP - 1);
  703.         } else {
  704.             bit = 0;
  705.             j = 0;
  706.         }
  707.         for (; bit <= in_use_bits; j++, bit += BITS_PER_MAP)
  708.             if (freep[j] != ALL_SET)
  709.                 goto found;
  710.     }
  711.  
  712.     /* No Free Page Found */
  713.     hashp->LAST_FREED = hashp->SPARES[splitnum];
  714.     hashp->SPARES[splitnum]++;
  715.     offset = hashp->SPARES[splitnum] -
  716.         (splitnum ? hashp->SPARES[splitnum - 1] : 0);
  717.  
  718. #define    OVMSG    "HASH: Out of overflow pages.  Increase page size\n"
  719.     if (offset > SPLITMASK) {
  720.         if (++splitnum >= NCACHED) {
  721.             (void)write(STDERR_FILENO, OVMSG, sizeof(OVMSG) - 1);
  722.             return (NULL);
  723.         }
  724.         hashp->OVFL_POINT = splitnum;
  725.         hashp->SPARES[splitnum] = hashp->SPARES[splitnum-1];
  726.         hashp->SPARES[splitnum-1]--;
  727.         offset = 1;
  728.     }
  729.  
  730.     /* Check if we need to allocate a new bitmap page */
  731.     if (free_bit == (hashp->BSIZE << BYTE_SHIFT) - 1) {
  732.         free_page++;
  733.         if (free_page >= NCACHED) {
  734.             (void)write(STDERR_FILENO, OVMSG, sizeof(OVMSG) - 1);
  735.             return (NULL);
  736.         }
  737.         /*
  738.          * This is tricky.  The 1 indicates that you want the new page
  739.          * allocated with 1 clear bit.  Actually, you are going to
  740.          * allocate 2 pages from this map.  The first is going to be
  741.          * the map page, the second is the overflow page we were
  742.          * looking for.  The init_bitmap routine automatically, sets
  743.          * the first bit of itself to indicate that the bitmap itself
  744.          * is in use.  We would explicitly set the second bit, but
  745.          * don't have to if we tell init_bitmap not to leave it clear
  746.          * in the first place.
  747.          */
  748.         if (__ibitmap(hashp, (int)OADDR_OF(splitnum, offset),
  749.             1, free_page))
  750.             return (NULL);
  751.         hashp->SPARES[splitnum]++;
  752. #ifdef DEBUG2
  753.         free_bit = 2;
  754. #endif
  755.         offset++;
  756.         if (offset > SPLITMASK) {
  757.             if (++splitnum >= NCACHED) {
  758.                 (void)write(STDERR_FILENO, OVMSG,
  759.                     sizeof(OVMSG) - 1);
  760.                 return (NULL);
  761.             }
  762.             hashp->OVFL_POINT = splitnum;
  763.             hashp->SPARES[splitnum] = hashp->SPARES[splitnum-1];
  764.             hashp->SPARES[splitnum-1]--;
  765.             offset = 0;
  766.         }
  767.     } else {
  768.         /*
  769.          * Free_bit addresses the last used bit.  Bump it to address
  770.          * the first available bit.
  771.          */
  772.         free_bit++;
  773.         SETBIT(freep, free_bit);
  774.     }
  775.  
  776.     /* Calculate address of the new overflow page */
  777.     addr = OADDR_OF(splitnum, offset);
  778. #ifdef DEBUG2
  779.     (void)fprintf(stderr, "OVERFLOW_PAGE: ADDR: %d BIT: %d PAGE %d\n",
  780.         addr, free_bit, free_page);
  781. #endif
  782.     return (addr);
  783.  
  784. found:
  785.     bit = bit + first_free(freep[j]);
  786.     SETBIT(freep, bit);
  787. #ifdef DEBUG2
  788.     tmp1 = bit;
  789.     tmp2 = i;
  790. #endif
  791.     /*
  792.      * Bits are addressed starting with 0, but overflow pages are addressed
  793.      * beginning at 1. Bit is a bit addressnumber, so we need to increment
  794.      * it to convert it to a page number.
  795.      */
  796.     bit = 1 + bit + (i * (hashp->BSIZE << BYTE_SHIFT));
  797.     if (bit >= hashp->LAST_FREED)
  798.         hashp->LAST_FREED = bit - 1;
  799.  
  800.     /* Calculate the split number for this page */
  801.     for (i = 0; (i < splitnum) && (bit > hashp->SPARES[i]); i++);
  802.     offset = (i ? bit - hashp->SPARES[i - 1] : bit);
  803.     if (offset >= SPLITMASK)
  804.         return (NULL);    /* Out of overflow pages */
  805.     addr = OADDR_OF(i, offset);
  806. #ifdef DEBUG2
  807.     (void)fprintf(stderr, "OVERFLOW_PAGE: ADDR: %d BIT: %d PAGE %d\n",
  808.         addr, tmp1, tmp2);
  809. #endif
  810.  
  811.     /* Allocate and return the overflow page */
  812.     return (addr);
  813. }
  814.  
  815. /*
  816.  * Mark this overflow page as free.
  817.  */
  818. extern void
  819. __free_ovflpage(hashp, obufp)
  820.     HTAB *hashp;
  821.     BUFHEAD *obufp;
  822. {
  823.     register u_int16_t addr;
  824.     u_int32_t *freep;
  825.     int bit_address, free_page, free_bit;
  826.     u_int16_t ndx;
  827.  
  828.     addr = obufp->addr;
  829. #ifdef DEBUG1
  830.     (void)fprintf(stderr, "Freeing %d\n", addr);
  831. #endif
  832.     ndx = (((u_int16_t)addr) >> SPLITSHIFT);
  833.     bit_address =
  834.         (ndx ? hashp->SPARES[ndx - 1] : 0) + (addr & SPLITMASK) - 1;
  835.      if (bit_address < hashp->LAST_FREED)
  836.         hashp->LAST_FREED = bit_address;
  837.     free_page = (bit_address >> (hashp->BSHIFT + BYTE_SHIFT));
  838.     free_bit = bit_address & ((hashp->BSIZE << BYTE_SHIFT) - 1);
  839.  
  840.     if (!(freep = hashp->mapp[free_page]))
  841.         freep = fetch_bitmap(hashp, free_page);
  842. #ifdef DEBUG
  843.     /*
  844.      * This had better never happen.  It means we tried to read a bitmap
  845.      * that has already had overflow pages allocated off it, and we
  846.      * failed to read it from the file.
  847.      */
  848.     if (!freep)
  849.         assert(0);
  850. #endif
  851.     CLRBIT(freep, free_bit);
  852. #ifdef DEBUG2
  853.     (void)fprintf(stderr, "FREE_OVFLPAGE: ADDR: %d BIT: %d PAGE %d\n",
  854.         obufp->addr, free_bit, free_page);
  855. #endif
  856.     __reclaim_buf(hashp, obufp);
  857. }
  858.  
  859. /*
  860.  * Returns:
  861.  *     0 success
  862.  *    -1 failure
  863.  */
  864. static int
  865. open_temp(hashp)
  866.     HTAB *hashp;
  867. {
  868.     sigset_t set, oset;
  869.     static char namestr[] = "_hashXXXXXX";
  870.  
  871.     /* Block signals; make sure file goes away at process exit. */
  872.     (void)sigfillset(&set);
  873.     (void)sigprocmask(SIG_BLOCK, &set, &oset);
  874.     if ((hashp->fp = mkstemp(namestr)) != -1) {
  875.         (void)unlink(namestr);
  876.         (void)fcntl(hashp->fp, F_SETFD, 1);
  877.     }
  878.     (void)sigprocmask(SIG_SETMASK, &oset, (sigset_t *)NULL);
  879.     return (hashp->fp != -1 ? 0 : -1);
  880. }
  881.  
  882. /*
  883.  * We have to know that the key will fit, but the last entry on the page is
  884.  * an overflow pair, so we need to shift things.
  885.  */
  886. static void
  887. squeeze_key(sp, key, val)
  888.     u_int16_t *sp;
  889.     const DBT *key, *val;
  890. {
  891.     register char *p;
  892.     u_int16_t free_space, n, off, pageno;
  893.  
  894.     p = (char *)sp;
  895.     n = sp[0];
  896.     free_space = FREESPACE(sp);
  897.     off = OFFSET(sp);
  898.  
  899.     pageno = sp[n - 1];
  900.     off -= key->size;
  901.     sp[n - 1] = off;
  902.     memmove(p + off, key->data, key->size);
  903.     off -= val->size;
  904.     sp[n] = off;
  905.     memmove(p + off, val->data, val->size);
  906.     sp[0] = n + 2;
  907.     sp[n + 1] = pageno;
  908.     sp[n + 2] = OVFLPAGE;
  909.     FREESPACE(sp) = free_space - PAIRSIZE(key, val);
  910.     OFFSET(sp) = off;
  911. }
  912.  
  913. static u_int32_t *
  914. fetch_bitmap(hashp, ndx)
  915.     HTAB *hashp;
  916.     int ndx;
  917. {
  918.     if (ndx >= hashp->nmaps)
  919.         return (NULL);
  920.     if ((hashp->mapp[ndx] = (u_int32_t *)malloc(hashp->BSIZE)) == NULL)
  921.         return (NULL);
  922.     if (__get_page(hashp,
  923.         (char *)hashp->mapp[ndx], hashp->BITMAPS[ndx], 0, 1, 1)) {
  924.         free(hashp->mapp[ndx]);
  925.         return (NULL);
  926.     }
  927.     return (hashp->mapp[ndx]);
  928. }
  929.  
  930. #ifdef DEBUG4
  931. int
  932. print_chain(addr)
  933.     int addr;
  934. {
  935.     BUFHEAD *bufp;
  936.     short *bp, oaddr;
  937.  
  938.     (void)fprintf(stderr, "%d ", addr);
  939.     bufp = __get_buf(hashp, addr, NULL, 0);
  940.     bp = (short *)bufp->page;
  941.     while (bp[0] && ((bp[bp[0]] == OVFLPAGE) ||
  942.         ((bp[0] > 2) && bp[2] < REAL_KEY))) {
  943.         oaddr = bp[bp[0] - 1];
  944.         (void)fprintf(stderr, "%d ", (int)oaddr);
  945.         bufp = __get_buf(hashp, (int)oaddr, bufp, 0);
  946.         bp = (short *)bufp->page;
  947.     }
  948.     (void)fprintf(stderr, "\n");
  949. }
  950. #endif
  951.