Return to btree_util.c CVS log

Up to [CSRG BSD Unix] / 43BSD / ingres / source / iutil

Annotation of 43BSD/ingres/source/iutil/btree_util.c, revision 1.1

1.1     ! root        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: }

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.