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