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