lib/libc/db/btree/delete.c

   1 /*-
   2  * Copyright (c) 1990 The Regents of the University of California.
   3  * All rights reserved.
   4  *
   5  * This code is derived from software contributed to Berkeley by
   6  * Mike Olson.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted provided that the following conditions
  10  * are met:
  11  * 1. Redistributions of source code must retain the above copyright
  12  *    notice, this list of conditions and the following disclaimer.
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice, this list of conditions and the following disclaimer in the
  15  *    documentation and/or other materials provided with the distribution.
  16  * 3. All advertising materials mentioning features or use of this software
  17  *    must display the following acknowledgement:
  18  *      This product includes software developed by the University of
  19  *      California, Berkeley and its contributors.
  20  * 4. Neither the name of the University nor the names of its contributors
  21  *    may be used to endorse or promote products derived from this software
  22  *    without specific prior written permission.
  23  *
  24  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34  * SUCH DAMAGE.
  35  */
  36
  37 #if defined(LIBC_SCCS) && !defined(lint)
  38 static char sccsid[] = "@(#)delete.c    5.2 (Berkeley) 2/22/91";
  39 #endif /* LIBC_SCCS and not lint */
  40
  41 #include <sys/types.h>
  42 #include <db.h>
  43 #include <errno.h>
  44 #include <string.h>
  45 #include "btree.h"
  46
  47 /*
  48  *  _BT_CRSRDEL -- Delete the item pointed to by the cursor.
  49  *
  50  *      This routine deletes the item most recently returned by a scan
  51  *      through the tree.  Since it only makes sense to delete the current
  52  *      record once, we make sure that we don't try to delete twice without
  53  *      advancing the scan.
  54  *
  55  *      Parameters:
  56  *              t -- tree in which to do deletion
  57  *
  58  *      Returns:
  59  *              RET_SUCCESS, RET_ERROR.
  60  *
  61  *      Side Effects:
  62  *              The call to _bt_delone marks the cursor, so we can tell that
  63  *              the current record has been deleted.
  64  */
  65
  66 int
  67 _bt_crsrdel(t)
  68         BTREE_P t;
  69 {
  70         CURSOR *c;
  71
  72         c = &(t->bt_cursor);
  73
  74         /* a cursor must exist, and can't have deleted the current key yet */
  75         if (!(t->bt_flags & BTF_SEQINIT) || (c->c_flags & CRSR_BEFORE)) {
  76                 errno = EINVAL;
  77                 return (RET_ERROR);
  78         }
  79
  80         if (_bt_getpage(t, c->c_pgno) == RET_ERROR)
  81                 return (RET_ERROR);
  82
  83         if (c->c_index >= NEXTINDEX(t->bt_curpage)) {
  84                 errno = EINVAL;
  85                 return (RET_ERROR);
  86         }
  87
  88         return (_bt_delone(t, c->c_index));
  89 }
  90
  91 /*
  92  *  _BT_DELONE -- Delete a single entry from a btree.
  93  *
  94  *      This routine physically removes a btree entry from a leaf page.
  95  *      IDATUM items are *never* removed from internal nodes, regardless
  96  *      of whether the entries that originally caused them to be added
  97  *      are removed from the tree or not.  In addition, pages made empty
  98  *      by element deletion are not actually reclaimed.  They are,
  99  *      however, made available for reuse.
 100  *
 101  *      To delete an item from a page, we pack the remaining items at
 102  *      the end of the page, overwriting the deleted item's entry.  We
 103  *      move the line pointers backward on the page, overwriting the
 104  *      original item's line pointer.  This guarantees that the space in
 105  *      the middle of the page is free -- a property that our insertion
 106  *      strategy relies on.
 107  *
 108  *      This routine doesn't reclaim pages all of whose entries have
 109  *      been deleted.  These pages are available for reuse, however.
 110  *      If an item is deleted that was too big to fit on a page, then
 111  *      the blocks that it occupies are put on a free list for reuse.
 112  *
 113  *      Parameters:
 114  *              t -- btree from which to delete item
 115  *              index -- index of entry on current page to delete
 116  *
 117  *      Returns:
 118  *              RET_SUCCESS, RET_ERROR.
 119  *
 120  *      Side Effects:
 121  *              Physically changes page layout, adjusts internal page
 122  *              state to reflect the deletion of the item, and updates
 123  *              the list of free pages for this tree.
 124  */
 125
 126 int
 127 _bt_delone(t, index)
 128         BTREE_P t;
 129         index_t index;
 130 {
 131         char *src, *dest;
 132         int nbytes, nmoved;
 133         index_t off;
 134         index_t top;
 135         index_t i;
 136         pgno_t chain;
 137         BTHEADER *h;
 138         CURSOR *c;
 139         DATUM *d;
 140
 141         /* deletion may confuse an active scan.  fix it.  */
 142         c = &(t->bt_cursor);
 143         if (t->bt_flags & BTF_SEQINIT && t->bt_curpage->h_pgno == c->c_pgno)
 144                 if (_bt_fixscan(t, index, (DATUM *) NULL, DELETE) == RET_ERROR)
 145                         return (RET_ERROR);
 146
 147         h = t->bt_curpage;
 148         off = h->h_linp[index];
 149         d = (DATUM *) GETDATUM(h, index);
 150
 151         /* if this is a big item, reclaim the space it occupies */
 152         if (d->d_flags & D_BIGKEY) {
 153                 bcopy(&(d->d_bytes[0]),
 154                       (char *) &chain,
 155                       sizeof(chain));
 156                 if (_bt_delindir(t, chain) == RET_ERROR)
 157                         return (RET_ERROR);
 158                 h = t->bt_curpage;
 159                 d = (DATUM *) GETDATUM(h, index);
 160         }
 161         if (d->d_flags & D_BIGDATA) {
 162                 bcopy(&(d->d_bytes[d->d_ksize]),
 163                       (char *) &chain,
 164                       sizeof(chain));
 165                 if (_bt_delindir(t, chain) == RET_ERROR)
 166                         return (RET_ERROR);
 167                 h = t->bt_curpage;
 168                 d = (DATUM *) GETDATUM(h, index);
 169         }
 170
 171         /* move the data down on the page */
 172         nbytes = d->d_ksize + d->d_dsize
 173                  + (sizeof(DATUM) - sizeof(char));
 174         nbytes = LONGALIGN(nbytes);
 175         src = ((char *) h) + h->h_upper;
 176         dest = src + nbytes;
 177         nmoved = (int) (((char *) d) - src);
 178         (void) bcopy(src, dest, nmoved);
 179
 180         /* next move the line pointers up */
 181         src = (char *) &(h->h_linp[index + 1]);
 182         dest = (char *) &(h->h_linp[index]);
 183         nmoved = (int) (((char *) &(h->h_linp[NEXTINDEX(h)])) - src);
 184         (void) bcopy(src, dest, nmoved);
 185
 186         /* remember that we freed up some space */
 187         h->h_upper += nbytes;
 188         h->h_lower -= sizeof(index_t);
 189
 190         /* adjust offsets in line pointers affected by moving the data */
 191         top = NEXTINDEX(h);
 192         for (i = 0; i < top; i++) {
 193                 if (h->h_linp[i] < off)
 194                         h->h_linp[i] += nbytes;
 195         }
 196
 197         /* it's gone */
 198         h->h_flags |= F_DIRTY;
 199
 200         return (RET_SUCCESS);
 201 }