![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to aggregate.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 / decomp|
Return to aggregate.c CVS log | Up to [CSRG BSD Unix] / 42BSD / ingres / source / decomp |
1.1 root 1: # include <ingres.h>
2: # include <tree.h>
3: # include <symbol.h>
4: # include "globs.h"
5: # include <sccs.h>
6:
7: SCCSID(@(#)aggregate.c 7.2 3/5/81)
8:
9:
10:
11:
12: /*
13: ** AGGREGATE - replace aggregates with their values
14: **
15: ** Aggregate attempts to optimize aggregate processing
16: ** wherever possible. It replaces aggregates with their
17: ** values, and links aggregate functions which have
18: ** identical by-lists together.
19: **
20: ** Note that for the sake of this code, A "prime"
21: ** aggregate is one in which duplicates are removed.
22: ** These are COUNTU, SUMU, and AVGU.
23: **
24: ** Aggregate first forms a list of all aggregates in
25: ** the order they should be processed.
26: **
27: ** For each aggregate, it looks at all other aggregates
28: ** to see if there are two simple aggregates
29: ** or if there is another aggregate funtion with the
30: ** same by-list.
31: **
32: ** An attempt is made to run
33: ** as many aggregates as possible at once. This can be
34: ** done only if two or more aggregates have the same
35: ** qualifications and in the case of aggregate functions,
36: ** they must have identical by-lists.
37: ** Even then, certain combinations
38: ** of aggregates cannot occure together. The list is
39: ** itemized later in the code.
40: **
41: ** Aggregate calls BYEVAL or AGEVAL to actually process
42: ** aggregate functions or aggregates respectively.
43: **
44: ** Trace Flags:
45: ** 40
46: */
47:
48: aggregate(root)
49: QTREE *root;
50: {
51: struct agglist alist[MAXAGG + 1];
52: QTREE *rlist[MAXAGG + 1];
53: struct agglist *al, *al1;
54: register QTREE *agg, *aop1, *r;
55: QTREE *aop, *agg1;
56: int i, simple_agg, varmap;
57: int attcnt, anyagg, attoff, twidth;
58: QTREE *makavar(), *agspace();
59: extern char *rangename();
60: extern QTREE *ageval();
61: extern QTREE *byeval();
62:
63: al = alist;
64: De.de_aggnext = al;
65: De.de_agglim = &al[MAXAGG];
66:
67: findagg(&root, root); /* generate list of all aggregates */
68: De.de_aggnext->agpoint = 0; /* mark end of the list */
69: anyagg = 0;
70:
71: varmap = root->sym.value.sym_root.lvarm | root->sym.value.sym_root.rvarm;
72:
73: /* process each aggregate */
74: for (;agg = al->agpoint; al++)
75: {
76: /* is this still an aggregate? */
77: if (agg->sym.type != AGHEAD)
78: continue;
79: mapvar(agg, 0); /* map the aggregate tree */
80: anyagg++;
81:
82: De.de_sourcevar = bitpos(agg->sym.value.sym_root.lvarm | agg->sym.value.sym_root.rvarm);
83: # ifdef xDTR1
84: if (tTf(40, 4))
85: printf("De.de_sourcevar=%d,rel=%s\n", De.de_sourcevar, rangename(De.de_sourcevar));
86: # endif
87:
88: simple_agg = (agg->left->sym.type == AOP); /* TRUE if no bylist */
89: aop = agg->left; /* assume it was TRUE */
90: # ifdef xDTR1
91: if (tTf(40, 0))
92: printf("%s\n", simple_agg ? "agg" : "agg-func");
93: # endif
94: if (simple_agg)
95: {
96: /* simple aggregate */
97: rlist[0] = agspace(aop);
98: twidth = aop->sym.value.sym_op.opfrml & I1MASK; /* init width to the width of the aggregate */
99: }
100: else
101: {
102: attoff = agg->left->left->sym.value.sym_resdom.resno + 2;
103: aop = aop->right; /* find the AOP node */
104: /* assign new source variable for aggregate */
105: al->agvarno = getrange(&varmap);
106: /* compute width of bylist + count field */
107: twidth = findwid(agg->left) + 4;
108:
109: /* make sure the aggregate does not exceed max dimensions */
110: if (chkwidth(aop, &twidth, attoff))
111: derror(AGFTOBIG);
112: }
113: attcnt = 1; /* one aggregate so far */
114:
115: /* look for another identical aggregate */
116: for (al1 = al + 1; agg1 = al1->agpoint; al1++)
117: {
118:
119: /* if agg is nested inside agg1 then ignore it */
120: if (al->agfather == agg1 || agg1->sym.type != AGHEAD)
121: {
122: continue;
123: }
124:
125: /* split aggs and agg-func apart */
126: /* check for identical aggregate */
127: if (simple_agg)
128: {
129: aop1 = agg1->left; /* find AOP node */
130:
131: if (aop1->sym.type != AOP)
132: continue; /* not a simple agg */
133:
134: /* make sure they can be run together */
135: if (checkagg(agg, aop, agg1, aop1) == 0)
136: continue;
137:
138: if ((i = sameagg(agg, aop1, attcnt)) >= 0)
139: {
140: /* found identical aggregate to rlist[i] */
141: r = rlist[i];
142: }
143: else
144: {
145: /* put this agg in with the others */
146:
147: /* first make sure it won't exceed tuple length */
148: if (chkwidth(aop1, &twidth, 0))
149: continue; /* can't be included */
150: r = rlist[attcnt++] = agspace(aop1);
151:
152: /* connect into tree */
153: aop1->left = agg->left;
154: agg->left = aop1;
155: }
156: }
157: else
158: {
159: /* aggregate function */
160: if (!sameafcn(agg->left->left, agg1->left->left))
161: continue;
162:
163: aop1 = agg1->left->right; /* find AOP */
164:
165:
166: if (checkagg(agg, aop, agg1, aop1) == 0)
167: {
168: /* same by-lists but they can't be run together */
169: continue;
170: }
171:
172: if ((i = sameagg(agg, aop1, attcnt)) < 0)
173: {
174: /* make sure there is room */
175: if (chkwidth(aop1, &twidth, attcnt + attoff))
176: continue;
177:
178: /* add aggregate into tree */
179: i = attcnt++;
180:
181: aop1->left = agg->left->right;
182: agg->left->right = aop1;
183: }
184:
185: r = makavar(aop1, al->agvarno, i + attoff);
186: }
187: /* replace aggregate in original tree with its value */
188: *(al1->father) = r;
189:
190: /* remove aggregate from local list */
191: agg1->sym.type = -1;
192: # ifdef xDTR1
193: if (tTf(40, 3))
194: printf("including aghead %x\n", agg1);
195: # endif
196: }
197:
198: /* process aggregate */
199: if (simple_agg)
200: {
201: rlist[attcnt] = 0;
202: ageval(agg, rlist); /* pass tree and result list */
203: r = rlist[0];
204: }
205: else
206: {
207: opt_bylist(alist, agg);
208: byeval(al->agfather, agg, al->agvarno);
209: r = makavar(aop, al->agvarno, attoff);
210: }
211: /*
212: ** Link result into tree. al->father hold the address
213: ** &(tree->left) or &(tree->right).
214: */
215: *(al->father) = r;
216: # ifdef xDTR1
217: if (tTf(40, 4))
218: {
219: printf("agg value\n");
220: treepr(*(al->father));
221: }
222: # endif
223: }
224: if (anyagg)
225: {
226: opt_bylist(alist, root);
227: mapvar(root, 0); /* remap main tree */
228: }
229: }
230: /*
231: ** findagg builds a list of all aggregates
232: ** in the tree. It finds them by leftmost
233: ** innermost first.
234: **
235: ** The parameters represent:
236: ** nodep: the address of the node pointing to you
237: ** eg. &(tree->left) or &(tree->right)
238: ** agf: the root node. or if we are inside
239: ** a nested aggregate, the AGHEAD node
240: */
241:
242: findagg(nodep, agf)
243: QTREE **nodep;
244: QTREE *agf;
245: {
246: register QTREE *q, *f;
247: register struct agglist *list;
248: int agg;
249:
250: if ((q = *nodep) == NULL)
251: return;
252:
253: f = agf;
254: if (agg = (q->sym.type == AGHEAD))
255: f = q; /* this aggregate is now the father root */
256:
257: /* find all aggregates below */
258: findagg(&(q->left), f);
259: findagg(&(q->right), f);
260:
261: /* if this is an aggregate, put it on the list */
262: if (agg)
263: {
264: if (De.de_aggnext >= De.de_agglim)
265: derror(TOOMANYAGGS);
266: list = De.de_aggnext;
267: list->father = nodep;
268: list->agpoint = q;
269: list->agfather = agf;
270: De.de_aggnext++;
271: }
272: }
273: /*
274: ** Agspace allocates space for the result of
275: ** a simple aggregate.
276: */
277:
278: QTREE *
279: agspace(aop)
280: QTREE *aop;
281: {
282: register QTREE *a, *r;
283: register int length;
284: extern char *need();
285:
286: a = aop;
287: length = a->sym.value.sym_op.opfrml & I1MASK;
288: r = (QTREE *) need(De.de_qbuf, length + QT_HDR_SIZ);
289: r->left = r->right = 0;
290: r->sym.type = a->sym.value.sym_op.opfrmt;
291: r->sym.len = length;
292:
293: return (r);
294: }
295: /*
296: ** Chkwidth -- make sure that the inclusion of another aggregate will
297: ** not exceed the system limit. This means that the total width
298: ** cannot exceed MAXTUP and the number of domains cannot exceed MAXDOM-1
299: */
300:
301: chkwidth(aop, widthp, domno)
302: QTREE *aop;
303: int *widthp;
304: int domno;
305: {
306: register int width;
307:
308: width = *widthp;
309:
310: # ifdef xDTR1
311: if (tTf(40, 10))
312: printf("agg width %d,dom %d\n", width, domno);
313: # endif
314:
315: width += (aop->sym.value.sym_op.opfrml & I1MASK);
316:
317: if (width > MAXTUP || domno > MAXDOM - 1)
318: return (1);
319:
320: *widthp = width;
321: return (0);
322: }
323: /*
324: ** Determine whether an aggregate is prime
325: ** or a don't care aggregate. Returns TRUE
326: ** if COUNTU,SUMU,AVGU,MIN,MAX,ANY.
327: ** Returns false if COUNT,SUM,AVG.
328: */
329:
330: cprime(aop)
331: QTREE *aop;
332: {
333: register int i;
334:
335: i = TRUE;
336: switch (aop->sym.value.sym_op.opno)
337: {
338: case opCOUNT:
339: case opSUM:
340: case opAVG:
341: i = FALSE;
342: }
343: return (i);
344: }
345: /*
346: ** Getrange find a free slot in the range table
347: ** for an aggregate function.
348: **
349: ** If there are no free slots,derror is called
350: */
351:
352: getrange(varmap)
353: int *varmap;
354: {
355: register int i, map, bit;
356:
357: map = *varmap;
358:
359: for (i = 0; i < MAXRANGE; i++)
360: {
361: /* if slot is used, continue */
362: if ((bit = 1 << i) & map)
363: continue;
364:
365: map |= bit; /* "or" bit into the map */
366: *varmap = map;
367:
368: # ifdef xDTR1
369: if (tTf(40, 10))
370: printf("Assn var %d, map %o\n", i, map);
371: # endif
372:
373: return (i);
374: }
375: derror(NODESCAG);
376: return (-1);
377: }
378:
379:
380: checkagg(aghead1, aop1, aghead2, aop2)
381: QTREE *aghead1;
382: QTREE *aop1;
383: QTREE *aghead2;
384: QTREE *aop2;
385: {
386: register QTREE *aop_1, *aop_2, *agg1;
387: int ok;
388:
389: /* two aggregate functions can be run together
390: ** according to the following table:
391: **
392: ** prime !prime don't care
393: **
394: ** prime afcn? never afcn?
395: ** !prime never always always
396: ** don't care afcn? always always
397: **
398: ** don't care includes: ANY, MIN, MAX
399: ** afcn? means only if a-fcn's are identical
400: */
401:
402: aop_1 = aop1;
403: aop_2 = aop2;
404: agg1 = aghead1;
405:
406: if (!prime(aop_1) && !prime(aop_2))
407: ok = TRUE;
408: else
409: if (sameafcn(aop_1->right, aop_2->right))
410: ok = cprime(aop_1) && cprime(aop_2);
411: else
412: ok = FALSE;
413: /* The two aggregates must range over the same variables */
414: if ((agg1->sym.value.sym_root.lvarm | agg1->sym.value.sym_root.rvarm) != (aghead2->sym.value.sym_root.lvarm | aghead2->sym.value.sym_root.rvarm))
415: ok = FALSE;
416:
417:
418: /* check the qualifications */
419: if (ok)
420: ok = sameafcn(agg1->right, aghead2->right);
421: return (ok);
422: }
423:
424:
425: sameagg(aghead, newaop, agg_depth)
426: QTREE *aghead;
427: QTREE *newaop;
428: int agg_depth;
429: {
430: register QTREE *agg, *newa;
431: register int i;
432:
433: agg = aghead;
434: newa = newaop;
435: agg = agg->left;
436: if (agg->sym.type == BYHEAD)
437: agg = agg->right;
438:
439: /* agg now points to first aggregate */
440: for (i = 1; agg; agg = agg->left, i++)
441: if (sameafcn(agg->right, newa->right) && agg->sym.value.sym_resdom.resno == newa->sym.value.sym_op.opno)
442: {
443: # ifdef xDTR1
444: if (tTf(40, 6))
445: printf("found identical aop %x\n", newa);
446: # endif
447: return (agg_depth - i);
448: }
449:
450: /* no match */
451: return (-1);
452: }
453:
454:
455:
456:
457: opt_bylist(alist, root)
458: struct agglist *alist;
459: QTREE *root;
460: {
461: register struct agglist *al;
462: register QTREE *agg;
463: register struct hitlist *hl;
464: QTREE **tpr, *tree, *lnodv[MAXDOM+2];
465: struct hitlist hlist[30];
466: int anyop, i, usedmap, vars, treemap;
467:
468: /* compute bitmap of all possible vars in tree (can include xtra vars) */
469: treemap = root->sym.value.sym_root.lvarm | root->sym.value.sym_root.rvarm;
470: anyop = FALSE;
471:
472: /* scan the list of aggregates looking for one nested in root */
473: for (al = alist; (agg = al->agpoint) && agg != root; al++)
474: {
475: if (agg->sym.type == AGHEAD && agg->left->sym.type == BYHEAD &&
476: al->agfather == root)
477: {
478:
479: /* this aggregate function is nested in root */
480:
481: /* make sure it has some vars of interest */
482: if ((treemap & varfind(agg->left->left, (QTREE *)NULL)) == 0)
483: continue;
484:
485: # ifdef xDTR1
486: if (tTf(40, 11))
487: {
488: printf("nested agg\n");
489: treepr(agg);
490: }
491: # endif
492:
493: /* form list of bydomains */
494: lnodv[lnode(agg->left->left, lnodv, 0)] = 0;
495: usedmap = 0;
496:
497: De.de_hnext = &hlist[0];
498: De.de_hlimit = &hlist[30];
499:
500: /* find all possible replacements */
501: vars = modtree(&root, lnodv, &usedmap);
502:
503: /*
504: ** All references to a variable must be replaced
505: ** in order to use this aggregates by-domains.
506: */
507: if (usedmap && ((vars & usedmap) == 0))
508: {
509: # ifdef xDTR1
510: if (tTf(40, 7))
511: printf("Committed\n");
512: # endif
513: /* success. Committ the tree changes */
514: De.de_hnext->trepr = NULL;
515:
516: for (hl = &hlist[0]; tpr = hl->trepr; hl++)
517: {
518: /* get bydomain number */
519: i = hl->byno;
520:
521: /* get node being replaced */
522: tree = *tpr;
523:
524: /* if it is already a var, just change it */
525: if (tree->sym.type == VAR)
526: {
527: tree->sym.value.sym_var.varno = al->agvarno;
528: tree->sym.value.sym_var.attno = i + 2;
529: }
530: else
531: *tpr = makavar(lnodv[i], al->agvarno, i + 2);
532:
533: anyop = TRUE;
534: # ifdef xDTR1
535: if (tTf(40, 7))
536: {
537: printf("modified tree\n");
538: treepr(*tpr);
539: }
540: # endif
541: }
542: }
543: /* vars is now a map of the variables in the root */
544: treemap = vars;
545: }
546: }
547:
548: /* if any changes were made, get rid of the unnecessary links */
549: if (anyop)
550: chklink(root);
551: }
552:
553:
554:
555:
556: modtree(pnode, lnodv, replmap)
557: QTREE **pnode;
558: QTREE *lnodv[];
559: int *replmap;
560: {
561: register QTREE *tree;
562: register int vars, i;
563: QTREE *afcn;
564:
565: /* point up current node */
566: if ((tree = *pnode) == NULL)
567: return (0);
568:
569: /* examine each by-list for match on this subtree */
570: for (i = 0; afcn = lnodv[i]; i++)
571: {
572: if (sameafcn(tree, afcn->right))
573: {
574: # ifdef xDTR1
575: if (tTf(40, 9))
576: {
577: printf("potential Jackpot");
578: treepr(tree);
579: }
580: # endif
581: vars = varfind(tree, (QTREE *)NULL);
582: if (De.de_hnext == De.de_hlimit)
583: return (vars); /* no more room */
584:
585: /* record what needs to be done */
586: De.de_hnext->trepr = pnode;
587: De.de_hnext->byno = i;
588: De.de_hnext++;
589: *replmap |= vars;
590: return (0);
591: }
592: }
593: if (tree->sym.type == VAR)
594: return (01 << tree->sym.value.sym_var.varno);
595:
596: /* try the subtrees */
597: vars = modtree(&(tree->left), lnodv, replmap);
598: if ((vars & *replmap) == 0)
599: vars |= modtree(&(tree->right), lnodv, replmap);
600:
601: return (vars);
602: }
603:
604:
605: chklink(root)
606: QTREE *root;
607: {
608: register QTREE *r, *b, *last;
609:
610: last = root;
611:
612: for (r = last->right; r->sym.type != QLEND; r = r->right)
613: {
614: /* if this is an EQ node then check for an unnecessary compare */
615: if ((b = r->left)->sym.type == BOP && b->sym.value.sym_op.opno == opEQ)
616: {
617: if (sameafcn(b->left, b->right))
618: {
619: # ifdef xDTR1
620: if (tTf(40, 5))
621: {
622: printf("unnec clause\n");
623: treepr(b);
624: }
625: # endif
626: last->right = r->right;
627: continue;
628: }
629: }
630: last = r;
631: }
632: }
633:
634:
635:
636: sameafcn(q1, q2)
637: QTREE *q1, *q2;
638: {
639:
640: register QTREE *t1, *t2;
641: register int len;
642: int type;
643:
644: t1 = q1;
645: t2 = q2;
646:
647: if (!(t1 && t2))
648: return(!(t1 || t2));
649: len = (t1->sym.len & 0377) + SYM_HDR_SIZ;
650: type = t1->sym.type;
651: if (type == VAR)
652: len = sizeof(struct varnode);
653: if (type == AND)
654: len = 2;
655: if (!bequal(&t1->sym.type, &t2->sym.type, len))
656: return(0);
657: return(sameafcn(t1->left,t2->left) && sameafcn(t1->right,t2->right));
658: }
659: /*
660: ** varfind -- find all variables in the tree pointed to by "root".
661: ** Examine all parts of the tree except aggregates. For
662: ** aggregates, ignore simple aggregate and look only
663: ** at the by-lists of aggregate functions. If the aggregate
664: ** is "aghead" then ignore it. There is no reason to look
665: ** at yourself!!!!
666: ** This routine is called by byeval() to determine
667: ** whether to link the aggregate to the root tree.
668: **
669: ** Curiosity note: since the tree being examined has not been
670: ** processed by decomp yet, ckvar does not need to be called
671: ** since the var could not have been altered.
672: */
673:
674: varfind(root, aghead)
675: QTREE *root;
676: QTREE *aghead;
677: {
678: register QTREE *tree;
679: register int type;
680:
681: if ((tree = root) == NULL)
682: return (0);
683:
684: if ((type = tree->sym.type) == AGHEAD)
685: {
686: /* ignore if it matches aghead */
687: if (tree == aghead)
688: return (0);
689: /* if this is an aggregate function, look at bylist */
690: tree = tree->left;
691: if ((type = tree->sym.type) != BYHEAD)
692: return (0);
693: }
694:
695: if (type == VAR)
696: return (1 << tree->sym.value.sym_var.varno);
697:
698: return (varfind(tree->left, aghead) | varfind(tree->right, aghead));
699: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.