home *** CD-ROM | disk | FTP | other *** search
/ ftp.mactech.com 2010 / ftp.mactech.com.tar / ftp.mactech.com / online / source / c / compilers / Tickle-4.0.sit.hqx / Tickle-4.0 / cbtree / src / split.c < prev    next >
Text File  |  1993-05-22  |  17KB  |  678 lines
  1.  
  2. #include <types.h>
  3. #include "db.h"
  4. #include <stdlib.h>
  5. #include <string.h>
  6. #include <stdio.h>
  7. #include "btree.h"
  8.  
  9. /*
  10.  *  _BT_SPLIT -- Split a page into two pages.
  11.  *
  12.  *    Splits are caused by insertions, and propogate up the tree in
  13.  *    the usual way.  The root page is always page 1 in the file on
  14.  *    disk, so root splits are handled specially.  On entry to this
  15.  *    routine, t->bt_curpage is the page to be split.
  16.  *
  17.  *    Parameters:
  18.  *        t -- btree in which to do split.
  19.  *
  20.  *    Returns:
  21.  *        RET_SUCCESS, RET_ERROR.
  22.  *
  23.  *    Side Effects:
  24.  *        Changes the notion of the current page.
  25.  */
  26.  
  27. int
  28. _bt_split(t)
  29.     BTREE_P t;
  30. {
  31.     BTHEADER *h;
  32.     BTHEADER *left, *right;
  33.     pgno_t nextpgno, parent;
  34.     int nbytes, len;
  35.     IDATUM *id;
  36.     DATUM *d;
  37.     char *src;
  38.     IDATUM *new;
  39.     pgno_t oldchain;
  40.     u_char flags;
  41.  
  42.     h = (BTHEADER *) t->bt_curpage;
  43.  
  44.     /* split root page specially, since it must remain page 1 */
  45.     if (h->h_pgno == P_ROOT) {
  46.         int result;
  47.         
  48.         result = (_bt_splitroot(t));
  49.         return result;
  50.     }
  51.  
  52.     /*
  53.      *  This is a little complicated.  We go to some trouble to
  54.      *  figure out which of the three possible cases -- in-memory tree,
  55.      *  disk tree (no cache), and disk tree (cache) -- we have, in order
  56.      *  to avoid unnecessary copying.  If we have a disk cache, then we
  57.      *  have to do some extra copying, though, since the cache code
  58.      *  manages buffers externally to this code.
  59.      */
  60.  
  61.     if (ISDISK(t) && ISCACHE(t)) {
  62.         if ((left = (BTHEADER *) cbMALLOC((unsigned) t->bt_psize))
  63.             == (BTHEADER *) NULL)
  64.             return (RET_ERROR);
  65.         left->h_pgno = left->h_prevpg = left->h_nextpg = P_NONE;
  66.         left->h_flags = t->bt_curpage->h_flags;
  67.         left->h_lower = (index_t)
  68.               (((char *) &(left->h_linp[0])) - ((char *) left));
  69.         left->h_upper = t->bt_psize;
  70.     } else {
  71.         if ((left = _bt_allocpg(t)) == (BTHEADER *) NULL)
  72.             return (RET_ERROR);
  73.     }
  74.     left->h_pgno = h->h_pgno;
  75.  
  76.     if ((right = _bt_allocpg(t)) == (BTHEADER *) NULL)
  77.         return (RET_ERROR);
  78.     right->h_pgno = ++(t->bt_npages);
  79.  
  80.     /* now do the split */
  81.     if (_bt_dopsplit(t, left, right) == RET_ERROR)
  82.         {
  83.         return (RET_ERROR);
  84.         }
  85.  
  86.     right->h_prevpg = left->h_pgno;
  87.     nextpgno = right->h_nextpg = h->h_nextpg;
  88.     left->h_nextpg = right->h_pgno;
  89.     left->h_prevpg = h->h_prevpg;
  90.  
  91.     /* okay, now use the left half of the page as the new page */
  92.     if (ISDISK(t) && ISCACHE(t)) {
  93.         bcopy((char *) left, (char *) t->bt_curpage,
  94.                  (int) t->bt_psize);
  95.         FREE ((char *) left);
  96.         left = t->bt_curpage;
  97.     } else {
  98.         FREE((char *) t->bt_curpage);
  99.         t->bt_curpage = left;
  100.     }
  101.  
  102.     /*
  103.      *  Write the new pages out.  We need them to stay where they are
  104.      *  until we're done updating the parent pages.
  105.      */
  106.  
  107.     if (_bt_write(t, left, NORELEASE) == RET_ERROR)
  108.         {
  109.         return (RET_ERROR);
  110.         }
  111.     if (_bt_write(t, right, NORELEASE) == RET_ERROR)
  112.         {
  113.         return (RET_ERROR);
  114.         }
  115.  
  116.     /* update 'prev' pointer of old neighbor of left */
  117.     if (nextpgno != P_NONE) {
  118.         if (_bt_getpage(t, nextpgno) == RET_ERROR)
  119.             return (RET_ERROR);
  120.         h = t->bt_curpage;
  121.         h->h_prevpg = right->h_pgno;
  122.         h->h_flags |= F_DIRTY;
  123.     }
  124.  
  125.     if ((parent = _bt_pop(t)) != P_NONE) {
  126.         if (right->h_flags & F_LEAF) {
  127.             d = (DATUM *) GETDATUM(right, 0);
  128.             len = d->d_ksize;
  129.             if (d->d_flags & D_BIGKEY) {
  130.                 bcopy(&(d->d_bytes[0]),
  131.                       (char *) &oldchain,
  132.                       sizeof(oldchain));
  133.                 if (_bt_markchain(t, oldchain) == RET_ERROR)
  134.                     return (RET_ERROR);
  135.                 src = (char *) &oldchain;
  136.                 flags = D_BIGKEY;
  137.             } else {
  138.                 src = (char *) &(d->d_bytes[0]);
  139.                 flags = 0;
  140.             }
  141.         } else {
  142.             id = (IDATUM *) GETDATUM(right, 0);
  143.             len = id->i_size;
  144.             flags = id->i_flags;
  145.             src = (char *) &(id->i_bytes[0]);
  146.         }
  147.         nbytes = len + (sizeof(IDATUM) - sizeof(char));
  148.         new = (IDATUM *) cbMALLOC((unsigned) nbytes);
  149.         if (new == (IDATUM *) NULL)
  150.             return (RET_ERROR);
  151.         new->i_size = len;
  152.         new->i_pgno = right->h_pgno;
  153.         new->i_flags = flags;
  154.         if (len > 0)
  155.             bcopy(src, (char *) &(new->i_bytes[0]), len);
  156.  
  157.         nbytes = LONGALIGN(nbytes) + sizeof(index_t);
  158.         if (_bt_getpage(t, parent) == RET_ERROR)
  159.             {            /* TGE */
  160.             FREE(new);    /* TGE */
  161.             return (RET_ERROR);
  162.             }            /* TGE */
  163.  
  164.         h = t->bt_curpage;
  165.  
  166.         /*
  167.          *  Split the parent if we need to, then reposition the
  168.          *  tree's current page pointer for the new datum.
  169.          */
  170.         if ((h->h_upper - h->h_lower) < nbytes) {
  171.             if (_bt_split(t) == RET_ERROR)
  172.                 {            /* TGE */
  173.                 FREE(new);    /* TGE */
  174.                 return (RET_ERROR);
  175.                 }            /* TGE */
  176.             if (_bt_reposition(t, new, parent, right->h_prevpg)
  177.                   == RET_ERROR)
  178.                 {            /* TGE */
  179.                 FREE(new);    /* TGE */
  180.                 return (RET_ERROR);
  181.                 }            /* TGE */
  182.             }
  183.  
  184.         /* okay, now insert the new idatum */
  185.         if (_bt_inserti(t, new, right->h_prevpg) == RET_ERROR)
  186.             {            /* TGE */
  187.             FREE(new);    /* TGE */
  188.             return (RET_ERROR);
  189.             }            /* TGE */
  190.         
  191.         FREE(new);    /* TGE */
  192.         }
  193.  
  194.     /*
  195.      *  Okay, split is done; don't need right page stapled down anymore.
  196.      *  The page we call 'left' above is the new version of the old
  197.      *  (split) page, so we can't release it.
  198.      */
  199.  
  200.     if (_bt_release(t, right) == RET_ERROR)
  201.         return (RET_ERROR);
  202.     if (ISDISK(t) && !ISCACHE(t))
  203.         FREE((char *) right);
  204.  
  205.     return (RET_SUCCESS);
  206. }
  207.  
  208. /*
  209.  *  _BT_REPOSITION -- Reposition the current page pointer of a btree.
  210.  *
  211.  *    After splitting a node in the tree in order to make room for
  212.  *    an insertion, we need to figure out which page after the split
  213.  *    should get the item we want to insert.  This routine positions
  214.  *    the tree's current page pointer appropriately.
  215.  *
  216.  *    Parameters:
  217.  *        t -- tree to position
  218.  *        new -- the item we want to insert
  219.  *        parent -- parent of the node that we just split
  220.  *        prev -- page number of item directly to the left of
  221.  *            new's position in the tree.
  222.  *
  223.  *    Returns:
  224.  *        RET_SUCCESS, RET_ERROR.
  225.  *
  226.  *    Side Effects:
  227.  *        None.
  228.  */
  229.  
  230. int
  231. _bt_reposition(t, new, parent, prev)
  232.     BTREE_P t;
  233.     IDATUM *new;
  234.     pgno_t parent;
  235.     pgno_t prev;
  236. {
  237.     index_t i, next;
  238.     IDATUM *idx;
  239.  
  240.  
  241.     if (parent == P_ROOT) {
  242.         /*
  243.          *  If we just split the root page, then there are guaranteed
  244.          *  to be exactly two IDATUMs on it.  Look at both of them
  245.          *  to see if they point to the page that we want.
  246.          */
  247.  
  248.         if (_bt_getpage(t, parent) == RET_ERROR)
  249.             return (RET_ERROR);
  250.  
  251.         next = NEXTINDEX(t->bt_curpage);
  252.         for (i = 0; i < next; i++) {
  253.             idx = (IDATUM *) GETDATUM(t->bt_curpage, i);
  254.             if (_bt_getpage(t, idx->i_pgno) == RET_ERROR)
  255.                 return (RET_ERROR);
  256.             if (_bt_isonpage(t, new, prev) == RET_SUCCESS)
  257.                 return (RET_SUCCESS);
  258.             if (_bt_getpage(t, parent) == RET_ERROR)
  259.                 return (RET_ERROR);
  260.         }
  261.     } else {
  262.  
  263.         /*
  264.          *  Get the parent page -- which is where the new item would
  265.          *  have gone -- and figure out whether the new item now goes
  266.          *  on the parent, or the page immediately to the right of
  267.          *  the parent.
  268.          */
  269.  
  270.         if (_bt_getpage(t, parent) == RET_ERROR)
  271.             return (RET_ERROR);
  272.         if (_bt_isonpage(t, new, prev) == RET_SUCCESS)
  273.             return (RET_SUCCESS);
  274.         if (_bt_getpage(t, t->bt_curpage->h_nextpg) == RET_ERROR)
  275.             return (RET_ERROR);
  276.         if (_bt_isonpage(t, new, prev) == RET_SUCCESS)
  277.             return (RET_SUCCESS);
  278.     }
  279.     return (RET_ERROR);
  280. }
  281.  
  282. /*
  283.  *  _BT_ISONPAGE -- Is the IDATUM for a given page number on the current page?
  284.  *
  285.  *    This routine is used by _bt_reposition to decide whether the current
  286.  *    page is the correct one on which to insert a new item.
  287.  *
  288.  *    Parameters:
  289.  *        t -- tree to check
  290.  *        new -- the item that will be inserted (used for binary search)
  291.  *        prev -- page number of page whose IDATUM is immediately to
  292.  *            the left of new's position in the tree.
  293.  *
  294.  *    Returns:
  295.  *        RET_SUCCESS, RET_ERROR (corresponding to TRUE, FALSE).
  296.  */
  297.  
  298. int
  299. _bt_isonpage(t, new, prev)
  300.     BTREE_P t;
  301.     IDATUM *new;
  302.     pgno_t prev;
  303. {
  304.     BTHEADER *h = (BTHEADER *) t->bt_curpage;
  305.     index_t i, next;
  306.     IDATUM *idx;
  307.  
  308.     i = _bt_binsrch(t, &(new->i_bytes[0]));
  309.     while (i != 0 && _bt_cmp(t, &(new->i_bytes[0]), i) == 0)
  310.         --i;
  311.     next = NEXTINDEX(h);
  312.     idx = (IDATUM *) GETDATUM(h, i);
  313.     while (i < next && idx->i_pgno != prev) {
  314.         i++;
  315.         idx = (IDATUM *) GETDATUM(h, i);
  316.     }
  317.     if (idx->i_pgno == prev)
  318.         return (RET_SUCCESS);
  319.     else
  320.         return (RET_ERROR);
  321. }
  322.  
  323. /*
  324.  *  _BT_SPLITROOT -- Split the root of a btree.
  325.  *
  326.  *    The root page for a btree is always page one.  This means that in
  327.  *    order to split the root, we need to do extra work.
  328.  *
  329.  *    Parameters:
  330.  *        t -- tree to split
  331.  *
  332.  *    Returns:
  333.  *        RET_SUCCESS, RET_ERROR.
  334.  *
  335.  *    Side Effects:
  336.  *        Splits root upward in the usual way, adding two new pages
  337.  *        to the tree (rather than just one, as in usual splits).
  338.  */
  339.  
  340. int
  341. _bt_splitroot(t)
  342.     BTREE_P t;
  343. {
  344.     BTHEADER *h = t->bt_curpage;
  345.     BTHEADER *left, *right;
  346.     IDATUM *id;
  347.     BTHEADER *where_h;
  348.     char *src, *dest;
  349.     int len, nbytes;
  350.     u_long was_leaf;
  351.     pgno_t oldchain;
  352.     u_char flags;
  353.  
  354.     /* get two new pages for the split */
  355.     if ((left = _bt_allocpg(t)) == (BTHEADER *) NULL)
  356.         return (RET_ERROR);
  357.     left->h_pgno = ++(t->bt_npages);
  358.     if ((right = _bt_allocpg(t)) == (BTHEADER *) NULL)
  359.         return (RET_ERROR);
  360.     right->h_pgno = ++(t->bt_npages);
  361.  
  362.     /* do the split */
  363.     if (_bt_dopsplit(t, left, right) == RET_ERROR)
  364.         return (RET_ERROR);
  365.  
  366.     /* connect the new pages correctly */
  367.     right->h_prevpg = left->h_pgno;
  368.     left->h_nextpg = right->h_pgno;
  369.  
  370.     /*
  371.      *  Write the child pages out now.  We need them to remain
  372.      *  where they are until we finish updating parent pages,
  373.      *  however.
  374.      */
  375.  
  376.     if (_bt_write(t, left, NORELEASE) == RET_ERROR)
  377.         return (RET_ERROR);
  378.     if (_bt_write(t, right, NORELEASE) == RET_ERROR)
  379.         return (RET_ERROR);
  380.  
  381.     /* now change the root page into an internal page */
  382.     was_leaf = (h->h_flags & F_LEAF);
  383.     h->h_flags &= ~F_LEAF;
  384.     h->h_lower = (index_t) (((char *) (&(h->h_linp[0]))) - ((char *) h));
  385.     h->h_upper = (index_t) t->bt_psize;
  386.     bzero((char *) &(h->h_linp[0]), (int) (h->h_upper - h->h_lower));
  387.  
  388.     /* put two new keys on root page */
  389.     where_h = left;
  390.     while (where_h) {
  391.         DATUM *data;
  392.         IDATUM *idata;
  393.  
  394.         if (was_leaf) {
  395.             data = (DATUM *) GETDATUM(where_h, 0);
  396.  
  397.             if (where_h == left) {
  398.                 len = 0;    /* first key in tree is null */
  399.             } else {
  400.                 if (data->d_flags & D_BIGKEY) {
  401.                     bcopy(&(data->d_bytes[0]),
  402.                           (char *) &oldchain,
  403.                           sizeof(oldchain));
  404.                     if (_bt_markchain(t, oldchain) == RET_ERROR)
  405.                         return (RET_ERROR);
  406.                     src = (char *) &oldchain;
  407.                     flags = D_BIGKEY;
  408.                 } else {
  409.                     src = (char *) &(data->d_bytes[0]);
  410.                     flags = 0;
  411.                 }
  412.                 len = data->d_ksize;
  413.             }
  414.         } else {
  415.             idata = (IDATUM *) GETDATUM(where_h, 0);
  416.             len = idata->i_size;
  417.             flags = idata->i_flags;
  418.             src = &(idata->i_bytes[0]);
  419.         }
  420.         dest = ((char *) h) + h->h_upper;
  421.         nbytes = len + (sizeof (IDATUM) - sizeof(char));
  422.         dest -= LONGALIGN(nbytes);
  423.         id = (IDATUM *) dest;
  424.         id->i_size = len;
  425.         id->i_pgno = where_h->h_pgno;
  426.         id->i_flags = flags;
  427.         if (len > 0)
  428.             bcopy((char *) src, (char *) &(id->i_bytes[0]), len);
  429.         dest -= ((int) h);
  430.         h->h_linp[NEXTINDEX(h)] = (index_t) dest;
  431.         h->h_upper = (index_t) dest;
  432.         h->h_lower += sizeof(index_t);
  433.  
  434.         /* next page */
  435.         if (where_h == left)
  436.             where_h = right;
  437.         else
  438.             where_h = (BTHEADER *) NULL;
  439.     }
  440.  
  441.     if (_bt_release(t, left) == RET_ERROR)
  442.         return (RET_ERROR);
  443.     if (_bt_release(t, right) == RET_ERROR)
  444.         return (RET_ERROR);
  445.  
  446.     /*
  447.      *  That's it, split is done.  If we're doing a non-cached disk
  448.      *  btree, we can free up the pages we allocated, as they're on
  449.      *  disk, now.
  450.      */
  451.  
  452.     if (ISDISK(t) && ! ISCACHE(t))
  453.         {
  454.         FREE ((char *) left);
  455.         FREE ((char *) right);
  456.         }
  457.  
  458.     h->h_flags |= F_DIRTY;
  459.  
  460.     return (RET_SUCCESS);
  461. }
  462.  
  463. /*
  464.  *  _BT_DOPSPLIT -- Do the work of splitting a page
  465.  *
  466.  *    This routine takes two page pointers and splits the data on the
  467.  *    current page of the btree between them.
  468.  *
  469.  *    We do a lot of work here to handle duplicate keys on a page; we
  470.  *    have to place these keys carefully to guarantee that later searches
  471.  *    will find them correctly.  See comments in the code below for details.
  472.  *
  473.  *    Parameters:
  474.  *        t -- tree to split
  475.  *        left -- pointer to page to get left half of the data
  476.  *        right -- pointer to page to get right half of the data
  477.  *
  478.  *    Returns:
  479.  *        None.
  480.  */
  481.  
  482. int
  483. _bt_dopsplit(t, left, right)
  484.     BTREE_P t;
  485.     BTHEADER *left;
  486.     BTHEADER *right;
  487. {
  488.     BTHEADER *h = t->bt_curpage;
  489.     size_t psize;
  490.     char *where;
  491.     BTHEADER *where_h;
  492.     index_t where_i;
  493.     int nbytes, dsize, fixedsize, freespc;
  494.     index_t i;
  495.     index_t save_lower, save_upper, save_i;
  496.     index_t switch_i;
  497.     char *save_key;
  498.     DATUM *d;
  499.     CURSOR *c;
  500.     index_t top;
  501.     int free_save;
  502.     pgno_t chain;
  503.     int ignore;
  504.  
  505.     /*
  506.      *  Our strategy is to put half the bytes on each page.  We figure
  507.      *  out how many bytes we have total, and then move items until
  508.      *  the last item moved put at least 50% of the data on the left
  509.      *  page.
  510.      */
  511.     save_key = (char *) NULL;
  512.     psize = (int) t->bt_psize;
  513.     where = ((char *) left) + psize;
  514.     where_h = left;
  515.     where_i = 0;
  516.     nbytes = psize - (int) ((char *) &(h->h_linp[0]) - ((char *) h));
  517.     freespc = nbytes;
  518.  
  519.     top = NEXTINDEX(h);
  520.     if (h->h_flags & F_LEAF)
  521.         fixedsize = (sizeof(DATUM) - sizeof(char));
  522.     else
  523.         fixedsize = (sizeof(IDATUM) - sizeof(char));
  524.  
  525.     save_key = (char *) NULL;
  526.  
  527.     /* move data */
  528.     for (i = 0; i < top; i++) {
  529.  
  530.         /*
  531.          *  Internal and leaf pages have different layouts for
  532.          *  data items, but in both cases the first entry in the
  533.          *  data item is a size_t.
  534.          */
  535.         d = (DATUM *) GETDATUM(h,i);
  536.         if (h->h_flags & F_LEAF) {
  537.             dsize = d->d_ksize + d->d_dsize + fixedsize;
  538.         } else {
  539.             dsize = d->d_ksize + fixedsize;
  540.         }
  541.  
  542.         /*
  543.          *  If a page contains duplicate keys, we have to be
  544.          *  careful about splits.  A sequence of duplicate keys
  545.          *  may not begin in the middle of one page and end in
  546.          *  the middle of another; it must begin on a page boundary,
  547.          *  in order for searches on the internal nodes to work
  548.          *  correctly.
  549.          */
  550.         if (where_h == left) {
  551.             if (save_key == (char *) NULL) {
  552.                 if (h->h_flags & F_LEAF) {
  553.                     if (d->d_flags & D_BIGKEY) {
  554.                         free_save = TRUE;
  555.                         bcopy(&(d->d_bytes[0]),
  556.                              (char *) &chain,
  557.                              sizeof(chain));
  558.                         if (_bt_getbig(t, chain,
  559.                                    &save_key,
  560.                                    &ignore)
  561.                             == RET_ERROR)
  562.                             return (RET_ERROR);
  563.                     } else {
  564.                         free_save = FALSE;
  565.                         save_key = (char *) &(d->d_bytes[0]);
  566.                     }
  567.                 } else {
  568.                     IDATUM *id = (IDATUM *) d;
  569.  
  570.                     if (id->i_flags & D_BIGKEY) {
  571.                         free_save = TRUE;
  572.                         bcopy(&(id->i_bytes[0]),
  573.                              (char *) &chain,
  574.                              sizeof(chain));
  575.                         if (_bt_getbig(t, chain,
  576.                                    &save_key,
  577.                                    &ignore)
  578.                             == RET_ERROR)
  579.                             return (RET_ERROR);
  580.                     } else {
  581.                         free_save = FALSE;
  582.                         save_key = (char *)
  583.                             &(id->i_bytes[0]);
  584.                     }
  585.                 }
  586.                 save_i = 0;
  587.                 save_lower = where_h->h_lower;
  588.                 save_upper = where_h->h_upper;
  589.             } else {
  590.                 if (_bt_cmp(t, save_key, i) != 0) {
  591.                     save_lower = where_h->h_lower;
  592.                     save_upper = where_h->h_upper;
  593.                     save_i = i;
  594.                 }
  595.                 if (h->h_flags & F_LEAF) {
  596.                     if (free_save)
  597.                         FREE(save_key);
  598.                     if (d->d_flags & D_BIGKEY) {
  599.                         free_save = TRUE;
  600.                         bcopy(&(d->d_bytes[0]),
  601.                              (char *) &chain,
  602.                              sizeof(chain));
  603.                         if (_bt_getbig(t, chain,
  604.                                    &save_key,
  605.                                    &ignore)
  606.                             == RET_ERROR)
  607.                             return (RET_ERROR);
  608.                     } else {
  609.                         free_save = FALSE;
  610.                         save_key = (char *) &(d->d_bytes[0]);
  611.                     }
  612.                 } else {
  613.                     IDATUM *id = (IDATUM *) d;
  614.  
  615.                     if (id->i_flags & D_BIGKEY) {
  616.                         free_save = TRUE;
  617.                         bcopy(&(id->i_bytes[0]),
  618.                              (char *) &chain,
  619.                              sizeof(chain));
  620.                         if (_bt_getbig(t, chain,
  621.                                    &save_key,
  622.                                    &ignore)
  623.                             == RET_ERROR)
  624.                             return (RET_ERROR);
  625.                     } else {
  626.                         free_save = FALSE;
  627.                         save_key = (char *)
  628.                             &(id->i_bytes[0]);
  629.                     }
  630.                 }
  631.             }
  632.         }
  633.  
  634.         /* copy data and update page state */
  635.         where -= LONGALIGN(dsize);
  636.         bcopy((char *) d, (char *) where, dsize);
  637.         where_h->h_upper = where_h->h_linp[where_i] =
  638.             (index_t) (where - (int) where_h);
  639.         where_h->h_lower += sizeof(index_t);
  640.         where_i++;
  641.  
  642.         /* if we've moved half, switch to the right-hand page */
  643.         nbytes -= LONGALIGN(dsize) + sizeof(index_t);
  644.         if ((freespc - nbytes) > nbytes) {
  645.             nbytes = 2 * freespc;
  646.  
  647.             /* identical keys go on the same page */
  648.             if (save_i > 0) {
  649.                 /* i gets incremented at loop bottom... */
  650.                 i = save_i - 1;
  651.                 where_h->h_lower = save_lower;
  652.                 where_h->h_upper = save_upper;
  653.             }
  654.             where = ((char *) right) + psize;
  655.             where_h = right;
  656.             switch_i = where_i;
  657.             where_i = 0;
  658.         }
  659.     }
  660.  
  661.     /*
  662.      *  If there was an active scan on the database, and we just
  663.      *  split the page that the cursor was on, we may need to
  664.      *  adjust the cursor to point to the same entry as before the
  665.      *  split.
  666.      */
  667.  
  668.     c = &(t->bt_cursor);
  669.     if ((t->bt_flags & BTF_SEQINIT)
  670.         && (c->c_pgno == h->h_pgno)
  671.         && (c->c_index >= switch_i))
  672.     {
  673.         c->c_pgno = where_h->h_pgno;
  674.         c->c_index -= where_i;
  675.     }
  676.     return (RET_SUCCESS);
  677. }
  678.