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