cde/lib/tt/mini_isam/isbtree3.c

   1 /*
   2  * CDE - Common Desktop Environment
   3  *
   4  * Copyright (c) 1993-2012, The Open Group. All rights reserved.
   5  *
   6  * These libraries and programs are free software; you can
   7  * redistribute them and/or modify them under the terms of the GNU
   8  * Lesser General Public License as published by the Free Software
   9  * Foundation; either version 2 of the License, or (at your option)
  10  * any later version.
  11  *
  12  * These libraries and programs are distributed in the hope that
  13  * they will be useful, but WITHOUT ANY WARRANTY; without even the
  14  * implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  15  * PURPOSE. See the GNU Lesser General Public License for more
  16  * details.
  17  *
  18  * You should have received a copy of the GNU Lesser General Public
  19  * License along with these libraries and programs; if not, write
  20  * to the Free Software Foundation, Inc., 51 Franklin Street, Fifth
  21  * Floor, Boston, MA 02110-1301 USA
  22  */
  23 /*%%  (c) Copyright 1993, 1994 Hewlett-Packard Company                   */
  24 /*%%  (c) Copyright 1993, 1994 International Business Machines Corp.     */
  25 /*%%  (c) Copyright 1993, 1994 Sun Microsystems, Inc.                    */
  26 /*%%  (c) Copyright 1993, 1994 Novell, Inc.                              */
  27 /*%%  $XConsortium: isbtree3.c /main/3 1995/10/23 11:36:12 rswiston $                                                    */
  28 #ifndef lint
  29     static char sccsid[] = "@(#)isbtree3.c 1.5 89/07/17 Copyr 1988 Sun Micro";
  30 #endif
  31
  32 /*
  33  * Copyright (c) 1988 by Sun Microsystems, Inc.
  34  */
  35
  36 /*
  37  * isbtree3.c
  38  *
  39  * Description:
  40  *      B-tree operations: REMOVE
  41  *
  42  */
  43
  44 #include "isam_impl.h"
  45
  46 extern int _iskeycmp();
  47
  48 static void remove_entry(Btree *, char *, int);
  49 static void move_from_right(Btree *, char *, char *, int);
  50 static void move_from_left(Btree *, char *, char *, int);
  51
  52 /* _isbtree_remove() - Remove entry from B-tree ----------------------------*/
  53
  54 void
  55 _isbtree_remove(Btree *btree)
  56 {
  57     struct keydesc2     *pkeydesc2 = btree->keydesc2;
  58     int                 nkeys;               /* Number of keys in the page */
  59     int i;
  60     char                *pkp, *pkp2, *pkp3;
  61     struct bufhdr       *kp2bhdr;
  62     Blkno               blkno2;
  63     int                 level;
  64     int                 capac, halfcapac;
  65     int                 move_keys;
  66
  67     /* Set comparison function. */
  68     _iskeycmp_set(pkeydesc2, pkeydesc2->k2_nparts+1); /* +1 for recno field */
  69
  70     /*
  71      * Main loop.
  72      *  Remove he current entry from leaf.
  73      *  If it was leftmost entry, propagate new leftmost to upper levels.
  74      *  If block has less than capac/2 + 1 entries, either move some entries
  75      *  from next left or right block, or merge with next left or right
  76      *  block.
  77      */
  78
  79     for (i = btree->depth - 1; i >= 0; i--) {
  80
  81         /* Re-fix the current page for update. */
  82         btree->bufhdr[i] = _isdisk_refix(btree->bufhdr[i], ISFIXWRITE);
  83         pkp = btree->bufhdr[i]->isb_buffer;
  84
  85         level = ldshort(pkp + BT_LEVEL_OFF);
  86         capac = ldshort(pkp + BT_CAPAC_OFF); /* Block capacity */
  87         nkeys = ldshort(pkp + BT_NKEYS_OFF); /* Number of keys in block */
  88
  89         halfcapac = (capac+1) >> 1;          /* same as capac/2 + 1 */
  90
  91         assert(level + i + 1 == btree->depth);
  92         assert(i == 0 || nkeys >= halfcapac);
  93
  94         /* Remove entry from this page. */
  95         remove_entry(btree, pkp, btree->curpos[i]);
  96         nkeys--;
  97
  98         /* Must propagate new leftmost key up. */
  99         if (btree->curpos[i] == 0 && i > 0)
 100             leftkey_up(btree, i);
 101
 102         if (nkeys >= halfcapac || i == 0) {
 103
 104             /*
 105              * Page is still balanced. No changes are necessary.
 106              * Also, no chages are needed if this is root block.
 107              */
 108
 109             break;
 110         }
 111         else {
 112
 113             if(btree->curpos[i-1] > 0) {
 114
 115                 /*
 116                  * Block pkp is not the leftmost descendent of its parent.
 117                  * Either merge with left brother, or move a few entries
 118                  * from it.
 119                  */
 120
 121                 pkp3 = btree->bufhdr[i-1]->isb_buffer;
 122
 123                 blkno2 = ldblkno(pkp3 + ISPAGESIZE -
 124                         (btree->curpos[i-1]) * BLKNOSIZE);
 125
 126                 /* Fix the left brother. */
 127                 kp2bhdr = _isdisk_fix(btree->fcb, btree->fcb->indfd,
 128                                       blkno2, ISFIXWRITE);
 129                 pkp2 = kp2bhdr->isb_buffer;
 130
 131                 if (ldshort(pkp2 + BT_NKEYS_OFF) + nkeys > capac) {
 132
 133                     /*
 134                      * Current page cannot be merged with the left brother.
 135                      * Move some entries from the left brother into current.
 136                      */
 137
 138                     move_keys = (ldshort(pkp2 + BT_NKEYS_OFF) - halfcapac +1)/2;
 139                     assert(move_keys > 0);
 140
 141                     move_from_left (btree, pkp2, pkp, move_keys);
 142
 143                     leftkey_up(btree, i);     /* Propagate new leftmost key */
 144
 145                     break;                   /* From main loop */
 146                 }
 147                 else {
 148
 149                     /*
 150                      * Current page and left brotehr will be merged.
 151                      * Move all entries from current into left, and free
 152                      * current.
 153                      */
 154
 155                     /* Move all entries from current into left. */
 156                     move_from_right(btree, pkp2, pkp, nkeys);
 157
 158                     /* Free current page. */
 159                     _isindfreel_free(btree->fcb, btree->bufhdr[i]->isb_blkno);
 160
 161                     btree->bufhdr[i] = kp2bhdr; /* Update search path */
 162
 163                     /* The loop must iterate to delete entry in parent block. */
 164                 }
 165             }
 166             else {
 167
 168                 /*
 169                  * Block pkp is the leftmost descendent of its parent.
 170                  * Either merge with right brother, or move a few entries
 171                  * from it.
 172                  */
 173
 174                 pkp3 = btree->bufhdr[i-1]->isb_buffer;
 175
 176                 blkno2 = ldblkno(pkp3 + ISPAGESIZE -
 177                         (btree->curpos[i-1] + 2) * BLKNOSIZE);
 178
 179                 /* Fix the right brother. */
 180                 kp2bhdr = _isdisk_fix(btree->fcb, btree->fcb->indfd,
 181                                       blkno2, ISFIXWRITE);
 182                 pkp2 = kp2bhdr->isb_buffer;
 183
 184                 if (ldshort(pkp2 + BT_NKEYS_OFF) + nkeys > capac) {
 185
 186                     /*
 187                      * Current page cannot be merged with the right brother.
 188                      * Move some entries from the right brother into current.
 189                      */
 190
 191                     move_keys = (ldshort(pkp2 + BT_NKEYS_OFF) - halfcapac +1)/2;
 192                     assert(move_keys > 0);
 193
 194                     move_from_right(btree, pkp, pkp2, move_keys);
 195
 196                     /* Update search path to go through right brother. */
 197                     btree->curpos[i-1]++;
 198                     btree->bufhdr[i] = kp2bhdr;
 199                     btree->curpos[i] = 0;
 200                     leftkey_up(btree, i);     /* Propagate new leftmost key */
 201
 202                     break;                   /* From main loop */
 203                 }
 204                 else {
 205
 206                     /*
 207                      * Current page and right brother will be merged.
 208                      * Move all entries from right into current, and free
 209                      * right.
 210                      */
 211
 212                     /* Move all entries from right brother into current. */
 213                     move_from_right(btree, pkp, pkp2, ldshort(pkp2 + BT_NKEYS_OFF));
 214
 215                     /* Free right brother page. */
 216                     _isindfreel_free(btree->fcb, kp2bhdr->isb_blkno);
 217
 218                     /* Update search path to point at right brother*/
 219                     btree->curpos[i-1]++;
 220                     /* The loop must iterate to delete entry in parent block. */
 221
 222                 }
 223             }
 224         }
 225     }  /* end of main loop */
 226
 227     if (btree->depth > 1) {
 228         pkp = btree->bufhdr[0]->isb_buffer;
 229
 230         if (ldshort(pkp + BT_NKEYS_OFF) < 2) {
 231
 232             /*
 233              * Root now has only 1 entry and it is not the sole block.
 234              * Replace root with its only descendant, don't change
 235              * root blkno.
 236              */
 237             pkp2 = btree->bufhdr[1]->isb_buffer;
 238             memcpy( pkp,pkp2, ISPAGESIZE);
 239
 240             /* Free page. */
 241             _isindfreel_free(btree->fcb, btree->bufhdr[1]->isb_blkno);
 242         }
 243     }
 244 }
 245
 246
 247 /*--------- remove supporting local functions -------------------------------*/
 248
 249 static void
 250 remove_entry(Btree *btree, char *pkp, int pos)
 251 {
 252     int                 keylength = btree->keydesc2->k2_len;
 253     int                 nkeys = ldshort(pkp + BT_NKEYS_OFF);
 254     int                 level = ldshort(pkp + BT_LEVEL_OFF);
 255
 256     assert(nkeys > 0);
 257     assert(pos >= 0 && pos < nkeys);
 258
 259     /* Shift nkeys - pos - 1 entries to the left. */
 260     memcpy(pkp + BT_KEYS_OFF + pos * keylength,
 261            pkp + BT_KEYS_OFF + (pos + 1) * keylength,
 262            (nkeys - pos - 1) * keylength);
 263
 264     /* For non-leaf nodes, remove block number from table of down pointers. */
 265     if (level > 0) {
 266
 267         memmove(pkp + ISPAGESIZE - (nkeys - 1) * BLKNOSIZE,
 268                pkp + ISPAGESIZE - nkeys * BLKNOSIZE,
 269                (nkeys - pos - 1) * BLKNOSIZE);
 270     }
 271
 272     stshort((short) (nkeys - 1), pkp + BT_NKEYS_OFF);
 273 }
 274
 275 static void
 276 move_from_right(Btree *btree, char *l, char *r, int move_keys)
 277 {
 278     int         keylength = btree->keydesc2->k2_len;
 279     int         lnkeys = ldshort(l + BT_NKEYS_OFF);
 280     int         rnkeys = ldshort(r + BT_NKEYS_OFF);
 281     int         level = ldshort(r + BT_LEVEL_OFF);
 282
 283     /* Move move_keys from l into r block. */
 284     memcpy( l + BT_KEYS_OFF + lnkeys * keylength,r + BT_KEYS_OFF,
 285           move_keys * keylength);
 286
 287     /* Move remaining entries in r to the left side. */
 288     memcpy( r + BT_KEYS_OFF,r + BT_KEYS_OFF + move_keys * keylength,
 289           (rnkeys - move_keys) * keylength);
 290
 291     /* If non-leaf, move the pointers stored at the end of block. */
 292     if (level > 0) {
 293         memcpy(l + ISPAGESIZE - (lnkeys + move_keys) * BLKNOSIZE,
 294                r + ISPAGESIZE - move_keys * BLKNOSIZE,
 295                move_keys * BLKNOSIZE);
 296
 297         memmove(r + ISPAGESIZE - (rnkeys - move_keys) * BLKNOSIZE,
 298                r + ISPAGESIZE - rnkeys * BLKNOSIZE,
 299                (rnkeys - move_keys) * BLKNOSIZE);
 300     }
 301
 302     lnkeys += move_keys;
 303     rnkeys -= move_keys;
 304
 305     stshort((short) lnkeys, l + BT_NKEYS_OFF);
 306     stshort((short) rnkeys, r + BT_NKEYS_OFF);
 307 }
 308
 309 static void
 310 move_from_left(Btree *btree, char *l, char *r, int move_keys)
 311 {
 312     int         keylength = btree->keydesc2->k2_len;
 313     int         lnkeys = ldshort(l + BT_NKEYS_OFF);
 314     int         rnkeys = ldshort(r + BT_NKEYS_OFF);
 315     int         level = ldshort(r + BT_LEVEL_OFF);
 316
 317     /* Move entries in r to the right side to create space for move_keys. */
 318     memmove( r + BT_KEYS_OFF + move_keys * keylength,r + BT_KEYS_OFF,
 319           rnkeys * keylength);
 320
 321     /* Move move_keys from l into r block. */
 322     memcpy( r + BT_KEYS_OFF,l + BT_KEYS_OFF + (lnkeys - move_keys) * keylength,
 323           move_keys * keylength);
 324
 325     /* If non-leaf,  move the pointers stored at the end of block. */
 326     if (level > 0) {
 327
 328         memcpy(r + ISPAGESIZE - (rnkeys + move_keys) * BLKNOSIZE,
 329                r + ISPAGESIZE - rnkeys * BLKNOSIZE,
 330                rnkeys * BLKNOSIZE);
 331
 332         memcpy(r + ISPAGESIZE - move_keys * BLKNOSIZE,
 333                l + ISPAGESIZE - lnkeys * BLKNOSIZE,
 334                move_keys * BLKNOSIZE);
 335     }
 336
 337     lnkeys -= move_keys;
 338     rnkeys += move_keys;
 339
 340     stshort((short) lnkeys, l + BT_NKEYS_OFF);
 341     stshort((short) rnkeys, r + BT_NKEYS_OFF);
 342 }
 343
 344