src/core/SkTileGrid.cpp

/*
 * Copyright 2012 Google Inc.
 *
 * Use of this source code is governed by a BSD-style license that can be
 * found in the LICENSE file.
 */

#include "SkTileGrid.h"
#include "SkPictureStateTree.h"

SkTileGrid::SkTileGrid(int xTileCount, int yTileCount, const SkTileGridFactory::TileGridInfo& info) {
    fXTileCount = xTileCount;
    fYTileCount = yTileCount;
    fInfo = info;
    // Margin is offset by 1 as a provision for AA and
    // to cancel-out the outset applied by getClipDeviceBounds.
    fInfo.fMargin.fHeight++;
    fInfo.fMargin.fWidth++;
    fTileCount = fXTileCount * fYTileCount;
    fInsertionCount = 0;
    fGridBounds = SkIRect::MakeXYWH(0, 0, fInfo.fTileInterval.width() * fXTileCount,
        fInfo.fTileInterval.height() * fYTileCount);
    fTileData = SkNEW_ARRAY(SkTDArray<void *>, fTileCount);
}

SkTileGrid::~SkTileGrid() {
    SkDELETE_ARRAY(fTileData);
}

int SkTileGrid::tileCount(int x, int y) {
    return this->tile(x, y).count();
}

const SkTDArray<void *>& SkTileGrid::tile(int x, int y) const {
    return fTileData[y * fXTileCount + x];
}

SkTDArray<void *>& SkTileGrid::tile(int x, int y) {
    return fTileData[y * fXTileCount + x];
}

void SkTileGrid::insert(void* data, const SkIRect& bounds, bool) {
    SkASSERT(!bounds.isEmpty());
    SkIRect dilatedBounds = bounds;
    dilatedBounds.outset(fInfo.fMargin.width(), fInfo.fMargin.height());
    dilatedBounds.offset(fInfo.fOffset);
    if (!SkIRect::Intersects(dilatedBounds, fGridBounds)) {
        return;
    }

    // Note: SkIRects are non-inclusive of the right() column and bottom() row,
    // hence the "-1"s in the computations of maxTileX and maxTileY.
    int minTileX = SkMax32(SkMin32(dilatedBounds.left() / fInfo.fTileInterval.width(),
        fXTileCount - 1), 0);
    int maxTileX = SkMax32(SkMin32((dilatedBounds.right() - 1) / fInfo.fTileInterval.width(),
        fXTileCount - 1), 0);
    int minTileY = SkMax32(SkMin32(dilatedBounds.top() / fInfo.fTileInterval.height(),
        fYTileCount -1), 0);
    int maxTileY = SkMax32(SkMin32((dilatedBounds.bottom() -1) / fInfo.fTileInterval.height(),
        fYTileCount -1), 0);

    for (int x = minTileX; x <= maxTileX; x++) {
        for (int y = minTileY; y <= maxTileY; y++) {
            this->tile(x, y).push(data);
        }
    }
    fInsertionCount++;
}

static void* next_datum(const SkTDArray<void*>** tileData,
                        SkAutoSTArray<SkTileGrid::kStackAllocationTileCount, int>& tileIndices) {
    SkPictureStateTree::Draw* minVal = NULL;
    int tileCount = tileIndices.count();
    int minIndex = tileCount;
    int maxIndex = 0;
    // Find the next Datum; track where it's found so we reduce the size of the second loop.
    for (int tile = 0; tile < tileCount; ++tile) {
        int pos = tileIndices[tile];
        if (pos != SkTileGrid::kTileFinished) {
            SkPictureStateTree::Draw* candidate = (SkPictureStateTree::Draw*)(*tileData[tile])[pos];
            if (NULL == minVal || (*candidate) < (*minVal)) {
                minVal = candidate;
                minIndex = tile;
                maxIndex = tile;
            } else if (!((*minVal) < (*candidate))) {
                // We don't require operator==; if !(candidate<minVal) && !(minVal<candidate),
                // candidate==minVal and we have to add this tile to the range searched.
                maxIndex = tile;
            }
        }
    }
    // Increment indices past the next datum
    if (minVal != NULL) {
        for (int tile = minIndex; tile <= maxIndex; ++tile) {
            int pos = tileIndices[tile];
            if (pos != SkTileGrid::kTileFinished && (*tileData[tile])[pos] == minVal) {
                if (++(tileIndices[tile]) >= tileData[tile]->count()) {
                    tileIndices[tile] = SkTileGrid::kTileFinished;
                }
            }
        }
        return minVal;
    }
    return NULL;
}

void SkTileGrid::search(const SkIRect& query, SkTDArray<void*>* results) const {
    SkIRect adjustedQuery = query;
    // The inset is to counteract the outset that was applied in 'insert'
    // The outset/inset is to optimize for lookups of size
    // 'tileInterval + 2 * margin' that are aligned with the tile grid.
    adjustedQuery.inset(fInfo.fMargin.width(), fInfo.fMargin.height());
    adjustedQuery.offset(fInfo.fOffset);
    adjustedQuery.sort();  // in case the inset inverted the rectangle
    // Convert the query rectangle from device coordinates to tile coordinates
    // by rounding outwards to the nearest tile boundary so that the resulting tile
    // region includes the query rectangle. (using truncating division to "floor")
    int tileStartX = adjustedQuery.left() / fInfo.fTileInterval.width();
    int tileEndX = (adjustedQuery.right() + fInfo.fTileInterval.width() - 1) /
        fInfo.fTileInterval.width();
    int tileStartY = adjustedQuery.top() / fInfo.fTileInterval.height();
    int tileEndY = (adjustedQuery.bottom() + fInfo.fTileInterval.height() - 1) /
        fInfo.fTileInterval.height();

    tileStartX = SkPin32(tileStartX, 0, fXTileCount - 1);
    tileEndX = SkPin32(tileEndX, tileStartX+1, fXTileCount);
    tileStartY = SkPin32(tileStartY, 0, fYTileCount - 1);
    tileEndY = SkPin32(tileEndY, tileStartY+1, fYTileCount);

    int queryTileCount = (tileEndX - tileStartX) * (tileEndY - tileStartY);
    SkASSERT(queryTileCount);
    if (queryTileCount == 1) {
        *results = this->tile(tileStartX, tileStartY);
    } else {
        results->reset();
        SkAutoSTArray<kStackAllocationTileCount, int> curPositions(queryTileCount);
        SkAutoSTArray<kStackAllocationTileCount, SkTDArray<void *>*> storage(queryTileCount);
        const SkTDArray<void *>** tileRange = const_cast<const SkTDArray<void*>**>(storage.get());
        int tile = 0;
        for (int x = tileStartX; x < tileEndX; ++x) {
            for (int y = tileStartY; y < tileEndY; ++y) {
                tileRange[tile] = &this->tile(x, y);
                curPositions[tile] = tileRange[tile]->count() ? 0 : kTileFinished;
                ++tile;
            }
        }
        while(void* nextElement = next_datum(tileRange, curPositions)) {
            results->push(nextElement);
        }
    }
}

void SkTileGrid::clear() {
    for (int i = 0; i < fTileCount; i++) {
        fTileData[i].reset();
    }
}

int SkTileGrid::getCount() const {
    return fInsertionCount;
}

void SkTileGrid::rewindInserts() {
    SkASSERT(fClient);
    for (int i = 0; i < fTileCount; ++i) {
        while (!fTileData[i].isEmpty() && fClient->shouldRewind(fTileData[i].top())) {
            fTileData[i].pop();
        }
    }
}