Home | History | Annotate | Download | only in src 
      1 /*
      2     Copyright 2010 Google Inc.
      3 
      4     Licensed under the Apache License, Version 2.0 (the "License");
      5     you may not use this file except in compliance with the License.
      6     You may obtain a copy of the License at
      7 
      8          http://www.apache.org/licenses/LICENSE-2.0
      9 
     10     Unless required by applicable law or agreed to in writing, software
     11     distributed under the License is distributed on an "AS IS" BASIS,
     12     WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
     13     See the License for the specific language governing permissions and
     14     limitations under the License.
     15  */
     16 
     17 
     18 #include "GrRectanizer.h"
     19 #include "GrTBSearch.h"
     20 
     21 #define MIN_HEIGHT_POW2     2
     22 
     23 class GrRectanizerFIFO : public GrRectanizer {
     24 public:
     25     GrRectanizerFIFO(int w, int h) : GrRectanizer(w, h) {
     26         fNextStripY = 0;
     27         fAreaSoFar = 0;
     28         Gr_bzero(fRows, sizeof(fRows));
     29     }
     30 
     31     virtual ~GrRectanizerFIFO() {
     32     }
     33 
     34     virtual bool addRect(int w, int h, GrIPoint16* loc);
     35 
     36     virtual float percentFull() const {
     37         return fAreaSoFar / ((float)this->width() * this->height());
     38     }
     39 
     40     virtual int stripToPurge(int height) const { return -1; }
     41     virtual void purgeStripAtY(int yCoord) { }
     42 
     43     ///////////////////////////////////////////////////////////////////////////
     44 
     45     struct Row {
     46         GrIPoint16  fLoc;
     47         int         fRowHeight;
     48 
     49         bool canAddWidth(int width, int containerWidth) const {
     50             return fLoc.fX + width <= containerWidth;
     51         }
     52     };
     53 
     54     Row fRows[16];
     55 
     56     static int HeightToRowIndex(int height) {
     57         GrAssert(height >= MIN_HEIGHT_POW2);
     58         return 32 - Gr_clz(height - 1);
     59     }
     60 
     61     int fNextStripY;
     62     int32_t fAreaSoFar;
     63 
     64     bool canAddStrip(int height) const {
     65         return fNextStripY + height <= this->height();
     66     }
     67 
     68     void initRow(Row* row, int rowHeight) {
     69         row->fLoc.set(0, fNextStripY);
     70         row->fRowHeight = rowHeight;
     71         fNextStripY += rowHeight;
     72     }
     73 };
     74 
     75 bool GrRectanizerFIFO::addRect(int width, int height, GrIPoint16* loc) {
     76     if ((unsigned)width > (unsigned)this->width() ||
     77         (unsigned)height > (unsigned)this->height()) {
     78         return false;
     79     }
     80 
     81     int32_t area = width * height;
     82 
     83     /*
     84      We use bsearch, but there may be more than one row with the same height,
     85      so we actually search for height-1, which can only be a pow2 itself if
     86      height == 2. Thus we set a minimum height.
     87      */
     88     height = GrNextPow2(height);
     89     if (height < MIN_HEIGHT_POW2) {
     90         height = MIN_HEIGHT_POW2;
     91     }
     92 
     93     Row* row = &fRows[HeightToRowIndex(height)];
     94     GrAssert(row->fRowHeight == 0 || row->fRowHeight == height);
     95 
     96     if (0 == row->fRowHeight) {
     97         if (!this->canAddStrip(height)) {
     98             return false;
     99         }
    100         this->initRow(row, height);
    101     } else {
    102         if (!row->canAddWidth(width, this->width())) {
    103             if (!this->canAddStrip(height)) {
    104                 return false;
    105             }
    106             // that row is now "full", so retarget our Row record for
    107             // another one
    108             this->initRow(row, height);
    109         }
    110     }
    111 
    112     GrAssert(row->fRowHeight == height);
    113     GrAssert(row->canAddWidth(width, this->width()));
    114     *loc = row->fLoc;
    115     row->fLoc.fX += width;
    116 
    117     GrAssert(row->fLoc.fX <= this->width());
    118     GrAssert(row->fLoc.fY <= this->height());
    119     GrAssert(fNextStripY <= this->height());
    120     fAreaSoFar += area;
    121     return true;
    122 }
    123 
    124 ///////////////////////////////////////////////////////////////////////////////
    125 
    126 GrRectanizer* GrRectanizer::Factory(int width, int height) {
    127     return new GrRectanizerFIFO(width, height);
    128 }
    129 
    130 
    131