home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 2 / Apprentice-Release2.iso / Source Code / C / Libraries / Berkeley DB 1.6 / hash / hash_bigkey.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-06-04  |  15.9 KB  |  670 lines  |  [TEXT/????]
  1. /*-
  2.  * Copyright (c) 1990, 1993
  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.1 (Berkeley) 6/4/93";
  39. #endif /* LIBC_SCCS and not lint */
  40.  
  41. /*
  42.  * PACKAGE: hash
  43.  * DESCRIPTION:
  44.  *    Big key/data handling for the hashing package.
  45.  *
  46.  * ROUTINES:
  47.  * External
  48.  *    __big_keydata
  49.  *    __big_split
  50.  *    __big_insert
  51.  *    __big_return
  52.  *    __big_delete
  53.  *    __find_last_page
  54.  * Internal
  55.  *    collect_key
  56.  *    collect_data
  57.  */
  58.  
  59. #include <sys/param.h>
  60.  
  61. #include <errno.h>
  62. #include <stdio.h>
  63. #include <stdlib.h>
  64. #include <string.h>
  65.  
  66. #ifdef DEBUG
  67. #include <assert.h>
  68. #endif
  69.  
  70. #include <db.h>
  71. #include "hash.h"
  72. #include "page.h"
  73. #include "extern.h"
  74.  
  75. static int collect_key __P((HTAB *, BUFHEAD *, int, DBT *, int));
  76. static int collect_data __P((HTAB *, BUFHEAD *, int, int));
  77.  
  78. /*
  79.  * Big_insert
  80.  *
  81.  * You need to do an insert and the key/data pair is too big
  82.  *
  83.  * Returns:
  84.  * 0 ==> OK
  85.  *-1 ==> ERROR
  86.  */
  87. extern int
  88. __big_insert(hashp, bufp, key, val)
  89.     HTAB *hashp;
  90.     BUFHEAD *bufp;
  91.     const DBT *key, *val;
  92. {
  93.     register u_short *p;
  94.     int key_size, n, val_size;
  95.     u_short space, move_bytes, off;
  96.     char *cp, *key_data, *val_data;
  97.  
  98.     cp = bufp->page;        /* Character pointer of p. */
  99.     p = (u_short *)cp;
  100.  
  101.     key_data = (char *)key->data;
  102.     key_size = key->size;
  103.     val_data = (char *)val->data;
  104.     val_size = val->size;
  105.  
  106.     /* First move the Key */
  107.     for (space = FREESPACE(p) - BIGOVERHEAD; key_size;
  108.         space = FREESPACE(p) - BIGOVERHEAD) {
  109.         move_bytes = MIN(space, key_size);
  110.         off = OFFSET(p) - move_bytes;
  111.         memmove(cp + off, key_data, move_bytes);
  112.         key_size -= move_bytes;
  113.         key_data += move_bytes;
  114.         n = p[0];
  115.         p[++n] = off;
  116.         p[0] = ++n;
  117.         FREESPACE(p) = off - PAGE_META(n);
  118.         OFFSET(p) = off;
  119.         p[n] = PARTIAL_KEY;
  120.         bufp = __add_ovflpage(hashp, bufp);
  121.         if (!bufp)
  122.             return (-1);
  123.         n = p[0];
  124.         if (!key_size)
  125.             if (FREESPACE(p)) {
  126.                 move_bytes = MIN(FREESPACE(p), val_size);
  127.                 off = OFFSET(p) - move_bytes;
  128.                 p[n] = off;
  129.                 memmove(cp + off, val_data, move_bytes);
  130.                 val_data += move_bytes;
  131.                 val_size -= move_bytes;
  132.                 p[n - 2] = FULL_KEY_DATA;
  133.                 FREESPACE(p) = FREESPACE(p) - move_bytes;
  134.                 OFFSET(p) = off;
  135.             } else
  136.                 p[n - 2] = FULL_KEY;
  137.         p = (u_short *)bufp->page;
  138.         cp = bufp->page;
  139.         bufp->flags |= BUF_MOD;
  140.     }
  141.  
  142.     /* Now move the data */
  143.     for (space = FREESPACE(p) - BIGOVERHEAD; val_size;
  144.         space = FREESPACE(p) - BIGOVERHEAD) {
  145.         move_bytes = MIN(space, val_size);
  146.         /*
  147.          * Here's the hack to make sure that if the data ends on the
  148.          * same page as the key ends, FREESPACE is at least one.
  149.          */
  150.         if (space == val_size && val_size == val->size)
  151.             move_bytes--;
  152.         off = OFFSET(p) - move_bytes;
  153.         memmove(cp + off, val_data, move_bytes);
  154.         val_size -= move_bytes;
  155.         val_data += move_bytes;
  156.         n = p[0];
  157.         p[++n] = off;
  158.         p[0] = ++n;
  159.         FREESPACE(p) = off - PAGE_META(n);
  160.         OFFSET(p) = off;
  161.         if (val_size) {
  162.             p[n] = FULL_KEY;
  163.             bufp = __add_ovflpage(hashp, bufp);
  164.             if (!bufp)
  165.                 return (-1);
  166.             cp = bufp->page;
  167.             p = (u_short *)cp;
  168.         } else
  169.             p[n] = FULL_KEY_DATA;
  170.         bufp->flags |= BUF_MOD;
  171.     }
  172.     return (0);
  173. }
  174.  
  175. /*
  176.  * Called when bufp's page  contains a partial key (index should be 1)
  177.  *
  178.  * All pages in the big key/data pair except bufp are freed.  We cannot
  179.  * free bufp because the page pointing to it is lost and we can't get rid
  180.  * of its pointer.
  181.  *
  182.  * Returns:
  183.  * 0 => OK
  184.  *-1 => ERROR
  185.  */
  186. extern int
  187. __big_delete(hashp, bufp)
  188.     HTAB *hashp;
  189.     BUFHEAD *bufp;
  190. {
  191.     register BUFHEAD *last_bfp, *rbufp;
  192.     u_short *bp, pageno;
  193.     int key_done, n;
  194.  
  195.     rbufp = bufp;
  196.     last_bfp = NULL;
  197.     bp = (u_short *)bufp->page;
  198.     pageno = 0;
  199.     key_done = 0;
  200.  
  201.     while (!key_done || (bp[2] != FULL_KEY_DATA)) {
  202.         if (bp[2] == FULL_KEY || bp[2] == FULL_KEY_DATA)
  203.             key_done = 1;
  204.  
  205.         /*
  206.          * If there is freespace left on a FULL_KEY_DATA page, then
  207.          * the data is short and fits entirely on this page, and this
  208.          * is the last page.
  209.          */
  210.         if (bp[2] == FULL_KEY_DATA && FREESPACE(bp))
  211.             break;
  212.         pageno = bp[bp[0] - 1];
  213.         rbufp->flags |= BUF_MOD;
  214.         rbufp = __get_buf(hashp, pageno, rbufp, 0);
  215.         if (last_bfp)
  216.             __free_ovflpage(hashp, last_bfp);
  217.         last_bfp = rbufp;
  218.         if (!rbufp)
  219.             return (-1);        /* Error. */
  220.         bp = (u_short *)rbufp->page;
  221.     }
  222.  
  223.     /*
  224.      * If we get here then rbufp points to the last page of the big
  225.      * key/data pair.  Bufp points to the first one -- it should now be
  226.      * empty pointing to the next page after this pair.  Can't free it
  227.      * because we don't have the page pointing to it.
  228.      */
  229.  
  230.     /* This is information from the last page of the pair. */
  231.     n = bp[0];
  232.     pageno = bp[n - 1];
  233.  
  234.     /* Now, bp is the first page of the pair. */
  235.     bp = (u_short *)bufp->page;
  236.     if (n > 2) {
  237.         /* There is an overflow page. */
  238.         bp[1] = pageno;
  239.         bp[2] = OVFLPAGE;
  240.         bufp->ovfl = rbufp->ovfl;
  241.     } else
  242.         /* This is the last page. */
  243.         bufp->ovfl = NULL;
  244.     n -= 2;
  245.     bp[0] = n;
  246.     FREESPACE(bp) = hashp->BSIZE - PAGE_META(n);
  247.     OFFSET(bp) = hashp->BSIZE - 1;
  248.  
  249.     bufp->flags |= BUF_MOD;
  250.     if (rbufp)
  251.         __free_ovflpage(hashp, rbufp);
  252.     if (last_bfp != rbufp)
  253.         __free_ovflpage(hashp, last_bfp);
  254.  
  255.     hashp->NKEYS--;
  256.     return (0);
  257. }
  258. /*
  259.  * Returns:
  260.  *  0 = key not found
  261.  * -1 = get next overflow page
  262.  * -2 means key not found and this is big key/data
  263.  * -3 error
  264.  */
  265. extern int
  266. __find_bigpair(hashp, bufp, ndx, key, size)
  267.     HTAB *hashp;
  268.     BUFHEAD *bufp;
  269.     int ndx;
  270.     char *key;
  271.     int size;
  272. {
  273.     register u_short *bp;
  274.     register char *p;
  275.     int ksize;
  276.     u_short bytes;
  277.     char *kkey;
  278.  
  279.     bp = (u_short *)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 = (u_short *)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 u_short
  318. __find_last_page(hashp, bpp)
  319.     HTAB *hashp;
  320.     BUFHEAD **bpp;
  321. {
  322.     BUFHEAD *bufp;
  323.     u_short *bp, pageno;
  324.     int n;
  325.  
  326.     bufp = *bpp;
  327.     bp = (u_short *)bufp->page;
  328.     for (;;) {
  329.         n = bp[0];
  330.  
  331.         /*
  332.          * This is the last page if: the tag is FULL_KEY_DATA and
  333.          * either only 2 entries OVFLPAGE marker is explicit there
  334.          * is freespace on the page.
  335.          */
  336.         if (bp[2] == FULL_KEY_DATA &&
  337.             ((n == 2) || (bp[n] == OVFLPAGE) || (FREESPACE(bp))))
  338.             break;
  339.  
  340.         pageno = bp[n - 1];
  341.         bufp = __get_buf(hashp, pageno, bufp, 0);
  342.         if (!bufp)
  343.             return (0);    /* Need to indicate an error! */
  344.         bp = (u_short *)bufp->page;
  345.     }
  346.  
  347.     *bpp = bufp;
  348.     if (bp[0] > 2)
  349.         return (bp[3]);
  350.     else
  351.         return (0);
  352. }
  353.  
  354. /*
  355.  * Return the data for the key/data pair that begins on this page at this
  356.  * index (index should always be 1).
  357.  */
  358. extern int
  359. __big_return(hashp, bufp, ndx, val, set_current)
  360.     HTAB *hashp;
  361.     BUFHEAD *bufp;
  362.     int ndx;
  363.     DBT *val;
  364.     int set_current;
  365. {
  366.     BUFHEAD *save_p;
  367.     u_short *bp, len, off, save_addr;
  368.     char *tp;
  369.  
  370.     bp = (u_short *)bufp->page;
  371.     while (bp[ndx + 1] == PARTIAL_KEY) {
  372.         bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
  373.         if (!bufp)
  374.             return (-1);
  375.         bp = (u_short *)bufp->page;
  376.         ndx = 1;
  377.     }
  378.  
  379.     if (bp[ndx + 1] == FULL_KEY) {
  380.         bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
  381.         if (!bufp)
  382.             return (-1);
  383.         bp = (u_short *)bufp->page;
  384.         save_p = bufp;
  385.         save_addr = save_p->addr;
  386.         off = bp[1];
  387.         len = 0;
  388.     } else
  389.         if (!FREESPACE(bp)) {
  390.             /*
  391.              * This is a hack.  We can't distinguish between
  392.              * FULL_KEY_DATA that contains complete data or
  393.              * incomplete data, so we require that if the data
  394.              * is complete, there is at least 1 byte of free
  395.              * space left.
  396.              */
  397.             off = bp[bp[0]];
  398.             len = bp[1] - off;
  399.             save_p = bufp;
  400.             save_addr = bufp->addr;
  401.             bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
  402.             if (!bufp)
  403.                 return (-1);
  404.             bp = (u_short *)bufp->page;
  405.         } else {
  406.             /* The data is all on one page. */
  407.             tp = (char *)bp;
  408.             off = bp[bp[0]];
  409.             val->data = (u_char *)tp + off;
  410.             val->size = bp[1] - off;
  411.             if (set_current) {
  412.                 if (bp[0] == 2) {    /* No more buckets in
  413.                              * chain */
  414.                     hashp->cpage = NULL;
  415.                     hashp->cbucket++;
  416.                     hashp->cndx = 1;
  417.                 } else {
  418.                     hashp->cpage = __get_buf(hashp,
  419.                         bp[bp[0] - 1], bufp, 0);
  420.                     if (!hashp->cpage)
  421.                         return (-1);
  422.                     hashp->cndx = 1;
  423.                     if (!((u_short *)
  424.                         hashp->cpage->page)[0]) {
  425.                         hashp->cbucket++;
  426.                         hashp->cpage = NULL;
  427.                     }
  428.                 }
  429.             }
  430.             return (0);
  431.         }
  432.  
  433.     val->size = collect_data(hashp, bufp, (int)len, set_current);
  434.     if (val->size == -1)
  435.         return (-1);
  436.     if (save_p->addr != save_addr) {
  437.         /* We are pretty short on buffers. */
  438.         errno = EINVAL;            /* OUT OF BUFFERS */
  439.         return (-1);
  440.     }
  441.     memmove(hashp->tmp_buf, (save_p->page) + off, len);
  442.     val->data = (u_char *)hashp->tmp_buf;
  443.     return (0);
  444. }
  445. /*
  446.  * Count how big the total datasize is by recursing through the pages.  Then
  447.  * allocate a buffer and copy the data as you recurse up.
  448.  */
  449. static int
  450. collect_data(hashp, bufp, len, set)
  451.     HTAB *hashp;
  452.     BUFHEAD *bufp;
  453.     int len, set;
  454. {
  455.     register u_short *bp;
  456.     register char *p;
  457.     BUFHEAD *xbp;
  458.     u_short save_addr;
  459.     int mylen, totlen;
  460.  
  461.     p = bufp->page;
  462.     bp = (u_short *)p;
  463.     mylen = hashp->BSIZE - bp[1];
  464.     save_addr = bufp->addr;
  465.  
  466.     if (bp[2] == FULL_KEY_DATA) {        /* End of Data */
  467.         totlen = len + mylen;
  468.         if (hashp->tmp_buf)
  469.             free(hashp->tmp_buf);
  470.         hashp->tmp_buf = malloc(totlen);
  471.         if (!hashp->tmp_buf)
  472.             return (-1);
  473.         if (set) {
  474.             hashp->cndx = 1;
  475.             if (bp[0] == 2) {    /* No more buckets in chain */
  476.                 hashp->cpage = NULL;
  477.                 hashp->cbucket++;
  478.             } else {
  479.                 hashp->cpage =
  480.                     __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
  481.                 if (!hashp->cpage)
  482.                     return (-1);
  483.                 else if (!((u_short *)hashp->cpage->page)[0]) {
  484.                     hashp->cbucket++;
  485.                     hashp->cpage = NULL;
  486.                 }
  487.             }
  488.         }
  489.     } else {
  490.         xbp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
  491.         if (!xbp || ((totlen =
  492.             collect_data(hashp, xbp, len + mylen, set)) < 1))
  493.             return (-1);
  494.     }
  495.     if (bufp->addr != save_addr) {
  496.         errno = EINVAL;            /* Out of buffers. */
  497.         return (-1);
  498.     }
  499.     memmove(&hashp->tmp_buf[len], (bufp->page) + bp[1], mylen);
  500.     return (totlen);
  501. }
  502.  
  503. /*
  504.  * Fill in the key and data for this big pair.
  505.  */
  506. extern int
  507. __big_keydata(hashp, bufp, key, val, set)
  508.     HTAB *hashp;
  509.     BUFHEAD *bufp;
  510.     DBT *key, *val;
  511.     int set;
  512. {
  513.     key->size = collect_key(hashp, bufp, 0, val, set);
  514.     if (key->size == -1)
  515.         return (-1);
  516.     key->data = (u_char *)hashp->tmp_key;
  517.     return (0);
  518. }
  519.  
  520. /*
  521.  * Count how big the total key size is by recursing through the pages.  Then
  522.  * collect the data, allocate a buffer and copy the key as you recurse up.
  523.  */
  524. static int
  525. collect_key(hashp, bufp, len, val, set)
  526.     HTAB *hashp;
  527.     BUFHEAD *bufp;
  528.     int len;
  529.     DBT *val;
  530.     int set;
  531. {
  532.     BUFHEAD *xbp;
  533.     char *p;
  534.     int mylen, totlen;
  535.     u_short *bp, save_addr;
  536.  
  537.     p = bufp->page;
  538.     bp = (u_short *)p;
  539.     mylen = hashp->BSIZE - bp[1];
  540.  
  541.     save_addr = bufp->addr;
  542.     totlen = len + mylen;
  543.     if (bp[2] == FULL_KEY || bp[2] == FULL_KEY_DATA) {    /* End of Key. */
  544.         if (hashp->tmp_key)
  545.             free(hashp->tmp_key);
  546.         hashp->tmp_key = malloc(totlen);
  547.         if (!hashp->tmp_key)
  548.             return (-1);
  549.         if (__big_return(hashp, bufp, 1, val, set))
  550.             return (-1);
  551.     } else {
  552.         xbp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
  553.         if (!xbp || ((totlen =
  554.             collect_key(hashp, xbp, totlen, val, set)) < 1))
  555.             return (-1);
  556.     }
  557.     if (bufp->addr != save_addr) {
  558.         errno = EINVAL;        /* MIS -- OUT OF BUFFERS */
  559.         return (-1);
  560.     }
  561.     memmove(&hashp->tmp_key[len], (bufp->page) + bp[1], mylen);
  562.     return (totlen);
  563. }
  564.  
  565. /*
  566.  * Returns:
  567.  *  0 => OK
  568.  * -1 => error
  569.  */
  570. extern int
  571. __big_split(hashp, op, np, big_keyp, addr, obucket, ret)
  572.     HTAB *hashp;
  573.     BUFHEAD *op;    /* Pointer to where to put keys that go in old bucket */
  574.     BUFHEAD *np;    /* Pointer to new bucket page */
  575.             /* Pointer to first page containing the big key/data */
  576.     BUFHEAD *big_keyp;
  577.     int addr;    /* Address of big_keyp */
  578.     u_int   obucket;/* Old Bucket */
  579.     SPLIT_RETURN *ret;
  580. {
  581.     register BUFHEAD *tmpp;
  582.     register u_short *tp;
  583.     BUFHEAD *bp;
  584.     DBT key, val;
  585.     u_int change;
  586.     u_short free_space, n, off;
  587.  
  588.     bp = big_keyp;
  589.  
  590.     /* Now figure out where the big key/data goes */
  591.     if (__big_keydata(hashp, big_keyp, &key, &val, 0))
  592.         return (-1);
  593.     change = (__call_hash(hashp, key.data, key.size) != obucket);
  594.  
  595.     if (ret->next_addr = __find_last_page(hashp, &big_keyp)) {
  596.         if (!(ret->nextp =
  597.             __get_buf(hashp, ret->next_addr, big_keyp, 0)))
  598.             return (-1);;
  599.     } else
  600.         ret->nextp = NULL;
  601.  
  602.     /* Now make one of np/op point to the big key/data pair */
  603. #ifdef DEBUG
  604.     assert(np->ovfl == NULL);
  605. #endif
  606.     if (change)
  607.         tmpp = np;
  608.     else
  609.         tmpp = op;
  610.  
  611.     tmpp->flags |= BUF_MOD;
  612. #ifdef DEBUG1
  613.     (void)fprintf(stderr,
  614.         "BIG_SPLIT: %d->ovfl was %d is now %d\n", tmpp->addr,
  615.         (tmpp->ovfl ? tmpp->ovfl->addr : 0), (bp ? bp->addr : 0));
  616. #endif
  617.     tmpp->ovfl = bp;    /* one of op/np point to big_keyp */
  618.     tp = (u_short *)tmpp->page;
  619. #ifdef DEBUG
  620.     assert(FREESPACE(tp) >= OVFLSIZE);
  621. #endif
  622.     n = tp[0];
  623.     off = OFFSET(tp);
  624.     free_space = FREESPACE(tp);
  625.     tp[++n] = (u_short)addr;
  626.     tp[++n] = OVFLPAGE;
  627.     tp[0] = n;
  628.     OFFSET(tp) = off;
  629.     FREESPACE(tp) = free_space - OVFLSIZE;
  630.  
  631.     /*
  632.      * Finally, set the new and old return values. BIG_KEYP contains a
  633.      * pointer to the last page of the big key_data pair. Make sure that
  634.      * big_keyp has no following page (2 elements) or create an empty
  635.      * following page.
  636.      */
  637.  
  638.     ret->newp = np;
  639.     ret->oldp = op;
  640.  
  641.     tp = (u_short *)big_keyp->page;
  642.     big_keyp->flags |= BUF_MOD;
  643.     if (tp[0] > 2) {
  644.         /*
  645.          * There may be either one or two offsets on this page.  If
  646.          * there is one, then the overflow page is linked on normally
  647.          * and tp[4] is OVFLPAGE.  If there are two, tp[4] contains
  648.          * the second offset and needs to get stuffed in after the
  649.          * next overflow page is added.
  650.          */
  651.         n = tp[4];
  652.         free_space = FREESPACE(tp);
  653.         off = OFFSET(tp);
  654.         tp[0] -= 2;
  655.         FREESPACE(tp) = free_space + OVFLSIZE;
  656.         OFFSET(tp) = off;
  657.         tmpp = __add_ovflpage(hashp, big_keyp);
  658.         if (!tmpp)
  659.             return (-1);
  660.         tp[4] = n;
  661.     } else
  662.         tmpp = big_keyp;
  663.  
  664.     if (change)
  665.         ret->newp = tmpp;
  666.     else
  667.         ret->oldp = tmpp;
  668.     return (0);
  669. }
  670.