![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to reduction.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 reduction.c CVS log | Up to [CSRG BSD Unix] / 42BSD / ingres / source / decomp |
1.1 root 1: # include <ingres.h>
2: # include <symbol.h>
3: # include <aux.h>
4: # include <tree.h>
5: # include "globs.h"
6: # include <sccs.h>
7:
8: SCCSID(@(#)reduction.c 7.1 2/5/81)
9:
10: /*
11: ** Reduction -- This file contains routines related to the
12: ** reduction algorithm. The routines are all called by
13: ** decision().
14: **
15: ** Included are:
16: **
17: ** algorithm -- groups clauses according to common variables
18: **
19: ** buildlist -- build linked list of clauses from a query tree
20: **
21: ** construct -- build query trees from link lists of clauses
22: **
23: ** order -- order a linked list of clauses into the prefered
24: ** execution sequence
25: */
26: /*
27: ** Algorithm - determine whether query is connected or not
28: **
29: ** Algorithm takes a linked list of query components
30: ** and groups them according to the variables involved
31: ** in each component. If the query is fully interconnected
32: ** then algorithm returns TRUE else it returns FALSE.
33: **
34: ** By definition a constant clause (one involving zero variables)
35: ** is considered to use all variables. Without this rule,
36: ** a query with a null target list would always break into
37: ** two pieces.
38: **
39: ** Whether a query is fully connected is independent
40: ** of whether there are any one variable components
41: ** or not. This includes the target list. After applying
42: ** the algorithm, a scan is made to see how many multi-var
43: ** components are present. If there are two or more multi-var
44: ** components then the query is disconnected.
45: **
46: ** Trace Flags:
47: ** 38
48: */
49:
50: algorithm(clist, varmap)
51: struct complist *clist;
52: int varmap;
53: {
54: register struct complist *chead, *cnext;
55: register int var;
56: int vmap;
57: struct complist *cprev, *cl;
58:
59: vmap = varmap;
60: for (var = 1; vmap; var <<= 1)
61: {
62: if ((vmap & var) == 0)
63: continue;
64: vmap &= ~var; /* remove var */
65:
66: /* done if query is already a single piece */
67: if (clist->nextcomp == 0)
68: break;
69:
70: /* find first component using variable var */
71: for (chead = clist; chead; chead = chead->nextcomp)
72: {
73: if (chead->bitmap == 0 || (chead->bitmap & var))
74: {
75: /* this component uses variable var */
76:
77: cprev = chead;
78:
79: /* look for other components using variable var */
80: for (cnext = chead->nextcomp; cnext; cnext = cnext->nextcomp)
81: {
82: if (cnext->bitmap == 0 || (cnext->bitmap & var))
83: {
84:
85: /*
86: ** Found a component. Remove it from "next"
87: ** link and put it with head piece
88: */
89:
90: /* remove piece */
91: cprev->nextcomp = cnext->nextcomp;
92:
93: /* fix up bit map */
94: chead->bitmap |= cnext->bitmap;
95:
96: /* find end of head component */
97: for (cl = chead; cl->linkcomp; cl = cl->linkcomp);
98:
99: /* connect with head piece */
100: cl->linkcomp = cnext;
101: }
102: else
103: cprev = cnext;
104: }
105: }
106: }
107: }
108:
109: /* return whether connected or not connected */
110: for (var =0, chead = clist; chead; chead = chead->nextcomp)
111: if (bitcnt(chead->bitmap) > 1)
112: var++; /* this component involves 2 or more vars */
113:
114: return (var < 2); /* return TRUE if zero or one component multi-var */
115: }
116: /*
117: ** Buildlist -- Build a component list from a query tree.
118: **
119: ** Each ROOT and AND node is treated as a separate component
120: ** and a linked list is built connecting them. The ROOT node
121: ** MUST be the first element. This list will later be manipulated
122: ** by algorithm() to determine the structure of the query.
123: **
124: ** Returns:
125: ** Head of the list
126: */
127:
128: struct complist *
129: buildlist(root1, buf)
130: QTREE *root1;
131: char *buf;
132: {
133: register struct complist *head, *next;
134: register QTREE *root;
135: struct complist *ret;
136: extern char *need();
137:
138: ret = (struct complist *) need(buf, 0);
139: head = 0;
140:
141: for (root = root1; root->sym.type != QLEND; root = root->right)
142: {
143: next = (struct complist *) need(buf, sizeof (*next));
144: next->clause = root;
145: next->nextcomp = next->linkcomp = 0;
146: next->bitmap = root->sym.value.sym_root.lvarm;
147:
148: if (head)
149: head->nextcomp = next;
150: head = next;
151: }
152: return (ret);
153: }
154: /*
155: ** Construct -- construct a tree from a list component
156: **
157: ** Construct takes a list head and builds a querytree
158: ** from the components in the list. If the head component
159: ** is the ROOT of the original query, then
160: ** the original ROOT node is reused.
161: **
162: */
163:
164: QTREE *
165: construct(root, listhead, buf)
166: QTREE *root;
167: struct complist *listhead;
168: char *buf;
169: {
170: register QTREE *ret, *q;
171: register struct complist *clist;
172: extern QTREE *makroot();
173:
174: clist = listhead;
175:
176: /* determine ROOT of tree */
177: if (root == clist->clause)
178: {
179: q = root;
180: clist = clist->linkcomp;
181: }
182: else
183: {
184: q = makroot(buf);
185: }
186: ret = q;
187: for (; clist; clist = clist->linkcomp)
188: {
189: q->right = clist->clause;
190: q = q->right;
191: }
192:
193: q->right = De.de_qle;
194:
195: mapvar(ret, 1);
196: # ifdef xDTR1
197: if (tTf(38, 0))
198: {
199: printf("Construct\n");
200: treepr(ret);
201: }
202: # endif
203: return (ret);
204: }
205: /*
206: ** Order -- order a link list set of query components.
207: **
208: ** Takes a list of components and orders them:
209: ** first - disjoint components
210: ** second - reduction pieces
211: ** last - the original target list piece
212: **
213: ** Return:
214: ** new head of list
215: */
216:
217: struct complist *
218: order(clist, ovlapvar)
219: struct complist *clist;
220: int ovlapvar;
221: {
222: register struct complist *cl, *joint, *disjoint;
223: struct complist *xd, *xj, *tlpiece, *ret;
224: QTREE *tmp;
225: int map;
226:
227: tlpiece = clist; /* target list piece always first */
228: disjoint = joint = 0;
229: map = ovlapvar >= 0 ? 1 << ovlapvar : 0;
230:
231: /* examine each irreducible component for disjointness */
232: for (cl = tlpiece->nextcomp; cl; cl = cl->nextcomp)
233: {
234: if (cl->bitmap & map)
235: {
236: /* joint piece */
237: if (joint == 0)
238: {
239: joint = cl;
240: xj = cl;
241: }
242: else
243: {
244: joint->nextcomp = cl;
245: joint = cl;
246: }
247: }
248: else
249: {
250: /* disjoint piece */
251: if (disjoint == 0)
252: {
253: disjoint = cl;
254: xd = cl;
255: }
256: else
257: {
258: disjoint->nextcomp = cl;
259: disjoint = cl;
260: }
261: }
262:
263: }
264: /* we now have all disjoint, joint and tl pieces */
265: /* order them in order (1) xd, (2) xj, (3) tlpiece */
266:
267: ret = tlpiece;
268: tlpiece->nextcomp = 0;
269:
270: if (joint)
271: {
272: ret = xj;
273: joint->nextcomp = tlpiece;
274: if ((tlpiece->bitmap & (~map)) == 0)
275: {
276: /*
277: ** This is the special case of the target list
278: ** being one (or zero) variable and that variable
279: ** is the overlap variable. If left as is, the
280: ** reduction will take one step more than is
281: ** necessary. The target list piece is combined
282: ** with the last joint piece and processed together.
283: **
284: ** An example of when this will happen is:
285: ** ret(p.a) : p.b = s.b ^ p.c = y.c
286: **
287: ** Reduction would split this up into
288: ** (1) ret (p.a,p.b) : p.c = y.c
289: ** (2) ret (p.a) : p.b = s.b
290: ** (3) ret (p.a)
291: **
292: ** Here we are allowing pieces (2) & (3) to be done together
293: */
294:
295: for (cl = joint; cl->linkcomp; cl = cl->linkcomp);
296:
297: cl->linkcomp = tlpiece;
298: joint->nextcomp = 0;
299:
300: /* switch tl clause to top of complist */
301: tmp = joint->clause;
302: joint->clause = tlpiece->clause;
303: tlpiece->clause = tmp;
304: }
305: }
306:
307: if (disjoint)
308: {
309: ret = xd;
310: disjoint->nextcomp = joint ? xj : tlpiece;
311: }
312:
313: return (ret);
314: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.