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