Return to reduction.c CVS log

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

Annotation of 43BSD/ingres/source/decomp/reduction.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(@(#)reduction.c 8.1     12/31/84)
        !             9: 
        !            10: /*
        !            11: **     Reduction -- This file contains routines related to the
        !            12: **     reduction algorithm. The routines are all called by
        !            13: **     decision().
        !            14: **
        !            15: **     Included are:
        !            16: **
        !            17: **             algorithm -- groups clauses according to common variables
        !            18: **
        !            19: **             buildlist -- build linked list of clauses from a query tree
        !            20: **
        !            21: **             construct -- build query trees from link lists of clauses
        !            22: **
        !            23: **             order     -- order a linked list of clauses into the prefered
        !            24: **                             execution sequence
        !            25: */
        !            26: /*
        !            27: **     Algorithm - determine whether query is connected or not
        !            28: **
        !            29: **     Algorithm takes a linked list of query components
        !            30: **     and groups them according to the variables involved
        !            31: **     in each component. If the query is fully interconnected
        !            32: **     then algorithm returns TRUE else it returns FALSE.
        !            33: **
        !            34: **     By definition a constant clause (one involving zero variables)
        !            35: **     is considered to use all variables. Without this rule,
        !            36: **     a query with a null target list would always break into
        !            37: **     two pieces.
        !            38: **
        !            39: **     Whether a query is fully connected is independent
        !            40: **     of whether there are any one variable components
        !            41: **     or not. This includes the target list. After applying
        !            42: **     the algorithm, a scan is made to see how many multi-var
        !            43: **     components are present. If there are two or more multi-var
        !            44: **     components then the query is disconnected.
        !            45: **
        !            46: **     Trace Flags:
        !            47: **             38
        !            48: */
        !            49: 
        !            50: algorithm(clist, varmap)
        !            51: struct complist        *clist;
        !            52: int            varmap;
        !            53: {
        !            54:        register struct complist        *chead, *cnext;
        !            55:        register int                    var;
        !            56:        int                             vmap;
        !            57:        struct complist                 *cprev, *cl;
        !            58: 
        !            59:        vmap = varmap;
        !            60:        for (var = 1; vmap; var <<= 1)
        !            61:        {
        !            62:                if ((vmap & var) == 0)
        !            63:                        continue;
        !            64:                vmap &= ~var;   /* remove var */
        !            65: 
        !            66:                /* done if query is already a single piece */
        !            67:                if (clist->nextcomp == 0)
        !            68:                        break;
        !            69: 
        !            70:                /* find first component using variable var */
        !            71:                for (chead = clist; chead; chead = chead->nextcomp)
        !            72:                {
        !            73:                        if (chead->bitmap == 0 || (chead->bitmap & var))
        !            74:                        {
        !            75:                                /* this component uses variable var */
        !            76: 
        !            77:                                cprev = chead;
        !            78:                
        !            79:                                /* look for other components using variable var */
        !            80:                                for (cnext = chead->nextcomp; cnext; cnext = cnext->nextcomp)
        !            81:                                {
        !            82:                                        if (cnext->bitmap == 0 || (cnext->bitmap & var))
        !            83:                                        {
        !            84:                
        !            85:                                                /*
        !            86:                                                ** Found a component. Remove it from "next"
        !            87:                                                ** link and put it with head piece
        !            88:                                                */
        !            89:                
        !            90:                                                /* remove piece */
        !            91:                                                cprev->nextcomp = cnext->nextcomp;
        !            92:                
        !            93:                                                /* fix up bit map */
        !            94:                                                chead->bitmap |= cnext->bitmap;
        !            95:                
        !            96:                                                /* find end of head component */
        !            97:                                                for (cl = chead; cl->linkcomp; cl = cl->linkcomp);
        !            98:                
        !            99:                                                /* connect with head piece */
        !           100:                                                cl->linkcomp = cnext;
        !           101:                                        }
        !           102:                                        else
        !           103:                                                cprev = cnext;
        !           104:                                }
        !           105:                        }
        !           106:                }
        !           107:        }
        !           108: 
        !           109:        /* return whether connected or not connected */
        !           110:        for (var =0, chead = clist; chead; chead = chead->nextcomp)
        !           111:                if (bitcnt(chead->bitmap) > 1)
        !           112:                        var++; /* this component involves 2 or more vars */
        !           113: 
        !           114:        return (var < 2); /* return TRUE if zero or one component multi-var */
        !           115: }
        !           116: /*
        !           117: **     Buildlist -- Build a component list from a query tree.
        !           118: **
        !           119: **     Each ROOT and AND node is treated as a separate component
        !           120: **     and a linked list is built connecting them. The ROOT node
        !           121: **     MUST be the first element. This list will later be manipulated
        !           122: **     by algorithm() to determine the structure of the query.
        !           123: **
        !           124: **     Returns:
        !           125: **             Head of the list
        !           126: */
        !           127: 
        !           128: struct complist *
        !           129: buildlist(root1, buf)
        !           130: QTREE  *root1;
        !           131: char   *buf;
        !           132: {
        !           133:        register struct complist        *head, *next;
        !           134:        register QTREE                  *root;
        !           135:        struct complist                 *ret;
        !           136:        extern char                     *need();
        !           137: 
        !           138:        ret = (struct complist *) need(buf, 0);
        !           139:        head = 0;
        !           140: 
        !           141:        for (root = root1; root->sym.type != QLEND; root = root->right)
        !           142:        {
        !           143:                next = (struct complist *) need(buf, sizeof (*next));
        !           144:                next->clause = root;
        !           145:                next->nextcomp = next->linkcomp = 0;
        !           146:                next->bitmap = root->sym.value.sym_root.lvarm;
        !           147: 
        !           148:                if (head)
        !           149:                        head->nextcomp = next;
        !           150:                head = next;
        !           151:        }
        !           152:        return (ret);
        !           153: }
        !           154: /*
        !           155: **  Construct -- construct a tree from a list component
        !           156: **
        !           157: **     Construct takes a list head and builds a querytree
        !           158: **     from the components in the list. If the head component
        !           159: **     is the ROOT of the original query, then
        !           160: **     the original ROOT node is reused.
        !           161: **
        !           162: */
        !           163: 
        !           164: QTREE *
        !           165: construct(root, listhead, buf)
        !           166: QTREE          *root;
        !           167: struct complist        *listhead;
        !           168: char           *buf;
        !           169: {
        !           170:        register QTREE                  *ret, *q;
        !           171:        register struct complist        *clist;
        !           172:        extern QTREE                    *makroot();
        !           173: 
        !           174:        clist = listhead;
        !           175: 
        !           176:        /* determine ROOT of tree */
        !           177:        if (root == clist->clause)
        !           178:        {
        !           179:                q = root;
        !           180:                clist = clist->linkcomp;
        !           181:        }
        !           182:        else
        !           183:        {
        !           184:                q = makroot(buf);
        !           185:        }
        !           186:        ret = q;
        !           187:        for (; clist; clist = clist->linkcomp)
        !           188:        {
        !           189:                q->right = clist->clause;
        !           190:                q = q->right;
        !           191:        }
        !           192: 
        !           193:        q->right = De.de_qle;
        !           194: 
        !           195:        mapvar(ret, 1);
        !           196: #      ifdef xDTR1
        !           197:        if (tTf(38, 0))
        !           198:        {
        !           199:                printf("Construct\n");
        !           200:                treepr(ret);
        !           201:        }
        !           202: #      endif
        !           203:        return (ret);
        !           204: }
        !           205: /*
        !           206: **  Order -- order a link list set of query components.
        !           207: **
        !           208: **     Takes a list of components and orders them:
        !           209: **             first - disjoint components
        !           210: **             second - reduction pieces
        !           211: **             last - the original target list piece
        !           212: **
        !           213: **     Return:
        !           214: **             new head of list
        !           215: */
        !           216: 
        !           217: struct complist *
        !           218: order(clist, ovlapvar)
        !           219: struct complist        *clist;
        !           220: int            ovlapvar;
        !           221: {
        !           222:        register struct complist        *cl, *joint, *disjoint;
        !           223:        struct complist                 *xd, *xj, *tlpiece, *ret;
        !           224:        QTREE                           *tmp;
        !           225:        int                             map;
        !           226: 
        !           227:        tlpiece = clist;        /* target list piece always first */
        !           228:        disjoint = joint = 0;
        !           229:        map = ovlapvar >= 0 ? 1 << ovlapvar : 0;
        !           230: 
        !           231:        /* examine each irreducible component for disjointness */
        !           232:        for (cl = tlpiece->nextcomp; cl; cl = cl->nextcomp)
        !           233:        {
        !           234:                if (cl->bitmap & map)
        !           235:                {
        !           236:                        /* joint piece */
        !           237:                        if (joint == 0)
        !           238:                        {
        !           239:                                joint = cl;
        !           240:                                xj = cl;
        !           241:                        }
        !           242:                        else
        !           243:                        {
        !           244:                                joint->nextcomp = cl;
        !           245:                                joint = cl;
        !           246:                        }
        !           247:                }
        !           248:                else
        !           249:                {
        !           250:                        /* disjoint piece */
        !           251:                        if (disjoint == 0)
        !           252:                        {
        !           253:                                disjoint = cl;
        !           254:                                xd = cl;
        !           255:                        }
        !           256:                        else
        !           257:                        {
        !           258:                                disjoint->nextcomp = cl;
        !           259:                                disjoint = cl;
        !           260:                        }
        !           261:                }
        !           262: 
        !           263:        }
        !           264:        /* we now have all disjoint, joint and tl pieces */
        !           265:        /* order them in order (1) xd, (2) xj, (3) tlpiece */
        !           266: 
        !           267:        ret = tlpiece;
        !           268:        tlpiece->nextcomp = 0;
        !           269: 
        !           270:        if (joint)
        !           271:        {
        !           272:                ret = xj;
        !           273:                joint->nextcomp = tlpiece;
        !           274:                if ((tlpiece->bitmap & (~map)) == 0)
        !           275:                {
        !           276:                        /*
        !           277:                        ** This is the special case of the target list
        !           278:                        ** being one (or zero) variable and that variable
        !           279:                        ** is the overlap variable. If left as is, the
        !           280:                        ** reduction will take one step more than is
        !           281:                        ** necessary. The target list piece is combined
        !           282:                        ** with the last joint piece and processed together.
        !           283:                        **
        !           284:                        ** An example of when this will happen is:
        !           285:                        ** ret(p.a) : p.b = s.b ^ p.c = y.c
        !           286:                        **
        !           287:                        ** Reduction would split this up into
        !           288:                        ** (1) ret (p.a,p.b) : p.c = y.c
        !           289:                        ** (2) ret (p.a) : p.b = s.b
        !           290:                        ** (3) ret (p.a)
        !           291:                        **
        !           292:                        ** Here we are allowing pieces (2) & (3) to be done together
        !           293:                        */
        !           294: 
        !           295:                        for (cl = joint; cl->linkcomp; cl = cl->linkcomp);
        !           296: 
        !           297:                        cl->linkcomp = tlpiece;
        !           298:                        joint->nextcomp = 0;
        !           299: 
        !           300:                        /* switch tl clause to top of complist */
        !           301:                        tmp = joint->clause;
        !           302:                        joint->clause = tlpiece->clause;
        !           303:                        tlpiece->clause = tmp;
        !           304:                }
        !           305:        }
        !           306: 
        !           307:        if (disjoint)
        !           308:        {
        !           309:                ret = xd;
        !           310:                disjoint->nextcomp = joint ? xj : tlpiece;
        !           311:        }
        !           312: 
        !           313:        return (ret);
        !           314: }

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