1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/gfx/skia/trunk/src/core/SkTileGrid.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,142 @@
1.4 +
1.5 +/*
1.6 + * Copyright 2012 Google Inc.
1.7 + *
1.8 + * Use of this source code is governed by a BSD-style license that can be
1.9 + * found in the LICENSE file.
1.10 + */
1.11 +
1.12 +#ifndef SkTileGrid_DEFINED
1.13 +#define SkTileGrid_DEFINED
1.14 +
1.15 +#include "SkBBoxHierarchy.h"
1.16 +#include "SkPictureStateTree.h"
1.17 +#include "SkTileGridPicture.h" // for TileGridInfo
1.18 +
1.19 +/**
1.20 + * Subclass of SkBBoxHierarchy that stores elements in buckets that correspond
1.21 + * to tile regions, disposed in a regular grid. This is useful when the tile
1.22 + * structure that will be use in search() calls is known prior to insertion.
1.23 + * Calls to search will return in constant time.
1.24 + *
1.25 + * Note: Current implementation of search() only supports looking-up regions
1.26 + * that are an exact match to a single tile. Implementation could be augmented
1.27 + * to support arbitrary rectangles, but performance would be sub-optimal.
1.28 + */
1.29 +class SkTileGrid : public SkBBoxHierarchy {
1.30 +public:
1.31 + enum {
1.32 + // Number of tiles for which data is allocated on the stack in
1.33 + // SkTileGrid::search. If malloc becomes a bottleneck, we may consider
1.34 + // increasing this number. Typical large web page, say 2k x 16k, would
1.35 + // require 512 tiles of size 256 x 256 pixels.
1.36 + kStackAllocationTileCount = 1024
1.37 + };
1.38 +
1.39 + typedef void* (*SkTileGridNextDatumFunctionPtr)(SkTDArray<void*>** tileData, SkAutoSTArray<kStackAllocationTileCount, int>& tileIndices);
1.40 +
1.41 + SkTileGrid(int xTileCount, int yTileCount, const SkTileGridPicture::TileGridInfo& info,
1.42 + SkTileGridNextDatumFunctionPtr nextDatumFunction);
1.43 +
1.44 + virtual ~SkTileGrid();
1.45 +
1.46 + /**
1.47 + * Insert a data pointer and corresponding bounding box
1.48 + * @param data The data pointer, may be NULL
1.49 + * @param bounds The bounding box, should not be empty
1.50 + * @param defer Ignored, TileArray does not defer insertions
1.51 + */
1.52 + virtual void insert(void* data, const SkIRect& bounds, bool) SK_OVERRIDE;
1.53 +
1.54 + virtual void flushDeferredInserts() SK_OVERRIDE {};
1.55 +
1.56 + /**
1.57 + * Populate 'results' with data pointers corresponding to bounding boxes that intersect 'query'
1.58 + * The query argument is expected to be an exact match to a tile of the grid
1.59 + */
1.60 + virtual void search(const SkIRect& query, SkTDArray<void*>* results) SK_OVERRIDE;
1.61 +
1.62 + virtual void clear() SK_OVERRIDE;
1.63 +
1.64 + /**
1.65 + * Gets the number of insertions
1.66 + */
1.67 + virtual int getCount() const SK_OVERRIDE;
1.68 +
1.69 + virtual int getDepth() const SK_OVERRIDE { return -1; }
1.70 +
1.71 + virtual void rewindInserts() SK_OVERRIDE;
1.72 +
1.73 + // Used by search() and in SkTileGridHelper implementations
1.74 + enum {
1.75 + kTileFinished = -1,
1.76 + };
1.77 +
1.78 + int tileCount(int x, int y); // For testing only.
1.79 +
1.80 +private:
1.81 + SkTDArray<void*>& tile(int x, int y);
1.82 +
1.83 + int fXTileCount, fYTileCount, fTileCount;
1.84 + SkTileGridPicture::TileGridInfo fInfo;
1.85 + SkTDArray<void*>* fTileData;
1.86 + int fInsertionCount;
1.87 + SkIRect fGridBounds;
1.88 + SkTileGridNextDatumFunctionPtr fNextDatumFunction;
1.89 +
1.90 + typedef SkBBoxHierarchy INHERITED;
1.91 +};
1.92 +
1.93 +/**
1.94 + * Generic implementation for SkTileGridNextDatumFunctionPtr. user code may instantiate
1.95 + * this template to get a valid SkTileGridNextDatumFunction implementation
1.96 + *
1.97 + * Returns the next element of tileData[i][tileIndices[i]] for all i and advances
1.98 + * tileIndices[] past them. The order in which data are returned by successive
1.99 + * calls to this method must reflect the order in which the were originally
1.100 + * recorded into the tile grid.
1.101 + *
1.102 + * \param tileData array of pointers to arrays of tile data
1.103 + * \param tileIndices per-tile data indices, indices are incremented for tiles that contain
1.104 + * the next datum.
1.105 + * \tparam T a type to which it is safe to cast a datum and that has an operator <
1.106 + * such that 'a < b' is true if 'a' was inserted into the tile grid before 'b'.
1.107 + */
1.108 +template <typename T>
1.109 +void* SkTileGridNextDatum(SkTDArray<void*>** tileData, SkAutoSTArray<SkTileGrid::kStackAllocationTileCount, int>& tileIndices) {
1.110 + T* minVal = NULL;
1.111 + int tileCount = tileIndices.count();
1.112 + int minIndex = tileCount;
1.113 + int maxIndex = 0;
1.114 + // Find the next Datum; track where it's found so we reduce the size of the second loop.
1.115 + for (int tile = 0; tile < tileCount; ++tile) {
1.116 + int pos = tileIndices[tile];
1.117 + if (pos != SkTileGrid::kTileFinished) {
1.118 + T* candidate = (T*)(*tileData[tile])[pos];
1.119 + if (NULL == minVal || (*candidate) < (*minVal)) {
1.120 + minVal = candidate;
1.121 + minIndex = tile;
1.122 + maxIndex = tile;
1.123 + } else if (!((*minVal) < (*candidate))) {
1.124 + // We don't require operator==; if !(candidate<minVal) && !(minVal<candidate),
1.125 + // candidate==minVal and we have to add this tile to the range searched.
1.126 + maxIndex = tile;
1.127 + }
1.128 + }
1.129 + }
1.130 + // Increment indices past the next datum
1.131 + if (minVal != NULL) {
1.132 + for (int tile = minIndex; tile <= maxIndex; ++tile) {
1.133 + int pos = tileIndices[tile];
1.134 + if (pos != SkTileGrid::kTileFinished && (*tileData[tile])[pos] == minVal) {
1.135 + if (++(tileIndices[tile]) >= tileData[tile]->count()) {
1.136 + tileIndices[tile] = SkTileGrid::kTileFinished;
1.137 + }
1.138 + }
1.139 + }
1.140 + return minVal;
1.141 + }
1.142 + return NULL;
1.143 +}
1.144 +
1.145 +#endif
