git.maemo.org Git - presencevnc/blob - libvnc/libvncserver/rfbregion.c

   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 *
  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 *
  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
  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
  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
  68 sraSpanRemove(sraSpan *span) {
  69   span->_prev->_next = span->_next;
  70   span->_next->_prev = span->_prev;
  71 }
  72
  73 static void
  74 sraSpanDestroy(sraSpan *span) {
  75   if (span->subspan) sraSpanListDestroy(span->subspan);
  76   free(span);
  77 }
  78
  79 #ifdef DEBUG
  80 static void
  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
  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
 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 *
 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 *
 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
 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
 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
 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
 207 sraSpanListEmpty(const sraSpanList *list) {
 208   return (list->front._next == &(list->back));
 209 }
 210
 211 static unsigned long
 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
 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
 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
 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
 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
 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 *
 511 sraRgnCreate(void) {
 512   return (sraRegion*)sraSpanListCreate();
 513 }
 514
 515 sraRegion *
 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 *
 536 sraRgnCreateRgn(const sraRegion *src) {
 537   return (sraRegion*)sraSpanListDup((sraSpanList*)src);
 538 }
 539
 540 void
 541 sraRgnDestroy(sraRegion *rgn) {
 542   sraSpanListDestroy((sraSpanList*)rgn);
 543 }
 544
 545 void
 546 sraRgnMakeEmpty(sraRegion *rgn) {
 547   sraSpanListMakeEmpty((sraSpanList*)rgn);
 548 }
 549
 550 /* -=- Boolean Region ops */
 551
 552 rfbBool
 553 sraRgnAnd(sraRegion *dst, const sraRegion *src) {
 554   return sraSpanListAnd((sraSpanList*)dst, (sraSpanList*)src);
 555 }
 556
 557 void
 558 sraRgnOr(sraRegion *dst, const sraRegion *src) {
 559   sraSpanListOr((sraSpanList*)dst, (sraSpanList*)src);
 560 }
 561
 562 rfbBool
 563 sraRgnSubtract(sraRegion *dst, const sraRegion *src) {
 564   return sraSpanListSubtract((sraSpanList*)dst, (sraSpanList*)src);
 565 }
 566
 567 void
 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
 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
 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
 672 sraRgnCountRects(const sraRegion *rgn) {
 673   unsigned long count = sraSpanListCount((sraSpanList*)rgn);
 674   return count;
 675 }
 676
 677 rfbBool
 678 sraRgnEmpty(const sraRegion *rgn) {
 679   return sraSpanListEmpty((sraSpanList*)rgn);
 680 }
 681
 682 /* iterator stuff */
 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
 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
 723 static rfbBool sraReverse(sraRectangleIterator *i)
 724 {
 725   return( ((i->ptrPos&2) && i->reverseX) ||
 726      (!(i->ptrPos&2) && i->reverseY));
 727 }
 728
 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
 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
 777 void sraRgnReleaseIterator(sraRectangleIterator* i)
 778 {
 779   free(i->sPtrs);
 780   free(i);
 781 }
 782
 783 void
 784 sraRgnPrint(const sraRegion *rgn) {
 785         sraSpanListPrint((sraSpanList*)rgn);
 786 }
 787
 788 rfbBool
 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
 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. */
 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