cde/lib/tt/mini_isam/isbtree.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: isbtree.c /main/3 1995/10/23 11:35:52 rswiston $                                                     */
  28
  29 /*
  30  * Copyright (c) 1988 by Sun Microsystems, Inc.
  31  */
  32
  33 /*
  34  * isbtree.c
  35  *
  36  * Description:
  37  *      B-tree operations: SEARCH
  38  *
  39  */
  40 #include <stdlib.h>
  41
  42 #include "isam_impl.h"
  43
  44
  45 /*
  46  * _isbtree_create()
  47  *
  48  * Create a B-tree path object that will used in subsequent operations.
  49  */
  50
  51 Btree *
  52     _isbtree_create(Fcb *fcb, Keydesc2 *pkeydesc2)
  53 {
  54     Btree       *p;
  55
  56     p = (Btree *) _ismalloc(sizeof(*p));
  57     memset((char *)p, 0, sizeof(*p));
  58
  59     p->fcb = fcb;
  60     p->keydesc2 = pkeydesc2;
  61
  62     return (p);
  63 }
  64
  65
  66 /*
  67  * _isbtr_destroy()
  68  *
  69  * Destroy B-tree path object
  70  */
  71
  72 void
  73 _isbtree_destroy(Btree *btree)
  74 {
  75     int i;
  76
  77     for (i = 0; i < btree->depth;i++) {
  78         _isdisk_unfix(btree->bufhdr[i]);
  79     }
  80     free((char *)btree);
  81 }
  82
  83
  84 /*
  85  * _isbtree_search()
  86  *
  87  * Descend the B-tree, position pointer on or before the matched key.
  88  */
  89
  90 void
  91 _isbtree_search( Btree *btree, char *key)
  92 {
  93     Keydesc2            *pkeydesc2 = btree->keydesc2;
  94     Blkno               rootblkno = pkeydesc2->k2_rootnode;
  95     int                 keylength = pkeydesc2->k2_len;
  96     int                 index;               /* Index to tables in btree */
  97     /* Has value of 1, next 2, etc. */
  98     int                 elevation;           /* Level - leaves have value 0 */
  99     char        *p;                  /* Pointer to key page */
 100     int                 nkeys;               /* Number of keys in the page */
 101     char                *key2;               /* Equal or next lower key */
 102     int                 curpos;              /* index of key2 in key page */
 103     Blkno               blkno;
 104
 105     /* Set comparison function. */
 106     _iskeycmp_set(pkeydesc2, pkeydesc2->k2_nparts + 1); /* +1 for recno field */
 107
 108     index = 0;
 109     blkno = rootblkno;
 110     do {
 111         btree->bufhdr[index] =
 112             _isdisk_fix(btree->fcb,  btree->fcb->indfd, blkno, ISFIXREAD);
 113         p = btree->bufhdr[index]->isb_buffer; /* pointer to buffer */
 114
 115         /* Load some fields from the key page. */
 116         nkeys = ldshort(p+BT_NKEYS_OFF);     /* Number of keys in the page */
 117         elevation = ldshort(p+BT_LEVEL_OFF); /* Level of the page */
 118
 119         /* Binary search in the key page to find equal or next lowere key. */
 120         key2 = _isbsearch(key, p+BT_KEYS_OFF, nkeys, keylength, _iskeycmp);
 121
 122         curpos = (key2) ? ((key2 - p - BT_NKEYS_OFF) / keylength) : 0;
 123
 124         btree->curpos[index] =
 125             (key2 == (char *)0 && elevation==0)? -1 : curpos;
 126
 127         if (elevation > 0)
 128             blkno = ldblkno(p + ISPAGESIZE - (curpos + 1) * BLKNOSIZE);
 129
 130         index++;
 131     } while (elevation > 0);
 132
 133     btree->depth = index;
 134 }
 135
 136 /*
 137  * _isbtree_current()
 138  *
 139  * Get pointer to the current key
 140  */
 141
 142 char *
 143 _isbtree_current(Btree *btree)
 144 {
 145     int                 curpos;
 146
 147     assert(btree->depth > 0);
 148     if ((curpos = btree->curpos[btree->depth - 1]) == -1)
 149         return (NULL);
 150     else
 151         return (btree->bufhdr[btree->depth - 1]->isb_buffer
 152                 + BT_KEYS_OFF + curpos * btree->keydesc2->k2_len);
 153 }
 154
 155 /*
 156  * _isbtree_next()
 157  *
 158  * Get pointer to the next key
 159  */
 160
 161 char *
 162 _isbtree_next(Btree *btree)
 163 {
 164     int                 curpos;
 165     int                 depth = btree->depth;
 166     char        *p;
 167     int level;
 168     Blkno               blkno;
 169
 170     assert(depth > 0);
 171
 172     /*
 173      * Move up along the path, find first block where we can move to the right.
 174      */
 175     for (level = depth - 1; level >= 0; level--) {
 176         p = btree->bufhdr[level]->isb_buffer;
 177
 178         if (btree->curpos[level] < ldshort(p + BT_NKEYS_OFF) - 1)
 179             break;
 180     }
 181
 182     if (level < 0) {
 183         /* Logical end of the index file. No next record. */
 184         return (NULL);
 185     }
 186
 187     curpos = ++(btree->curpos[level]);
 188
 189     while (++level < depth) {
 190
 191         /* Get block number to block in next lower level. */
 192         if (level > 0)
 193             blkno = ldblkno(p + ISPAGESIZE - (curpos + 1) * BLKNOSIZE);
 194
 195         /* Unfix page in this level, fetch its right brother. */
 196         _isdisk_unfix(btree->bufhdr[level]);
 197         btree->bufhdr[level] =
 198             _isdisk_fix(btree->fcb, btree->fcb->indfd, blkno, ISFIXREAD);
 199         p = btree->bufhdr[level]->isb_buffer;
 200
 201         curpos = btree->curpos[level] = 0;
 202     }
 203
 204     return (p + BT_KEYS_OFF + curpos * btree->keydesc2->k2_len);
 205 }