Back to index

lightning-sunbird  0.9+nobinonly
h_bigkey.c
Go to the documentation of this file.
00001 /*-
00002  * Copyright (c) 1990, 1993, 1994
00003  *     The Regents of the University of California.  All rights reserved.
00004  *
00005  * This code is derived from software contributed to Berkeley by
00006  * Margo Seltzer.
00007  *
00008  * Redistribution and use in source and binary forms, with or without
00009  * modification, are permitted provided that the following conditions
00010  * are met:
00011  * 1. Redistributions of source code must retain the above copyright
00012  *    notice, this list of conditions and the following disclaimer.
00013  * 2. Redistributions in binary form must reproduce the above copyright
00014  *    notice, this list of conditions and the following disclaimer in the
00015  *    documentation and/or other materials provided with the distribution.
00016  * 3. ***REMOVED*** - see 
00017  *    ftp://ftp.cs.berkeley.edu/pub/4bsd/README.Impt.License.Change
00018  * 4. Neither the name of the University nor the names of its contributors
00019  *    may be used to endorse or promote products derived from this software
00020  *    without specific prior written permission.
00021  *
00022  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
00023  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
00024  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
00025  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
00026  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
00027  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
00028  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
00029  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
00030  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
00031  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
00032  * SUCH DAMAGE.
00033  */
00034 
00035 #if defined(LIBC_SCCS) && !defined(lint)
00036 static char sccsid[] = "@(#)hash_bigkey.c 8.3 (Berkeley) 5/31/94";
00037 #endif /* LIBC_SCCS and not lint */
00038 
00039 #include "watcomfx.h"
00040 
00041 /*
00042  * PACKAGE: hash
00043  * DESCRIPTION:
00044  *     Big key/data handling for the hashing package.
00045  *
00046  * ROUTINES:
00047  * External
00048  *     __big_keydata
00049  *     __big_split
00050  *     __big_insert
00051  *     __big_return
00052  *     __big_delete
00053  *     __find_last_page
00054  * Internal
00055  *     collect_key
00056  *     collect_data
00057  */
00058 
00059 #if !defined(_WIN32) && !defined(_WINDOWS) && !defined(macintosh) && !defined(XP_OS2_VACPP)
00060 #include <sys/param.h>
00061 #endif
00062 
00063 #include <errno.h>
00064 #include <stdio.h>
00065 #include <stdlib.h>
00066 #include <string.h>
00067 
00068 #ifdef DEBUG
00069 #include <assert.h>
00070 #endif
00071 
00072 #include "mcom_db.h"
00073 #include "hash.h"
00074 #include "page.h"
00075 /* #include "extern.h" */
00076 
00077 static int collect_key __P((HTAB *, BUFHEAD *, int, DBT *, int));
00078 static int collect_data __P((HTAB *, BUFHEAD *, int, int));
00079 
00080 /*
00081  * Big_insert
00082  *
00083  * You need to do an insert and the key/data pair is too big
00084  *
00085  * Returns:
00086  * 0 ==> OK
00087  *-1 ==> ERROR
00088  */
00089 extern int
00090 __big_insert(HTAB *hashp, BUFHEAD *bufp, const DBT *key, const DBT *val)
00091 {
00092        register uint16 *p;
00093        uint key_size, n, val_size;
00094        uint16 space, move_bytes, off;
00095        char *cp, *key_data, *val_data;
00096 
00097        cp = bufp->page;            /* Character pointer of p. */
00098        p = (uint16 *)cp;
00099 
00100        key_data = (char *)key->data;
00101        key_size = key->size;
00102        val_data = (char *)val->data;
00103        val_size = val->size;
00104 
00105        /* First move the Key */
00106        for (space = FREESPACE(p) - BIGOVERHEAD; key_size;
00107            space = FREESPACE(p) - BIGOVERHEAD) {
00108               move_bytes = PR_MIN(space, key_size);
00109               off = OFFSET(p) - move_bytes;
00110               memmove(cp + off, key_data, move_bytes);
00111               key_size -= move_bytes;
00112               key_data += move_bytes;
00113               n = p[0];
00114               p[++n] = off;
00115               p[0] = ++n;
00116               FREESPACE(p) = off - PAGE_META(n);
00117               OFFSET(p) = off;
00118               p[n] = PARTIAL_KEY;
00119               bufp = __add_ovflpage(hashp, bufp);
00120               if (!bufp)
00121                      return (-1);
00122               n = p[0];
00123               if (!key_size) {
00124                      if (FREESPACE(p)) {
00125                             move_bytes = PR_MIN(FREESPACE(p), val_size);
00126                             off = OFFSET(p) - move_bytes;
00127                             p[n] = off;
00128                             memmove(cp + off, val_data, move_bytes);
00129                             val_data += move_bytes;
00130                             val_size -= move_bytes;
00131                             p[n - 2] = FULL_KEY_DATA;
00132                             FREESPACE(p) = FREESPACE(p) - move_bytes;
00133                             OFFSET(p) = off;
00134                      } else
00135                             p[n - 2] = FULL_KEY;
00136               }
00137               p = (uint16 *)bufp->page;
00138               cp = bufp->page;
00139               bufp->flags |= BUF_MOD;
00140        }
00141 
00142        /* Now move the data */
00143        for (space = FREESPACE(p) - BIGOVERHEAD; val_size;
00144            space = FREESPACE(p) - BIGOVERHEAD) {
00145               move_bytes = PR_MIN(space, val_size);
00146               /*
00147                * Here's the hack to make sure that if the data ends on the
00148                * same page as the key ends, FREESPACE is at least one.
00149                */
00150               if (space == val_size && val_size == val->size)
00151                      move_bytes--;
00152               off = OFFSET(p) - move_bytes;
00153               memmove(cp + off, val_data, move_bytes);
00154               val_size -= move_bytes;
00155               val_data += move_bytes;
00156               n = p[0];
00157               p[++n] = off;
00158               p[0] = ++n;
00159               FREESPACE(p) = off - PAGE_META(n);
00160               OFFSET(p) = off;
00161               if (val_size) {
00162                      p[n] = FULL_KEY;
00163                      bufp = __add_ovflpage(hashp, bufp);
00164                      if (!bufp)
00165                             return (-1);
00166                      cp = bufp->page;
00167                      p = (uint16 *)cp;
00168               } else
00169                      p[n] = FULL_KEY_DATA;
00170               bufp->flags |= BUF_MOD;
00171        }
00172        return (0);
00173 }
00174 
00175 /*
00176  * Called when bufp's page  contains a partial key (index should be 1)
00177  *
00178  * All pages in the big key/data pair except bufp are freed.  We cannot
00179  * free bufp because the page pointing to it is lost and we can't get rid
00180  * of its pointer.
00181  *
00182  * Returns:
00183  * 0 => OK
00184  *-1 => ERROR
00185  */
00186 extern int
00187 __big_delete(HTAB *hashp, BUFHEAD *bufp)
00188 {
00189        register BUFHEAD *last_bfp, *rbufp;
00190        uint16 *bp, pageno;
00191        int key_done, n;
00192 
00193        rbufp = bufp;
00194        last_bfp = NULL;
00195        bp = (uint16 *)bufp->page;
00196        pageno = 0;
00197        key_done = 0;
00198 
00199        while (!key_done || (bp[2] != FULL_KEY_DATA)) {
00200               if (bp[2] == FULL_KEY || bp[2] == FULL_KEY_DATA)
00201                      key_done = 1;
00202 
00203               /*
00204                * If there is freespace left on a FULL_KEY_DATA page, then
00205                * the data is short and fits entirely on this page, and this
00206                * is the last page.
00207                */
00208               if (bp[2] == FULL_KEY_DATA && FREESPACE(bp))
00209                      break;
00210               pageno = bp[bp[0] - 1];
00211               rbufp->flags |= BUF_MOD;
00212               rbufp = __get_buf(hashp, pageno, rbufp, 0);
00213               if (last_bfp)
00214                      __free_ovflpage(hashp, last_bfp);
00215               last_bfp = rbufp;
00216               if (!rbufp)
00217                      return (-1);         /* Error. */
00218               bp = (uint16 *)rbufp->page;
00219        }
00220 
00221        /*
00222         * If we get here then rbufp points to the last page of the big
00223         * key/data pair.  Bufp points to the first one -- it should now be
00224         * empty pointing to the next page after this pair.  Can't free it
00225         * because we don't have the page pointing to it.
00226         */
00227 
00228        /* This is information from the last page of the pair. */
00229        n = bp[0];
00230        pageno = bp[n - 1];
00231 
00232        /* Now, bp is the first page of the pair. */
00233        bp = (uint16 *)bufp->page;
00234        if (n > 2) {
00235               /* There is an overflow page. */
00236               bp[1] = pageno;
00237               bp[2] = OVFLPAGE;
00238               bufp->ovfl = rbufp->ovfl;
00239        } else
00240               /* This is the last page. */
00241               bufp->ovfl = NULL;
00242        n -= 2;
00243        bp[0] = n;
00244        FREESPACE(bp) = hashp->BSIZE - PAGE_META(n);
00245        OFFSET(bp) = hashp->BSIZE - 1;
00246 
00247        bufp->flags |= BUF_MOD;
00248        if (rbufp)
00249               __free_ovflpage(hashp, rbufp);
00250        if (last_bfp != rbufp)
00251               __free_ovflpage(hashp, last_bfp);
00252 
00253        hashp->NKEYS--;
00254        return (0);
00255 }
00256 /*
00257  * Returns:
00258  *  0 = key not found
00259  * -1 = get next overflow page
00260  * -2 means key not found and this is big key/data
00261  * -3 error
00262  */
00263 extern int
00264 __find_bigpair(HTAB *hashp, BUFHEAD *bufp, int ndx, char *key, int size)
00265 {
00266        register uint16 *bp;
00267        register char *p;
00268        int ksize;
00269        uint16 bytes;
00270        char *kkey;
00271 
00272        bp = (uint16 *)bufp->page;
00273        p = bufp->page;
00274        ksize = size;
00275        kkey = key;
00276 
00277        for (bytes = hashp->BSIZE - bp[ndx];
00278            bytes <= size && bp[ndx + 1] == PARTIAL_KEY;
00279            bytes = hashp->BSIZE - bp[ndx]) {
00280               if (memcmp(p + bp[ndx], kkey, bytes))
00281                      return (-2);
00282               kkey += bytes;
00283               ksize -= bytes;
00284               bufp = __get_buf(hashp, bp[ndx + 2], bufp, 0);
00285               if (!bufp)
00286                      return (-3);
00287               p = bufp->page;
00288               bp = (uint16 *)p;
00289               ndx = 1;
00290        }
00291 
00292        if (bytes != ksize || memcmp(p + bp[ndx], kkey, bytes)) {
00293 #ifdef HASH_STATISTICS
00294               ++hash_collisions;
00295 #endif
00296               return (-2);
00297        } else
00298               return (ndx);
00299 }
00300 
00301 /*
00302  * Given the buffer pointer of the first overflow page of a big pair,
00303  * find the end of the big pair
00304  *
00305  * This will set bpp to the buffer header of the last page of the big pair.
00306  * It will return the pageno of the overflow page following the last page
00307  * of the pair; 0 if there isn't any (i.e. big pair is the last key in the
00308  * bucket)
00309  */
00310 extern uint16
00311 __find_last_page(HTAB *hashp, BUFHEAD **bpp)
00312 {
00313        BUFHEAD *bufp;
00314        uint16 *bp, pageno;
00315        uint n;
00316 
00317        bufp = *bpp;
00318        bp = (uint16 *)bufp->page;
00319        for (;;) {
00320               n = bp[0];
00321 
00322               /*
00323                * This is the last page if: the tag is FULL_KEY_DATA and
00324                * either only 2 entries OVFLPAGE marker is explicit there
00325                * is freespace on the page.
00326                */
00327               if (bp[2] == FULL_KEY_DATA &&
00328                   ((n == 2) || (bp[n] == OVFLPAGE) || (FREESPACE(bp))))
00329                      break;
00330 
00331               /* LJM bound the size of n to reasonable limits
00332                */
00333               if(n > hashp->BSIZE/sizeof(uint16))
00334                      return(0);
00335 
00336               pageno = bp[n - 1];
00337               bufp = __get_buf(hashp, pageno, bufp, 0);
00338               if (!bufp)
00339                      return (0);   /* Need to indicate an error! */
00340               bp = (uint16 *)bufp->page;
00341        }
00342 
00343        *bpp = bufp;
00344        if (bp[0] > 2)
00345               return (bp[3]);
00346        else
00347               return (0);
00348 }
00349 
00350 /*
00351  * Return the data for the key/data pair that begins on this page at this
00352  * index (index should always be 1).
00353  */
00354 extern int
00355 __big_return(
00356        HTAB *hashp,
00357        BUFHEAD *bufp,
00358        int ndx,
00359        DBT *val,
00360        int set_current)
00361 {
00362        BUFHEAD *save_p;
00363        uint16 *bp, len, off, save_addr;
00364        char *tp;
00365        int save_flags;
00366 
00367        bp = (uint16 *)bufp->page;
00368        while (bp[ndx + 1] == PARTIAL_KEY) {
00369               bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
00370               if (!bufp)
00371                      return (-1);
00372               bp = (uint16 *)bufp->page;
00373               ndx = 1;
00374        }
00375 
00376        if (bp[ndx + 1] == FULL_KEY) {
00377               bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
00378               if (!bufp)
00379                      return (-1);
00380               bp = (uint16 *)bufp->page;
00381               save_p = bufp;
00382               save_addr = save_p->addr;
00383               off = bp[1];
00384               len = 0;
00385        } else
00386               if (!FREESPACE(bp)) {
00387                      /*
00388                       * This is a hack.  We can't distinguish between
00389                       * FULL_KEY_DATA that contains complete data or
00390                       * incomplete data, so we require that if the data
00391                       * is complete, there is at least 1 byte of free
00392                       * space left.
00393                       */
00394                      off = bp[bp[0]];
00395                      len = bp[1] - off;
00396                      save_p = bufp;
00397                      save_addr = bufp->addr;
00398                      bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
00399                      if (!bufp)
00400                             return (-1);
00401                      bp = (uint16 *)bufp->page;
00402               } else {
00403                      /* The data is all on one page. */
00404                      tp = (char *)bp;
00405                      off = bp[bp[0]];
00406                      val->data = (uint8 *)tp + off;
00407                      val->size = bp[1] - off;
00408                      if (set_current) {
00409                             if (bp[0] == 2) {    /* No more buckets in
00410                                                   * chain */
00411                                    hashp->cpage = NULL;
00412                                    hashp->cbucket++;
00413                                    hashp->cndx = 1;
00414                             } else {
00415                                    hashp->cpage = __get_buf(hashp,
00416                                        bp[bp[0] - 1], bufp, 0);
00417                                    if (!hashp->cpage)
00418                                           return (-1);
00419                                    hashp->cndx = 1;
00420                                    if (!((uint16 *)
00421                                        hashp->cpage->page)[0]) {
00422                                           hashp->cbucket++;
00423                                           hashp->cpage = NULL;
00424                                    }
00425                             }
00426                      }
00427                      return (0);
00428               }
00429 
00430        /* pin our saved buf so that we don't lose if 
00431         * we run out of buffers */
00432        save_flags = save_p->flags;
00433        save_p->flags |= BUF_PIN;
00434        val->size = collect_data(hashp, bufp, (int)len, set_current);
00435        save_p->flags = save_flags;
00436        if (val->size == (size_t)-1)
00437               return (-1);
00438        if (save_p->addr != save_addr) {
00439               /* We are pretty short on buffers. */
00440               errno = EINVAL;                    /* OUT OF BUFFERS */
00441               return (-1);
00442        }
00443        memmove(hashp->tmp_buf, (save_p->page) + off, len);
00444        val->data = (uint8 *)hashp->tmp_buf;
00445        return (0);
00446 }
00447 
00448 
00449 /*
00450  * Count how big the total datasize is by looping through the pages.  Then
00451  * allocate a buffer and copy the data in the second loop. NOTE: Our caller
00452  * may already have a bp which it is holding onto. The caller is
00453  * responsible for copying that bp into our temp buffer. 'len' is how much
00454  * space to reserve for that buffer.
00455  */
00456 static int
00457 collect_data(
00458        HTAB *hashp,
00459        BUFHEAD *bufp,
00460        int len, int set)
00461 {
00462        register uint16 *bp;
00463        BUFHEAD *save_bufp;
00464        int save_flags;
00465        int mylen, totlen;
00466 
00467        /*
00468         * save the input buf head because we need to walk the list twice.
00469         * pin it to make sure it doesn't leave the buffer pool. 
00470         * This has the effect of growing the buffer pool if necessary.
00471         */
00472        save_bufp = bufp;
00473        save_flags = save_bufp->flags;
00474        save_bufp->flags |= BUF_PIN;
00475 
00476        /* read the length of the buffer */
00477        for (totlen = len; bufp ; bufp = __get_buf(hashp, bp[bp[0]-1], bufp, 0)) {
00478               bp = (uint16 *)bufp->page;
00479               mylen = hashp->BSIZE - bp[1];
00480 
00481               /* if mylen ever goes negative it means that the
00482                * page is screwed up.
00483                */
00484               if (mylen < 0) {
00485                      save_bufp->flags = save_flags;
00486                      return (-1);
00487               }
00488               totlen += mylen;
00489               if (bp[2] == FULL_KEY_DATA) {             /* End of Data */
00490                      break;
00491               }
00492        }
00493 
00494        if (!bufp) {
00495               save_bufp->flags = save_flags;
00496               return (-1);
00497        }
00498 
00499        /* allocate a temp buf */
00500        if (hashp->tmp_buf)
00501               free(hashp->tmp_buf);
00502        if ((hashp->tmp_buf = (char *)malloc((size_t)totlen)) == NULL) {
00503               save_bufp->flags = save_flags;
00504               return (-1);
00505        }
00506 
00507        /* copy the buffers back into temp buf */
00508        for (bufp = save_bufp; bufp ;
00509                             bufp = __get_buf(hashp, bp[bp[0]-1], bufp, 0)) {
00510               bp = (uint16 *)bufp->page;
00511               mylen = hashp->BSIZE - bp[1];
00512               memmove(&hashp->tmp_buf[len], (bufp->page) + bp[1], (size_t)mylen);
00513               len += mylen;
00514               if (bp[2] == FULL_KEY_DATA) {
00515                      break;
00516               }
00517        }
00518 
00519        /* 'clear' the pin flags */
00520        save_bufp->flags = save_flags;
00521 
00522        /* update the database cursor */
00523        if (set) {
00524               hashp->cndx = 1;
00525               if (bp[0] == 2) {    /* No more buckets in chain */
00526                      hashp->cpage = NULL;
00527                      hashp->cbucket++;
00528               } else {
00529                      hashp->cpage = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
00530                      if (!hashp->cpage)
00531                             return (-1);
00532                      else if (!((uint16 *)hashp->cpage->page)[0]) {
00533                             hashp->cbucket++;
00534                             hashp->cpage = NULL;
00535                      }
00536               }
00537        }
00538        return (totlen);
00539 }
00540 
00541 /*
00542  * Fill in the key and data for this big pair.
00543  */
00544 extern int
00545 __big_keydata(
00546        HTAB *hashp, 
00547        BUFHEAD *bufp, 
00548        DBT *key, DBT *val,
00549        int set)
00550 {
00551        key->size = collect_key(hashp, bufp, 0, val, set);
00552        if (key->size == (size_t)-1)
00553               return (-1);
00554        key->data = (uint8 *)hashp->tmp_key;
00555        return (0);
00556 }
00557 
00558 /*
00559  * Count how big the total key size is by recursing through the pages.  Then
00560  * collect the data, allocate a buffer and copy the key as you recurse up.
00561  */
00562 static int
00563 collect_key(
00564        HTAB *hashp,
00565        BUFHEAD *bufp,
00566        int len,
00567        DBT *val,
00568        int set)
00569 {
00570        BUFHEAD *xbp;
00571        char *p;
00572        int mylen, totlen;
00573        uint16 *bp, save_addr;
00574 
00575        p = bufp->page;
00576        bp = (uint16 *)p;
00577        mylen = hashp->BSIZE - bp[1];
00578 
00579        save_addr = bufp->addr;
00580        totlen = len + mylen;
00581        if (bp[2] == FULL_KEY || bp[2] == FULL_KEY_DATA) {    /* End of Key. */
00582               if (hashp->tmp_key != NULL)
00583                      free(hashp->tmp_key);
00584               if ((hashp->tmp_key = (char *)malloc((size_t)totlen)) == NULL)
00585                      return (-1);
00586               if (__big_return(hashp, bufp, 1, val, set))
00587                      return (-1);
00588        } else {
00589               xbp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
00590               if (!xbp || ((totlen =
00591                   collect_key(hashp, xbp, totlen, val, set)) < 1))
00592                      return (-1);
00593        }
00594        if (bufp->addr != save_addr) {
00595               errno = EINVAL;             /* MIS -- OUT OF BUFFERS */
00596               return (-1);
00597        }
00598        memmove(&hashp->tmp_key[len], (bufp->page) + bp[1], (size_t)mylen);
00599        return (totlen);
00600 }
00601 
00602 /*
00603  * Returns:
00604  *  0 => OK
00605  * -1 => error
00606  */
00607 extern int
00608 __big_split(
00609        HTAB *hashp,
00610        BUFHEAD *op,  /* Pointer to where to put keys that go in old bucket */
00611        BUFHEAD *np,  /* Pointer to new bucket page */
00612                      /* Pointer to first page containing the big key/data */
00613        BUFHEAD *big_keyp,
00614        uint32 addr,  /* Address of big_keyp */
00615        uint32   obucket,/* Old Bucket */
00616        SPLIT_RETURN *ret)
00617 {
00618        register BUFHEAD *tmpp;
00619        register uint16 *tp;
00620        BUFHEAD *bp;
00621        DBT key, val;
00622        uint32 change;
00623        uint16 free_space, n, off;
00624 
00625        bp = big_keyp;
00626 
00627        /* Now figure out where the big key/data goes */
00628        if (__big_keydata(hashp, big_keyp, &key, &val, 0))
00629               return (-1);
00630        change = (__call_hash(hashp,(char*) key.data, key.size) != obucket);
00631 
00632        if ((ret->next_addr = __find_last_page(hashp, &big_keyp))) {
00633               if (!(ret->nextp =
00634                   __get_buf(hashp, ret->next_addr, big_keyp, 0)))
00635                      return (-1);;
00636        } else
00637               ret->nextp = NULL;
00638 
00639        /* Now make one of np/op point to the big key/data pair */
00640 #ifdef DEBUG
00641        assert(np->ovfl == NULL);
00642 #endif
00643        if (change)
00644               tmpp = np;
00645        else
00646               tmpp = op;
00647 
00648        tmpp->flags |= BUF_MOD;
00649 #ifdef DEBUG1
00650        (void)fprintf(stderr,
00651            "BIG_SPLIT: %d->ovfl was %d is now %d\n", tmpp->addr,
00652            (tmpp->ovfl ? tmpp->ovfl->addr : 0), (bp ? bp->addr : 0));
00653 #endif
00654        tmpp->ovfl = bp;     /* one of op/np point to big_keyp */
00655        tp = (uint16 *)tmpp->page;
00656 
00657 
00658 #if 0  /* this get's tripped on database corrupted error */
00659        assert(FREESPACE(tp) >= OVFLSIZE);
00660 #endif
00661        if(FREESPACE(tp) < OVFLSIZE)
00662               return(DATABASE_CORRUPTED_ERROR);
00663 
00664        n = tp[0];
00665        off = OFFSET(tp);
00666        free_space = FREESPACE(tp);
00667        tp[++n] = (uint16)addr;
00668        tp[++n] = OVFLPAGE;
00669        tp[0] = n;
00670        OFFSET(tp) = off;
00671        FREESPACE(tp) = free_space - OVFLSIZE;
00672 
00673        /*
00674         * Finally, set the new and old return values. BIG_KEYP contains a
00675         * pointer to the last page of the big key_data pair. Make sure that
00676         * big_keyp has no following page (2 elements) or create an empty
00677         * following page.
00678         */
00679 
00680        ret->newp = np;
00681        ret->oldp = op;
00682 
00683        tp = (uint16 *)big_keyp->page;
00684        big_keyp->flags |= BUF_MOD;
00685        if (tp[0] > 2) {
00686               /*
00687                * There may be either one or two offsets on this page.  If
00688                * there is one, then the overflow page is linked on normally
00689                * and tp[4] is OVFLPAGE.  If there are two, tp[4] contains
00690                * the second offset and needs to get stuffed in after the
00691                * next overflow page is added.
00692                */
00693               n = tp[4];
00694               free_space = FREESPACE(tp);
00695               off = OFFSET(tp);
00696               tp[0] -= 2;
00697               FREESPACE(tp) = free_space + OVFLSIZE;
00698               OFFSET(tp) = off;
00699               tmpp = __add_ovflpage(hashp, big_keyp);
00700               if (!tmpp)
00701                      return (-1);
00702               tp[4] = n;
00703        } else
00704               tmpp = big_keyp;
00705 
00706        if (change)
00707               ret->newp = tmpp;
00708        else
00709               ret->oldp = tmpp;
00710        return (0);
00711 }