4.3BSD - /usr/ingres/source/parser/norml.c

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

Defined functions