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