db/recno/rec_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 "recno.h"
  67
  68 static int rec_rdelete __P((BTREE *, recno_t));
  69
  70 /*
  71  * __REC_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 __rec_delete(dbp, key, flags)
  83         const DB *dbp;
  84         const DBT *key;
  85         u_int flags;
  86 {
  87         BTREE *t;
  88         recno_t nrec;
  89         int status;
  90
  91         t = dbp->internal;
  92
  93         /* Toss any page pinned across calls. */
  94         if (t->bt_pinned != NULL) {
  95                 mpool_put(t->bt_mp, t->bt_pinned, 0);
  96                 t->bt_pinned = NULL;
  97         }
  98
  99         switch(flags) {
 100         case 0:
 101                 if ((nrec = *(recno_t *)key->data) == 0)
 102                         goto einval;
 103                 if (nrec > t->bt_nrecs)
 104                         return (RET_SPECIAL);
 105                 --nrec;
 106                 status = rec_rdelete(t, nrec);
 107                 break;
 108         case R_CURSOR:
 109                 if (!ISSET(t, B_SEQINIT))
 110                         goto einval;
 111                 if (t->bt_nrecs == 0)
 112                         return (RET_SPECIAL);
 113                 status = rec_rdelete(t, t->bt_rcursor - 1);
 114                 if (status == RET_SUCCESS)
 115                         --t->bt_rcursor;
 116                 break;
 117         default:
 118 einval:         errno = EINVAL;
 119                 return (RET_ERROR);
 120         }
 121
 122         if (status == RET_SUCCESS)
 123                 SET(t, B_MODIFIED | R_MODIFIED);
 124         return (status);
 125 }
 126
 127 /*
 128  * REC_RDELETE -- Delete the data matching the specified key.
 129  *
 130  * Parameters:
 131  *      tree:   tree
 132  *      nrec:   record to delete
 133  *
 134  * Returns:
 135  *      RET_ERROR, RET_SUCCESS and RET_SPECIAL if the key not found.
 136  */
 137 static int
 138 rec_rdelete(t, nrec)
 139         BTREE *t;
 140         recno_t nrec;
 141 {
 142         EPG *e;
 143         PAGE *h;
 144         int status;
 145
 146         /* Find the record; __rec_search pins the page. */
 147         if ((e = __rec_search(t, nrec, SDELETE)) == NULL)
 148                 return (RET_ERROR);
 149
 150         /* Delete the record. */
 151         h = e->page;
 152         status = __rec_dleaf(t, h, e->index);
 153         if (status != RET_SUCCESS) {
 154                 mpool_put(t->bt_mp, h, 0);
 155                 return (status);
 156         }
 157         mpool_put(t->bt_mp, h, MPOOL_DIRTY);
 158         return (RET_SUCCESS);
 159 }
 160
 161 /*
 162  * __REC_DLEAF -- Delete a single record from a recno leaf page.
 163  *
 164  * Parameters:
 165  *      t:      tree
 166  *      index:  index on current page to delete
 167  *
 168  * Returns:
 169  *      RET_SUCCESS, RET_ERROR.
 170  */
 171 int
 172 __rec_dleaf(t, h, index)
 173         BTREE *t;
 174         PAGE *h;
 175         indx_t index;
 176 {
 177         register RLEAF *rl;
 178         register indx_t *ip, cnt, offset;
 179         register size_t nbytes;
 180         char *from;
 181         void *to;
 182
 183         /*
 184          * Delete a record from a recno leaf page.  Internal records are never
 185          * deleted from internal pages, regardless of the records that caused
 186          * them to be added being deleted.  Pages made empty by deletion are
 187          * not reclaimed.  They are, however, made available for reuse.
 188          *
 189          * Pack the remaining entries at the end of the page, shift the indices
 190          * down, overwriting the deleted record and its index.  If the record
 191          * uses overflow pages, make them available for reuse.
 192          */
 193         to = rl = GETRLEAF(h, index);
 194         if (rl->flags & P_BIGDATA && __ovfl_delete(t, rl->bytes) == RET_ERROR)
 195                 return (RET_ERROR);
 196         nbytes = NRLEAF(rl);
 197
 198         /*
 199          * Compress the key/data pairs.  Compress and adjust the [BR]LEAF
 200          * offsets.  Reset the headers.
 201          */
 202         from = (char *)h + h->upper;
 203         memmove(from + nbytes, from, (char *)to - from);
 204         h->upper += nbytes;
 205
 206         offset = h->linp[index];
 207         for (cnt = &h->linp[index] - (ip = &h->linp[0]); cnt--; ++ip)
 208                 if (ip[0] < offset)
 209                         ip[0] += nbytes;
 210         for (cnt = &h->linp[NEXTINDEX(h)] - ip; --cnt; ++ip)
 211                 ip[0] = ip[1] < offset ? ip[1] + nbytes : ip[1];
 212         h->lower -= sizeof(indx_t);
 213         --t->bt_nrecs;
 214         return (RET_SUCCESS);
 215 }