Return to decision.c CVS log

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

Annotation of 43BSD/ingres/source/decomp/decision.c, revision 1.1

1.1     ! root        1: # include      <ingres.h>
        !             2: # include      <symbol.h>
        !             3: # include      <aux.h>
        !             4: # include      <tree.h>
        !             5: # include      "globs.h"
        !             6: # include      <sccs.h>
        !             7: 
        !             8: SCCSID(@(#)decision.c  8.1     12/31/84)
        !             9: 
        !            10: /*
        !            11: ** DECISION -- This file contains code related to deciding how to
        !            12: **     process the remaining query. The main routine is decision()
        !            13: **     and the other routines are called only by decision. The routine
        !            14: **     in this file include:
        !            15: **
        !            16: **     Decision -- Decides how to process a query.
        !            17: **
        !            18: **     Fixtl     -- Determines the target list for each component.
        !            19: **
        !            20: **     Fixresult -- Determines the result relation for the next query
        !            21: **
        !            22: **     Fixrange  -- Adjust the range table after a query
        !            23: **
        !            24: **     Fixovlap  -- Fixes trees in cases where reduction is used
        !            25: **
        !            26: **     Rmovlap   -- Restores trees in cases where reduction was used.
        !            27: **
        !            28: **     Listcomp  -- Debugging routine.
        !            29: */
        !            30: /*
        !            31: **     Decision is given a subquery and decides how to process it.
        !            32: **     The choices are:
        !            33: **             Disjoint pieces -- The original query had disjoint components.
        !            34: **                                     Do each component separately.
        !            35: **             Reduction       -- The query is joined by a single variable.
        !            36: **                                     Reduce the query on that joining variable
        !            37: **                                     and do each component separately.
        !            38: **             Substitution    -- The query is neither disjoint nor reducible.
        !            39: **                                     Process by tuple substitution.
        !            40: **
        !            41: **     Notice that decision() is recursive and will call itself on each
        !            42: **     subcomponent it decides to do. Decision calls various support
        !            43: **     routines in the file "reduction.c".
        !            44: */
        !            45: 
        !            46: decision(root, qmode, result_num, buf)
        !            47: QTREE  *root;
        !            48: int    qmode;
        !            49: int    result_num;
        !            50: char   *buf;
        !            51: {
        !            52:        register QTREE          **qp;
        !            53:        register struct complist *clist;
        !            54:        register int            ovlapvar;
        !            55:        struct complist         *cp;
        !            56:        int                     i, onepiece, qtrue, map;
        !            57:        int                     mark, mark1, cand_map;
        !            58:        QTREE                   *tree, *newtree;
        !            59:        QTREE                   *qlist[MAXRANGE];
        !            60:        int                     newqmode;
        !            61:        int                     ovlaprelnum, newr;
        !            62:        int                     locrange[MAXRANGE];
        !            63:        extern QTREE            *copy_ands();
        !            64:        extern struct complist  *buildlist(), *order();
        !            65:        extern QTREE            *construct();
        !            66: 
        !            67: #      ifdef xDTR1
        !            68:        if (tTf(37, -1))
        !            69:        {
        !            70:                printf("DECISION root=%x,vc=%d,res=%d\n", root, root->sym.value.sym_root.tvarc, result_num);
        !            71:        }
        !            72: #      endif
        !            73:        mark = markbuf(buf);
        !            74:        if (root->sym.value.sym_root.tvarc < 3)
        !            75:        {
        !            76:                /* setup to do as one single piece */
        !            77:                onepiece = TRUE;
        !            78:        }
        !            79:        else
        !            80:        {
        !            81:                /* break the query apart if possible */
        !            82: 
        !            83:                /* build component list */
        !            84:                clist = buildlist(root, buf);
        !            85: #              ifdef xDTR1
        !            86:                if (tTf(37, 2))
        !            87:                        listcomp(clist, "Original Comp");
        !            88: #              endif
        !            89: 
        !            90:                /* is query completely connected or disjoint */
        !            91:                map = root->sym.value.sym_root.lvarm | root->sym.value.sym_root.rvarm;
        !            92:                onepiece = algorithm(clist, map);
        !            93: #              ifdef xDTR1
        !            94:                if (tTf(37, 1))
        !            95:                        printf("Orig query %s\n", onepiece ? "connected" : "disjoint");
        !            96: #              endif
        !            97:                /* assume there is no joining variable */
        !            98:                ovlapvar = -1;
        !            99: 
        !           100:                if (onepiece)
        !           101:                {
        !           102:                        /*
        !           103:                        ** Try to reduce a single connected piece.
        !           104:                        ** In turn each variable will be logically
        !           105:                        ** removed from the query and a test will
        !           106:                        ** be made to see if the query is still
        !           107:                        ** connected.
        !           108:                        */
        !           109: 
        !           110:                        cand_map = map;
        !           111:                        for (i = 1; cand_map; i <<= 1)
        !           112:                        {
        !           113:                                if ((cand_map & i) == 0)
        !           114:                                        continue;
        !           115:                                cand_map &= ~i;
        !           116:                                freebuf(buf, mark);
        !           117:                                clist = buildlist(root, buf);
        !           118:                                if (algorithm(clist, map & ~i) == 0)
        !           119:                                {
        !           120:                                        ovlapvar = bitpos(i);
        !           121:                                        ovlaprelnum = De.de_rangev[ovlapvar].relnum;
        !           122:                                        onepiece = FALSE;
        !           123:                                        break;
        !           124:                                }
        !           125:                        }
        !           126: #                      ifdef xDTR1
        !           127:                        if (tTf(37, 1))
        !           128:                        {
        !           129:                                if (ovlapvar < 0)
        !           130:                                        printf("Query not reducible\n");
        !           131:                                else
        !           132:                                {
        !           133:                                        printf("Query Reducible on %d\n", ovlapvar);
        !           134:                                        if (tTf(37, 3))
        !           135:                                                listcomp(clist, "After reduct");
        !           136:                                }
        !           137:                        }
        !           138: #                      endif
        !           139:                }
        !           140: 
        !           141:                /*
        !           142:                ** If query is more than one piece, build trees
        !           143:                ** for each piece.
        !           144:                */
        !           145: 
        !           146:                if (!onepiece)
        !           147:                {
        !           148:                        /* order pieces */
        !           149:                        clist = order(clist, ovlapvar);
        !           150: #                      ifdef xDTR1
        !           151:                        if (tTf(37, 4))
        !           152:                                listcomp(clist, "After ordering");
        !           153: #                      endif
        !           154:                        cp = clist;
        !           155:                        qp = qlist;
        !           156:                        do
        !           157:                        {
        !           158:                                *qp++ = construct(root, cp, buf);
        !           159:                        } while (cp = cp->nextcomp);
        !           160:                        *qp++ = 0;
        !           161:                }
        !           162:        }
        !           163: 
        !           164:        /*
        !           165:        ** The query is now either the one original piece or
        !           166:        ** is in multiple pieces. The information in clist
        !           167:        ** has been thrown away and now the ordered pieces
        !           168:        ** will be processed.
        !           169:        */
        !           170: 
        !           171:        if (onepiece)
        !           172:        {
        !           173:                freebuf(buf, mark);
        !           174:                qtrue = decompy(root, qmode, result_num, buf);
        !           175:        }
        !           176:        else
        !           177:        {
        !           178:                /* the query is in pieces. prepare to process */
        !           179: 
        !           180:                newquery(locrange);     /* save state of range table */
        !           181: 
        !           182:                /* determine the target list for each piece of the query */
        !           183:                for (qp = qlist; tree = *qp++; )
        !           184:                        fixtl(tree, qp, ovlapvar, buf);
        !           185: 
        !           186:                /* adjust refs to ovlapvar since domain #'s could have changed */
        !           187:                fixovlap(qlist, ovlapvar, buf);
        !           188: 
        !           189: 
        !           190:                /* now process each component */
        !           191:                mark1 = markbuf(buf);
        !           192:                for (qp = qlist; tree = *qp++; )
        !           193:                {
        !           194: 
        !           195: #                      ifdef xDTR1
        !           196:                        if (tTf(37, 6))
        !           197:                        {
        !           198:                                printf("next piece\n");
        !           199:                                treepr(tree);
        !           200:                        }
        !           201: #                      endif
        !           202: 
        !           203:                        /* determine result relation name */
        !           204:                        newr = fixresult(root, tree, &newqmode, qmode, result_num);
        !           205:        
        !           206:                        /*
        !           207:                        ** Run the query. If reduction is being
        !           208:                        ** performed, the actual tree given to
        !           209:                        ** the decision routine must be a copy
        !           210:                        ** to protect from the recursive call changing
        !           211:                        ** the tree. Any work done at this level,
        !           212:                        ** must be to the original tree
        !           213:                        */
        !           214:                        newtree = tree;
        !           215:                        if (ovlapvar != -1)
        !           216:                        {
        !           217:                                freebuf(buf, mark1);
        !           218:                                newtree = copy_ands(tree, buf);
        !           219:                        }
        !           220:                        qtrue = decision(newtree, newqmode, newr, buf);
        !           221:        
        !           222:                        /* fix up the range table */
        !           223:                        fixrange(root, tree, ovlapvar, ovlaprelnum, newr);
        !           224:        
        !           225:                        /* if last piece was false then done */
        !           226:                        if (!qtrue)
        !           227:                                break;
        !           228:        
        !           229:                }
        !           230: 
        !           231:                /* restore the trees */
        !           232:                rmovlap(qlist, ovlapvar);
        !           233: 
        !           234:                /* restore range table back to original */
        !           235:                endquery(locrange, TRUE);       /* reopen previous range */
        !           236: 
        !           237:                /* return any buffer space used */
        !           238:                freebuf(buf, mark);
        !           239:        }
        !           240: 
        !           241:        /* all done with query */
        !           242:        return (qtrue);
        !           243: }
        !           244: /*
        !           245: ** Fixresult -- Determine result relation for "tree" query.
        !           246: **     If "tree" is the original target list piece then use the
        !           247: **             original relation and mode.
        !           248: **     If "tree" is a reduction piece then create a temporary relation
        !           249: **             for it.
        !           250: **     If "tree" is a disjoint piece then there is no target list nor
        !           251: **             result relation.
        !           252: **
        !           253: **     Return:
        !           254: **             result relation number
        !           255: **     Side Effects:
        !           256: **             *newmode is set to the query mode of the next piece
        !           257: */
        !           258: 
        !           259: fixresult(root, tree1, newmode, origmode, resnum)
        !           260: QTREE  *root;
        !           261: QTREE  *tree1;
        !           262: int    *newmode;
        !           263: int    origmode;
        !           264: int    resnum;
        !           265: {
        !           266:        register QTREE  *tree;
        !           267:        register int    newresult;
        !           268: 
        !           269:        tree = tree1;
        !           270:        *newmode = mdRETR;
        !           271:        if (tree->left->sym.type != TREE)
        !           272:        {
        !           273:                if (tree != root)
        !           274:                {
        !           275:                        /* make new result for reduction step */
        !           276:                        newresult = mak_t_rel(tree, "r", -1);
        !           277:                }
        !           278:                else
        !           279:                {
        !           280:                        /* final piece with original result and mode */
        !           281:                        newresult = resnum;
        !           282:                        *newmode = origmode;
        !           283:                }
        !           284:        }
        !           285:        else
        !           286:                newresult = NORESULT;
        !           287:        return (newresult);
        !           288: }
        !           289: /*
        !           290: **     Update range table after a reduction has been processed.
        !           291: **     Only the intermediate reductions will affect the range
        !           292: **     table. The last piece does not.
        !           293: */
        !           294: 
        !           295: fixrange(root, tree, ovlapvar, reductnum, newrelnum)
        !           296: QTREE  *root;
        !           297: QTREE  *tree;
        !           298: int    ovlapvar;
        !           299: int    reductnum;
        !           300: int    newrelnum;
        !           301: {
        !           302:        register int    old;
        !           303:        register int    i;
        !           304:        extern DESC     *openr1();
        !           305: 
        !           306:        if (root != tree)
        !           307:        {
        !           308:                /* this is an intermediate piece */
        !           309:                i = ovlapvar;
        !           310: 
        !           311:                if (newrelnum >= 0)
        !           312:                {
        !           313:                        old = new_range(i, newrelnum);
        !           314:                        if (old != reductnum)
        !           315:                                dstr_rel(old);
        !           316:                        openr1(i);
        !           317:                }
        !           318:        }
        !           319: }
        !           320: /*
        !           321: ** Fixovlap -- Adjust subsequent trees which reference the reduction var
        !           322: **
        !           323: **     If the first query in list redefines the reduction variable
        !           324: **     (if any) then each subsequent query which references the
        !           325: **     reduction variable is adjusted.
        !           326: **     Since there may be multiple pieces,
        !           327: **     subsequence redefinitions are done without
        !           328: **     reallocating buffer space.
        !           329: **
        !           330: */
        !           331: 
        !           332: fixovlap(qlist, ovlapvar, buf)
        !           333: QTREE  *qlist[];
        !           334: int    ovlapvar;
        !           335: char   *buf;
        !           336: {
        !           337:        register QTREE  **qp, *piece, **qp1;
        !           338:        QTREE           *next;
        !           339:        int             ovmap;
        !           340:        extern QTREE    **mksqlist();
        !           341: 
        !           342:        ovmap = 1 << ovlapvar;
        !           343: 
        !           344:        /* for each piece, if it redefines ovlapvar, then fix up rest */
        !           345:        for (qp = qlist; piece = *qp++; )
        !           346:        {
        !           347:                if (piece->sym.value.sym_root.lvarm & ovmap)
        !           348:                {
        !           349:                        for (qp1 = qp; next = *qp1++; )
        !           350:                        {
        !           351:                                if ((next->sym.value.sym_root.lvarm | next->sym.value.sym_root.rvarm) & ovmap)
        !           352:                                {
        !           353:                                        tempvar(next, mksqlist(piece, ovlapvar), buf);
        !           354:                                        buf = NULL;     /* do not allocate on subsequent refs */
        !           355:                                }
        !           356:                        }
        !           357:                }
        !           358:        }
        !           359: }
        !           360: /*
        !           361: ** Rmovlap -- Restore query trees back to their original state.
        !           362: **
        !           363: **     Rmovlap undoes the effect of fixovlap(). Any references
        !           364: **     to the reduction variable which were adjusted are now
        !           365: **     reverted back to the original reference. Note that the
        !           366: **     first piece is not effected by fixovlap.
        !           367: */
        !           368: 
        !           369: rmovlap(qlist, ovlapvar)
        !           370: QTREE  *qlist[];
        !           371: int    ovlapvar;
        !           372: {
        !           373:        register QTREE  **qp, *tree;
        !           374:        int             ovmap;
        !           375: 
        !           376:        if (ovmap = (1 << ovlapvar))
        !           377:        {
        !           378:                /* for each piece, remove any tempvars */
        !           379:                for (qp = &qlist[1]; tree = *qp++; )
        !           380:                {
        !           381:                        origvar(tree, mksqlist(tree, ovlapvar));
        !           382:                }
        !           383:        }
        !           384: }
        !           385: /*
        !           386: ** Fixtl -- Determine what the target list of each tree should be.
        !           387: **
        !           388: **     Fixtl takes each query which references the reduction variable
        !           389: **     and looks for references to that variable in subsequent queries.
        !           390: **     Dfind will build a target list which includes every domain
        !           391: **     which will later be referenced.
        !           392: */
        !           393: 
        !           394: fixtl(tree1, qp1, ovlapvar, buf)
        !           395: QTREE  *tree1;
        !           396: QTREE  *qp1[];
        !           397: int    ovlapvar;
        !           398: char   *buf;
        !           399: {
        !           400:        register QTREE  *tree, **qp, *next;
        !           401:        int             var, map;
        !           402:        extern QTREE    **mksqlist();
        !           403: 
        !           404:        tree = tree1;
        !           405:        var = ovlapvar;
        !           406:        map = 1 << var;
        !           407: 
        !           408:        /*
        !           409:        ** if the last tree referenced the overlap variable then
        !           410:        ** try to fix next tree
        !           411:        */
        !           412:        if (tree->sym.value.sym_root.rvarm & map)
        !           413:        {
        !           414:                qp = qp1;
        !           415:                while (next = *qp++)
        !           416:                {
        !           417:                        if ((next->sym.value.sym_root.lvarm | next->sym.value.sym_root.rvarm) & map)
        !           418:                                dfind(next, buf, mksqlist(tree, var));
        !           419:                }
        !           420:        }
        !           421: }
        !           422: 
        !           423: 
        !           424: 
        !           425: # ifdef        xDTR1
        !           426: 
        !           427: /*
        !           428: **     This is strictly a debuggin routine used for
        !           429: **     printing component lists.
        !           430: */
        !           431: 
        !           432: listcomp(list, mesg)
        !           433: struct complist        *list;
        !           434: char           *mesg;
        !           435: {
        !           436:        register struct complist        *c, *cl;
        !           437:        register int                    i;
        !           438: 
        !           439:        if (tTf(37, 14))
        !           440:        {
        !           441:                printf("%s\n", mesg);
        !           442:            i = -1;
        !           443: 
        !           444:            for (cl = list; cl; cl = cl->nextcomp)
        !           445:            {
        !           446:                    i++;
        !           447:                    printf("Component %d:map=%o\n", i, cl->bitmap);
        !           448:                    for (c = cl; c; c = c->linkcomp)
        !           449:                    {
        !           450:                            printf("%x, ", c->clause);
        !           451:                            if (tTf(37, 15))
        !           452:                            {
        !           453:                                    treepr(c->clause->left);
        !           454:                                    nodepr(c->clause);
        !           455:                            }
        !           456:                    }
        !           457:                    printf("\n");
        !           458:            }
        !           459:     }
        !           460: }
        !           461: # endif

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