4.3BSD - /usr/ingres/source/iutil/btree_util.c

   1: #include    <btree.h>
   2: #include    <ingres.h>
   3: #include    <opsys.h>
   4: #include    <sccs.h>
   5: 
   6: SCCSID(@(#)btree_util.c	8.2	1/31/86)
   7: 
   8: /*	Trace up to the root of the BTree, incrementing (or decrementing) all
   9: **	key values.
  10: **
  11: **	Parameters :
  12: **		tree - BTree filename (I)
  13: **		block - starting node from which path is traced (I)
  14: **		inc - either +1 or -1 (I)
  15: */
  16: 
  17: tracepath(rootpage, block, inc)
  18: 
  19: long rootpage;
  20: register struct locator *block;
  21: register int inc;
  22: {
  23:     struct locator  p, child;
  24: 
  25:     if (block->pageno != rootpage)  /* if at root, no need for adjustment */
  26:     {
  27:         bmove(block, &child, sizeof(struct locator));
  28: 
  29:         /* trace up to root node */
  30:         do
  31:         {
  32:             p.pageno = child.page.parent;
  33:             parentkey(child.pageno, &p);
  34:             p.page.node.intnode.key[p.offset] += inc;
  35:             write_node(p.pageno, &p.page);
  36:             bmove(&p, &child, sizeof(struct locator));
  37:         } while (p.pageno != rootpage);
  38:     }
  39: }
  40: 
  41: /*	Determines which key/ptr pair is the parent of the given page
  42: **
  43: **	Parameters :
  44: **		tree - BTree filename (I)
  45: **		block - page number of child (I)
  46: **		prt - information about the parent of the child (I, O)
  47: **
  48: */
  49: 
  50: parentkey(block, prt)
  51: 
  52: long block;
  53: register struct locator *prt;
  54: {
  55:     register int    i;
  56: 
  57:     get_node(prt->pageno, &prt->page);
  58:     /* find pointer in parent which references desired block */
  59:     for (i = 0; prt->page.node.intnode.ptr[i] != block && i < prt->page.nelmts; ++i)
  60:         continue;
  61: 
  62:     if (i == prt->page.nelmts)
  63:         syserr("parentkey: child = %ld", block);
  64:     prt->offset = i;
  65:     return(0);
  66: }
  67: 
  68: /*	Retrieve a node from the BTree
  69: **
  70: **	Parameters :
  71: **		tree - BTree filename (I)
  72: **		pagenum - page number of page to be retrieved (I)
  73: **		buffer - buffer into which page is retrieved (O)
  74: */
  75: 
  76: get_node(pagenum, buffer)
  77: 
  78: long pagenum;
  79: register struct BTreeNode *buffer;
  80: {
  81:     extern int  Btree_fd;
  82: 
  83:     if ( lseek(Btree_fd, pagenum * PGSIZE, 0) == -1 )
  84:         syserr("GET_NODE: seek to %ld failed",pagenum);
  85:     if (read(Btree_fd, buffer, sizeof *buffer) != sizeof *buffer)
  86:         syserr("GET_NODE: read btree, page %ld", pagenum);
  87: }
  88: 
  89: /*	Write a node into the BTree file name
  90: **
  91: **	Parameters :
  92: **		tree - BTree filename (I)
  93: **		pagenum - page number of page to be written (I)
  94: **		buffer - buffer containing page to be written (I)
  95: */
  96: 
  97: write_node(pagenum, buffer)
  98: 
  99: long pagenum;
 100: register struct BTreeNode *buffer;
 101: {
 102:     extern int  Btree_fd;
 103: 
 104:     lseek(Btree_fd, pagenum * PGSIZE, 0);
 105:     if (write(Btree_fd, buffer, sizeof *buffer) != sizeof *buffer)
 106:         syserr("WRITE_NODE: write btree, page %ld", pagenum);
 107: }
 108: 
 109: /*	Retrieves a new page from the BTree file.  If there is an empty page
 110: **	in the file, that page is used.  Otherwise, a new page is added to
 111: **	the end of the file.
 112: **
 113: **	Parameters :
 114: **		tree - BTree filename (I)
 115: **
 116: **	Returns :
 117: **		page number of new page
 118: */
 119: 
 120: long
 121: new_page(tree)
 122: 
 123: char *tree;
 124: {
 125:     int             i;
 126:     long            freepage, newpage;
 127:     struct BTreeNode    page, root, garbage;
 128:     struct stat     fileinfo;
 129:     extern DESC     Btreesec;
 130: 
 131:     get_node(RT, &root);
 132:     freepage = root.parent;
 133:     if (freepage == 0)
 134:     /* no free pages in file, add a new page to the end */
 135:     {
 136:         /* determine page number of page at very end of file */
 137:         stat(tree, &fileinfo);
 138:         newpage = fileinfo.st_size / PGSIZE;
 139:         write_node(newpage, &page);
 140:     }
 141:     else
 142:     /* use first free page, adjusting free page chain */
 143:     {
 144:         newpage = freepage;
 145:         get_node(newpage, &garbage);
 146:         root.parent = garbage.parent;
 147:         write_node(RT, &root);
 148:     }
 149:     return(newpage);
 150: }
 151: 
 152: /*	Returns an empty file to the empty file list.  The head of the list
 153: **	is indicated through the parent of the root and linked together
 154: **	through the parents of the empty pages.
 155: **
 156: **	Parameters :
 157: **		tree - BTree filename (I)
 158: **		pagenum - page number of empty page (I)
 159: */
 160: 
 161: return_page(pagenum)
 162: 
 163: long pagenum;
 164: {
 165:     struct BTreeNode    root, freepage;
 166: 
 167:     /* indicate that page is free by inserting its page number at the
 168: 	** head of the free page list */
 169:     get_node(RT, &root);
 170:     get_node(pagenum, &freepage);
 171:     freepage.parent = root.parent;
 172:     freepage.depth = 0;
 173:     write_node(pagenum, &freepage);
 174:     root.parent = pagenum;
 175:     write_node(RT, &root);
 176: }
 177: 
 178: /*
 179: **	Determine the lid that corresponds to a given position in the B-Tree.
 180: **
 181: **	Parameters :
 182: **		tree - BTree name (I)
 183: **		tidloc - location in BTree (I)
 184: **
 185: **	Returns :
 186: **		lid value
 187: */
 188: get_lid(tidloc, lid)
 189: 
 190: TID *tidloc;
 191: long lid[];
 192: {
 193:     static struct locator   tid;
 194:     register int        i, j;
 195:     long            l, child;
 196: 
 197:     do
 198:     {
 199:         /* determine where in BTree to search */
 200:         pluck_page(tidloc, &tid.pageno);
 201: 
 202:         get_node(tid.pageno, (char *) &tid.page);
 203:         tid.offset = tid.page.node.leafnode.back_ptr[tidloc->line_id & I1MASK];
 204: 
 205:         if (tid.offset > tid.page.nelmts - 1)
 206:             syserr("get_lid: bad tid location %ld, tid.offset=%d, tid.page.nelmts=%d", *tidloc, tid.offset,tid.page.nelmts);
 207: 
 208:         /* scan through leaf */
 209:         for (l = 1, i = tid.offset; i > 0; ++l, --i)
 210:             continue;
 211:         /* trace up to root, adding keys */
 212:         while (!tid.page.depth)
 213:         {
 214:             child = tid.pageno;
 215:             tid.pageno = tid.page.parent;
 216:             parentkey(child, &tid);
 217:             for (i = tid.offset - 1; i >= 0; l += tid.page.node.intnode.key[i--])
 218:                 continue;
 219:         }
 220:         lid[tid.page.depth - 1] = l;
 221: #		ifdef xATR1
 222:             if (tTf(24,0))
 223:                 printf("lid=%ld\n", lid[tid.page.depth - 1]);
 224: #		endif
 225:         bmove(&tid.page.prttree, tidloc, LIDSIZE);
 226:     } while (tid.page.depth > 1);
 227: }
 228: 
 229: /*
 230: **	Uses the secondary btree relation to find the btree tid corresponding
 231: **	to a given main relation tid
 232: */
 233: 
 234: search_btree(mtid, tidloc)
 235: 
 236: TID mtid;
 237: register TID *tidloc;
 238: {
 239:     char        key[2 * LIDSIZE], tup[2 * LIDSIZE];
 240:     TID     tid;
 241:     extern DESC Btreesec;
 242: 
 243: #	ifdef xATR1
 244:         if (tTf(24,0))
 245:         {
 246:             printf("In Search_btree: searching for tid %ld\n", mtid);
 247:             printdesc(&Btreesec);
 248:         }
 249: #	endif
 250:     clearkeys(&Btreesec);
 251:     setkey(&Btreesec, key, &mtid, 1);
 252:     if (!getequal(&Btreesec, key, tup, &tid))
 253:         bmove(tup + LIDSIZE, tidloc, LIDSIZE);
 254:     else
 255:         syserr("search_btree:can't find mtid %ld in btree", mtid);
 256: #	ifdef xATR1
 257:         if (tTf(24,0))
 258:             printup(&Btreesec, tup);
 259: #	endif
 260: }
 261: 
 262: /*
 263: **	Linearly searches the leaves of the BTree for a desired tid
 264: **
 265: **	Parameters :
 266: **		tree - BTree file name (I)
 267: **		tid - desired tid value (I)
 268: **		tidloc - location of the desired tid (O)
 269: */
 270: 
 271: lin_search(level, tid, tidloc, lid, tupcnt)
 272: 
 273: int level;
 274: long tid;
 275: TID *tidloc;
 276: long lid[];
 277: long tupcnt;
 278: {
 279:     struct locator  block;
 280:     register int    i;
 281:     long        page, t, next;
 282:     int     found;
 283:     long        nextpage, count;
 284:     int     forward, first;
 285: 
 286:     page = RT;
 287:     for (i = 0; i < level - 1; ++i)
 288:     {
 289:         t = get_tid(page, lid[i], &block);
 290:         page = t;
 291:     }
 292: 
 293:     found = 0;
 294:     forward  = 0;
 295:     first = 1;
 296:     do
 297:     {
 298:         if (!forward)
 299:         {
 300:             get_node(page, &block.page);
 301:             next = block.page.nexttree;
 302:         }
 303:         count = 0;
 304: 
 305:         /* start at leftmost leaf */
 306:         do
 307:         {
 308:             get_node(page, &block.page);
 309:             if (forward)
 310:                 nextpage = block.page.nexttree;
 311:             else
 312:                 nextpage = block.page.prevtree;
 313:             get_tid(page, 1, &block);
 314:             for ( ; ; )
 315:             {
 316:                 /* search through leaf */
 317:                 for (i = 0; i < block.page.nelmts && block.page.node.leafnode.tid_pos[block.page.node.leafnode.tid_loc[i]] != tid; ++i)
 318:                 {
 319:                     if (!first)
 320:                         ++count;
 321:                 }
 322:                 if (i < block.page.nelmts && block.page.node.leafnode.tid_pos[block.page.node.leafnode.tid_loc[i]] == tid)
 323:                 {
 324:                     found = 1;
 325:                     break;  /* tid found */
 326:                 }
 327:                 first = 0;
 328:                 if (!(block.pageno = block.page.node.leafnode.nextleaf) || count >= tupcnt)
 329:                     break;  /* all leaves exhausted */
 330:                 else
 331:                     /* try leaf to the right */
 332:                     get_node(block.pageno, &block.page);
 333:             }
 334:             if (found || count >= tupcnt)
 335:                 break;
 336:         } while (page = nextpage);
 337:         nextpage = next;
 338:         forward = !forward;
 339:     } while (forward != 0 && !found);
 340:     if (!found)
 341:         syserr("search_btree: tid not found %ld", tid);
 342:     else
 343:     {
 344:         stuff_page(tidloc, &block.pageno);
 345:         tidloc->line_id = block.page.node.leafnode.tid_loc[i];
 346:     }
 347: }
 348: 
 349: /*
 350: **	Determines the value corresponding to the very last lid in the
 351: **	BTree.
 352: **
 353: **	Parameters :
 354: **		tree - BTree file name (I)
 355: **
 356: **	Returns :
 357: **		value of last lid
 358: */
 359: long
 360: last_lid(rootpage)
 361: 
 362: long rootpage;
 363: 
 364: {
 365:     register int        i;
 366:     long            lid;
 367:     struct BTreeNode    root;
 368: 
 369:     lid = 0;
 370:     get_node(rootpage, &root);
 371:     if (root.nodetype == 'L')
 372:         lid = root.nelmts;
 373:     else
 374:         for (i = 0; i < root.nelmts; ++i)
 375:             lid += root.node.intnode.key[i];
 376:     ++lid;
 377:     return(lid);
 378: }
 379: 
 380: /*
 381: **	Changes the tid value stored in the leaf of a BTree node
 382: **
 383: **	Parameters :
 384: **		tree - BTree file name (I)
 385: **		tid - new tid value (I)
 386: **		tidloc - location of tid to be replaced (I)
 387: */
 388: 
 389: replace_btree(tid, tidloc)
 390: 
 391: long tid;
 392: register TID *tidloc;
 393: 
 394: {
 395:     long            pageno;
 396:     struct BTreeNode    p;
 397: 
 398:     pluck_page(tidloc, &pageno);
 399:     get_node(pageno, &p);
 400:     p.node.leafnode.tid_pos[tidloc->line_id] = tid;
 401:     write_node(pageno, &p);
 402: }

Defined functions