home *** CD-ROM | disk | FTP | other *** search
/ Geek Gadgets 1 / ADE-1.bin / ade-dist / ixemul-45.0-src.tgz / tar.out / contrib / ixemul / db / btree / bt_delete.c < prev    next >
C/C++ Source or Header  |  1996-09-28  |  10KB  |  331 lines
  1. /*    $NetBSD: bt_delete.c,v 1.6 1995/02/27 13:20:16 cgd Exp $    */
  2.  
  3. /*-
  4.  * Copyright (c) 1990, 1993, 1994
  5.  *    The Regents of the University of California.  All rights reserved.
  6.  *
  7.  * This code is derived from software contributed to Berkeley by
  8.  * Mike Olson.
  9.  *
  10.  * Redistribution and use in source and binary forms, with or without
  11.  * modification, are permitted provided that the following conditions
  12.  * are met:
  13.  * 1. Redistributions of source code must retain the above copyright
  14.  *    notice, this list of conditions and the following disclaimer.
  15.  * 2. Redistributions in binary form must reproduce the above copyright
  16.  *    notice, this list of conditions and the following disclaimer in the
  17.  *    documentation and/or other materials provided with the distribution.
  18.  * 3. All advertising materials mentioning features or use of this software
  19.  *    must display the following acknowledgement:
  20.  *    This product includes software developed by the University of
  21.  *    California, Berkeley and its contributors.
  22.  * 4. Neither the name of the University nor the names of its contributors
  23.  *    may be used to endorse or promote products derived from this software
  24.  *    without specific prior written permission.
  25.  *
  26.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  27.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  28.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  29.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  30.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  31.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  32.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  33.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  34.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  35.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  36.  * SUCH DAMAGE.
  37.  */
  38.  
  39. #if defined(LIBC_SCCS) && !defined(lint)
  40. #if 0
  41. static char sccsid[] = "@(#)bt_delete.c    8.4 (Berkeley) 5/31/94";
  42. #else
  43. static char rcsid[] = "$NetBSD: bt_delete.c,v 1.6 1995/02/27 13:20:16 cgd Exp $";
  44. #endif
  45. #endif /* LIBC_SCCS and not lint */
  46.  
  47. #include <sys/types.h>
  48.  
  49. #include <errno.h>
  50. #include <stdio.h>
  51. #include <string.h>
  52.  
  53. #include <db.h>
  54. #include "btree.h"
  55.  
  56. static int bt_bdelete __P((BTREE *, const DBT *));
  57.  
  58. /*
  59.  * __BT_DELETE -- Delete the item(s) referenced by a key.
  60.  *
  61.  * Parameters:
  62.  *    dbp:    pointer to access method
  63.  *    key:    key to delete
  64.  *    flags:    R_CURSOR if deleting what the cursor references
  65.  *
  66.  * Returns:
  67.  *    RET_ERROR, RET_SUCCESS and RET_SPECIAL if the key not found.
  68.  */
  69. int
  70. __bt_delete(dbp, key, flags)
  71.     const DB *dbp;
  72.     const DBT *key;
  73.     u_int flags;
  74. {
  75.     BTREE *t;
  76.     int status;
  77.  
  78.     t = dbp->internal;
  79.  
  80.     /* Toss any page pinned across calls. */
  81.     if (t->bt_pinned != NULL) {
  82.         mpool_put(t->bt_mp, t->bt_pinned, 0);
  83.         t->bt_pinned = NULL;
  84.     }
  85.  
  86.     if (ISSET(t, B_RDONLY)) {
  87.         errno = EPERM;
  88.         return (RET_ERROR);
  89.     }
  90.  
  91.     switch(flags) {
  92.     case 0:
  93.         status = bt_bdelete(t, key);
  94.         break;
  95.     case R_CURSOR:
  96.         /*
  97.          * If flags is R_CURSOR, delete the cursor; must already have
  98.          * started a scan and not have already deleted the record.  For
  99.          * the delete cursor bit to have been set requires that the
  100.          * scan be initialized, so no reason to check.
  101.          */
  102.         if (!ISSET(t, B_SEQINIT))
  103.                         goto einval;
  104.         status = ISSET(t, B_DELCRSR) ?
  105.             RET_SPECIAL : __bt_crsrdel(t, &t->bt_bcursor);
  106.         break;
  107.     default:
  108. einval:        errno = EINVAL;
  109.         return (RET_ERROR);
  110.     }
  111.     if (status == RET_SUCCESS)
  112.         SET(t, B_MODIFIED);
  113.     return (status);
  114. }
  115.  
  116. /*
  117.  * BT_BDELETE -- Delete all key/data pairs matching the specified key.
  118.  *
  119.  * Parameters:
  120.  *    tree:    tree
  121.  *    key:    key to delete
  122.  *
  123.  * Returns:
  124.  *    RET_ERROR, RET_SUCCESS and RET_SPECIAL if the key not found.
  125.  */
  126. static int
  127. bt_bdelete(t, key)
  128.     BTREE *t;
  129.     const DBT *key;
  130. {
  131.     EPG *e, save;
  132.     PAGE *h;
  133.     pgno_t cpgno, pg;
  134.     indx_t cindex;
  135.     int deleted, dirty1, dirty2, exact;
  136.  
  137.     /* Find any matching record; __bt_search pins the page. */
  138.     if ((e = __bt_search(t, key, &exact)) == NULL)
  139.         return (RET_ERROR);
  140.     if (!exact) {
  141.         mpool_put(t->bt_mp, e->page, 0);
  142.         return (RET_SPECIAL);
  143.     }
  144.  
  145.     /*
  146.      * Delete forward, then delete backward, from the found key.  The
  147.      * ordering is so that the deletions don't mess up the page refs.
  148.      * The first loop deletes the key from the original page, the second
  149.      * unpins the original page.  In the first loop, dirty1 is set if
  150.      * the original page is modified, and dirty2 is set if any subsequent
  151.      * pages are modified.  In the second loop, dirty1 starts off set if
  152.      * the original page has been modified, and is set if any subsequent
  153.      * pages are modified.
  154.      *
  155.      * If find the key referenced by the cursor, don't delete it, just
  156.      * flag it for future deletion.  The cursor page number is P_INVALID
  157.      * unless the sequential scan is initialized, so no reason to check.
  158.      * A special case is when the already deleted cursor record was the
  159.      * only record found.  If so, then the delete opertion fails as no
  160.      * records were deleted.
  161.      *
  162.      * Cycle in place in the current page until the current record doesn't
  163.      * match the key or the page is empty.  If the latter, walk forward,
  164.      * skipping empty pages and repeating until a record doesn't match
  165.      * the key or the end of the tree is reached.
  166.      */
  167.     cpgno = t->bt_bcursor.pgno;
  168.     cindex = t->bt_bcursor.index;
  169.     save = *e;
  170.     dirty1 = 0;
  171.     for (h = e->page, deleted = 0;;) {
  172.         dirty2 = 0;
  173.         do {
  174.             if (h->pgno == cpgno && e->index == cindex) {
  175.                 if (!ISSET(t, B_DELCRSR)) {
  176.                     SET(t, B_DELCRSR);
  177.                     deleted = 1;
  178.                 }
  179.                 ++e->index;
  180.             } else {
  181.                 if (__bt_dleaf(t, h, e->index)) {
  182.                     if (h->pgno != save.page->pgno)
  183.                         mpool_put(t->bt_mp, h, dirty2);
  184.                     mpool_put(t->bt_mp, save.page, dirty1);
  185.                     return (RET_ERROR);
  186.                 }
  187.                 if (h->pgno == save.page->pgno)
  188.                     dirty1 = MPOOL_DIRTY;
  189.                 else
  190.                     dirty2 = MPOOL_DIRTY;
  191.                 deleted = 1;
  192.             }
  193.         } while (e->index < NEXTINDEX(h) && __bt_cmp(t, key, e) == 0);
  194.  
  195.         /*
  196.          * Quit if didn't find a match, no next page, or first key on
  197.          * the next page doesn't match.  Don't unpin the original page
  198.          * unless an error occurs.
  199.          */
  200.         if (e->index < NEXTINDEX(h))
  201.             break;
  202.         for (;;) {
  203.             if ((pg = h->nextpg) == P_INVALID)
  204.                 goto done1;
  205.             if (h->pgno != save.page->pgno)
  206.                 mpool_put(t->bt_mp, h, dirty2);
  207.             if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) {
  208.                 mpool_put(t->bt_mp, save.page, dirty1);
  209.                 return (RET_ERROR);
  210.             }
  211.             if (NEXTINDEX(h) != 0) {
  212.                 e->page = h;
  213.                 e->index = 0;
  214.                 break;
  215.             }
  216.         }
  217.  
  218.         if (__bt_cmp(t, key, e) != 0)
  219.             break;
  220.     }
  221.  
  222.     /*
  223.      * Reach here with the original page and the last page referenced
  224.      * pinned (they may be the same).  Release it if not the original.
  225.      */
  226. done1:    if (h->pgno != save.page->pgno)
  227.         mpool_put(t->bt_mp, h, dirty2);
  228.  
  229.     /*
  230.      * Walk backwards from the record previous to the record returned by
  231.      * __bt_search, skipping empty pages, until a record doesn't match
  232.      * the key or reach the beginning of the tree.
  233.      */
  234.     *e = save;
  235.     for (;;) {
  236.         if (e->index)
  237.             --e->index;
  238.         for (h = e->page; e->index; --e->index) {
  239.             if (__bt_cmp(t, key, e) != 0)
  240.                 goto done2;
  241.             if (h->pgno == cpgno && e->index == cindex) {
  242.                 if (!ISSET(t, B_DELCRSR)) {
  243.                     SET(t, B_DELCRSR);
  244.                     deleted = 1;
  245.                 }
  246.             } else {
  247.                 if (__bt_dleaf(t, h, e->index) == RET_ERROR) {
  248.                     mpool_put(t->bt_mp, h, dirty1);
  249.                     return (RET_ERROR);
  250.                 }
  251.                 if (h->pgno == save.page->pgno)
  252.                     dirty1 = MPOOL_DIRTY;
  253.                 deleted = 1;
  254.             }
  255.         }
  256.  
  257.         if ((pg = h->prevpg) == P_INVALID)
  258.             goto done2;
  259.         mpool_put(t->bt_mp, h, dirty1);
  260.         dirty1 = 0;
  261.         if ((e->page = mpool_get(t->bt_mp, pg, 0)) == NULL)
  262.             return (RET_ERROR);
  263.         e->index = NEXTINDEX(e->page);
  264.     }
  265.  
  266.     /*
  267.      * Reach here with the last page that was looked at pinned.  Release
  268.      * it.
  269.      */
  270. done2:    mpool_put(t->bt_mp, h, dirty1);
  271.     return (deleted ? RET_SUCCESS : RET_SPECIAL);
  272. }
  273.  
  274. /*
  275.  * __BT_DLEAF -- Delete a single record from a leaf page.
  276.  *
  277.  * Parameters:
  278.  *    t:    tree
  279.  *    index:    index on current page to delete
  280.  *
  281.  * Returns:
  282.  *    RET_SUCCESS, RET_ERROR.
  283.  */
  284. int
  285. __bt_dleaf(t, h, index)
  286.     BTREE *t;
  287.     PAGE *h;
  288.     indx_t index;
  289. {
  290.     register BLEAF *bl;
  291.     register indx_t cnt, *ip, offset;
  292.     register u_int32_t nbytes;
  293.     char *from;
  294.     void *to;
  295.  
  296.     /*
  297.      * Delete a record from a btree leaf page.  Internal records are never
  298.      * deleted from internal pages, regardless of the records that caused
  299.      * them to be added being deleted.  Pages made empty by deletion are
  300.      * not reclaimed.  They are, however, made available for reuse.
  301.      *
  302.      * Pack the remaining entries at the end of the page, shift the indices
  303.      * down, overwriting the deleted record and its index.  If the record
  304.      * uses overflow pages, make them available for reuse.
  305.      */
  306.     to = bl = GETBLEAF(h, index);
  307.     if (bl->flags & P_BIGKEY && __ovfl_delete(t, bl->bytes) == RET_ERROR)
  308.         return (RET_ERROR);
  309.     if (bl->flags & P_BIGDATA &&
  310.         __ovfl_delete(t, bl->bytes + bl->ksize) == RET_ERROR)
  311.         return (RET_ERROR);
  312.     nbytes = NBLEAF(bl);
  313.  
  314.     /*
  315.      * Compress the key/data pairs.  Compress and adjust the [BR]LEAF
  316.      * offsets.  Reset the headers.
  317.      */
  318.     from = (char *)h + h->upper;
  319.     memmove(from + nbytes, from, (char *)to - from);
  320.     h->upper += nbytes;
  321.  
  322.     offset = h->linp[index];
  323.     for (cnt = index, ip = &h->linp[0]; cnt--; ++ip)
  324.         if (ip[0] < offset)
  325.             ip[0] += nbytes;
  326.     for (cnt = NEXTINDEX(h) - index; --cnt; ++ip)
  327.         ip[0] = ip[1] < offset ? ip[1] + nbytes : ip[1];
  328.     h->lower -= sizeof(indx_t);
  329.     return (RET_SUCCESS);
  330. }
  331.