michael@0: 
michael@0: /*
michael@0:  * Copyright 2012 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: #include "SkTileGrid.h"
michael@0: 
michael@0: SkTileGrid::SkTileGrid(int xTileCount, int yTileCount, const SkTileGridPicture::TileGridInfo& info,
michael@0:     SkTileGridNextDatumFunctionPtr nextDatumFunction)
michael@0: {
michael@0:     fXTileCount = xTileCount;
michael@0:     fYTileCount = yTileCount;
michael@0:     fInfo = info;
michael@0:     // Margin is offset by 1 as a provision for AA and
michael@0:     // to cancel-out the outset applied by getClipDeviceBounds.
michael@0:     fInfo.fMargin.fHeight++;
michael@0:     fInfo.fMargin.fWidth++;
michael@0:     fTileCount = fXTileCount * fYTileCount;
michael@0:     fInsertionCount = 0;
michael@0:     fGridBounds = SkIRect::MakeXYWH(0, 0, fInfo.fTileInterval.width() * fXTileCount,
michael@0:         fInfo.fTileInterval.height() * fYTileCount);
michael@0:     fNextDatumFunction = nextDatumFunction;
michael@0:     fTileData = SkNEW_ARRAY(SkTDArray<void *>, fTileCount);
michael@0: }
michael@0: 
michael@0: SkTileGrid::~SkTileGrid() {
michael@0:     SkDELETE_ARRAY(fTileData);
michael@0: }
michael@0: 
michael@0: int SkTileGrid::tileCount(int x, int y) {
michael@0:     return this->tile(x, y).count();
michael@0: }
michael@0: 
michael@0: SkTDArray<void *>& SkTileGrid::tile(int x, int y) {
michael@0:     return fTileData[y * fXTileCount + x];
michael@0: }
michael@0: 
michael@0: void SkTileGrid::insert(void* data, const SkIRect& bounds, bool) {
michael@0:     SkASSERT(!bounds.isEmpty());
michael@0:     SkIRect dilatedBounds = bounds;
michael@0:     dilatedBounds.outset(fInfo.fMargin.width(), fInfo.fMargin.height());
michael@0:     dilatedBounds.offset(fInfo.fOffset);
michael@0:     if (!SkIRect::Intersects(dilatedBounds, fGridBounds)) {
michael@0:         return;
michael@0:     }
michael@0: 
michael@0:     // Note: SkIRects are non-inclusive of the right() column and bottom() row,
michael@0:     // hence the "-1"s in the computations of maxTileX and maxTileY.
michael@0:     int minTileX = SkMax32(SkMin32(dilatedBounds.left() / fInfo.fTileInterval.width(),
michael@0:         fXTileCount - 1), 0);
michael@0:     int maxTileX = SkMax32(SkMin32((dilatedBounds.right() - 1) / fInfo.fTileInterval.width(),
michael@0:         fXTileCount - 1), 0);
michael@0:     int minTileY = SkMax32(SkMin32(dilatedBounds.top() / fInfo.fTileInterval.height(),
michael@0:         fYTileCount -1), 0);
michael@0:     int maxTileY = SkMax32(SkMin32((dilatedBounds.bottom() -1) / fInfo.fTileInterval.height(),
michael@0:         fYTileCount -1), 0);
michael@0: 
michael@0:     for (int x = minTileX; x <= maxTileX; x++) {
michael@0:         for (int y = minTileY; y <= maxTileY; y++) {
michael@0:             this->tile(x, y).push(data);
michael@0:         }
michael@0:     }
michael@0:     fInsertionCount++;
michael@0: }
michael@0: 
michael@0: void SkTileGrid::search(const SkIRect& query, SkTDArray<void*>* results) {
michael@0:     SkIRect adjustedQuery = query;
michael@0:     // The inset is to counteract the outset that was applied in 'insert'
michael@0:     // The outset/inset is to optimize for lookups of size
michael@0:     // 'tileInterval + 2 * margin' that are aligned with the tile grid.
michael@0:     adjustedQuery.inset(fInfo.fMargin.width(), fInfo.fMargin.height());
michael@0:     adjustedQuery.offset(fInfo.fOffset);
michael@0:     adjustedQuery.sort();  // in case the inset inverted the rectangle
michael@0:     // Convert the query rectangle from device coordinates to tile coordinates
michael@0:     // by rounding outwards to the nearest tile boundary so that the resulting tile
michael@0:     // region includes the query rectangle. (using truncating division to "floor")
michael@0:     int tileStartX = adjustedQuery.left() / fInfo.fTileInterval.width();
michael@0:     int tileEndX = (adjustedQuery.right() + fInfo.fTileInterval.width() - 1) /
michael@0:         fInfo.fTileInterval.width();
michael@0:     int tileStartY = adjustedQuery.top() / fInfo.fTileInterval.height();
michael@0:     int tileEndY = (adjustedQuery.bottom() + fInfo.fTileInterval.height() - 1) /
michael@0:         fInfo.fTileInterval.height();
michael@0: 
michael@0:     tileStartX = SkPin32(tileStartX, 0, fXTileCount - 1);
michael@0:     tileEndX = SkPin32(tileEndX, tileStartX+1, fXTileCount);
michael@0:     tileStartY = SkPin32(tileStartY, 0, fYTileCount - 1);
michael@0:     tileEndY = SkPin32(tileEndY, tileStartY+1, fYTileCount);
michael@0: 
michael@0:     int queryTileCount = (tileEndX - tileStartX) * (tileEndY - tileStartY);
michael@0:     SkASSERT(queryTileCount);
michael@0:     if (queryTileCount == 1) {
michael@0:         *results = this->tile(tileStartX, tileStartY);
michael@0:     } else {
michael@0:         results->reset();
michael@0:         SkAutoSTArray<kStackAllocationTileCount, int> curPositions(queryTileCount);
michael@0:         SkAutoSTArray<kStackAllocationTileCount, SkTDArray<void *>*> storage(queryTileCount);
michael@0:         SkTDArray<void *>** tileRange = storage.get();
michael@0:         int tile = 0;
michael@0:         for (int x = tileStartX; x < tileEndX; ++x) {
michael@0:             for (int y = tileStartY; y < tileEndY; ++y) {
michael@0:                 tileRange[tile] = &this->tile(x, y);
michael@0:                 curPositions[tile] = tileRange[tile]->count() ? 0 : kTileFinished;
michael@0:                 ++tile;
michael@0:             }
michael@0:         }
michael@0:         void *nextElement;
michael@0:         while(NULL != (nextElement = fNextDatumFunction(tileRange, curPositions))) {
michael@0:             results->push(nextElement);
michael@0:         }
michael@0:     }
michael@0: }
michael@0: 
michael@0: void SkTileGrid::clear() {
michael@0:     for (int i = 0; i < fTileCount; i++) {
michael@0:         fTileData[i].reset();
michael@0:     }
michael@0: }
michael@0: 
michael@0: int SkTileGrid::getCount() const {
michael@0:     return fInsertionCount;
michael@0: }
michael@0: 
michael@0: void SkTileGrid::rewindInserts() {
michael@0:     SkASSERT(fClient);
michael@0:     for (int i = 0; i < fTileCount; ++i) {
michael@0:         while (!fTileData[i].isEmpty() && fClient->shouldRewind(fTileData[i].top())) {
michael@0:             fTileData[i].pop();
michael@0:         }
michael@0:     }
michael@0: }