apps/window_server/Region.cpp

   1 #include <stdlib.h>
   2 #include <stdio.h>
   3 #include <string.h>
   4 #include "Region.h"
   5 #include "util.h"
   6
   7 const int kRectAllocSize = 16;
   8
   9 Region::Region()
  10         :       fRects(0),
  11                 fNumRects(0),
  12                 fOpLevel(0)
  13 {
  14 }
  15
  16 Region::Region(const Region &copyRegion)
  17         :       fRects(0),
  18                 fNumRects(0),
  19                 fOpLevel(0)
  20 {
  21         SetTo(copyRegion);
  22 }
  23
  24 Region::~Region()
  25 {
  26         free(fRects);
  27 }
  28
  29 Region& Region::SetTo(const Region &copyRegion)
  30 {
  31         AllocSpace(copyRegion.fNumRects);
  32         fNumRects = copyRegion.fNumRects;
  33         memcpy(fRects, copyRegion.fRects, fNumRects * sizeof(Rect));
  34         return *this;
  35 }
  36
  37 Region& Region::operator=(const Region &copyRegion)
  38 {
  39         return SetTo(copyRegion);
  40 }
  41
  42 Rect Region::Bounds() const
  43 {
  44         Rect bounds(COORD_MAX, COORD_MAX, -COORD_MAX, -COORD_MAX);
  45         for (int i = 0; i < fNumRects; i++) {
  46                 const Rect &rect = RectAt(i);
  47                 bounds.left = min(bounds.left, rect.left);
  48                 bounds.right = max(bounds.right, rect.right);
  49                 bounds.top = min(bounds.top, rect.top);
  50                 bounds.bottom = max(bounds.bottom, rect.bottom);
  51         }
  52
  53         return bounds;
  54 }
  55
  56 Region& Region::Include(const Rect &rect)
  57 {
  58         Region temp;
  59
  60         BeginOperation();
  61         // Make sure that there are no overlaps
  62         temp.AddRect(rect);
  63         for (int i = 0; i < fNumRects; i++)
  64                 temp.Exclude(RectAt(i));
  65
  66         AddRegionRects(temp);
  67         EndOperation();
  68         return *this;
  69 }
  70
  71 Region& Region::Include(const Region &region)
  72 {
  73         BeginOperation();
  74         for (int i = 0; i < region.CountRects(); i++)
  75                 Include(region.RectAt(i));
  76         EndOperation();
  77
  78         return *this;
  79 }
  80
  81 #define SPLIT_TEST(rect1, rect2)                                                                                        \
  82         (max(rect1.left, rect2.left) < min(rect1.right, rect2.right)                    \
  83                 && max(rect1.top, rect2.top) < min(rect1.bottom, rect2.bottom))
  84
  85 Region& Region::Exclude(const Rect &excludeRect)
  86 {
  87         BeginOperation();
  88         int index = 0;
  89         int rectsToCheck = fNumRects;
  90         while (index < rectsToCheck) {
  91                 Rect &clipRect = fRects[index];
  92
  93                 if (!excludeRect.Intersects(clipRect)) {
  94                         index++;
  95                         continue;
  96                 }
  97
  98                 // This clip rect intersects the excluded rect, and could be divided into
  99                 // as many as eight pieces.  Test for each case.  Note that none of these
 100                 // rectangles overlap!!!!
 101                 Rect quad1(clipRect.left, clipRect.top, excludeRect.left - 1, excludeRect.top - 1);
 102                 if (SPLIT_TEST(clipRect, quad1)) {
 103                         quad1.Intersect(clipRect);
 104                         AddRect(quad1);
 105                 }
 106
 107                 Rect quad2(excludeRect.left, clipRect.top, excludeRect.right, excludeRect.top - 1);
 108                 if (SPLIT_TEST(clipRect, quad2)) {
 109                         quad2.Intersect(clipRect);
 110                         AddRect(quad2);
 111                 }
 112
 113                 Rect quad3(excludeRect.right + 1, clipRect.top, clipRect.right, excludeRect.top - 1);
 114                 if (SPLIT_TEST(clipRect, quad3)) {
 115                         quad3.Intersect(clipRect);
 116                         AddRect(quad3);
 117                 }
 118
 119                 Rect quad4(clipRect.left, excludeRect.top, excludeRect.left - 1, excludeRect.bottom);
 120                 if (SPLIT_TEST(clipRect, quad4)) {
 121                         quad4.Intersect(clipRect);
 122                         AddRect(quad4);
 123                 }
 124
 125                 Rect quad5(excludeRect.right + 1, excludeRect.top, clipRect.right, excludeRect.bottom);
 126                 if (SPLIT_TEST(clipRect, quad5)) {
 127                         quad5.Intersect(clipRect);
 128                         AddRect(quad5);
 129                 }
 130
 131                 Rect quad6(clipRect.left, excludeRect.bottom + 1, excludeRect.left - 1, clipRect.bottom);
 132                 if (SPLIT_TEST(clipRect, quad6)) {
 133                         quad6.Intersect(clipRect);
 134                         AddRect(quad6);
 135                 }
 136
 137                 Rect quad7(excludeRect.left, excludeRect.bottom + 1, excludeRect.right, clipRect.bottom);
 138                 if (SPLIT_TEST(clipRect, quad7)) {
 139                         quad7.Intersect(clipRect);
 140                         AddRect(quad7);
 141                 }
 142
 143                 Rect quad8(excludeRect.right + 1, excludeRect.bottom + 1, clipRect.right, clipRect.bottom);
 144                 if (SPLIT_TEST(clipRect, quad8)) {
 145                         quad8.Intersect(clipRect);
 146                         AddRect(quad8);
 147                 }
 148
 149                 // This rect has been split, remove it.  Note we don't
 150                 // change the index
 151                 RemoveRect(index);
 152                 rectsToCheck--;
 153         }
 154         EndOperation();
 155         return *this;
 156 }
 157
 158 Region& Region::Exclude(const Region &ex)
 159 {
 160         BeginOperation();
 161         Region temp(ex);
 162         temp.Invert();
 163         Intersect(temp);
 164         EndOperation();
 165         return *this;
 166 }
 167
 168
 169
 170 Region& Region::Clear()
 171 {
 172         fNumRects = 0;
 173         AllocSpace(0);
 174         return *this;
 175 }
 176
 177 Region& Region::ConstrainTo(const Rect &rect)
 178 {
 179         BeginOperation();
 180         for (int i = fNumRects - 1; i >= 0; i--) {
 181                 fRects[i].left = max(rect.left, fRects[i].left);
 182                 fRects[i].right = min(rect.right, fRects[i].right);
 183                 fRects[i].top = max(rect.top, fRects[i].top);
 184                 fRects[i].bottom = min(rect.bottom, fRects[i].bottom);
 185                 if (!fRects[i].Valid())
 186                         RemoveRect(i);
 187         }
 188
 189         EndOperation();
 190         return *this;
 191 }
 192
 193 Region& Region::Translate(int x, int y)
 194 {
 195         for (int i = 0; i < fNumRects; i++) {
 196                 fRects[i].left += x;
 197                 fRects[i].right += x;
 198                 fRects[i].top += y;
 199                 fRects[i].bottom += y;
 200         }
 201
 202         return *this;
 203 }
 204
 205 Region& Region::Intersect(const Region &intersectRegion)
 206 {
 207         BeginOperation();
 208         Region newRegion;
 209         for (int i = 0; i < fNumRects; i++) {
 210                 for (int j = 0; j < intersectRegion.fNumRects; j++) {
 211                         if (RectAt(i).Intersects(intersectRegion.RectAt(j))) {
 212                                 Rect temp(RectAt(i));
 213                                 temp.Intersect(intersectRegion.RectAt(j));
 214                                 newRegion.AddRect(temp);
 215                         }
 216                 }
 217         }
 218
 219         SetTo(newRegion);
 220         EndOperation();
 221         return *this;
 222 }
 223
 224 bool Region::Intersects(const Rect &intersectsRect) const
 225 {
 226         for (int i = 0; i < fNumRects; i++) {
 227                 if(RectAt(i).Intersects(intersectsRect))
 228                         return true;
 229         }
 230         return false;
 231 }
 232
 233 Region& Region::Invert()
 234 {
 235         BeginOperation();
 236         Region temp;
 237         temp.Include(Rect(-COORD_MAX, -COORD_MAX, COORD_MAX, COORD_MAX));
 238         for (int i = 0; i < fNumRects; i++)
 239                 temp.Exclude(fRects[i]);
 240
 241         SetTo(temp);
 242         EndOperation();
 243         return *this;
 244 }
 245
 246 const bool Region::FindRect(int x, int y, Rect &outRect) const
 247 {
 248         for (int i = 0; i < CountRects(); i++) {
 249                 if (RectAt(i).Contains(x, y)) {
 250                         outRect = RectAt(i);
 251                         return true;
 252                 }
 253         }
 254
 255         return false;
 256 }
 257
 258 void Region::AddRect(const Rect &rect)
 259 {
 260         AllocSpace(fNumRects + 1);
 261         fRects[fNumRects++] = rect;
 262 }
 263
 264 void Region::RemoveRect(int index)
 265 {
 266         fNumRects--;
 267         memcpy(fRects + index, fRects + index + 1, (fNumRects - index) * sizeof(Rect));
 268         AllocSpace(fNumRects);
 269 }
 270
 271 void Region::AddRegionRects(const Region &region)
 272 {
 273         for (int i = 0; i < region.fNumRects; i++)
 274                 AddRect(region.RectAt(i));
 275 }
 276
 277 void Region::Consolidate()
 278 {
 279         // Optimize region by consolidating adjacent rectangles.
 280         for (int i = 0; i < fNumRects; i++) {
 281                 for (int j = fNumRects - 1; j > i; j--) {
 282                         Rect &rect1 = fRects[i];
 283                         Rect &rect2 = fRects[j];
 284                         if (rect1.top == rect2.top && rect1.bottom == rect2.bottom) {
 285                                 if (rect1.right + 1 == rect2.left) {
 286                                         rect1.right = rect2.right;
 287                                         RemoveRect(j);
 288                                 } else if (rect2.right + 1 == rect1.left) {
 289                                         rect1.left = rect2.left;
 290                                         RemoveRect(j);
 291                                 }
 292                         } else if (rect1.left == rect2.left && rect1.right == rect2.right) {
 293                                 if (rect1.top == rect2.bottom + 1) {
 294                                         rect1.top = rect2.top;
 295                                         RemoveRect(j);
 296                                 } else if (rect1.bottom + 1 == rect2.top) {
 297                                         rect1.bottom = rect2.bottom;
 298                                         RemoveRect(j);
 299                                 }
 300                         }
 301                 }
 302         }
 303 }
 304
 305 void Region::AllocSpace(int numRects)
 306 {
 307         int currentAlloc = ((fNumRects + kRectAllocSize - 1) / kRectAllocSize)
 308                 * kRectAllocSize;
 309         int sizeWanted = ((numRects + kRectAllocSize - 1) / kRectAllocSize)
 310                 * kRectAllocSize;
 311
 312         if (sizeWanted != currentAlloc) {
 313                 if (fRects == 0 && sizeWanted > 0)
 314                         fRects = (Rect*) malloc(sizeWanted * sizeof(Rect));
 315                 else if (sizeWanted == 0 && fRects != 0) {
 316                         free(fRects);
 317                         fRects = 0;
 318                 } else
 319                         fRects = (Rect*) realloc(fRects, sizeWanted * sizeof(Rect));
 320         }
 321 }
 322
 323
 324 void Region::BeginOperation()
 325 {
 326         fOpLevel++;
 327 }
 328
 329 void Region::EndOperation()
 330 {
 331         if (--fOpLevel == 0)
 332                 Consolidate();
 333
 334         ASSERT(fOpLevel >= 0);
 335 }
 336
 337
 338
 339 void Region::Dump() const
 340 {
 341         printf("Region:  ");
 342         for (int i = 0; i < fNumRects; i++) {
 343                 if ((i % 6) == 5)
 344                         printf("\n");
 345                 printf("(%d %d %d %d)   ", fRects[i].left, fRects[i].top, fRects[i].right,
 346                         fRects[i].bottom);
 347         }
 348
 349         printf("\n");
 350 }