# 2.11BSD#431 - /usr/ingres/source/decomp/reduction.c

##### Functions

    algorithm         X
    buildlist         X
    construct         X
    order             X

       1: # include   "../ingres.h"
       2: # include   "../symbol.h"
       3: # include   "../tree.h"
       4: # include   "decomp.h"
       5:
       6: /*
       7: **	Reduction -- This file contains routines related to the
       8: **	reduction algorithm. The routines are all called by
       9: **	decision().
      10: **
      11: **	Included are:
      12: **
      13: **		algorithm -- groups clauses according to common variables
      14: **
      15: **		buildlist -- build linked list of clauses from a query tree
      16: **
      17: **		construct -- build query trees from link lists of clauses
      18: **
      19: **		order     -- order a linked list of clauses into the prefered
      20: **				execution sequence
      21: */
      22:
      23:
      24: algorithm(clist, varmap)
      25: struct complist *clist;
      26: int     varmap;
      27:
      28: /*
      29: **	Algorithm - determine whether query is connected or not
      30: **
      31: **	Algorithm takes a linked list of query components
      32: **	and groups them according to the variables involved
      33: **	in each component. If the query is fully interconnected
      34: **	then algorithm returns TRUE else it returns FALSE.
      35: **
      36: **	By definition a constant clause (one involving zero variables)
      37: **	is considered to use all variables. Without this rule,
      38: **	a query with a null target list would always break into
      39: **	two pieces.
      40: **
      41: **	Whether a query is fully connected is independent
      42: **	of whether there are any one variable components
      43: **	or not. This includes the target list. After applying
      44: **	the algorithm, a scan is made to see how many multi-var
      45: **	components are present. If there are two or more multi-var
      46: **	components then the query is disconnected.
      47: */
      48:
      49: {
      50:     register struct complist    *chead, *cnext;
      51:     register int            var;
      52:     int             vmap;
      53:     struct complist         *cprev, *cl;
      54:
      55:     vmap = varmap;
      56:     for (var = 1; vmap; var <<= 1)
      57:     {
      58:         if ((vmap & var) == 0)
      59:             continue;
      60:         vmap &= ~var;   /* remove var */
      61:
      62:         /* done if query is already a single piece */
      63:         if (clist->nextcomp == 0)
      64:             break;
      65:
      66:         /* find first component using variable var */
      67:         for (chead = clist; chead; chead = chead->nextcomp)
      68:         {
      69:             if (chead->bitmap == 0 || (chead->bitmap & var))
      70:             {
      71:                 /* this component uses variable var */
      72:
      73:                 cprev = chead;
      74:
      75:                 /* look for other components using variable var */
      76:                 for (cnext = chead->nextcomp; cnext; cnext = cnext->nextcomp)
      77:                 {
      78:                     if (cnext->bitmap == 0 || (cnext->bitmap & var))
      79:                     {
      80:
      81:                         /*
      82: 						** Found a component. Remove it from "next"
      83: 						** link and put it with head piece
      84: 						*/
      85:
      86:                         /* remove piece */
      87:                         cprev->nextcomp = cnext->nextcomp;
      88:
      89:                         /* fix up bit map */
      90:                         chead->bitmap |= cnext->bitmap;
      91:
      92:                         /* find end of head component */
      93:                         for (cl = chead; cl->linkcomp; cl = cl->linkcomp);
      94:
      95:                         /* connect with head piece */
      96:                         cl->linkcomp = cnext;
      97:                     }
      98:                     else
      99:                         cprev = cnext;
     100:                 }
     101:             }
     102:         }
     103:     }
     104:
     105:     /* return whether connected or not connected */
     106:     for (var =0, chead = clist; chead; chead = chead->nextcomp)
     107:         if (bitcnt(chead->bitmap) > 1)
     108:             var++; /* this component involves 2 or more vars */
     109:
     110:     return (var < 2); /* return TRUE if zero or one component multi-var */
     111: }
     112:
     113:
     114: struct complist *buildlist(root1, buf)
     115: struct querytree    *root1;
     116: char            *buf;
     117:
     118: /*
     119: **	Buildlist -- Build a component list from a query tree.
     120: **
     121: **	Each ROOT and AND node is treated as a separate component
     122: **	and a linked list is built connecting them. The ROOT node
     123: **	MUST be the first element. This list will later be manipulated
     124: **	by algorithm() to determine the structure of the query.
     125: **
     126: **	Returns:
     127: **		Head of the list
     128: */
     129:
     130: {
     131:     register struct complist    *head, *next;
     132:     register struct querytree   *root;
     133:     struct complist         *ret;
     134:     extern struct querytree     *need();
     135:
     136:     ret = (struct complist *) need(buf, 0);
     137:     head = 0;
     138:
     139:     for (root = root1; root->sym.type != QLEND; root = root->right)
     140:     {
     141:         next = (struct complist *) need(buf, sizeof (struct complist));
     142:         next->clause = root;
     143:         next->nextcomp = next->linkcomp = 0;
     144:         next->bitmap = ((struct qt_root *)root)->lvarm;
     145:
     146:         if (head)
     147:             head->nextcomp = next;
     148:         head = next;
     149:     }
     150:     return (ret);
     151: }
     152:
     153:
     154: struct querytree *construct(root, listhead, buf)
     155: struct querytree    *root;
     156: struct complist     *listhead;
     157: char            *buf;
     158:
     159: /*
     160: **  Construct -- construct a tree from a list component
     161: **
     162: **	Construct takes a list head and builds a querytree
     163: **	from the components in the list. If the head component
     164: **	is the ROOT of the original query, then
     165: **	the original ROOT node is reused.
     166: **
     167: */
     168:
     169: {
     170:     register struct querytree   *ret, *q;
     171:     register struct complist    *clist;
     172:     extern struct querytree     *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 = Qle;
     194:
     195:     mapvar(ret, 1);
     196: #	ifdef xDTR1
     197:     if (tTf(16, 0))
     198:         printree(ret, "Construct");
     199: #	endif
     200:     return (ret);
     201: }
     202:
     203:
     204:
     205: struct complist *order(clist, ovlapvar)
     206: struct complist *clist;
     207: int     ovlapvar;
     208:
     209: /*
     210: **  Order -- order a link list set of query components.
     211: **
     212: **	Takes a list of components and orders them:
     213: **		first - disjoint components
     214: **		second - reduction pieces
     215: **		last - the original target list piece
     216: **
     217: **	Return:
     218: **		new head of list
     219: */
     220:
     221: {
     222:     register struct complist    *cl, *joint, *disjoint;
     223:     struct complist         *xd, *xj, *tlpiece, *ret;
     224:     struct querytree        *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: }

#### Defined functions

algorithm defined in line 24; used 2 times

- in /usr/ingres/source/decomp/decision.c line 90, 116

buildlist defined in line 114; used 3 times

- in /usr/ingres/source/decomp/decision.c line 56, 82, 115

construct defined in line 154; used 2 times

- in /usr/ingres/source/decomp/decision.c line 59, 156

order defined in line 205; used 2 times

- in /usr/ingres/source/decomp/decision.c line 56, 147

Last modified: 1995-04-14 Generated: 2016-12-26 | Generated by src2html V0.67 page hit count: 1095 |