michael@0: 
michael@0: /*
michael@0:  * Copyright 2010 Google Inc.
michael@0:  *
michael@0:  * Use of this source code is governed by a BSD-style license that can be
michael@0:  * found in the LICENSE file.
michael@0:  */
michael@0: 
michael@0: 
michael@0: 
michael@0: #include "GrRectanizer.h"
michael@0: #include "GrTBSearch.h"
michael@0: 
michael@0: #define MIN_HEIGHT_POW2     2
michael@0: 
michael@0: class GrRectanizerPow2 : public GrRectanizer {
michael@0: public:
michael@0:     GrRectanizerPow2(int w, int h) : GrRectanizer(w, h) {
michael@0:         fNextStripY = 0;
michael@0:         fAreaSoFar = 0;
michael@0:         sk_bzero(fRows, sizeof(fRows));
michael@0:     }
michael@0: 
michael@0:     virtual ~GrRectanizerPow2() {
michael@0:     }
michael@0: 
michael@0:     virtual void reset() {
michael@0:         fNextStripY = 0;
michael@0:         fAreaSoFar = 0;
michael@0:         sk_bzero(fRows, sizeof(fRows));
michael@0:     }
michael@0: 
michael@0:     virtual bool addRect(int w, int h, GrIPoint16* loc);
michael@0: 
michael@0:     virtual float percentFull() const {
michael@0:         return fAreaSoFar / ((float)this->width() * this->height());
michael@0:     }
michael@0: 
michael@0:     virtual int stripToPurge(int height) const { return -1; }
michael@0:     virtual void purgeStripAtY(int yCoord) { }
michael@0: 
michael@0:     ///////////////////////////////////////////////////////////////////////////
michael@0: 
michael@0:     struct Row {
michael@0:         GrIPoint16  fLoc;
michael@0:         int         fRowHeight;
michael@0: 
michael@0:         bool canAddWidth(int width, int containerWidth) const {
michael@0:             return fLoc.fX + width <= containerWidth;
michael@0:         }
michael@0:     };
michael@0: 
michael@0:     Row fRows[16];
michael@0: 
michael@0:     static int HeightToRowIndex(int height) {
michael@0:         SkASSERT(height >= MIN_HEIGHT_POW2);
michael@0:         return 32 - SkCLZ(height - 1);
michael@0:     }
michael@0: 
michael@0:     int fNextStripY;
michael@0:     int32_t fAreaSoFar;
michael@0: 
michael@0:     bool canAddStrip(int height) const {
michael@0:         return fNextStripY + height <= this->height();
michael@0:     }
michael@0: 
michael@0:     void initRow(Row* row, int rowHeight) {
michael@0:         row->fLoc.set(0, fNextStripY);
michael@0:         row->fRowHeight = rowHeight;
michael@0:         fNextStripY += rowHeight;
michael@0:     }
michael@0: };
michael@0: 
michael@0: bool GrRectanizerPow2::addRect(int width, int height, GrIPoint16* loc) {
michael@0:     if ((unsigned)width > (unsigned)this->width() ||
michael@0:         (unsigned)height > (unsigned)this->height()) {
michael@0:         return false;
michael@0:     }
michael@0: 
michael@0:     int32_t area = width * height;
michael@0: 
michael@0:     /*
michael@0:         We use bsearch, but there may be more than one row with the same height,
michael@0:         so we actually search for height-1, which can only be a pow2 itself if
michael@0:         height == 2. Thus we set a minimum height.
michael@0:      */
michael@0:     height = GrNextPow2(height);
michael@0:     if (height < MIN_HEIGHT_POW2) {
michael@0:         height = MIN_HEIGHT_POW2;
michael@0:     }
michael@0: 
michael@0:     Row* row = &fRows[HeightToRowIndex(height)];
michael@0:     SkASSERT(row->fRowHeight == 0 || row->fRowHeight == height);
michael@0: 
michael@0:     if (0 == row->fRowHeight) {
michael@0:         if (!this->canAddStrip(height)) {
michael@0:             return false;
michael@0:         }
michael@0:         this->initRow(row, height);
michael@0:     } else {
michael@0:         if (!row->canAddWidth(width, this->width())) {
michael@0:             if (!this->canAddStrip(height)) {
michael@0:                 return false;
michael@0:             }
michael@0:             // that row is now "full", so retarget our Row record for
michael@0:             // another one
michael@0:             this->initRow(row, height);
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     SkASSERT(row->fRowHeight == height);
michael@0:     SkASSERT(row->canAddWidth(width, this->width()));
michael@0:     *loc = row->fLoc;
michael@0:     row->fLoc.fX += width;
michael@0: 
michael@0:     SkASSERT(row->fLoc.fX <= this->width());
michael@0:     SkASSERT(row->fLoc.fY <= this->height());
michael@0:     SkASSERT(fNextStripY <= this->height());
michael@0:     fAreaSoFar += area;
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: ///////////////////////////////////////////////////////////////////////////////
michael@0: 
michael@0: // factory is now in GrRectanizer_skyline.cpp
michael@0: //GrRectanizer* GrRectanizer::Factory(int width, int height) {
michael@0: //    return SkNEW_ARGS(GrRectanizerPow2, (width, height));
michael@0: //}