lib/libc/db/btree/updutils.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[] = "@(#)updutils.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 <stdlib.h>
  44 #include <string.h>
  45 #include "btree.h"
  46
  47 /*
  48  *  _BT_FIXSCAN -- Adjust a scan to cope with a change in tree structure.
  49  *
  50  *      If the user has an active scan on the database, and we delete an
  51  *      item from the page the cursor is pointing at, we need to figure
  52  *      out what to do about it.  Basically, the solution is to point
  53  *      "between" keys in the tree, using the CRSR_BEFORE flag.  The
  54  *      requirement is that the user should not miss any data in the
  55  *      tree during a scan, just because he happened to do some deletions
  56  *      or insertions while it was active.
  57  *
  58  *      In order to guarantee that the scan progresses properly, we need
  59  *      to save the key of any deleted item we were pointing at, so that
  60  *      we can check later insertions against it.
  61  *
  62  *      Parameters:
  63  *              t -- tree to adjust
  64  *              index -- index of item at which change was made
  65  *              newd -- new datum (for insertions only)
  66  *              op -- operation (DELETE or INSERT) causing change
  67  *
  68  *      Returns:
  69  *              RET_SUCCESS, RET_ERROR (errno is set).
  70  *
  71  *      Side Effects:
  72  *              None.
  73  */
  74
  75 int
  76 _bt_fixscan(t, index, newd, op)
  77         BTREE_P t;
  78         index_t index;
  79         DATUM *newd;
  80         int op;
  81 {
  82         CURSOR *c;
  83         DATUM *d;
  84
  85         c = &(t->bt_cursor);
  86
  87         if (op == DELETE) {
  88                 if (index < c->c_index)
  89                         c->c_index--;
  90                 else if (index == c->c_index) {
  91                         if (!(c->c_flags & CRSR_BEFORE)) {
  92                                 if (_bt_crsrkey(t) == RET_ERROR)
  93                                         return (RET_ERROR);
  94                                 c->c_flags |= CRSR_BEFORE;
  95                         }
  96                 }
  97         } else {
  98                 /*
  99                  *  If we previously deleted the object at this location,
 100                  *  and now we're inserting a new one, we need to do the
 101                  *  right thing -- the cursor should come either before
 102                  *  or after the new item, depending on the key that was
 103                  *  here, and the new one.
 104                  */
 105
 106                 if (c->c_flags & CRSR_BEFORE) {
 107                         if (index <= c->c_index) {
 108                                 char *tmp;
 109                                 int itmp;
 110                                 pgno_t chain;
 111                                 int r;
 112
 113                                 d = (DATUM *) GETDATUM(t->bt_curpage, index);
 114                                 if (d->d_flags & D_BIGKEY) {
 115                                         bcopy(&(newd->d_bytes[0]),
 116                                               (char *) &chain,
 117                                               sizeof(chain));
 118                                         if (_bt_getbig(t, chain, &tmp, &itmp)
 119                                              == RET_ERROR)
 120                                                 return (RET_ERROR);
 121                                 } else
 122                                         tmp = &(newd->d_bytes[0]);
 123
 124                                 r = (*(t->bt_compare))(tmp, c->c_key);
 125                                 if (r < 0)
 126                                         c->c_index++;
 127
 128                                 if (d->d_flags & D_BIGKEY)
 129                                         (void) free (tmp);
 130                         }
 131                 } else if (index <= c->c_index)
 132                         c->c_index++;
 133         }
 134         return (RET_SUCCESS);
 135 }
 136
 137 /*
 138  *  _BT_CRSRKEY -- Save a copy of the key of the record that the cursor
 139  *                 is pointing to.  The record is about to be deleted.
 140  *
 141  *      Parameters:
 142  *              t -- btree
 143  *
 144  *      Returns:
 145  *              RET_SUCCESS, RET_ERROR.
 146  *
 147  *      Side Effects:
 148  *              Allocates memory for the copy which should be released when
 149  *              it is no longer needed.
 150  */
 151
 152 int
 153 _bt_crsrkey(t)
 154         BTREE_P t;
 155 {
 156         CURSOR *c;
 157         DATUM *d;
 158         pgno_t pgno;
 159         int ignore;
 160
 161         c = &(t->bt_cursor);
 162         d = (DATUM *) GETDATUM(t->bt_curpage, c->c_index);
 163
 164         if (d->d_flags & D_BIGKEY) {
 165                 bcopy(&(d->d_bytes[0]), (char *) &pgno, sizeof(pgno));
 166                 return (_bt_getbig(t, pgno, &(c->c_key), &ignore));
 167         } else {
 168                 if ((c->c_key = (char *) malloc(d->d_ksize)) == (char *) NULL)
 169                         return (RET_ERROR);
 170
 171                 bcopy(&(d->d_bytes[0]), c->c_key, (size_t) (d->d_ksize));
 172         }
 173         return (RET_SUCCESS);
 174 }