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 / insert.c < prev    next >
Text File  |  1993-05-22  |  6KB  |  293 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_INSERT -- Insert a new user datum in the btree.
  11.  *
  12.  *    This routine is called by bt_put, the public interface, once the
  13.  *    location for the new item is known.  We do the work here, and
  14.  *    handle splits if necessary.
  15.  *
  16.  *    Parameters:
  17.  *        t -- btree in which to do the insertion.
  18.  *        item -- BTITEM describing location of new datum
  19.  *        key -- key to insert
  20.  *        data -- data associated with key
  21.  *        flag -- magic cookie passed recursively to bt_put if we
  22.  *            have to do a split
  23.  *
  24.  *    Returns:
  25.  *        RET_SUCCESS, RET_ERROR.
  26.  */
  27.  
  28. int
  29. _bt_insert(t, item, key, data, flag)
  30.     BTREE_P t;
  31.     BTITEM *item;
  32.     DBT *key;
  33.     DBT *data;
  34.     int flag;
  35. {
  36.     index_t index;
  37.     BTHEADER *h;
  38.     DATUM *d;
  39.     int nbytes;
  40.     int status;
  41.     pgno_t pgno;
  42.     int keysize, datasize;
  43.     int bigkey, bigdata;
  44.  
  45.     if (_bt_getpage(t, item->bti_pgno) == RET_ERROR)
  46.         {
  47.         return (RET_ERROR);
  48.         }
  49.     h = t->bt_curpage;
  50.  
  51.     if (TOOBIG(t, data->size)) {
  52.         bigdata = TRUE;
  53.         datasize = sizeof(pgno_t);
  54.     } else {
  55.         bigdata = FALSE;
  56.         datasize = data->size;
  57.     }
  58.  
  59.     if (TOOBIG(t, key->size)) {
  60.         bigkey = TRUE;
  61.         keysize = sizeof(pgno_t);
  62.     } else {
  63.         bigkey = FALSE;
  64.         keysize = key->size;
  65.     }
  66.  
  67.     nbytes = keysize + datasize + (sizeof(DATUM) - sizeof(char));
  68.     nbytes = LONGALIGN(nbytes) + sizeof(index_t);
  69.  
  70.     /* if there's not enough room here, split the page */
  71.     if ((h->h_upper - h->h_lower) < nbytes) {
  72.         int aresult;
  73.         
  74.         if (_bt_split(t) == RET_ERROR)
  75.             {
  76.             return (RET_ERROR);
  77.             }
  78.  
  79.         /* okay, try again (empty the stack first, though) */
  80.         while (_bt_pop((BTREE) t) != P_NONE)
  81.             continue;
  82.  
  83.         aresult = _bt_put(t, key, data, flag);
  84.         /* aresult = bt_put((BTREE) t, key, data, flag); */
  85.         return aresult;
  86.     }
  87.  
  88.     /* put together a leaf page datum from the key/data pair */
  89.     index = item->bti_index;
  90.     nbytes = keysize + datasize + (sizeof(DATUM) - sizeof(char));
  91.  
  92.     if ((d = (DATUM *) cbMALLOC((unsigned) nbytes)) == (DATUM *) NULL)
  93.         {
  94.         return (RET_ERROR);
  95.         }
  96.  
  97.     d->d_ksize = keysize;
  98.     d->d_dsize = datasize;
  99.     d->d_flags = 0;
  100.  
  101.     if (bigkey) {
  102.         if (_bt_indirect(t, key, &pgno) == RET_ERROR)
  103.             {
  104.             return (RET_ERROR);
  105.             }
  106.         (void) bcopy((char *) &pgno, &(d->d_bytes[0]), sizeof(pgno));
  107.         d->d_flags |= D_BIGKEY;
  108.         if (_bt_getpage(t, item->bti_pgno) == RET_ERROR)
  109.             {
  110.             return (RET_ERROR);
  111.             }
  112.     } else {
  113.         if (d->d_ksize > 0) {
  114.             (void) bcopy((char *) key->data,
  115.                       (char *) &(d->d_bytes[0]),
  116.                       (int) d->d_ksize);
  117.         }
  118.     }
  119.  
  120.     if (bigdata) {
  121.         if (_bt_indirect(t, data, &pgno) == RET_ERROR)
  122.             {
  123.             return (RET_ERROR);
  124.             }
  125.         (void) bcopy((char *) &pgno,
  126.                  &(d->d_bytes[keysize]),
  127.                  sizeof(pgno));
  128.         d->d_flags |= D_BIGDATA;
  129.         if (_bt_getpage(t, item->bti_pgno) == RET_ERROR)
  130.             {
  131.             return (RET_ERROR);
  132.             }
  133.     } else {
  134.         if (d->d_dsize > 0) {
  135.             (void) bcopy((char *) data->data,
  136.                       (char *) &(d->d_bytes[keysize]),
  137.                       (int) d->d_dsize);
  138.         }
  139.     }
  140.  
  141.     /* do the insertion */
  142.     status = _bt_insertat(t, (char *) d, index);
  143.  
  144.     FREE((char *) d);
  145.  
  146.     return (status);
  147. }
  148.  
  149. /*
  150.  *  _BT_INSERTI -- Insert IDATUM on current page in the btree.
  151.  *
  152.  *    This routine handles insertions to internal pages after splits
  153.  *    lower in the tree.  On entry, t->bt_curpage is the page to get
  154.  *    the new IDATUM.  We are also given pgno, the page number of the
  155.  *    IDATUM that is immediately left of the new IDATUM's position.
  156.  *    This guarantees that the IDATUM for the right half of the page
  157.  *    after a split goes next to the IDATUM for its left half.
  158.  *
  159.  *    Parameters:
  160.  *        t -- tree in which to do insertion.
  161.  *        id -- new IDATUM to insert
  162.  *        pgno -- page number of IDATUM left of id's position
  163.  *
  164.  *    Returns:
  165.  *        RET_SUCCESS, RET_ERROR.
  166.  */
  167.  
  168. int
  169. _bt_inserti(t, id, pgno)
  170.     BTREE_P t;
  171.     IDATUM *id;
  172.     pgno_t pgno;
  173. {
  174.     BTHEADER *h = t->bt_curpage;
  175.     index_t next, i;
  176.     IDATUM *idx;
  177.     char *key;
  178.     pgno_t chain;
  179.     int free_key;
  180.     int ignore;
  181.  
  182.     if (id->i_flags & D_BIGKEY) {
  183.         free_key = TRUE;
  184.         bcopy(&(id->i_bytes[0]), (char *) &chain, sizeof(chain));
  185.         if (_bt_getbig(t, chain, &key, &ignore) == RET_ERROR)
  186.             return (RET_ERROR);
  187.     } else {
  188.         free_key = FALSE;
  189.         key = &(id->i_bytes[0]);
  190.     }
  191.     i = _bt_binsrch(t, key);
  192.  
  193.     next = NEXTINDEX(h);
  194.     while (i < next && _bt_cmp(t, key, i) >= 0)
  195.         i++;
  196.  
  197.     if (free_key)
  198.         FREE(key);
  199.  
  200.     /* okay, now we're close; find adjacent IDATUM */
  201.     for (;;) {
  202.         idx = (IDATUM *) GETDATUM(h,i);
  203.         if (idx->i_pgno == pgno) {
  204.             i++;
  205.             break;
  206.         }
  207.         --i;
  208.     }
  209.  
  210.     /* correctly positioned, do the insertion */
  211.     return (_bt_insertat(t, (char *) id, i));
  212. }
  213.  
  214. /*
  215.  *  _BT_INSERTAT -- Insert a datum at a given location on the current page.
  216.  *
  217.  *    This routine does insertions on both leaf and internal pages.
  218.  *
  219.  *    Parameters:
  220.  *        t -- tree in which to do insertion.
  221.  *        p -- DATUM or IDATUM to insert.
  222.  *        index -- index in line pointer array to put this item.
  223.  *
  224.  *    Returns:
  225.  *        RET_SUCCESS, RET_ERROR.
  226.  *
  227.  *    Side Effects:
  228.  *        Will rearrange line pointers to make space for the new
  229.  *        entry.  This means that any scans currently active are
  230.  *        invalid after this.
  231.  *
  232.  *    Warnings:
  233.  *        There must be sufficient room for the new item on the page.
  234.  */
  235.  
  236. int
  237. _bt_insertat(t, p, index)
  238.     BTREE_P t;
  239.     char *p;
  240.     index_t index;
  241. {
  242.     IDATUM *id = (IDATUM *) p;
  243.     DATUM *d = (DATUM *) p;
  244.     BTHEADER *h;
  245.     CURSOR *c;
  246.     index_t nxtindex;
  247.     char *src, *dest;
  248.     int nbytes;
  249.  
  250.     /* insertion may confuse an active scan.  fix it. */
  251.     c = &(t->bt_cursor);
  252.     if (t->bt_flags & BTF_SEQINIT && t->bt_curpage->h_pgno == c->c_pgno)
  253.         if (_bt_fixscan(t, index, d, INSERT) == RET_ERROR)
  254.             return (RET_ERROR);
  255.  
  256.     h = t->bt_curpage;
  257.     nxtindex = (index_t) NEXTINDEX(h);
  258.  
  259.     /*
  260.      *  If we're inserting at the middle of the line pointer array,
  261.      *  copy pointers that will follow the new one up on the page.
  262.      */
  263.  
  264.     if (index < nxtindex) {
  265.         src = (char *) &(h->h_linp[index]);
  266.         dest = (char *) &(h->h_linp[index + 1]);
  267.         nbytes = (h->h_lower - (src - ((char *) h)))
  268.              + sizeof(h->h_linp[0]);
  269.         bcopy(src, dest, nbytes);
  270.     }
  271.  
  272.     /* compute size and copy data to page */
  273.     if (h->h_flags & F_LEAF) {
  274.         nbytes = d->d_ksize + d->d_dsize
  275.              + (sizeof(DATUM) - sizeof(char));
  276.     } else {
  277.         nbytes = id->i_size + (sizeof(IDATUM) - sizeof(char));
  278.     }
  279.     dest = (((char *) h) + h->h_upper) - LONGALIGN(nbytes);
  280.     bcopy((char *) p, dest, nbytes);
  281.  
  282.     /* update statistics */
  283.     dest -= (int) h;
  284.     h->h_linp[index] = (index_t) dest;
  285.     h->h_upper = (index_t) dest;
  286.     h->h_lower += sizeof(index_t);
  287.  
  288.     /* we're done */
  289.     h->h_flags |= F_DIRTY;
  290.  
  291.     return (RET_SUCCESS);
  292. }
  293.