![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to norml.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 42BSD / ingres / source / parser|
Return to norml.c CVS log | Up to [CSRG BSD Unix] / 42BSD / ingres / source / parser |
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 7.1 2/5/81)
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.