# 2.11BSD#431 - /usr/ingres/source/parser/norml.c

##### Functions

    adjust            X
    mvands            X
    nnorm             X
    norm              X
    norml             X
    notpush           X
    travers           X
    treedup           X

       1: # include   "../ingres.h"
       2: # include   "../aux.h"
       3: # include   "../pipes.h"
       4: # include   "../tree.h"
       5: # include   "../symbol.h"
       6:
       7: /*
       8: ** NORML
       9: **	this routine passes the qualification clause portion of the query
      10: **	tree to the routines for depressing nots and for conjunctive
      11: **	normalization.  It also calls a routine to place an and with one
      12: **	null branch at the rightmost end of the tree.
      13: */
      14: struct querytree *
      15: norml(ptr)
      16: struct querytree    *ptr;
      17: {
      18:     extern struct querytree *nnorm();
      19:     extern struct querytree *travers();
      20:     extern struct querytree *tree();
      21:
      22:     if (ptr == NULL)
      23:         return (tree(NULL, NULL, QLEND, 0, 0));
      24:
      25:     /* push through the 'nots' as far a possible */
      26:     ptr = nnorm(ptr);
      27:
      28:     /* make tree into conjunctive normal form */
      29:     ptr = travers(ptr);
      30:
      31:     /* terminate the list on the rightmost branch */
      32:     adjust(&ptr);
      33:
      34:     /* make 'ands' into a linear list */
      35:     mvands(ptr);
      36:     return (ptr);
      37: }
      38:
      39:
      40: /*
      41: ** NORM
      42: **	this routine takes a tree which has nots only at the lower ends, and
      43: **	places it into conjunctive normal form by repeatedly applying the
      44: **	replacement rule: A or (B and C) ==> (A or B) and (A or C)
      45: */
      46: struct querytree *
      47: norm(p1)
      48: struct querytree    *p1;
      49: {
      50:     extern struct querytree     *tree();
      51:     register struct querytree   *p;
      52:     register struct querytree   *lptr;
      53:     register struct querytree   *rptr;
      54:
      55:     p = p1;
      56:     switch (p->sym.type)
      57:     {
      58:       case AND:
      59:         p->left = norm(p->left);
      60:         p->right = norm(p->right);
      61:         break;
      62:
      63:       case OR:
      64:         if (p->right->sym.type == AND)
      65:         {
      66:         andright:
      67:             /*
      68: 			** combine left subtree with each subtree of the
      69: 			** right subtree
      70: 			*/
      71:             /*
      72: 			** use copy first so that the copy is guaranteed to be
      73: 			** the same as the original
      74: 			*/
      75:             lptr = tree(treedup(p->left), p->right->left, OR, 0, 0);
      76:             rptr = tree(p->left, p->right->right, OR, 0, 0);
      77:             lptr = norm(lptr);
      78:             rptr = norm(rptr);
      79:             /* change node type to AND from OR */
      80:             p->left = lptr;
      81:             p->right = rptr;
      82:             p->sym.type = AND;  /* length is same */
      83:             break;
      84:         }
      85:         if (p->left->sym.type == AND)
      86:         {
      87:         andleft:
      88:             /*
      89: 			** combine right subtree with each subtree of the
      90: 			** left subtree
      91: 			*/
      92:             /*
      93: 			** again, the copy should be used first
      94: 			*/
      95:             lptr = tree(p->left->left, treedup(p->right), OR, 0, 0);
      96:             rptr = tree(p->left->right, p->right, OR, 0, 0);
      97:             lptr = norm(lptr);
      98:             rptr = norm(rptr);
      99:             /* change node type to AND from OR */
     100:             p->left = lptr;
     101:             p->right = rptr;
     102:             p->sym.type = AND;
     103:             break;
     104:         }
     105:         /*
     106: 		** when TRAVERS is being used to optomize the normalization
     107: 		** order there should never be (I think) an OR as a child
     108: 		** of the OR in the parent.  Since TRAVERS works bottom up
     109: 		** in the tree the second OR level should be gone.
     110: 		*/
     111:         if (p->right->sym.type == OR)
     112:         {
     113:             /* skip this (p->sym.type) "or" and normalize the right subtree */
     114:             p->right = norm(p->right);
     115:
     116:             /* now re-try the current node */
     117:             if (p->right->sym.type == AND)
     118:                 goto andright;
     119:             break;
     120:         }
     121:         if (p->left->sym.type == OR)
     122:         {
     123:             /* skip this "or" and normalize the left subtree */
     124:             p->left = norm(p->left);
     125:
     126:             /* now re-try the current node */
     127:             if (p->left->sym.type == AND)
     128:                 goto andleft;
     129:             break;
     130:         }
     131:         break;
     132:     }
     133:     return (p);
     134: }
     135:
     136: /*
     137: ** TRAVERS
     138: **	traverse the tree so that conversion of ORs of ANDs can
     139: **	take place at the innermost clauses first.  IE, normalize
     140: **	before replication rather than after replication.
     141: **
     142: **	This routine need not be used.  The NORM routine will completely
     143: **	traverse the tree and normalize it but...    TRAVERS finds
     144: **	the lowest subtree to normalize first so that sub-trees can
     145: **	be normalized before replication, hence reducing the time required
     146: **	to normalize large trees.  It will also make OR-less trees faster
     147: **	to normalize (since nothing need be done to it).
     148: */
     149: struct querytree *
     150: travers(p1)
     151: struct querytree    *p1;
     152: {
     153:     register struct querytree   *p;
     154:     extern struct querytree     *norm();
     155:
     156:     p = p1;
     157:     if (p->right != NULL)
     158:         p->right = travers(p->right);
     159:     if (p->left != NULL)
     160:         p->left = travers(p->left);
     161:     if (p->sym.type == OR)
     162:         p = norm(p);
     163:     return (p);
     164: }
     165: /*
     166: ** NNORM
     167: **	this routine depresses nots in the query tree to the lowest possible
     168: **	nodes.  It may also affect arithmetic operators in this procedure
     169: */
     170: struct querytree *
     171: nnorm(p1)
     172: struct querytree    *p1;
     173: {
     174:     extern struct querytree     *notpush();
     175:     register struct querytree   *p;
     176:
     177:     p = p1;
     178:     if (p->sym.type == AGHEAD)
     179:     {
     180:         /*
     181: 		** don't need to continue past an AGHEAD
     182: 		** actually, it causes problems if you do
     183: 		** because the qualification on the agg
     184: 		** has already been normalized and the
     185: 		** QLEND needs to stay put
     186: 		*/
     187:         return (p);
     188:     }
     189:     if ((p->sym.type == UOP) && (((struct qt_op *)p)->opno == opNOT))
     190:     {
     191:         /* skip not node */
     192:         p = p->right;
     193:         p = notpush(p);
     194:     }
     195:     else
     196:     {
     197:         if (p->left != NULL)
     198:             p->left = nnorm(p->left);
     199:         if (p->right != NULL)
     200:             p->right = nnorm(p->right);
     201:     }
     202:     return (p);
     203: }
     204:
     205: /*
     206: ** NOTPUSH
     207: **	this routine decides what to do once a not has been found in the
     208: **	query tree
     209: */
     210: struct querytree *
     211: notpush(p1)
     212: struct querytree    *p1;
     213: {
     214:     extern struct querytree     *nnorm();
     215:     register struct querytree   *p;
     216:
     217:     p = p1;
     218:     switch (p->sym.type)
     219:     {
     220:       case AND:
     221:         p->sym.type = OR;
     222:         p->left = notpush(p->left);
     223:         p->right = notpush(p->right);
     224:         break;
     225:
     226:       case OR:
     227:         p->sym.type = AND;
     228:         p->left = notpush(p->left);
     229:         p->right = notpush(p->right);
     230:         break;
     231:
     232:       case BOP:
     233:         switch (((struct qt_op *)p)->opno)
     234:         {
     235:           case opEQ:
     236:             ((struct qt_op *)p)->opno = opNE;
     237:             break;
     238:
     239:           case opNE:
     240:             ((struct qt_op *)p)->opno = opEQ;
     241:             break;
     242:
     243:           case opLT:
     244:             ((struct qt_op *)p)->opno = opGE;
     245:             break;
     246:
     247:           case opGE:
     248:             ((struct qt_op *)p)->opno = opLT;
     249:             break;
     250:
     251:           case opLE:
     252:             ((struct qt_op *)p)->opno = opGT;
     253:             break;
     254:
     255:           case opGT:
     256:             ((struct qt_op *)p)->opno = opLE;
     257:             break;
     258:
     259:           default:
     260:             syserr("strange BOP in notpush '%d'", ((struct qt_op *)p)->opno);
     261:         }
     262:         break;
     263:
     264:       case UOP:
     265:         if (((struct qt_op *)p)->opno == opNOT)
     266:         {
     267:             /* skip not node */
     268:             p = p->right;
     269:             p = nnorm(p);
     270:         }
     271:         else
     272:             syserr("strange UOP in notpush '%d'", ((struct qt_op *)p)->opno);
     273:         break;
     274:
     275:       default:
     276:         syserr("unrecognizable node type in notpush '%d'", p->sym.type);
     277:     }
     278:     return (p);
     279: }
     280:
     281: /*
     282: ** ADJUST
     283: **	terminate qual with an AND and a QLEND at the rightmost branch
     284: */
     285: adjust(pp)
     286: struct querytree    **pp;
     287: {
     288:     extern struct querytree     *tree();
     289:     register struct querytree   *p;
     290:
     291:     p = *pp;
     292:     switch (p->sym.type)
     293:     {
     294:       case AND:
     295:         adjust(&(p->right));
     296:         break;
     297:
     298:       case OR:
     299:       default:
     300:         *pp = tree(p, tree(NULL, NULL, QLEND, 0, NULL), AND, 0, 0);
     301:         break;
     302:     }
     303: }
     304:
     305: struct querytree *treedup(p1)
     306: struct querytree    *p1;
     307: {
     308:     register struct querytree   *np;
     309:     register struct querytree   *p;
     310:     extern char         *Qbuf;
     311:
     312:     if ((p = p1) == NULL)
     313:         return (p);
     314:     np = (struct querytree *) need(Qbuf, (p->sym.len & I1MASK) + 6);
     315:     bmove(p, np, (p->sym.len & I1MASK) + 6);
     316:     np->left = treedup(p->left);
     317:     np->right = treedup(p->right);
     318:     return (np);
     319: }
     320:
     321: /*
     322: **	MVANDS -- pushes all AND's in Qual into linear list
     323: */
     324: mvands(andp)
     325: struct querytree    *andp;
     326: {
     327:     register struct querytree   *ap, *lp, *rp;
     328:
     329:     ap = andp;
     330:     if (ap->sym.type == QLEND)
     331:         return;
     332:     rp = ap->right;
     333:     lp = ap->left;
     334:     if (lp->sym.type == AND)
     335:     {
     336:         ap->left = lp->right;
     337:         ap->right = lp;
     338:         lp->right = rp;
     339:         mvands(ap);
     340:     }
     341:     else
     342:         mvands(rp);
     343: }

#### Defined functions

adjust defined in line 285; used 2 times

- in line 32, 295

mvands defined in line 324; used 3 times

- in line 35, 339-342(2)

nnorm defined in line 170; used 6 times

- in line 18, 26, 198-200(2), 214, 269

norm defined in line 46; used 11 times

- in line 59-60(2), 77-78(2), 97-98(2), 114, 124, 154, 162
- in /usr/ingres/source/parser/tree.c line 27

norml defined in line 14; used 4 times

- in /usr/ingres/source/parser/master.grammar line 326, 369, 497, 507

notpush defined in line 210; used 6 times

- in line 174, 193, 222-229(4)

travers defined in line 149; used 4 times

- in line 19, 29, 158-160(2)

treedup defined in line 305; used 4 times

- in line 75, 95, 316-317(2)

Last modified: 1995-02-19 Generated: 2016-12-26 | Generated by src2html V0.67 page hit count: 1329 |