1 /* -=- sraRegion.c
2 * Copyright (c) 2001 James "Wez" Weatherall, Johannes E. Schindelin
3 *
4 * A general purpose region clipping library
5 * Only deals with rectangular regions, though.
6 */
7
8 #include <rfb/rfb.h>
9 #include <rfb/rfbregion.h>
10
11 /* -=- Internal Span structure */
12
13 struct sraRegion;
14
15 typedef struct sraSpan {
16 struct sraSpan *_next;
17 struct sraSpan *_prev;
18 int start;
19 int end;
20 struct sraRegion *subspan;
21 } sraSpan;
22
23 typedef struct sraRegion {
24 sraSpan front;
25 sraSpan back;
26 } sraSpanList;
27
28 /* -=- Span routines */
29
30 sraSpanList *sraSpanListDup(const sraSpanList *src);
31 void sraSpanListDestroy(sraSpanList *list);
32
33 static sraSpan *
sraSpanCreate(int start,int end,const sraSpanList * subspan)34 sraSpanCreate(int start, int end, const sraSpanList *subspan) {
35 sraSpan *item = (sraSpan*)malloc(sizeof(sraSpan));
36 if (!item) return NULL;
37 item->_next = item->_prev = NULL;
38 item->start = start;
39 item->end = end;
40 item->subspan = sraSpanListDup(subspan);
41 return item;
42 }
43
44 static sraSpan *
sraSpanDup(const sraSpan * src)45 sraSpanDup(const sraSpan *src) {
46 sraSpan *span;
47 if (!src) return NULL;
48 span = sraSpanCreate(src->start, src->end, src->subspan);
49 return span;
50 }
51
52 static void
sraSpanInsertAfter(sraSpan * newspan,sraSpan * after)53 sraSpanInsertAfter(sraSpan *newspan, sraSpan *after) {
54 if(newspan && after) {
55 newspan->_next = after->_next;
56 newspan->_prev = after;
57 after->_next->_prev = newspan;
58 after->_next = newspan;
59 }
60 }
61
62 static void
sraSpanInsertBefore(sraSpan * newspan,sraSpan * before)63 sraSpanInsertBefore(sraSpan *newspan, sraSpan *before) {
64 if(newspan && before) {
65 newspan->_next = before;
66 newspan->_prev = before->_prev;
67 before->_prev->_next = newspan;
68 before->_prev = newspan;
69 }
70 }
71
72 static void
sraSpanRemove(sraSpan * span)73 sraSpanRemove(sraSpan *span) {
74 if(span) {
75 span->_prev->_next = span->_next;
76 span->_next->_prev = span->_prev;
77 }
78 }
79
80 static void
sraSpanDestroy(sraSpan * span)81 sraSpanDestroy(sraSpan *span) {
82 if (span->subspan) sraSpanListDestroy(span->subspan);
83 free(span);
84 }
85
86 #ifdef DEBUG
87 static void
sraSpanCheck(const sraSpan * span,const char * text)88 sraSpanCheck(const sraSpan *span, const char *text) {
89 /* Check the span is valid! */
90 if (span->start == span->end) {
91 printf(text);
92 printf(":%d-%d\n", span->start, span->end);
93 }
94 }
95 #endif
96
97 /* -=- SpanList routines */
98
99 static void sraSpanPrint(const sraSpan *s);
100
101 static void
sraSpanListPrint(const sraSpanList * l)102 sraSpanListPrint(const sraSpanList *l) {
103 sraSpan *curr;
104 if (!l) {
105 printf("NULL");
106 return;
107 }
108 curr = l->front._next;
109 printf("[");
110 while (curr != &(l->back)) {
111 sraSpanPrint(curr);
112 curr = curr->_next;
113 }
114 printf("]");
115 }
116
117 void
sraSpanPrint(const sraSpan * s)118 sraSpanPrint(const sraSpan *s) {
119 printf("(%d-%d)", (s->start), (s->end));
120 if (s->subspan)
121 sraSpanListPrint(s->subspan);
122 }
123
124 static sraSpanList *
sraSpanListCreate(void)125 sraSpanListCreate(void) {
126 sraSpanList *item = (sraSpanList*)malloc(sizeof(sraSpanList));
127 if (!item) return NULL;
128 item->front._next = &(item->back);
129 item->front._prev = NULL;
130 item->back._prev = &(item->front);
131 item->back._next = NULL;
132 return item;
133 }
134
135 sraSpanList *
sraSpanListDup(const sraSpanList * src)136 sraSpanListDup(const sraSpanList *src) {
137 sraSpanList *newlist;
138 sraSpan *newspan, *curr;
139
140 if (!src) return NULL;
141 newlist = sraSpanListCreate();
142 curr = src->front._next;
143 while (curr != &(src->back)) {
144 newspan = sraSpanDup(curr);
145 sraSpanInsertBefore(newspan, &(newlist->back));
146 curr = curr->_next;
147 }
148
149 return newlist;
150 }
151
152 void
sraSpanListDestroy(sraSpanList * list)153 sraSpanListDestroy(sraSpanList *list) {
154 sraSpan *curr;
155 while (list->front._next != &(list->back)) {
156 curr = list->front._next;
157 sraSpanRemove(curr);
158 sraSpanDestroy(curr);
159 }
160 free(list);
161 }
162
163 static void
sraSpanListMakeEmpty(sraSpanList * list)164 sraSpanListMakeEmpty(sraSpanList *list) {
165 sraSpan *curr;
166 while (list->front._next != &(list->back)) {
167 curr = list->front._next;
168 sraSpanRemove(curr);
169 sraSpanDestroy(curr);
170 }
171 list->front._next = &(list->back);
172 list->front._prev = NULL;
173 list->back._prev = &(list->front);
174 list->back._next = NULL;
175 }
176
177 static rfbBool
sraSpanListEqual(const sraSpanList * s1,const sraSpanList * s2)178 sraSpanListEqual(const sraSpanList *s1, const sraSpanList *s2) {
179 sraSpan *sp1, *sp2;
180
181 if (!s1) {
182 if (!s2) {
183 return 1;
184 } else {
185 rfbErr("sraSpanListEqual:incompatible spans (only one NULL!)\n");
186 return FALSE;
187 }
188 }
189
190 sp1 = s1->front._next;
191 sp2 = s2->front._next;
192 while ((sp1 != &(s1->back)) &&
193 (sp2 != &(s2->back))) {
194 if ((sp1->start != sp2->start) ||
195 (sp1->end != sp2->end) ||
196 (!sraSpanListEqual(sp1->subspan, sp2->subspan))) {
197 return 0;
198 }
199 sp1 = sp1->_next;
200 sp2 = sp2->_next;
201 }
202
203 if ((sp1 == &(s1->back)) && (sp2 == &(s2->back))) {
204 return 1;
205 } else {
206 return 0;
207 }
208 }
209
210 static rfbBool
sraSpanListEmpty(const sraSpanList * list)211 sraSpanListEmpty(const sraSpanList *list) {
212 return (list->front._next == &(list->back));
213 }
214
215 static unsigned long
sraSpanListCount(const sraSpanList * list)216 sraSpanListCount(const sraSpanList *list) {
217 sraSpan *curr = list->front._next;
218 unsigned long count = 0;
219 while (curr != &(list->back)) {
220 if (curr->subspan) {
221 count += sraSpanListCount(curr->subspan);
222 } else {
223 count += 1;
224 }
225 curr = curr->_next;
226 }
227 return count;
228 }
229
230 static void
sraSpanMergePrevious(sraSpan * dest)231 sraSpanMergePrevious(sraSpan *dest) {
232 sraSpan *prev = dest->_prev;
233
234 while ((prev->_prev) &&
235 (prev->end == dest->start) &&
236 (sraSpanListEqual(prev->subspan, dest->subspan))) {
237 /*
238 printf("merge_prev:");
239 sraSpanPrint(prev);
240 printf(" & ");
241 sraSpanPrint(dest);
242 printf("\n");
243 */
244 dest->start = prev->start;
245 sraSpanRemove(prev);
246 sraSpanDestroy(prev);
247 prev = dest->_prev;
248 }
249 }
250
251 static void
sraSpanMergeNext(sraSpan * dest)252 sraSpanMergeNext(sraSpan *dest) {
253 sraSpan *next = dest->_next;
254 while ((next->_next) &&
255 (next->start == dest->end) &&
256 (sraSpanListEqual(next->subspan, dest->subspan))) {
257 /*
258 printf("merge_next:");
259 sraSpanPrint(dest);
260 printf(" & ");
261 sraSpanPrint(next);
262 printf("\n");
263 */
264 dest->end = next->end;
265 sraSpanRemove(next);
266 sraSpanDestroy(next);
267 next = dest->_next;
268 }
269 }
270
271 static void
sraSpanListOr(sraSpanList * dest,const sraSpanList * src)272 sraSpanListOr(sraSpanList *dest, const sraSpanList *src) {
273 sraSpan *d_curr, *s_curr;
274 int s_start, s_end;
275
276 if (!dest) {
277 if (!src) {
278 return;
279 } else {
280 rfbErr("sraSpanListOr:incompatible spans (only one NULL!)\n");
281 return;
282 }
283 }
284
285 d_curr = dest->front._next;
286 s_curr = src->front._next;
287 s_start = s_curr->start;
288 s_end = s_curr->end;
289 while (s_curr != &(src->back)) {
290
291 /* - If we are at end of destination list OR
292 If the new span comes before the next destination one */
293 if ((d_curr == &(dest->back)) ||
294 (d_curr->start >= s_end)) {
295 /* - Add the span */
296 sraSpanInsertBefore(sraSpanCreate(s_start, s_end,
297 s_curr->subspan),
298 d_curr);
299 if (d_curr != &(dest->back))
300 sraSpanMergePrevious(d_curr);
301 s_curr = s_curr->_next;
302 s_start = s_curr->start;
303 s_end = s_curr->end;
304 } else {
305
306 /* - If the new span overlaps the existing one */
307 if ((s_start < d_curr->end) &&
308 (s_end > d_curr->start)) {
309
310 /* - Insert new span before the existing destination one? */
311 if (s_start < d_curr->start) {
312 sraSpanInsertBefore(sraSpanCreate(s_start,
313 d_curr->start,
314 s_curr->subspan),
315 d_curr);
316 sraSpanMergePrevious(d_curr);
317 }
318
319 /* Split the existing span if necessary */
320 if (s_end < d_curr->end) {
321 sraSpanInsertAfter(sraSpanCreate(s_end,
322 d_curr->end,
323 d_curr->subspan),
324 d_curr);
325 d_curr->end = s_end;
326 }
327 if (s_start > d_curr->start) {
328 sraSpanInsertBefore(sraSpanCreate(d_curr->start,
329 s_start,
330 d_curr->subspan),
331 d_curr);
332 d_curr->start = s_start;
333 }
334
335 /* Recursively OR subspans */
336 sraSpanListOr(d_curr->subspan, s_curr->subspan);
337
338 /* Merge this span with previous or next? */
339 if (d_curr->_prev != &(dest->front))
340 sraSpanMergePrevious(d_curr);
341 if (d_curr->_next != &(dest->back))
342 sraSpanMergeNext(d_curr);
343
344 /* Move onto the next pair to compare */
345 if (s_end > d_curr->end) {
346 s_start = d_curr->end;
347 d_curr = d_curr->_next;
348 } else {
349 s_curr = s_curr->_next;
350 s_start = s_curr->start;
351 s_end = s_curr->end;
352 }
353 } else {
354 /* - No overlap. Move to the next destination span */
355 d_curr = d_curr->_next;
356 }
357 }
358 }
359 }
360
361 static rfbBool
sraSpanListAnd(sraSpanList * dest,const sraSpanList * src)362 sraSpanListAnd(sraSpanList *dest, const sraSpanList *src) {
363 sraSpan *d_curr, *s_curr, *d_next;
364
365 if (!dest) {
366 if (!src) {
367 return 1;
368 } else {
369 rfbErr("sraSpanListAnd:incompatible spans (only one NULL!)\n");
370 return FALSE;
371 }
372 }
373
374 d_curr = dest->front._next;
375 s_curr = src->front._next;
376 while ((s_curr != &(src->back)) && (d_curr != &(dest->back))) {
377
378 /* - If we haven't reached a destination span yet then move on */
379 if (d_curr->start >= s_curr->end) {
380 s_curr = s_curr->_next;
381 continue;
382 }
383
384 /* - If we are beyond the current destination span then remove it */
385 if (d_curr->end <= s_curr->start) {
386 sraSpan *next = d_curr->_next;
387 sraSpanRemove(d_curr);
388 sraSpanDestroy(d_curr);
389 d_curr = next;
390 continue;
391 }
392
393 /* - If we partially overlap a span then split it up or remove bits */
394 if (s_curr->start > d_curr->start) {
395 /* - The top bit of the span does not match */
396 d_curr->start = s_curr->start;
397 }
398 if (s_curr->end < d_curr->end) {
399 /* - The end of the span does not match */
400 sraSpanInsertAfter(sraSpanCreate(s_curr->end,
401 d_curr->end,
402 d_curr->subspan),
403 d_curr);
404 d_curr->end = s_curr->end;
405 }
406
407 /* - Now recursively process the affected span */
408 if (!sraSpanListAnd(d_curr->subspan, s_curr->subspan)) {
409 /* - The destination subspan is now empty, so we should remove it */
410 sraSpan *next = d_curr->_next;
411 sraSpanRemove(d_curr);
412 sraSpanDestroy(d_curr);
413 d_curr = next;
414 } else {
415 /* Merge this span with previous or next? */
416 if (d_curr->_prev != &(dest->front))
417 sraSpanMergePrevious(d_curr);
418
419 /* - Move on to the next span */
420 d_next = d_curr;
421 if (s_curr->end >= d_curr->end) {
422 d_next = d_curr->_next;
423 }
424 if (s_curr->end <= d_curr->end) {
425 s_curr = s_curr->_next;
426 }
427 d_curr = d_next;
428 }
429 }
430
431 while (d_curr != &(dest->back)) {
432 sraSpan *next = d_curr->_next;
433 sraSpanRemove(d_curr);
434 sraSpanDestroy(d_curr);
435 d_curr=next;
436 }
437
438 return !sraSpanListEmpty(dest);
439 }
440
441 static rfbBool
sraSpanListSubtract(sraSpanList * dest,const sraSpanList * src)442 sraSpanListSubtract(sraSpanList *dest, const sraSpanList *src) {
443 sraSpan *d_curr, *s_curr;
444
445 if (!dest) {
446 if (!src) {
447 return 1;
448 } else {
449 rfbErr("sraSpanListSubtract:incompatible spans (only one NULL!)\n");
450 return FALSE;
451 }
452 }
453
454 d_curr = dest->front._next;
455 s_curr = src->front._next;
456 while ((s_curr != &(src->back)) && (d_curr != &(dest->back))) {
457
458 /* - If we haven't reached a destination span yet then move on */
459 if (d_curr->start >= s_curr->end) {
460 s_curr = s_curr->_next;
461 continue;
462 }
463
464 /* - If we are beyond the current destination span then skip it */
465 if (d_curr->end <= s_curr->start) {
466 d_curr = d_curr->_next;
467 continue;
468 }
469
470 /* - If we partially overlap the current span then split it up */
471 if (s_curr->start > d_curr->start) {
472 sraSpanInsertBefore(sraSpanCreate(d_curr->start,
473 s_curr->start,
474 d_curr->subspan),
475 d_curr);
476 d_curr->start = s_curr->start;
477 }
478 if (s_curr->end < d_curr->end) {
479 sraSpanInsertAfter(sraSpanCreate(s_curr->end,
480 d_curr->end,
481 d_curr->subspan),
482 d_curr);
483 d_curr->end = s_curr->end;
484 }
485
486 /* - Now recursively process the affected span */
487 if ((!d_curr->subspan) || !sraSpanListSubtract(d_curr->subspan, s_curr->subspan)) {
488 /* - The destination subspan is now empty, so we should remove it */
489 sraSpan *next = d_curr->_next;
490 sraSpanRemove(d_curr);
491 sraSpanDestroy(d_curr);
492 d_curr = next;
493 } else {
494 /* Merge this span with previous or next? */
495 if (d_curr->_prev != &(dest->front))
496 sraSpanMergePrevious(d_curr);
497 if (d_curr->_next != &(dest->back))
498 sraSpanMergeNext(d_curr);
499
500 /* - Move on to the next span */
501 if (s_curr->end > d_curr->end) {
502 d_curr = d_curr->_next;
503 } else {
504 s_curr = s_curr->_next;
505 }
506 }
507 }
508
509 return !sraSpanListEmpty(dest);
510 }
511
512 /* -=- Region routines */
513
514 sraRegion *
sraRgnCreate(void)515 sraRgnCreate(void) {
516 return (sraRegion*)sraSpanListCreate();
517 }
518
519 sraRegion *
sraRgnCreateRect(int x1,int y1,int x2,int y2)520 sraRgnCreateRect(int x1, int y1, int x2, int y2) {
521 sraSpanList *vlist, *hlist;
522 sraSpan *vspan, *hspan;
523
524 /* - Build the horizontal portion of the span */
525 hlist = sraSpanListCreate();
526 hspan = sraSpanCreate(x1, x2, NULL);
527 sraSpanInsertAfter(hspan, &(hlist->front));
528
529 /* - Build the vertical portion of the span */
530 vlist = sraSpanListCreate();
531 vspan = sraSpanCreate(y1, y2, hlist);
532 sraSpanInsertAfter(vspan, &(vlist->front));
533
534 sraSpanListDestroy(hlist);
535
536 return (sraRegion*)vlist;
537 }
538
539 sraRegion *
sraRgnCreateRgn(const sraRegion * src)540 sraRgnCreateRgn(const sraRegion *src) {
541 return (sraRegion*)sraSpanListDup((sraSpanList*)src);
542 }
543
544 void
sraRgnDestroy(sraRegion * rgn)545 sraRgnDestroy(sraRegion *rgn) {
546 sraSpanListDestroy((sraSpanList*)rgn);
547 }
548
549 void
sraRgnMakeEmpty(sraRegion * rgn)550 sraRgnMakeEmpty(sraRegion *rgn) {
551 sraSpanListMakeEmpty((sraSpanList*)rgn);
552 }
553
554 /* -=- Boolean Region ops */
555
556 rfbBool
sraRgnAnd(sraRegion * dst,const sraRegion * src)557 sraRgnAnd(sraRegion *dst, const sraRegion *src) {
558 return sraSpanListAnd((sraSpanList*)dst, (sraSpanList*)src);
559 }
560
561 void
sraRgnOr(sraRegion * dst,const sraRegion * src)562 sraRgnOr(sraRegion *dst, const sraRegion *src) {
563 sraSpanListOr((sraSpanList*)dst, (sraSpanList*)src);
564 }
565
566 rfbBool
sraRgnSubtract(sraRegion * dst,const sraRegion * src)567 sraRgnSubtract(sraRegion *dst, const sraRegion *src) {
568 return sraSpanListSubtract((sraSpanList*)dst, (sraSpanList*)src);
569 }
570
571 void
sraRgnOffset(sraRegion * dst,int dx,int dy)572 sraRgnOffset(sraRegion *dst, int dx, int dy) {
573 sraSpan *vcurr, *hcurr;
574
575 vcurr = ((sraSpanList*)dst)->front._next;
576 while (vcurr != &(((sraSpanList*)dst)->back)) {
577 vcurr->start += dy;
578 vcurr->end += dy;
579
580 hcurr = vcurr->subspan->front._next;
581 while (hcurr != &(vcurr->subspan->back)) {
582 hcurr->start += dx;
583 hcurr->end += dx;
584 hcurr = hcurr->_next;
585 }
586
587 vcurr = vcurr->_next;
588 }
589 }
590
sraRgnBBox(const sraRegion * src)591 sraRegion *sraRgnBBox(const sraRegion *src) {
592 int xmin=((unsigned int)(int)-1)>>1,ymin=xmin,xmax=1-xmin,ymax=xmax;
593 sraSpan *vcurr, *hcurr;
594
595 if(!src)
596 return sraRgnCreate();
597
598 vcurr = ((sraSpanList*)src)->front._next;
599 while (vcurr != &(((sraSpanList*)src)->back)) {
600 if(vcurr->start<ymin)
601 ymin=vcurr->start;
602 if(vcurr->end>ymax)
603 ymax=vcurr->end;
604
605 hcurr = vcurr->subspan->front._next;
606 while (hcurr != &(vcurr->subspan->back)) {
607 if(hcurr->start<xmin)
608 xmin=hcurr->start;
609 if(hcurr->end>xmax)
610 xmax=hcurr->end;
611 hcurr = hcurr->_next;
612 }
613
614 vcurr = vcurr->_next;
615 }
616
617 if(xmax<xmin || ymax<ymin)
618 return sraRgnCreate();
619
620 return sraRgnCreateRect(xmin,ymin,xmax,ymax);
621 }
622
623 rfbBool
sraRgnPopRect(sraRegion * rgn,sraRect * rect,unsigned long flags)624 sraRgnPopRect(sraRegion *rgn, sraRect *rect, unsigned long flags) {
625 sraSpan *vcurr, *hcurr;
626 sraSpan *vend, *hend;
627 rfbBool right2left = (flags & 2) == 2;
628 rfbBool bottom2top = (flags & 1) == 1;
629
630 /* - Pick correct order */
631 if (bottom2top) {
632 vcurr = ((sraSpanList*)rgn)->back._prev;
633 vend = &(((sraSpanList*)rgn)->front);
634 } else {
635 vcurr = ((sraSpanList*)rgn)->front._next;
636 vend = &(((sraSpanList*)rgn)->back);
637 }
638
639 if (vcurr != vend) {
640 rect->y1 = vcurr->start;
641 rect->y2 = vcurr->end;
642
643 /* - Pick correct order */
644 if (right2left) {
645 hcurr = vcurr->subspan->back._prev;
646 hend = &(vcurr->subspan->front);
647 } else {
648 hcurr = vcurr->subspan->front._next;
649 hend = &(vcurr->subspan->back);
650 }
651
652 if (hcurr != hend) {
653 rect->x1 = hcurr->start;
654 rect->x2 = hcurr->end;
655
656 sraSpanRemove(hcurr);
657 sraSpanDestroy(hcurr);
658
659 if (sraSpanListEmpty(vcurr->subspan)) {
660 sraSpanRemove(vcurr);
661 sraSpanDestroy(vcurr);
662 }
663
664 #if 0
665 printf("poprect:(%dx%d)-(%dx%d)\n",
666 rect->x1, rect->y1, rect->x2, rect->y2);
667 #endif
668 return 1;
669 }
670 }
671
672 return 0;
673 }
674
675 unsigned long
sraRgnCountRects(const sraRegion * rgn)676 sraRgnCountRects(const sraRegion *rgn) {
677 unsigned long count = sraSpanListCount((sraSpanList*)rgn);
678 return count;
679 }
680
681 rfbBool
sraRgnEmpty(const sraRegion * rgn)682 sraRgnEmpty(const sraRegion *rgn) {
683 return sraSpanListEmpty((sraSpanList*)rgn);
684 }
685
686 /* iterator stuff */
sraRgnGetIterator(sraRegion * s)687 sraRectangleIterator *sraRgnGetIterator(sraRegion *s)
688 {
689 /* these values have to be multiples of 4 */
690 #define DEFSIZE 4
691 #define DEFSTEP 8
692 sraRectangleIterator *i =
693 (sraRectangleIterator*)malloc(sizeof(sraRectangleIterator));
694 if(!i)
695 return NULL;
696
697 /* we have to recurse eventually. So, the first sPtr is the pointer to
698 the sraSpan in the first level. the second sPtr is the pointer to
699 the sraRegion.back. The third and fourth sPtr are for the second
700 recursion level and so on. */
701 i->sPtrs = (sraSpan**)malloc(sizeof(sraSpan*)*DEFSIZE);
702 if(!i->sPtrs) {
703 free(i);
704 return NULL;
705 }
706 i->ptrSize = DEFSIZE;
707 i->sPtrs[0] = &(s->front);
708 i->sPtrs[1] = &(s->back);
709 i->ptrPos = 0;
710 i->reverseX = 0;
711 i->reverseY = 0;
712 return i;
713 }
714
sraRgnGetReverseIterator(sraRegion * s,rfbBool reverseX,rfbBool reverseY)715 sraRectangleIterator *sraRgnGetReverseIterator(sraRegion *s,rfbBool reverseX,rfbBool reverseY)
716 {
717 sraRectangleIterator *i = sraRgnGetIterator(s);
718 if(reverseY) {
719 i->sPtrs[1] = &(s->front);
720 i->sPtrs[0] = &(s->back);
721 }
722 i->reverseX = reverseX;
723 i->reverseY = reverseY;
724 return(i);
725 }
726
sraReverse(sraRectangleIterator * i)727 static rfbBool sraReverse(sraRectangleIterator *i)
728 {
729 return( ((i->ptrPos&2) && i->reverseX) ||
730 (!(i->ptrPos&2) && i->reverseY));
731 }
732
sraNextSpan(sraRectangleIterator * i)733 static sraSpan* sraNextSpan(sraRectangleIterator *i)
734 {
735 if(sraReverse(i))
736 return(i->sPtrs[i->ptrPos]->_prev);
737 else
738 return(i->sPtrs[i->ptrPos]->_next);
739 }
740
sraRgnIteratorNext(sraRectangleIterator * i,sraRect * r)741 rfbBool sraRgnIteratorNext(sraRectangleIterator* i,sraRect* r)
742 {
743 /* is the subspan finished? */
744 while(sraNextSpan(i) == i->sPtrs[i->ptrPos+1]) {
745 i->ptrPos -= 2;
746 if(i->ptrPos < 0) /* the end */
747 return(0);
748 }
749
750 i->sPtrs[i->ptrPos] = sraNextSpan(i);
751
752 /* is this a new subspan? */
753 while(i->sPtrs[i->ptrPos]->subspan) {
754 if(i->ptrPos+2 > i->ptrSize) { /* array is too small */
755 i->ptrSize += DEFSTEP;
756 i->sPtrs = (sraSpan**)realloc(i->sPtrs, sizeof(sraSpan*)*i->ptrSize);
757 }
758 i->ptrPos += 2;
759 if(sraReverse(i)) {
760 i->sPtrs[i->ptrPos] = i->sPtrs[i->ptrPos-2]->subspan->back._prev;
761 i->sPtrs[i->ptrPos+1] = &(i->sPtrs[i->ptrPos-2]->subspan->front);
762 } else {
763 i->sPtrs[i->ptrPos] = i->sPtrs[i->ptrPos-2]->subspan->front._next;
764 i->sPtrs[i->ptrPos+1] = &(i->sPtrs[i->ptrPos-2]->subspan->back);
765 }
766 }
767
768 if((i->ptrPos%4)!=2) {
769 rfbErr("sraRgnIteratorNext: offset is wrong (%d%%4!=2)\n",i->ptrPos);
770 return FALSE;
771 }
772
773 r->y1 = i->sPtrs[i->ptrPos-2]->start;
774 r->y2 = i->sPtrs[i->ptrPos-2]->end;
775 r->x1 = i->sPtrs[i->ptrPos]->start;
776 r->x2 = i->sPtrs[i->ptrPos]->end;
777
778 return(-1);
779 }
780
sraRgnReleaseIterator(sraRectangleIterator * i)781 void sraRgnReleaseIterator(sraRectangleIterator* i)
782 {
783 free(i->sPtrs);
784 free(i);
785 }
786
787 void
sraRgnPrint(const sraRegion * rgn)788 sraRgnPrint(const sraRegion *rgn) {
789 sraSpanListPrint((sraSpanList*)rgn);
790 }
791
792 rfbBool
sraClipRect(int * x,int * y,int * w,int * h,int cx,int cy,int cw,int ch)793 sraClipRect(int *x, int *y, int *w, int *h,
794 int cx, int cy, int cw, int ch) {
795 if (*x < cx) {
796 *w -= (cx-*x);
797 *x = cx;
798 }
799 if (*y < cy) {
800 *h -= (cy-*y);
801 *y = cy;
802 }
803 if (*x+*w > cx+cw) {
804 *w = (cx+cw)-*x;
805 }
806 if (*y+*h > cy+ch) {
807 *h = (cy+ch)-*y;
808 }
809 return (*w>0) && (*h>0);
810 }
811
812 rfbBool
sraClipRect2(int * x,int * y,int * x2,int * y2,int cx,int cy,int cx2,int cy2)813 sraClipRect2(int *x, int *y, int *x2, int *y2,
814 int cx, int cy, int cx2, int cy2) {
815 if (*x < cx)
816 *x = cx;
817 if (*y < cy)
818 *y = cy;
819 if (*x >= cx2)
820 *x = cx2-1;
821 if (*y >= cy2)
822 *y = cy2-1;
823 if (*x2 <= cx)
824 *x2 = cx+1;
825 if (*y2 <= cy)
826 *y2 = cy+1;
827 if (*x2 > cx2)
828 *x2 = cx2;
829 if (*y2 > cy2)
830 *y2 = cy2;
831 return (*x2>*x) && (*y2>*y);
832 }
833
834 /* test */
835
836 #ifdef SRA_TEST
837 /* pipe the output to sort|uniq -u and you'll get the errors. */
main(int argc,char ** argv)838 int main(int argc, char** argv)
839 {
840 sraRegionPtr region, region1, region2;
841 sraRectangleIterator* i;
842 sraRect rect;
843 rfbBool b;
844
845 region = sraRgnCreateRect(10, 10, 600, 300);
846 region1 = sraRgnCreateRect(40, 50, 350, 200);
847 region2 = sraRgnCreateRect(0, 0, 20, 40);
848
849 sraRgnPrint(region);
850 printf("\n[(10-300)[(10-600)]]\n\n");
851
852 b = sraRgnSubtract(region, region1);
853 printf("%s ",b?"true":"false");
854 sraRgnPrint(region);
855 printf("\ntrue [(10-50)[(10-600)](50-200)[(10-40)(350-600)](200-300)[(10-600)]]\n\n");
856
857 sraRgnOr(region, region2);
858 printf("%ld\n6\n\n", sraRgnCountRects(region));
859
860 i = sraRgnGetIterator(region);
861 while(sraRgnIteratorNext(i, &rect))
862 printf("%dx%d+%d+%d ",
863 rect.x2-rect.x1,rect.y2-rect.y1,
864 rect.x1,rect.y1);
865 sraRgnReleaseIterator(i);
866 printf("\n20x10+0+0 600x30+0+10 590x10+10+40 30x150+10+50 250x150+350+50 590x100+10+200 \n\n");
867
868 i = sraRgnGetReverseIterator(region,1,0);
869 while(sraRgnIteratorNext(i, &rect))
870 printf("%dx%d+%d+%d ",
871 rect.x2-rect.x1,rect.y2-rect.y1,
872 rect.x1,rect.y1);
873 sraRgnReleaseIterator(i);
874 printf("\n20x10+0+0 600x30+0+10 590x10+10+40 250x150+350+50 30x150+10+50 590x100+10+200 \n\n");
875
876 i = sraRgnGetReverseIterator(region,1,1);
877 while(sraRgnIteratorNext(i, &rect))
878 printf("%dx%d+%d+%d ",
879 rect.x2-rect.x1,rect.y2-rect.y1,
880 rect.x1,rect.y1);
881 sraRgnReleaseIterator(i);
882 printf("\n590x100+10+200 250x150+350+50 30x150+10+50 590x10+10+40 600x30+0+10 20x10+0+0 \n\n");
883
884 sraRgnDestroy(region);
885 sraRgnDestroy(region1);
886 sraRgnDestroy(region2);
887
888 return(0);
889 }
890 #endif
891