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 / delete.c < prev    next >
Text File  |  1992-05-03  |  4KB  |  166 lines
  1.  
  2. #include <types.h>
  3. #include "db.h"
  4. #include <errno.h>
  5. #include <stdio.h>
  6. #include <string.h>
  7. #include "btree.h"
  8.  
  9. /*
  10.  *  _BT_CRSRDEL -- Delete the item pointed to by the cursor.
  11.  *
  12.  *    This routine deletes the item most recently returned by a scan
  13.  *    through the tree.  Since it only makes sense to delete the current
  14.  *    record once, we make sure that we don't try to delete twice without
  15.  *    advancing the scan.
  16.  *
  17.  *    Parameters:
  18.  *        t -- tree in which to do deletion
  19.  *
  20.  *    Returns:
  21.  *        RET_SUCCESS, RET_ERROR.
  22.  *
  23.  *    Side Effects:
  24.  *        The call to _bt_delone marks the cursor, so we can tell that
  25.  *        the current record has been deleted.
  26.  */
  27.  
  28. int
  29. _bt_crsrdel(t)
  30.     BTREE_P t;
  31. {
  32.     CURSOR *c;
  33.  
  34.     c = &(t->bt_cursor);
  35.  
  36.     /* a cursor must exist, and can't have deleted the current key yet */
  37.     if (!(t->bt_flags & BTF_SEQINIT) || (c->c_flags & CRSR_BEFORE)) {
  38.         errno = EINVAL;
  39.         return (RET_ERROR);
  40.     }
  41.  
  42.     if (_bt_getpage(t, c->c_pgno) == RET_ERROR)
  43.         return (RET_ERROR);
  44.  
  45.     if (c->c_index >= NEXTINDEX(t->bt_curpage)) {
  46.         errno = EINVAL;
  47.         return (RET_ERROR);
  48.     }
  49.  
  50.     return (_bt_delone(t, c->c_index));
  51. }
  52.  
  53. /*
  54.  *  _BT_DELONE -- Delete a single entry from a btree.
  55.  *
  56.  *    This routine physically removes a btree entry from a leaf page.
  57.  *    IDATUM items are *never* removed from internal nodes, regardless
  58.  *    of whether the entries that originally caused them to be added
  59.  *    are removed from the tree or not.  In addition, pages made empty
  60.  *    by element deletion are not actually reclaimed.  They are,
  61.  *    however, made available for reuse.
  62.  *
  63.  *    To delete an item from a page, we pack the remaining items at
  64.  *    the end of the page, overwriting the deleted item's entry.  We
  65.  *    move the line pointers backward on the page, overwriting the
  66.  *    original item's line pointer.  This guarantees that the space in
  67.  *    the middle of the page is free -- a property that our insertion
  68.  *    strategy relies on.
  69.  *
  70.  *    This routine doesn't reclaim pages all of whose entries have
  71.  *    been deleted.  These pages are available for reuse, however.
  72.  *    If an item is deleted that was too big to fit on a page, then
  73.  *    the blocks that it occupies are put on a free list for reuse.
  74.  *
  75.  *    Parameters:
  76.  *        t -- btree from which to delete item
  77.  *        index -- index of entry on current page to delete
  78.  *
  79.  *    Returns:
  80.  *        RET_SUCCESS, RET_ERROR.
  81.  *
  82.  *    Side Effects:
  83.  *        Physically changes page layout, adjusts internal page
  84.  *        state to reflect the deletion of the item, and updates
  85.  *        the list of free pages for this tree.
  86.  */
  87.  
  88. int
  89. _bt_delone(t, index)
  90.     BTREE_P t;
  91.     index_t index;
  92. {
  93.     char *src, *dest;
  94.     int nbytes, nmoved;
  95.     index_t off;
  96.     index_t top;
  97.     index_t i;
  98.     pgno_t chain;
  99.     BTHEADER *h;
  100.     CURSOR *c;
  101.     DATUM *d;
  102.  
  103.     /* deletion may confuse an active scan.  fix it.  */
  104.     c = &(t->bt_cursor);
  105.     if (t->bt_flags & BTF_SEQINIT && t->bt_curpage->h_pgno == c->c_pgno)
  106.         if (_bt_fixscan(t, index, (DATUM *) NULL, DELETE) == RET_ERROR)
  107.             {
  108.             return (RET_ERROR);
  109.             }
  110.  
  111.     h = t->bt_curpage;
  112.     off = h->h_linp[index];
  113.     d = (DATUM *) GETDATUM(h, index);
  114.  
  115.     /* if this is a big item, reclaim the space it occupies */
  116.     if (d->d_flags & D_BIGKEY) {
  117.         bcopy(&(d->d_bytes[0]),
  118.               (char *) &chain,
  119.               sizeof(chain));
  120.         if (_bt_delindir(t, chain) == RET_ERROR)
  121.             return (RET_ERROR);
  122.         h = t->bt_curpage;
  123.         d = (DATUM *) GETDATUM(h, index);
  124.     }
  125.     if (d->d_flags & D_BIGDATA) {
  126.         bcopy(&(d->d_bytes[d->d_ksize]),
  127.               (char *) &chain,
  128.               sizeof(chain));
  129.         if (_bt_delindir(t, chain) == RET_ERROR)
  130.             return (RET_ERROR);
  131.         h = t->bt_curpage;
  132.         d = (DATUM *) GETDATUM(h, index);
  133.     }
  134.  
  135.     /* move the data down on the page */
  136.     nbytes = d->d_ksize + d->d_dsize
  137.          + (sizeof(DATUM) - sizeof(char));
  138.     nbytes = LONGALIGN(nbytes);
  139.     src = ((char *) h) + h->h_upper;
  140.     dest = src + nbytes;
  141.     nmoved = (int) (((char *) d) - src);
  142.     (void) bcopy(src, dest, nmoved);
  143.  
  144.     /* next move the line pointers up */
  145.     src = (char *) &(h->h_linp[index + 1]);
  146.     dest = (char *) &(h->h_linp[index]);
  147.     nmoved = (int) (((char *) &(h->h_linp[NEXTINDEX(h)])) - src);
  148.     (void) bcopy(src, dest, nmoved);
  149.  
  150.     /* remember that we freed up some space */
  151.     h->h_upper += nbytes;
  152.     h->h_lower -= sizeof(index_t);
  153.  
  154.     /* adjust offsets in line pointers affected by moving the data */
  155.     top = NEXTINDEX(h);
  156.     for (i = 0; i < top; i++) {
  157.         if (h->h_linp[i] < off)
  158.             h->h_linp[i] += nbytes;
  159.     }
  160.  
  161.     /* it's gone */
  162.     h->h_flags |= F_DIRTY;
  163.  
  164.     return (RET_SUCCESS);
  165. }
  166.