![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to misetclip.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv9 / X11 / src / X.V11R1 / server / ddx / mi|
Return to misetclip.c CVS log | Up to [Research Unix] / researchv9 / X11 / src / X.V11R1 / server / ddx / mi |
1.1 root 1: /***********************************************************
2: Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts,
3: and the Massachusetts Institute of Technology, Cambridge, Massachusetts.
4:
5: All Rights Reserved
6:
7: Permission to use, copy, modify, and distribute this software and its
8: documentation for any purpose and without fee is hereby granted,
9: provided that the above copyright notice appear in all copies and that
10: both that copyright notice and this permission notice appear in
11: supporting documentation, and that the names of Digital or MIT not be
12: used in advertising or publicity pertaining to distribution of the
13: software without specific, written prior permission.
14:
15: DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
16: ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
17: DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
18: ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
19: WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
20: ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
21: SOFTWARE.
22:
23: ******************************************************************/
24: /* $Header: misetclip.c,v 1.4 87/09/11 07:20:53 toddb Exp $ */
25: /* Author: Todd Newman */
26:
27: #include "X.h"
28: #include "Xprotostr.h"
29: #include "miscstruct.h"
30: #include "scrnintstr.h"
31: #include "pixmap.h"
32: #include "regionstr.h"
33: #include "gcstruct.h"
34:
35: /* The file name is something of a misnomer. Actually, this just contains
36: * a routine to convert a set of rectangles into a region
37: */
38:
39: typedef struct _ybucket
40: {
41: short y;
42: short count;
43: BoxPtr boxes;
44: short miny2;
45: short fdiff; /* do any have different y2s */
46: struct _ybucket *next;
47: } YBUCKET;
48:
49:
50: /* NEWBUCKET -- a private helper to build a bucket for sorting */
51: static
52: YBUCKET *
53: newbucket(y, miny2)
54: {
55: YBUCKET *pb;
56:
57: pb = (YBUCKET *) Xalloc( sizeof(YBUCKET));
58: pb->count = 0;
59: pb->y = y;
60: pb->miny2 = miny2;
61: pb->fdiff = FALSE;
62: pb->boxes = (BoxPtr)Xalloc(sizeof(BoxRec));
63: pb->next = (YBUCKET *) NULL;
64: return(pb);
65: }
66:
67: /* MIRECTSTOREGION -- helper called by the device private routine called when
68: * the clipmask changes. Converts the set of rectangles to a region.
69: * dix/gc/SetClipRects has already checked that the rectangles are sorted as
70: * advertised.
71: * We just take those rectangles and convert to a YX banded region.
72: * First we sort the rectangles by starting Y values. Then we make sure that
73: * all rectangles that start at a given line all end at the same line. Bits
74: * that hang over fall into the next Y bucket. (Sort of Procrustean, isn't
75: * it?) Next, we sort within each Y bucket by X starting values. Finally,
76: * we take the resulting set of rectangles and stuff it into a region.
77: */
78: RegionPtr
79: miRectsToRegion(pGC, nrects, prect, ordering)
80: GCPtr pGC;
81: int nrects;
82: xRectangle *prect;
83: int ordering;
84: {
85: register YBUCKET *pb;
86: register BoxRec *pbox, *pboxNew;
87: BoxRec tbox;
88: RegionPtr pReg;
89: YBUCKET *pbFirst, *pbNew, *newbucket();
90: int count, miny2;
91: Bool fInserted, fChanged;
92: int xMin, xMax, yMin, yMax;
93: BoxRec b;
94:
95: /* if there's only one rectangle, we don't care about ordering */
96: if (nrects == 1)
97: {
98: b.x1 = prect->x;
99: b.y1 = prect->y;
100: b.x2 = b.x1 + prect->width;
101: b.y2 = b.y1 + prect->height;
102: return ((* pGC->pScreen->RegionCreate)(&b, 1));
103: }
104: /* setting the number of rectangles to zero stops all output */
105: if (nrects == 0)
106: {
107: b.x1 = 0;
108: b.y1 = 0;
109: b.x2 = 0;
110: b.y2 = 0;
111: return ((* pGC->pScreen->RegionCreate)(&b, 1));
112: }
113:
114: xMin = yMin = MAXSHORT;
115: xMax = yMax = -1;
116: if ((nrects < 0) ||
117: ((pReg = (* pGC->pScreen->RegionCreate)(NULL, 1)) == NullRegion))
118: {
119: return NullRegion;
120: }
121:
122: if (ordering == YXBanded)
123: {
124: pReg->rects = (BoxPtr)Xrealloc(pReg->rects, nrects * sizeof(BoxRec));
125: pbox = pReg->rects;
126: while(pbox < pReg->rects + nrects)
127: {
128: pbox->x1 = prect->x;
129: pbox->y1 = prect->y;
130: pbox->x2 = prect->x + prect->width;
131: pbox->y2 = prect->y + prect->height;
132: xMin = min(xMin, pbox->x1);
133: xMax = max(xMax, pbox->x2);
134: yMin = min(yMin, pbox->y1);
135: yMax = max(yMax, pbox->y2);
136: prect++;
137: pbox++;
138: }
139: pReg->numRects = nrects;
140: pReg->size = nrects;
141: pReg->extents.x1 = xMin;
142: pReg->extents.y1 = yMin;
143: pReg->extents.x2 = xMax;
144: pReg->extents.y2 = yMax;
145: return (pReg);
146: }
147:
148: pbFirst = (YBUCKET *) newbucket(prect->y, prect->y + prect->height);
149: pb = pbFirst;
150: count = nrects;
151:
152: /* Sort into Y buckets -- everthing in a bucket has the same starting
153: * scanline. Also note the smallest box in the band and whether any
154: * boxes are of other sizes */
155: while(count--)
156: {
157: if(ordering == Unsorted)
158: {
159: /* We have to search from the top, otherwise we know no
160: * box will be before the current one */
161: pb = pbFirst;
162: }
163:
164: fInserted = FALSE;
165: while(!fInserted)
166: {
167: if(prect->y == pb->y)
168: {
169: /* add rectangle at the end of this bucket */
170: pb->count++;
171: pb->boxes = (BoxPtr)Xrealloc(pb->boxes,
172: pb->count * sizeof(BoxRec));
173: pbox = &pb->boxes[pb->count - 1];
174:
175: pbox->x1 = prect->x;
176: pbox->y1 = prect->y;
177: pbox->x2 = prect->x + prect->width;
178: pbox->y2 = prect->y + prect->height;
179: xMin = min(xMin, pbox->x1);
180: xMax = max(xMax, pbox->x2);
181: yMin = min(yMin, pbox->y1);
182: yMax = max(yMax, pbox->y2);
183:
184: if (pbox->y2 != pb->miny2)
185: pb->fdiff = TRUE;
186: if (pbox->y2 < pb->miny2)
187: pb->miny2 = pbox->y2;
188: fInserted = TRUE;
189: }
190: else if(prect->y < pbFirst->y)
191: {
192: /* Create a new first record in the list */
193: pbNew = newbucket(prect->y, prect->y + prect->height);
194: pbNew->next = pbFirst;
195: pbFirst = pbNew;
196: pb = pbNew;
197: }
198: else if ((pb->next == (YBUCKET *) NULL) ||
199: (pb->next->y > prect->y))
200: {
201: /* create a new ybucket linked between this and the next.
202: * set pb to new bucket */
203: pbNew = newbucket(prect->y, prect->y + prect->height);
204: pbNew->next = pb->next;
205: pb->next = pbNew;
206: pb = pbNew;
207:
208: }
209: else
210: {
211: /* try with next bucket */
212: pb = pb->next;
213: }
214: }
215: prect++;
216: }
217:
218: /* YBand the buckets */
219: pb = pbFirst;
220: while(pb)
221: {
222: if(pb->fdiff)
223: {
224: miny2 = pb->miny2;
225:
226: /* Figure out which ybucket the lopped-off part of these boxes
227: * will go in */
228: if(pb->next ? (miny2 < pb->next->y) : TRUE)
229: {
230: /* create new y bucket */
231: pbNew = newbucket(miny2, MAXSHORT);
232: pbNew->next = pb->next;
233: pb->next = pbNew;
234: }
235: else
236: {
237: pbNew = pb->next;
238: }
239:
240: /* if any rectangle is longer than the shortest in this ybucket,
241: * drop the rest of the rectangle into the next lowest bucket */
242: pbox = pb->boxes;
243: while(pbox < pb->boxes + pb->count)
244: {
245: if(pbox->y2 > miny2)
246: {
247: if(pbNew->count == 0)
248: {
249: pbNew->miny2 = pbox->y2;
250: }
251: pbNew->count++;
252: pbNew->boxes = (BoxPtr)Xrealloc(pbNew->boxes, pbNew->count *
253: sizeof(BoxRec));
254: pboxNew = &pbNew->boxes[pbNew->count - 1];
255: pboxNew->x1 = pbox->x1;
256: pboxNew->y1 = pbNew->y;
257: pboxNew->x2 = pbox->x2;
258: pboxNew->y2 = pbox->y2;
259: if(pboxNew->y2 !=pbNew->miny2)
260: pbNew->fdiff = TRUE;
261: if(pboxNew->y2 < pbNew->miny2)
262: pbNew->miny2 = pboxNew->y2;
263:
264: }
265: pbox++;
266: }
267: }
268: else
269: {
270: pbNew = pb->next;
271: }
272:
273: pb = pbNew;
274: }
275:
276: /* X sort the buckets, and tally total size */
277: pb = pbFirst;
278: count = 0;
279: while(pb)
280: {
281: count += pb->count;
282: /* Yes, it's a bubble sort. I wanted something (a) in place,
283: * (b) with a low startup cost, because I expect to find few
284: * rectangles per yband and don't want to spend more effort setting
285: * up the sort than I do performing it.
286: */
287: fChanged = TRUE;
288: while(fChanged)
289: {
290: fChanged = FALSE;
291: pbox = pb->boxes;
292: while(pbox < pb->boxes + pb->count - 1)
293: {
294: if(pbox->x1 > (pbox+1)->x1)
295: {
296: tbox = *pbox;
297: *pbox = *(pbox + 1);
298: *(pbox + 1) = tbox;
299: fChanged = TRUE;
300: }
301: pbox++;
302: }
303: }
304: pb = pb->next;
305: }
306:
307: /* copy the rectangles into the region and free up the buckets */
308: pReg->rects = (BoxPtr) Xrealloc (pReg->rects, count * sizeof(BoxRec));
309: pReg->numRects = count;
310: pReg->size = count;
311: pboxNew = pReg->rects;
312: pb = pbFirst;
313: while(pb)
314: {
315: for(pbox = pb->boxes; pbox < pb->boxes + pb->count; pbox++)
316: {
317: *pboxNew++ = *pbox;
318: }
319: Xfree((char *)pb->boxes);
320:
321: pb = pb->next;
322: Xfree(pb);
323: }
324: pReg->extents.x1 = xMin;
325: pReg->extents.y1 = yMin;
326: pReg->extents.x2 = xMax;
327: pReg->extents.y2 = yMax;
328: return(pReg);
329:
330: }
331:
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.