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