home *** CD-ROM | disk | FTP | other *** search
/ Tools / WinSN5.0Ver.iso / NETSCAP.50 / WIN1998.ZIP / ns / dbm / src / h_bigkey.c < prev    next >
Encoding:
C/C++ Source or Header  |  1998-04-08  |  16.8 KB  |  683 lines
  1. /*-
  2.  * Copyright (c) 1990, 1993, 1994
  3.  *    The Regents of the University of California.  All rights reserved.
  4.  *
  5.  * This code is derived from software contributed to Berkeley by
  6.  * Margo Seltzer.
  7.  *
  8.  * Redistribution and use in source and binary forms, with or without
  9.  * modification, are permitted provided that the following conditions
  10.  * are met:
  11.  * 1. Redistributions of source code must retain the above copyright
  12.  *    notice, this list of conditions and the following disclaimer.
  13.  * 2. Redistributions in binary form must reproduce the above copyright
  14.  *    notice, this list of conditions and the following disclaimer in the
  15.  *    documentation and/or other materials provided with the distribution.
  16.  * 3. All advertising materials mentioning features or use of this software
  17.  *    must display the following acknowledgement:
  18.  *    This product includes software developed by the University of
  19.  *    California, Berkeley and its contributors.
  20.  * 4. Neither the name of the University nor the names of its contributors
  21.  *    may be used to endorse or promote products derived from this software
  22.  *    without specific prior written permission.
  23.  *
  24.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34.  * SUCH DAMAGE.
  35.  */
  36.  
  37. #if defined(LIBC_SCCS) && !defined(lint)
  38. static char sccsid[] = "@(#)hash_bigkey.c    8.3 (Berkeley) 5/31/94";
  39. #endif /* LIBC_SCCS and not lint */
  40.  
  41. #include "watcomfx.h"
  42.  
  43. /*
  44.  * PACKAGE: hash
  45.  * DESCRIPTION:
  46.  *    Big key/data handling for the hashing package.
  47.  *
  48.  * ROUTINES:
  49.  * External
  50.  *    __big_keydata
  51.  *    __big_split
  52.  *    __big_insert
  53.  *    __big_return
  54.  *    __big_delete
  55.  *    __find_last_page
  56.  * Internal
  57.  *    collect_key
  58.  *    collect_data
  59.  */
  60.  
  61. #if !defined(_WIN32) && !defined(_WINDOWS) && !defined(macintosh)
  62. #include <sys/param.h>
  63. #endif
  64.  
  65. #include <errno.h>
  66. #include <stdio.h>
  67. #include <stdlib.h>
  68. #include <string.h>
  69.  
  70. #ifdef DEBUG
  71. #include <assert.h>
  72. #endif
  73.  
  74. #include "mcom_db.h"
  75. #include "hash.h"
  76. #include "page.h"
  77. /* #include "extern.h" */
  78.  
  79. #ifndef NSPR20
  80. #if defined(__sun)
  81. # include "sunos4.h"
  82. #endif /* __sun */
  83. #endif /* NSPR20 */
  84.  
  85. static int collect_key __P((HTAB *, BUFHEAD *, int, DBT *, int));
  86. static int collect_data __P((HTAB *, BUFHEAD *, int, int));
  87.  
  88. /*
  89.  * Big_insert
  90.  *
  91.  * You need to do an insert and the key/data pair is too big
  92.  *
  93.  * Returns:
  94.  * 0 ==> OK
  95.  *-1 ==> ERROR
  96.  */
  97. extern int
  98. __big_insert(HTAB *hashp, BUFHEAD *bufp, const DBT *key, const DBT *val)
  99. {
  100.     register uint16 *p;
  101.     int key_size, n, val_size;
  102.     uint16 space, move_bytes, off;
  103.     char *cp, *key_data, *val_data;
  104.  
  105.     cp = bufp->page;        /* Character pointer of p. */
  106.     p = (uint16 *)cp;
  107.  
  108.     key_data = (char *)key->data;
  109.     key_size = key->size;
  110.     val_data = (char *)val->data;
  111.     val_size = val->size;
  112.  
  113.     /* First move the Key */
  114.     for (space = FREESPACE(p) - BIGOVERHEAD; key_size;
  115.         space = FREESPACE(p) - BIGOVERHEAD) {
  116.         move_bytes = MIN(space, key_size);
  117.         off = OFFSET(p) - move_bytes;
  118.         memmove(cp + off, key_data, move_bytes);
  119.         key_size -= move_bytes;
  120.         key_data += move_bytes;
  121.         n = p[0];
  122.         p[++n] = off;
  123.         p[0] = ++n;
  124.         FREESPACE(p) = off - PAGE_META(n);
  125.         OFFSET(p) = off;
  126.         p[n] = PARTIAL_KEY;
  127.         bufp = __add_ovflpage(hashp, bufp);
  128.         if (!bufp)
  129.             return (-1);
  130.         n = p[0];
  131.         if (!key_size)
  132.             if (FREESPACE(p)) {
  133.                 move_bytes = MIN(FREESPACE(p), val_size);
  134.                 off = OFFSET(p) - move_bytes;
  135.                 p[n] = off;
  136.                 memmove(cp + off, val_data, move_bytes);
  137.                 val_data += move_bytes;
  138.                 val_size -= move_bytes;
  139.                 p[n - 2] = FULL_KEY_DATA;
  140.                 FREESPACE(p) = FREESPACE(p) - move_bytes;
  141.                 OFFSET(p) = off;
  142.             } else
  143.                 p[n - 2] = FULL_KEY;
  144.         p = (uint16 *)bufp->page;
  145.         cp = bufp->page;
  146.         bufp->flags |= BUF_MOD;
  147.     }
  148.  
  149.     /* Now move the data */
  150.     for (space = FREESPACE(p) - BIGOVERHEAD; val_size;
  151.         space = FREESPACE(p) - BIGOVERHEAD) {
  152.         move_bytes = MIN(space, val_size);
  153.         /*
  154.          * Here's the hack to make sure that if the data ends on the
  155.          * same page as the key ends, FREESPACE is at least one.
  156.          */
  157.         if (space == val_size && val_size == val->size)
  158.             move_bytes--;
  159.         off = OFFSET(p) - move_bytes;
  160.         memmove(cp + off, val_data, move_bytes);
  161.         val_size -= move_bytes;
  162.         val_data += move_bytes;
  163.         n = p[0];
  164.         p[++n] = off;
  165.         p[0] = ++n;
  166.         FREESPACE(p) = off - PAGE_META(n);
  167.         OFFSET(p) = off;
  168.         if (val_size) {
  169.             p[n] = FULL_KEY;
  170.             bufp = __add_ovflpage(hashp, bufp);
  171.             if (!bufp)
  172.                 return (-1);
  173.             cp = bufp->page;
  174.             p = (uint16 *)cp;
  175.         } else
  176.             p[n] = FULL_KEY_DATA;
  177.         bufp->flags |= BUF_MOD;
  178.     }
  179.     return (0);
  180. }
  181.  
  182. /*
  183.  * Called when bufp's page  contains a partial key (index should be 1)
  184.  *
  185.  * All pages in the big key/data pair except bufp are freed.  We cannot
  186.  * free bufp because the page pointing to it is lost and we can't get rid
  187.  * of its pointer.
  188.  *
  189.  * Returns:
  190.  * 0 => OK
  191.  *-1 => ERROR
  192.  */
  193. extern int
  194. __big_delete(HTAB *hashp, BUFHEAD *bufp)
  195. {
  196.     register BUFHEAD *last_bfp, *rbufp;
  197.     uint16 *bp, pageno;
  198.     int key_done, n;
  199.  
  200.     rbufp = bufp;
  201.     last_bfp = NULL;
  202.     bp = (uint16 *)bufp->page;
  203.     pageno = 0;
  204.     key_done = 0;
  205.  
  206.     while (!key_done || (bp[2] != FULL_KEY_DATA)) {
  207.         if (bp[2] == FULL_KEY || bp[2] == FULL_KEY_DATA)
  208.             key_done = 1;
  209.  
  210.         /*
  211.          * If there is freespace left on a FULL_KEY_DATA page, then
  212.          * the data is short and fits entirely on this page, and this
  213.          * is the last page.
  214.          */
  215.         if (bp[2] == FULL_KEY_DATA && FREESPACE(bp))
  216.             break;
  217.         pageno = bp[bp[0] - 1];
  218.         rbufp->flags |= BUF_MOD;
  219.         rbufp = __get_buf(hashp, pageno, rbufp, 0);
  220.         if (last_bfp)
  221.             __free_ovflpage(hashp, last_bfp);
  222.         last_bfp = rbufp;
  223.         if (!rbufp)
  224.             return (-1);        /* Error. */
  225.         bp = (uint16 *)rbufp->page;
  226.     }
  227.  
  228.     /*
  229.      * If we get here then rbufp points to the last page of the big
  230.      * key/data pair.  Bufp points to the first one -- it should now be
  231.      * empty pointing to the next page after this pair.  Can't free it
  232.      * because we don't have the page pointing to it.
  233.      */
  234.  
  235.     /* This is information from the last page of the pair. */
  236.     n = bp[0];
  237.     pageno = bp[n - 1];
  238.  
  239.     /* Now, bp is the first page of the pair. */
  240.     bp = (uint16 *)bufp->page;
  241.     if (n > 2) {
  242.         /* There is an overflow page. */
  243.         bp[1] = pageno;
  244.         bp[2] = OVFLPAGE;
  245.         bufp->ovfl = rbufp->ovfl;
  246.     } else
  247.         /* This is the last page. */
  248.         bufp->ovfl = NULL;
  249.     n -= 2;
  250.     bp[0] = n;
  251.     FREESPACE(bp) = hashp->BSIZE - PAGE_META(n);
  252.     OFFSET(bp) = hashp->BSIZE - 1;
  253.  
  254.     bufp->flags |= BUF_MOD;
  255.     if (rbufp)
  256.         __free_ovflpage(hashp, rbufp);
  257.     if (last_bfp != rbufp)
  258.         __free_ovflpage(hashp, last_bfp);
  259.  
  260.     hashp->NKEYS--;
  261.     return (0);
  262. }
  263. /*
  264.  * Returns:
  265.  *  0 = key not found
  266.  * -1 = get next overflow page
  267.  * -2 means key not found and this is big key/data
  268.  * -3 error
  269.  */
  270. extern int
  271. __find_bigpair(HTAB *hashp, BUFHEAD *bufp, int ndx, char *key, int size)
  272. {
  273.     register uint16 *bp;
  274.     register char *p;
  275.     int ksize;
  276.     uint16 bytes;
  277.     char *kkey;
  278.  
  279.     bp = (uint16 *)bufp->page;
  280.     p = bufp->page;
  281.     ksize = size;
  282.     kkey = key;
  283.  
  284.     for (bytes = hashp->BSIZE - bp[ndx];
  285.         bytes <= size && bp[ndx + 1] == PARTIAL_KEY;
  286.         bytes = hashp->BSIZE - bp[ndx]) {
  287.         if (memcmp(p + bp[ndx], kkey, bytes))
  288.             return (-2);
  289.         kkey += bytes;
  290.         ksize -= bytes;
  291.         bufp = __get_buf(hashp, bp[ndx + 2], bufp, 0);
  292.         if (!bufp)
  293.             return (-3);
  294.         p = bufp->page;
  295.         bp = (uint16 *)p;
  296.         ndx = 1;
  297.     }
  298.  
  299.     if (bytes != ksize || memcmp(p + bp[ndx], kkey, bytes)) {
  300. #ifdef HASH_STATISTICS
  301.         ++hash_collisions;
  302. #endif
  303.         return (-2);
  304.     } else
  305.         return (ndx);
  306. }
  307.  
  308. /*
  309.  * Given the buffer pointer of the first overflow page of a big pair,
  310.  * find the end of the big pair
  311.  *
  312.  * This will set bpp to the buffer header of the last page of the big pair.
  313.  * It will return the pageno of the overflow page following the last page
  314.  * of the pair; 0 if there isn't any (i.e. big pair is the last key in the
  315.  * bucket)
  316.  */
  317. extern uint16
  318. __find_last_page(HTAB *hashp, BUFHEAD **bpp)
  319. {
  320.     BUFHEAD *bufp;
  321.     uint16 *bp, pageno;
  322.     int n;
  323.  
  324.     bufp = *bpp;
  325.     bp = (uint16 *)bufp->page;
  326.     for (;;) {
  327.         n = bp[0];
  328.  
  329.         /*
  330.          * This is the last page if: the tag is FULL_KEY_DATA and
  331.          * either only 2 entries OVFLPAGE marker is explicit there
  332.          * is freespace on the page.
  333.          */
  334.         if (bp[2] == FULL_KEY_DATA &&
  335.             ((n == 2) || (bp[n] == OVFLPAGE) || (FREESPACE(bp))))
  336.             break;
  337.  
  338.         /* LJM bound the size of n to reasonable limits
  339.          */
  340.         if(n > hashp->BSIZE/sizeof(uint16))
  341.             return(0);
  342.  
  343.         pageno = bp[n - 1];
  344.         bufp = __get_buf(hashp, pageno, bufp, 0);
  345.         if (!bufp)
  346.             return (0);    /* Need to indicate an error! */
  347.         bp = (uint16 *)bufp->page;
  348.     }
  349.  
  350.     *bpp = bufp;
  351.     if (bp[0] > 2)
  352.         return (bp[3]);
  353.     else
  354.         return (0);
  355. }
  356.  
  357. /*
  358.  * Return the data for the key/data pair that begins on this page at this
  359.  * index (index should always be 1).
  360.  */
  361. extern int
  362. __big_return(
  363.     HTAB *hashp,
  364.     BUFHEAD *bufp,
  365.     int ndx,
  366.     DBT *val,
  367.     int set_current)
  368. {
  369.     BUFHEAD *save_p;
  370.     uint16 *bp, len, off, save_addr;
  371.     char *tp;
  372.  
  373.     bp = (uint16 *)bufp->page;
  374.     while (bp[ndx + 1] == PARTIAL_KEY) {
  375.         bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
  376.         if (!bufp)
  377.             return (-1);
  378.         bp = (uint16 *)bufp->page;
  379.         ndx = 1;
  380.     }
  381.  
  382.     if (bp[ndx + 1] == FULL_KEY) {
  383.         bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
  384.         if (!bufp)
  385.             return (-1);
  386.         bp = (uint16 *)bufp->page;
  387.         save_p = bufp;
  388.         save_addr = save_p->addr;
  389.         off = bp[1];
  390.         len = 0;
  391.     } else
  392.         if (!FREESPACE(bp)) {
  393.             /*
  394.              * This is a hack.  We can't distinguish between
  395.              * FULL_KEY_DATA that contains complete data or
  396.              * incomplete data, so we require that if the data
  397.              * is complete, there is at least 1 byte of free
  398.              * space left.
  399.              */
  400.             off = bp[bp[0]];
  401.             len = bp[1] - off;
  402.             save_p = bufp;
  403.             save_addr = bufp->addr;
  404.             bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
  405.             if (!bufp)
  406.                 return (-1);
  407.             bp = (uint16 *)bufp->page;
  408.         } else {
  409.             /* The data is all on one page. */
  410.             tp = (char *)bp;
  411.             off = bp[bp[0]];
  412.             val->data = (uint8 *)tp + off;
  413.             val->size = bp[1] - off;
  414.             if (set_current) {
  415.                 if (bp[0] == 2) {    /* No more buckets in
  416.                              * chain */
  417.                     hashp->cpage = NULL;
  418.                     hashp->cbucket++;
  419.                     hashp->cndx = 1;
  420.                 } else {
  421.                     hashp->cpage = __get_buf(hashp,
  422.                         bp[bp[0] - 1], bufp, 0);
  423.                     if (!hashp->cpage)
  424.                         return (-1);
  425.                     hashp->cndx = 1;
  426.                     if (!((uint16 *)
  427.                         hashp->cpage->page)[0]) {
  428.                         hashp->cbucket++;
  429.                         hashp->cpage = NULL;
  430.                     }
  431.                 }
  432.             }
  433.             return (0);
  434.         }
  435.  
  436.     val->size = collect_data(hashp, bufp, (int)len, set_current);
  437.     if (val->size == -1)
  438.         return (-1);
  439.     if (save_p->addr != save_addr) {
  440.         /* We are pretty short on buffers. */
  441.         errno = EINVAL;            /* OUT OF BUFFERS */
  442.         return (-1);
  443.     }
  444.     memmove(hashp->tmp_buf, (save_p->page) + off, len);
  445.     val->data = (uint8 *)hashp->tmp_buf;
  446.     return (0);
  447. }
  448. /*
  449.  * Count how big the total datasize is by recursing through the pages.  Then
  450.  * allocate a buffer and copy the data as you recurse up.
  451.  */
  452. static int
  453. collect_data(
  454.     HTAB *hashp,
  455.     BUFHEAD *bufp,
  456.     int len, int set)
  457. {
  458.     register uint16 *bp;
  459.     register char *p;
  460.     BUFHEAD *xbp;
  461.     uint16 save_addr;
  462.     int mylen, totlen;
  463.  
  464.     p = bufp->page;
  465.     bp = (uint16 *)p;
  466.     mylen = hashp->BSIZE - bp[1];
  467.  
  468.     /* if mylen ever goes negative it means that the 
  469.      * page is screwed up.
  470.      */
  471.     if(mylen < 0)
  472.         return (-1);
  473.  
  474.     save_addr = bufp->addr;
  475.  
  476.     if (bp[2] == FULL_KEY_DATA) {        /* End of Data */
  477.         totlen = len + mylen;
  478.         if (hashp->tmp_buf)
  479.             free(hashp->tmp_buf);
  480.         if ((hashp->tmp_buf = (char *)malloc(totlen)) == NULL)
  481.             return (-1);
  482.         if (set) {
  483.             hashp->cndx = 1;
  484.             if (bp[0] == 2) {    /* No more buckets in chain */
  485.                 hashp->cpage = NULL;
  486.                 hashp->cbucket++;
  487.             } else {
  488.                 hashp->cpage =
  489.                     __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
  490.                 if (!hashp->cpage)
  491.                     return (-1);
  492.                 else if (!((uint16 *)hashp->cpage->page)[0]) {
  493.                     hashp->cbucket++;
  494.                     hashp->cpage = NULL;
  495.                 }
  496.             }
  497.         }
  498.     } else {
  499.         xbp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
  500.         if (!xbp || ((totlen =
  501.             collect_data(hashp, xbp, len + mylen, set)) < 1))
  502.             return (-1);
  503.     }
  504.     if (bufp->addr != save_addr) {
  505.         errno = EINVAL;            /* Out of buffers. */
  506.         return (-1);
  507.     }
  508.     memmove(&hashp->tmp_buf[len], (bufp->page) + bp[1], mylen);
  509.     return (totlen);
  510. }
  511.  
  512. /*
  513.  * Fill in the key and data for this big pair.
  514.  */
  515. extern int
  516. __big_keydata(
  517.     HTAB *hashp, 
  518.     BUFHEAD *bufp, 
  519.     DBT *key, DBT *val,
  520.     int set)
  521. {
  522.     key->size = collect_key(hashp, bufp, 0, val, set);
  523.     if (key->size == -1)
  524.         return (-1);
  525.     key->data = (uint8 *)hashp->tmp_key;
  526.     return (0);
  527. }
  528.  
  529. /*
  530.  * Count how big the total key size is by recursing through the pages.  Then
  531.  * collect the data, allocate a buffer and copy the key as you recurse up.
  532.  */
  533. static int
  534. collect_key(
  535.     HTAB *hashp,
  536.     BUFHEAD *bufp,
  537.     int len,
  538.     DBT *val,
  539.     int set)
  540. {
  541.     BUFHEAD *xbp;
  542.     char *p;
  543.     int mylen, totlen;
  544.     uint16 *bp, save_addr;
  545.  
  546.     p = bufp->page;
  547.     bp = (uint16 *)p;
  548.     mylen = hashp->BSIZE - bp[1];
  549.  
  550.     save_addr = bufp->addr;
  551.     totlen = len + mylen;
  552.     if (bp[2] == FULL_KEY || bp[2] == FULL_KEY_DATA) {    /* End of Key. */
  553.         if (hashp->tmp_key != NULL)
  554.             free(hashp->tmp_key);
  555.         if ((hashp->tmp_key = (char *)malloc(totlen)) == NULL)
  556.             return (-1);
  557.         if (__big_return(hashp, bufp, 1, val, set))
  558.             return (-1);
  559.     } else {
  560.         xbp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
  561.         if (!xbp || ((totlen =
  562.             collect_key(hashp, xbp, totlen, val, set)) < 1))
  563.             return (-1);
  564.     }
  565.     if (bufp->addr != save_addr) {
  566.         errno = EINVAL;        /* MIS -- OUT OF BUFFERS */
  567.         return (-1);
  568.     }
  569.     memmove(&hashp->tmp_key[len], (bufp->page) + bp[1], mylen);
  570.     return (totlen);
  571. }
  572.  
  573. /*
  574.  * Returns:
  575.  *  0 => OK
  576.  * -1 => error
  577.  */
  578. extern int
  579. __big_split(
  580.     HTAB *hashp,
  581.     BUFHEAD *op,    /* Pointer to where to put keys that go in old bucket */
  582.     BUFHEAD *np,    /* Pointer to new bucket page */
  583.             /* Pointer to first page containing the big key/data */
  584.     BUFHEAD *big_keyp,
  585.     int addr,    /* Address of big_keyp */
  586.     uint32   obucket,/* Old Bucket */
  587.     SPLIT_RETURN *ret)
  588. {
  589.     register BUFHEAD *tmpp;
  590.     register uint16 *tp;
  591.     BUFHEAD *bp;
  592.     DBT key, val;
  593.     uint32 change;
  594.     uint16 free_space, n, off;
  595.  
  596.     bp = big_keyp;
  597.  
  598.     /* Now figure out where the big key/data goes */
  599.     if (__big_keydata(hashp, big_keyp, &key, &val, 0))
  600.         return (-1);
  601.     change = (__call_hash(hashp,(char*) key.data, key.size) != obucket);
  602.  
  603.     if ((ret->next_addr = __find_last_page(hashp, &big_keyp))) {
  604.         if (!(ret->nextp =
  605.             __get_buf(hashp, ret->next_addr, big_keyp, 0)))
  606.             return (-1);;
  607.     } else
  608.         ret->nextp = NULL;
  609.  
  610.     /* Now make one of np/op point to the big key/data pair */
  611. #ifdef DEBUG
  612.     assert(np->ovfl == NULL);
  613. #endif
  614.     if (change)
  615.         tmpp = np;
  616.     else
  617.         tmpp = op;
  618.  
  619.     tmpp->flags |= BUF_MOD;
  620. #ifdef DEBUG1
  621.     (void)fprintf(stderr,
  622.         "BIG_SPLIT: %d->ovfl was %d is now %d\n", tmpp->addr,
  623.         (tmpp->ovfl ? tmpp->ovfl->addr : 0), (bp ? bp->addr : 0));
  624. #endif
  625.     tmpp->ovfl = bp;    /* one of op/np point to big_keyp */
  626.     tp = (uint16 *)tmpp->page;
  627.  
  628.  
  629. #if 0  /* this get's tripped on database corrupted error */
  630.     assert(FREESPACE(tp) >= OVFLSIZE);
  631. #endif
  632.     if(FREESPACE(tp) < OVFLSIZE)
  633.         return(DATABASE_CORRUPTED_ERROR);
  634.  
  635.     n = tp[0];
  636.     off = OFFSET(tp);
  637.     free_space = FREESPACE(tp);
  638.     tp[++n] = (uint16)addr;
  639.     tp[++n] = OVFLPAGE;
  640.     tp[0] = n;
  641.     OFFSET(tp) = off;
  642.     FREESPACE(tp) = free_space - OVFLSIZE;
  643.  
  644.     /*
  645.      * Finally, set the new and old return values. BIG_KEYP contains a
  646.      * pointer to the last page of the big key_data pair. Make sure that
  647.      * big_keyp has no following page (2 elements) or create an empty
  648.      * following page.
  649.      */
  650.  
  651.     ret->newp = np;
  652.     ret->oldp = op;
  653.  
  654.     tp = (uint16 *)big_keyp->page;
  655.     big_keyp->flags |= BUF_MOD;
  656.     if (tp[0] > 2) {
  657.         /*
  658.          * There may be either one or two offsets on this page.  If
  659.          * there is one, then the overflow page is linked on normally
  660.          * and tp[4] is OVFLPAGE.  If there are two, tp[4] contains
  661.          * the second offset and needs to get stuffed in after the
  662.          * next overflow page is added.
  663.          */
  664.         n = tp[4];
  665.         free_space = FREESPACE(tp);
  666.         off = OFFSET(tp);
  667.         tp[0] -= 2;
  668.         FREESPACE(tp) = free_space + OVFLSIZE;
  669.         OFFSET(tp) = off;
  670.         tmpp = __add_ovflpage(hashp, big_keyp);
  671.         if (!tmpp)
  672.             return (-1);
  673.         tp[4] = n;
  674.     } else
  675.         tmpp = big_keyp;
  676.  
  677.     if (change)
  678.         ret->newp = tmpp;
  679.     else
  680.         ret->oldp = tmpp;
  681.     return (0);
  682. }
  683.