cde/lib/tt/mini_isam/isbtree2.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: isbtree2.c /main/3 1995/10/23 11:36:02 rswiston $                                                    */
  28
  29 /*
  30  * Copyright (c) 1988 by Sun Microsystems, Inc.
  31  */
  32
  33 /*
  34  * isbtree2.c
  35  *
  36  * Description:
  37  *      B-tree operations:  INSERT
  38  *
  39  */
  40
  41 #include "isam_impl.h"
  42
  43 extern int _iskeycmp();
  44
  45 void leftkey_up(Btree *, int);
  46
  47 static void insert_key(Btree *, char *, int, char *, Blkno);
  48 static void splitblock(Btree *, char *, char *, int);
  49
  50
  51 /* _isbtree_insert() - Insert entry into B-tree ----------------------------*/
  52
  53 void
  54 _isbtree_insert(Btree *btree, char *key)
  55 {
  56     Keydesc2            *pkeydesc2 = btree->keydesc2;
  57     int                 keylength = pkeydesc2->k2_len;
  58     int                 nkeys;               /* Number of keys in the page */
  59     int                 capac;
  60     char                keybuf[MAXKEYSIZE];
  61     int i;
  62     Blkno               blkno;
  63     char                *pkp, *pkp2, *pkp3;
  64     Bufhdr              *kp2bhdr, *kp3bhdr;
  65     Blkno               blkno2, blkno3;
  66     int                 level;
  67     int                 halfcapac;
  68
  69
  70     /*
  71      * Set key comparison function.
  72      */
  73     _iskeycmp_set(pkeydesc2, pkeydesc2->k2_nparts+1); /* +1 for recno field */
  74
  75     /*
  76      * Initialize data structure before main loop.
  77      */
  78     blkno = NULL_BLKNO;
  79     memcpy( keybuf,key, keylength);
  80
  81     /*
  82      * Main loop:
  83      *   Starting from the leaf, insert key after current search position.
  84      *   If necessary make block split and propage changes to upper levels.
  85      *   Root split is handled differently because we don't want to change
  86      *   root block number.
  87      */
  88
  89     for (i = btree->depth - 1; i >= 0; i--) {
  90
  91         /* We have to fix the block for update. */
  92         btree->bufhdr[i] = _isdisk_refix(btree->bufhdr[i], ISFIXWRITE);
  93         pkp = btree->bufhdr[i]->isb_buffer;
  94
  95         level = ldshort(pkp + BT_LEVEL_OFF);
  96         capac = ldshort(pkp + BT_CAPAC_OFF); /* Block capacity */
  97         nkeys = ldshort(pkp + BT_NKEYS_OFF); /* Number of keys in block */
  98
  99         assert(level + i + 1 == btree->depth);
 100         assert(nkeys <= capac);
 101
 102         if (nkeys == capac) {
 103             /*
 104              * This block must be split.
 105              * Allocate new block, move half of the entries into the new
 106              * block, and insert the key into the appropriate
 107              * block. If this block is not root, the loop will iterate
 108              * to update upper levels.
 109              */
 110
 111             /* Get new page. */
 112             kp2bhdr = _allockpage(btree->fcb, capac, level, &blkno2);
 113             pkp2 = kp2bhdr->isb_buffer;
 114
 115             halfcapac = (nkeys+1) >> 1;      /* Same as nkeys/2 + 1 */
 116
 117             splitblock(btree, pkp, pkp2, btree->curpos[i]);
 118
 119             if (btree->curpos[i] > halfcapac - 2) {
 120
 121                 /* Insert entry into right block. */
 122                 insert_key(btree, pkp2, btree->curpos[i] - halfcapac, keybuf,
 123                            blkno);
 124             }
 125             else {
 126                 /* Insert entry into left block. */
 127                 insert_key(btree, pkp, btree->curpos[i], keybuf, blkno);
 128
 129                 if (btree->curpos[i] == -1) /* Leftmost entry inserted - */
 130                     leftkey_up(btree, i);   /* propagate to upper levels. */
 131             }
 132
 133             /* Set variables for next loop iteration. */
 134             memcpy( keybuf,pkp2 + BT_KEYS_OFF, keylength); /* Leftmost key */
 135             blkno = blkno2;
 136
 137             /*
 138              * Next loop iteration will insert entry pointing to
 139              * new allocated page into next upper level.
 140              */
 141         }
 142         else {
 143             /*
 144              * Block split is not necessary. Simply insert key into
 145              * the block. If the inserted key becomes the leftmost entry
 146              * in the block,  update upper levels.
 147              */
 148
 149             insert_key(btree, pkp, btree->curpos[i], keybuf, blkno);
 150
 151             if (btree->curpos[i] == -1 && i > 0)
 152                 leftkey_up(btree, i);
 153
 154             break;                           /* from main loop */
 155         }
 156
 157     }
 158
 159     if (i < 0) {
 160
 161         /*
 162          * Root was split.
 163          * Allocate new page.  However, to keep root block the same,
 164          * the new page is used for the left son of root.
 165          *
 166          * pkp is the new root, pkp3 is the left son,
 167          * and pkp3 is the right of the root.
 168          */
 169
 170         kp3bhdr = _allockpage(btree->fcb, capac, 1, &blkno3);
 171         pkp3 = kp3bhdr->isb_buffer;
 172
 173         memcpy( pkp3,pkp, ISPAGESIZE);
 174
 175         stshort((short) getkeyspernode(keylength), pkp + BT_CAPAC_OFF);
 176         stshort((short) 0, pkp + BT_NKEYS_OFF);
 177         stshort((short)btree->depth, pkp + BT_LEVEL_OFF);
 178
 179         insert_key(btree, pkp, -1, pkp3 + BT_KEYS_OFF, blkno3);
 180         insert_key(btree, pkp, 0 , keybuf, blkno);
 181     }
 182 }
 183
 184 /*--------- insert supporting local functions -------------------------------*/
 185
 186 /* leftkey_up() - Update upper levels with new leftmost entry -----------*/
 187 void
 188 leftkey_up(Btree *btree, int level)
 189 {
 190     int                 keylength = btree->keydesc2->k2_len;
 191     char                *pkp;
 192     char                *key;
 193
 194     pkp = btree->bufhdr[level]->isb_buffer;
 195     key = pkp + BT_KEYS_OFF;                 /* Leftmost key */
 196
 197     while (--level >= 0) {
 198
 199         btree->bufhdr[level] = _isdisk_refix(btree->bufhdr[level], ISFIXWRITE);
 200         pkp = btree->bufhdr[level]->isb_buffer;
 201
 202         memcpy( pkp + BT_KEYS_OFF + (btree->curpos[level] * keylength),key,
 203               keylength);
 204
 205         if (btree->curpos[level] > 0)
 206             break;
 207     }
 208 }
 209
 210 /* insert_key - Insert key into block ------------------------*/
 211 static void
 212 insert_key(Btree *btree, char *pkp, int pos, char *key, Blkno blkno)
 213 {
 214     int         keylength = btree->keydesc2->k2_len;
 215     int         nkeys = ldshort(pkp + BT_NKEYS_OFF);
 216     int         capac = ldshort(pkp + BT_CAPAC_OFF);
 217     int         level = ldshort(pkp + BT_LEVEL_OFF);
 218
 219     assert(nkeys < capac);
 220
 221     /* Shift nkeys - pos - 1 entries to the right. */
 222     /* memmove() handle overlaps correctly */
 223
 224     memmove(pkp + BT_KEYS_OFF + (pos + 2) * keylength,
 225            pkp + BT_KEYS_OFF + (pos + 1) * keylength,
 226            (nkeys - pos - 1) * keylength);
 227
 228     /* Copy new key entry into the block. */
 229     memcpy( pkp + BT_KEYS_OFF + (pos + 1) * keylength,key, keylength);
 230
 231     /* For non-leaf nodes,  insert block number into table of down pointers. */
 232     if (level > 0) {
 233
 234         memcpy(pkp + ISPAGESIZE - (nkeys + 1) * BLKNOSIZE,
 235                pkp + ISPAGESIZE - nkeys * BLKNOSIZE,
 236                (nkeys - pos - 1) * BLKNOSIZE);
 237
 238         stblkno(blkno, pkp + ISPAGESIZE - (pos + 2) * BLKNOSIZE);
 239     }
 240
 241     stshort((short) (nkeys + 1), pkp + BT_NKEYS_OFF);
 242 }
 243
 244 /* splitblock() - Split block into two -----------------------------*/
 245 static void
 246 splitblock(Btree *btree, char *fullpage, char *newpage, int pos)
 247 {
 248     int                 keylength = btree->keydesc2->k2_len;
 249     int                 nkeys, capac, level;
 250     int                 halfcapac;
 251     int                 newpage_nkeys;
 252     int                 fullpage_nkeys;
 253
 254     nkeys = ldshort(fullpage + BT_NKEYS_OFF);
 255     capac = ldshort(fullpage + BT_NKEYS_OFF);
 256     level = ldshort(fullpage + BT_LEVEL_OFF);
 257
 258     assert(nkeys == capac);
 259
 260     halfcapac = (capac + 1) >> 1;            /* same as capac/2 + 1 */
 261
 262     if (pos > halfcapac - 2) {
 263
 264         /* New entry will go into right page(fullpage). */
 265         fullpage_nkeys = halfcapac;
 266         newpage_nkeys   = halfcapac - 1;
 267     }
 268     else {
 269
 270         /* New entry will go into left page (newpage). */
 271         fullpage_nkeys = halfcapac - 1;
 272         newpage_nkeys   = halfcapac;
 273     }
 274
 275     /* Move newpage_nkeys keys into newpage. */
 276     memcpy(newpage + BT_KEYS_OFF,
 277            fullpage + BT_KEYS_OFF + fullpage_nkeys * keylength,
 278            keylength * newpage_nkeys);
 279
 280     /* If non-leaf, move corresponding entries from block number table. */
 281     if (level > 0) {
 282         memcpy(newpage + ISPAGESIZE - newpage_nkeys * BLKNOSIZE,
 283                fullpage + ISPAGESIZE - nkeys * BLKNOSIZE,
 284                newpage_nkeys * BLKNOSIZE);
 285     }
 286
 287     stshort((short) fullpage_nkeys, fullpage + BT_NKEYS_OFF);
 288     stshort((short) newpage_nkeys, newpage + BT_NKEYS_OFF);
 289 }