krfb/libvncserver/sraRegion.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.h"
   9 #include "sraRegion.h"
  10
  11 #include <stdlib.h>
  12 #include <stdio.h>
  13
  14 /* -=- Internal Span structure */
  15
  16 struct sraRegion;
  17
  18 typedef struct sraSpan {
  19   struct sraSpan *_next;
  20   struct sraSpan *_prev;
  21   int start;
  22   int end;
  23   struct sraRegion *subspan;
  24 } sraSpan;
  25
  26 typedef struct sraRegion {
  27   sraSpan front;
  28   sraSpan back;
  29 } sraSpanList;
  30
  31 /* -=- Span routines */
  32
  33 sraSpanList *sraSpanListDup(const sraSpanList *src);
  34 void sraSpanListDestroy(sraSpanList *list);
  35
  36 sraSpan *
  37 sraSpanCreate(int start, int end, const sraSpanList *subspan) {
  38   sraSpan *item = (sraSpan*)malloc(sizeof(sraSpan));
  39   item->_next = item->_prev = NULL;
  40   item->start = start;
  41   item->end = end;
  42   item->subspan = sraSpanListDup(subspan);
  43   return item;
  44 }
  45
  46 sraSpan *
  47 sraSpanDup(const sraSpan *src) {
  48   sraSpan *span;
  49   if (!src) return NULL;
  50   span = sraSpanCreate(src->start, src->end, src->subspan);
  51   return span;
  52 }
  53
  54 void
  55 sraSpanInsertAfter(sraSpan *newspan, sraSpan *after) {
  56   newspan->_next = after->_next;
  57   newspan->_prev = after;
  58   after->_next->_prev = newspan;
  59   after->_next = newspan;
  60 }
  61
  62 void
  63 sraSpanInsertBefore(sraSpan *newspan, sraSpan *before) {
  64   newspan->_next = before;
  65   newspan->_prev = before->_prev;
  66   before->_prev->_next = newspan;
  67   before->_prev = newspan;
  68 }
  69
  70 void
  71 sraSpanRemove(sraSpan *span) {
  72   span->_prev->_next = span->_next;
  73   span->_next->_prev = span->_prev;
  74 }
  75
  76 void
  77 sraSpanDestroy(sraSpan *span) {
  78   if (span->subspan) sraSpanListDestroy(span->subspan);
  79   free(span);
  80 }
  81
  82 void
  83 sraSpanCheck(const sraSpan *span, const char *text) {
  84   /* Check the span is valid! */
  85   if (span->start == span->end) {
  86     printf("%s:%d-%d\n", text, span->start, span->end);
  87     exit(0);
  88   }
  89 }
  90
  91 /* -=- SpanList routines */
  92
  93 void sraSpanPrint(const sraSpan *s);
  94
  95 void
  96 sraSpanListPrint(const sraSpanList *l) {
  97   sraSpan *curr;
  98   if (!l) {
  99           printf("NULL");
 100           return;
 101   }
 102   curr = l->front._next;
 103   printf("[");
 104   while (curr != &(l->back)) {
 105     sraSpanPrint(curr);
 106     curr = curr->_next;
 107   }
 108   printf("]");
 109 }
 110
 111 void
 112 sraSpanPrint(const sraSpan *s) {
 113   printf("(%d-%d)", (s->start), (s->end));
 114   if (s->subspan)
 115     sraSpanListPrint(s->subspan);
 116 }
 117
 118 sraSpanList *
 119 sraSpanListCreate() {
 120   sraSpanList *item = (sraSpanList*)malloc(sizeof(sraSpanList));
 121   item->front._next = &(item->back);
 122   item->front._prev = NULL;
 123   item->back._prev = &(item->front);
 124   item->back._next = NULL;
 125   return item;
 126 }
 127
 128 sraSpanList *
 129 sraSpanListDup(const sraSpanList *src) {
 130   sraSpanList *newlist;
 131   sraSpan *newspan, *curr;
 132
 133   if (!src) return NULL;
 134   newlist = sraSpanListCreate();
 135   curr = src->front._next;
 136   while (curr != &(src->back)) {
 137     newspan = sraSpanDup(curr);
 138     sraSpanInsertBefore(newspan, &(newlist->back));
 139     curr = curr->_next;
 140   }
 141
 142   return newlist;
 143 }
 144
 145 void
 146 sraSpanListDestroy(sraSpanList *list) {
 147   sraSpan *curr, *next;
 148   while (list->front._next != &(list->back)) {
 149     curr = list->front._next;
 150     next = curr->_next;
 151     sraSpanRemove(curr);
 152     sraSpanDestroy(curr);
 153     curr = next;
 154   }
 155   free(list);
 156 }
 157
 158 void
 159 sraSpanListMakeEmpty(sraSpanList *list) {
 160   sraSpan *curr, *next;
 161   while (list->front._next != &(list->back)) {
 162     curr = list->front._next;
 163     next = curr->_next;
 164     sraSpanRemove(curr);
 165     sraSpanDestroy(curr);
 166     curr = next;
 167   }
 168   list->front._next = &(list->back);
 169   list->front._prev = NULL;
 170   list->back._prev = &(list->front);
 171   list->back._next = NULL;
 172 }
 173
 174 Bool
 175 sraSpanListEqual(const sraSpanList *s1, const sraSpanList *s2) {
 176   sraSpan *sp1, *sp2;
 177
 178   if (!s1) {
 179     if (!s2) {
 180       return 1;
 181     } else {
 182       printf("sraSpanListEqual:incompatible spans (only one NULL!)\n");
 183       exit(1);
 184     }
 185   }
 186
 187   sp1 = s1->front._next;
 188   sp2 = s2->front._next;
 189   while ((sp1 != &(s1->back)) &&
 190          (sp2 != &(s2->back))) {
 191     if ((sp1->start != sp2->start) ||
 192         (sp1->end != sp2->end) ||
 193         (!sraSpanListEqual(sp1->subspan, sp2->subspan))) {
 194       return 0;
 195     }
 196     sp1 = sp1->_next;
 197     sp2 = sp2->_next;
 198   }
 199
 200   if ((sp1 == &(s1->back)) && (sp2 == &(s2->back))) {
 201     return 1;
 202   } else {
 203     return 0;
 204   }
 205 }
 206
 207 Bool
 208 sraSpanListEmpty(const sraSpanList *list) {
 209   return (list->front._next == &(list->back));
 210 }
 211
 212 unsigned long
 213 sraSpanListCount(const sraSpanList *list) {
 214   sraSpan *curr = list->front._next;
 215   unsigned long count = 0;
 216   while (curr != &(list->back)) {
 217     if (curr->subspan) {
 218       count += sraSpanListCount(curr->subspan);
 219     } else {
 220       count += 1;
 221     }
 222     curr = curr->_next;
 223   }
 224   return count;
 225 }
 226
 227 void
 228 sraSpanMergePrevious(sraSpan *dest) {
 229   sraSpan *prev = dest->_prev;
 230   while ((prev->end == dest->start) &&
 231          (prev->_prev) &&
 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 void
 248 sraSpanMergeNext(sraSpan *dest) {
 249   sraSpan *next = dest->_next;
 250   while ((next->start == dest->end) &&
 251          (next->_next) &&
 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 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       printf("sraSpanListOr:incompatible spans (only one NULL!)\n");
 277       exit(1);
 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 Bool
 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       printf("sraSpanListAnd:incompatible spans (only one NULL!)\n");
 366       exit(1);
 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 Bool
 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       printf("sraSpanListSubtract:incompatible spans (only one NULL!)\n");
 446       exit(1);
 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() {
 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 Bool
 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 Bool
 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 Bool
 588 sraRgnPopRect(sraRegion *rgn, sraRect *rect, unsigned long flags) {
 589   sraSpan *vcurr, *hcurr;
 590   sraSpan *vend, *hend;
 591   Bool right2left = flags & 2;
 592   Bool bottom2top = flags & 1;
 593
 594   /* - Pick correct order */
 595   if (bottom2top) {
 596     vcurr = ((sraSpanList*)rgn)->back._prev;
 597     vend = &(((sraSpanList*)rgn)->front);
 598   } else {
 599     vcurr = ((sraSpanList*)rgn)->front._next;
 600     vend = &(((sraSpanList*)rgn)->back);
 601   }
 602
 603   if (vcurr != vend) {
 604     rect->y1 = vcurr->start;
 605     rect->y2 = vcurr->end;
 606
 607     /* - Pick correct order */
 608     if (right2left) {
 609       hcurr = vcurr->subspan->back._prev;
 610       hend = &(vcurr->subspan->front);
 611     } else {
 612       hcurr = vcurr->subspan->front._next;
 613       hend = &(vcurr->subspan->back);
 614     }
 615
 616     if (hcurr != hend) {
 617       rect->x1 = hcurr->start;
 618       rect->x2 = hcurr->end;
 619
 620       sraSpanRemove(hcurr);
 621       sraSpanDestroy(hcurr);
 622
 623       if (sraSpanListEmpty(vcurr->subspan)) {
 624         sraSpanRemove(vcurr);
 625         sraSpanDestroy(vcurr);
 626       }
 627
 628 #if 0
 629       printf("poprect:(%dx%d)-(%dx%d)\n",
 630              rect->x1, rect->y1, rect->x2, rect->y2);
 631 #endif
 632       return 1;
 633     }
 634   }
 635
 636   return 0;
 637 }
 638
 639 unsigned long
 640 sraRgnCountRects(const sraRegion *rgn) {
 641   unsigned long count = sraSpanListCount((sraSpanList*)rgn);
 642   return count;
 643 }
 644
 645 Bool
 646 sraRgnEmpty(const sraRegion *rgn) {
 647   return sraSpanListEmpty((sraSpanList*)rgn);
 648 }
 649
 650 /* iterator stuff */
 651 sraRectangleIterator *sraRgnGetIterator(sraRegion *s)
 652 {
 653   /* these values have to be multiples of 4 */
 654 #define DEFSIZE 4
 655 #define DEFSTEP 8
 656   sraRectangleIterator *i =
 657     (sraRectangleIterator*)malloc(sizeof(sraRectangleIterator));
 658   if(!i)
 659     return(0);
 660
 661   /* we have to recurse eventually. So, the first sPtr is the pointer to
 662      the sraSpan in the first level. the second sPtr is the pointer to
 663      the sraRegion.back. The third and fourth sPtr are for the second
 664      recursion level and so on. */
 665   i->sPtrs = (sraSpan**)malloc(sizeof(sraSpan*)*DEFSIZE);
 666   if(!i->sPtrs) {
 667     free(i);
 668     return(0);
 669   }
 670   i->ptrSize = DEFSIZE;
 671   i->sPtrs[0] = &(s->front);
 672   i->sPtrs[1] = &(s->back);
 673   i->ptrPos = 0;
 674   i->reverseX = 0;
 675   i->reverseY = 0;
 676   return(i);
 677 }
 678
 679 sraRectangleIterator *sraRgnGetReverseIterator(sraRegion *s,Bool reverseX,Bool reverseY)
 680 {
 681   sraRectangleIterator *i = sraRgnGetIterator(s);
 682   if(reverseY) {
 683     i->sPtrs[1] = &(s->front);
 684     i->sPtrs[0] = &(s->back);
 685   }
 686   i->reverseX = reverseX;
 687   i->reverseY = reverseY;
 688   return(i);
 689 }
 690
 691 Bool sraReverse(sraRectangleIterator *i)
 692 {
 693   return( ((i->ptrPos&2) && i->reverseX) ||
 694      (!(i->ptrPos&2) && i->reverseY));
 695 }
 696
 697 sraSpan* sraNextSpan(sraRectangleIterator *i)
 698 {
 699   if(sraReverse(i))
 700     return(i->sPtrs[i->ptrPos]->_prev);
 701   else
 702     return(i->sPtrs[i->ptrPos]->_next);
 703 }
 704
 705 Bool sraRgnIteratorNext(sraRectangleIterator* i,sraRect* r)
 706 {
 707   /* is the subspan finished? */
 708   while(sraNextSpan(i) == i->sPtrs[i->ptrPos+1]) {
 709     i->ptrPos -= 2;
 710     if(i->ptrPos < 0) /* the end */
 711       return(0);
 712   }
 713
 714   i->sPtrs[i->ptrPos] = sraNextSpan(i);
 715
 716   /* is this a new subspan? */
 717   while(i->sPtrs[i->ptrPos]->subspan) {
 718     if(i->ptrPos+2 > i->ptrSize) { /* array is too small */
 719       i->ptrSize += DEFSTEP;
 720       i->sPtrs = (sraSpan**)realloc(i->sPtrs, sizeof(sraSpan*)*i->ptrSize);
 721     }
 722     i->ptrPos =+ 2;
 723     if(sraReverse(i)) {
 724       i->sPtrs[i->ptrPos]   =   i->sPtrs[i->ptrPos-2]->subspan->back._prev;
 725       i->sPtrs[i->ptrPos+1] = &(i->sPtrs[i->ptrPos-2]->subspan->front);
 726     } else {
 727       i->sPtrs[i->ptrPos]   =   i->sPtrs[i->ptrPos-2]->subspan->front._next;
 728       i->sPtrs[i->ptrPos+1] = &(i->sPtrs[i->ptrPos-2]->subspan->back);
 729     }
 730   }
 731
 732   if((i->ptrPos%4)!=2) {
 733     fprintf(stderr,"sraRgnIteratorNext: offset is wrong (%d%%4!=2)\n",i->ptrPos);
 734     exit(-1);
 735   }
 736
 737   r->y1 = i->sPtrs[i->ptrPos-2]->start;
 738   r->y2 = i->sPtrs[i->ptrPos-2]->end;
 739   r->x1 = i->sPtrs[i->ptrPos]->start;
 740   r->x2 = i->sPtrs[i->ptrPos]->end;
 741
 742   return(-1);
 743 }
 744
 745 void sraRgnReleaseIterator(sraRectangleIterator* i)
 746 {
 747   free(i->sPtrs);
 748   free(i);
 749 }
 750
 751 void
 752 sraRgnPrint(const sraRegion *rgn) {
 753         sraSpanListPrint((sraSpanList*)rgn);
 754 }
 755
 756 Bool
 757 sraClipRect(int *x, int *y, int *w, int *h,
 758             int cx, int cy, int cw, int ch) {
 759   if (*x < cx) {
 760     *w -= (cx-*x);
 761     *x = cx;
 762   }
 763   if (*y < cy) {
 764     *h -= (cy-*y);
 765     *y = cy;
 766   }
 767   if (*x+*w > cx+cw) {
 768     *w = (cx+cw)-*x;
 769   }
 770   if (*y+*h > cy+ch) {
 771     *h = (cy+ch)-*y;
 772   }
 773   return (*w>0) && (*h>0);
 774 }
 775
 776 /* test */
 777
 778 #ifdef SRA_TEST
 779 /* pipe the output to sort|uniq -u and you'll get the errors. */
 780 int main(int argc, char** argv)
 781 {
 782   sraRegionPtr region, region1, region2;
 783   sraRectangleIterator* i;
 784   sraRect rect;
 785   Bool b;
 786
 787   region = sraRgnCreateRect(10, 10, 600, 300);
 788   region1 = sraRgnCreateRect(40, 50, 350, 200);
 789   region2 = sraRgnCreateRect(0, 0, 20, 40);
 790
 791   sraRgnPrint(region);
 792   printf("\n[(10-300)[(10-600)]]\n\n");
 793
 794   b = sraRgnSubtract(region, region1);
 795   printf("%s ",b?"true":"false");
 796   sraRgnPrint(region);
 797   printf("\ntrue [(10-50)[(10-600)](50-200)[(10-40)(350-600)](200-300)[(10-600)]]\n\n");
 798
 799   sraRgnOr(region, region2);
 800   printf("%ld\n6\n\n", sraRgnCountRects(region));
 801
 802   i = sraRgnGetIterator(region);
 803   while(sraRgnIteratorNext(i, &rect))
 804     printf("%dx%d+%d+%d ",
 805            rect.x2-rect.x1,rect.y2-rect.y1,
 806            rect.x1,rect.y1);
 807   sraRgnReleaseIterator(i);
 808   printf("\n20x10+0+0 600x30+0+10 590x10+10+40 30x150+10+50 250x150+350+50 590x100+10+200\n\n");
 809
 810   i = sraRgnGetReverseIterator(region,1,0);
 811   while(sraRgnIteratorNext(i, &rect))
 812     printf("%dx%d+%d+%d ",
 813            rect.x2-rect.x1,rect.y2-rect.y1,
 814            rect.x1,rect.y1);
 815   sraRgnReleaseIterator(i);
 816   printf("\n20x10+0+0 600x30+0+10 590x10+10+40 250x150+350+50 30x150+10+50 590x100+10+200\n\n");
 817
 818   i = sraRgnGetReverseIterator(region,1,1);
 819   while(sraRgnIteratorNext(i, &rect))
 820     printf("%dx%d+%d+%d ",
 821            rect.x2-rect.x1,rect.y2-rect.y1,
 822            rect.x1,rect.y1);
 823   sraRgnReleaseIterator(i);
 824   printf("\n590x100+10+200 250x150+350+50 30x150+10+50 590x10+10+40 600x30+0+10 20x10+0+0\n\n");
 825
 826   return(0);
 827 }
 828 #endif