DXR is a code search and navigation tool aimed at making sense of large projects. It supports full-text and regex searches as well as structural queries.

Implementation

Mercurial (d8847129d134)

VCS Links

Line Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142

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

#ifndef SkTileGrid_DEFINED
#define SkTileGrid_DEFINED

#include "SkBBHFactory.h"
#include "SkBBoxHierarchy.h"
#include "SkPictureStateTree.h"

/**
 * Subclass of SkBBoxHierarchy that stores elements in buckets that correspond
 * to tile regions, disposed in a regular grid.  This is useful when the tile
 * structure that will be use in search() calls is known prior to insertion.
 * Calls to search will return in constant time.
 *
 * Note: Current implementation of search() only supports looking-up regions
 * that are an exact match to a single tile.  Implementation could be augmented
 * to support arbitrary rectangles, but performance would be sub-optimal.
 */
class SkTileGrid : public SkBBoxHierarchy {
public:
    enum {
        // Number of tiles for which data is allocated on the stack in
        // SkTileGrid::search. If malloc becomes a bottleneck, we may consider
        // increasing this number. Typical large web page, say 2k x 16k, would
        // require 512 tiles of size 256 x 256 pixels.
        kStackAllocationTileCount = 1024
    };

    typedef void* (*SkTileGridNextDatumFunctionPtr)(SkTDArray<void*>** tileData, SkAutoSTArray<kStackAllocationTileCount, int>& tileIndices);

    SkTileGrid(int xTileCount, int yTileCount, const SkTileGridFactory::TileGridInfo& info,
        SkTileGridNextDatumFunctionPtr nextDatumFunction);

    virtual ~SkTileGrid();

    /**
     * Insert a data pointer and corresponding bounding box
     * @param data The data pointer, may be NULL
     * @param bounds The bounding box, should not be empty
     * @param defer Ignored, TileArray does not defer insertions
     */
    virtual void insert(void* data, const SkIRect& bounds, bool) SK_OVERRIDE;

    virtual void flushDeferredInserts() SK_OVERRIDE {};

    /**
     * Populate 'results' with data pointers corresponding to bounding boxes that intersect 'query'
     * The query argument is expected to be an exact match to a tile of the grid
     */
    virtual void search(const SkIRect& query, SkTDArray<void*>* results) SK_OVERRIDE;

    virtual void clear() SK_OVERRIDE;

    /**
     * Gets the number of insertions
     */
    virtual int getCount() const SK_OVERRIDE;

    virtual int getDepth() const SK_OVERRIDE { return -1; }

    virtual void rewindInserts() SK_OVERRIDE;

    // Used by search() and in SkTileGridHelper implementations
    enum {
        kTileFinished = -1,
    };

    int tileCount(int x, int y);  // For testing only.

private:
    SkTDArray<void*>& tile(int x, int y);

    int fXTileCount, fYTileCount, fTileCount;
    SkTileGridFactory::TileGridInfo fInfo;
    SkTDArray<void*>* fTileData;
    int fInsertionCount;
    SkIRect fGridBounds;
    SkTileGridNextDatumFunctionPtr fNextDatumFunction;

    typedef SkBBoxHierarchy INHERITED;
};

/**
 * Generic implementation for SkTileGridNextDatumFunctionPtr. user code may instantiate
 * this template to get a valid SkTileGridNextDatumFunction implementation
 *
 * Returns the next element of tileData[i][tileIndices[i]] for all i and advances
 * tileIndices[] past them. The order in which data are returned by successive
 * calls to this method must reflect the order in which the were originally
 * recorded into the tile grid.
 *
 * \param tileData array of pointers to arrays of tile data
 * \param tileIndices per-tile data indices, indices are incremented for tiles that contain
 *     the next datum.
 * \tparam T a type to which it is safe to cast a datum and that has an operator <
 *     such that 'a < b' is true if 'a' was inserted into the tile grid before 'b'.
 */
template <typename T>
void* SkTileGridNextDatum(SkTDArray<void*>** tileData, SkAutoSTArray<SkTileGrid::kStackAllocationTileCount, int>& tileIndices) {
    T* 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) {
            T* candidate = (T*)(*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;
}

#endif