Return to norml.c CVS log

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

Annotation of 43BSD/ingres/source/parser/norml.c, revision 1.1

1.1     ! root        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: }

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