db.subproj/btree.subproj/bt_delete.c

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