OLD | NEW |
1 | 1 |
2 /* | 2 /* |
3 * Copyright 2012 Google Inc. | 3 * Copyright 2012 Google Inc. |
4 * | 4 * |
5 * Use of this source code is governed by a BSD-style license that can be | 5 * Use of this source code is governed by a BSD-style license that can be |
6 * found in the LICENSE file. | 6 * found in the LICENSE file. |
7 */ | 7 */ |
8 | 8 |
9 #ifndef SkTileGrid_DEFINED | 9 #ifndef SkTileGrid_DEFINED |
10 #define SkTileGrid_DEFINED | 10 #define SkTileGrid_DEFINED |
11 | 11 |
12 #include "SkBBoxHierarchy.h" | 12 #include "SkBBoxHierarchy.h" |
13 #include "SkPictureStateTree.h" | 13 #include "SkPictureStateTree.h" |
14 #include "SkTileGridPicture.h" // for TileGridInfo | 14 #include "SkTileGridPicture.h" // for TileGridInfo |
15 | 15 |
16 /** | 16 /** |
17 * Subclass of SkBBoxHierarchy that stores elements in buckets that correspond | 17 * Subclass of SkBBoxHierarchy that stores elements in buckets that correspond |
18 * to tile regions, disposed in a regular grid. This is useful when the tile | 18 * to tile regions, disposed in a regular grid. This is useful when the tile |
19 * structure that will be use in search() calls is known prior to insertion. | 19 * structure that will be use in search() calls is known prior to insertion. |
20 * Calls to search will return in constant time. | 20 * Calls to search will return in constant time. |
21 * | 21 * |
22 * Note: Current implementation of search() only supports looking-up regions | 22 * Note: Current implementation of search() only supports looking-up regions |
23 * that are an exact match to a single tile. Implementation could be augmented | 23 * that are an exact match to a single tile. Implementation could be augmented |
24 * to support arbitrary rectangles, but performance would be sub-optimal. | 24 * to support arbitrary rectangles, but performance would be sub-optimal. |
25 */ | 25 */ |
26 class SkTileGrid : public SkBBoxHierarchy { | 26 class SkTileGrid : public SkBBoxHierarchy { |
27 public: | 27 public: |
28 typedef void* (*SkTileGridNextDatumFunctionPtr)(SkTDArray<void*>** tileData,
SkTDArray<int>& tileIndices); | 28 enum { |
| 29 // Number of tiles for which data is allocated on the stack in |
| 30 // SkTileGrid::search. If malloc becomes a bottleneck, we may consider |
| 31 // increasing this number. Typical large web page, say 2k x 16k, would |
| 32 // require 512 tiles of size 256 x 256 pixels. |
| 33 kStackAllocationTileCount = 1024 |
| 34 }; |
| 35 |
| 36 typedef void* (*SkTileGridNextDatumFunctionPtr)(SkTDArray<void*>** tileData,
SkAutoSTArray<kStackAllocationTileCount, int>& tileIndices); |
29 | 37 |
30 SkTileGrid(int xTileCount, int yTileCount, const SkTileGridPicture::TileGrid
Info& info, | 38 SkTileGrid(int xTileCount, int yTileCount, const SkTileGridPicture::TileGrid
Info& info, |
31 SkTileGridNextDatumFunctionPtr nextDatumFunction); | 39 SkTileGridNextDatumFunctionPtr nextDatumFunction); |
32 | 40 |
33 virtual ~SkTileGrid(); | 41 virtual ~SkTileGrid(); |
34 | 42 |
35 /** | 43 /** |
36 * Insert a data pointer and corresponding bounding box | 44 * Insert a data pointer and corresponding bounding box |
37 * @param data The data pointer, may be NULL | 45 * @param data The data pointer, may be NULL |
38 * @param bounds The bounding box, should not be empty | 46 * @param bounds The bounding box, should not be empty |
(...skipping 45 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
84 * calls to this method must reflect the order in which the were originally | 92 * calls to this method must reflect the order in which the were originally |
85 * recorded into the tile grid. | 93 * recorded into the tile grid. |
86 * | 94 * |
87 * \param tileData array of pointers to arrays of tile data | 95 * \param tileData array of pointers to arrays of tile data |
88 * \param tileIndices per-tile data indices, indices are incremented for tiles t
hat contain | 96 * \param tileIndices per-tile data indices, indices are incremented for tiles t
hat contain |
89 * the next datum. | 97 * the next datum. |
90 * \tparam T a type to which it is safe to cast a datum and that has an operator
< | 98 * \tparam T a type to which it is safe to cast a datum and that has an operator
< |
91 * such that 'a < b' is true if 'a' was inserted into the tile grid before '
b'. | 99 * such that 'a < b' is true if 'a' was inserted into the tile grid before '
b'. |
92 */ | 100 */ |
93 template <typename T> | 101 template <typename T> |
94 void* SkTileGridNextDatum(SkTDArray<void*>** tileData, SkTDArray<int>& tileIndic
es) { | 102 void* SkTileGridNextDatum(SkTDArray<void*>** tileData, SkAutoSTArray<SkTileGrid:
:kStackAllocationTileCount, int>& tileIndices) { |
95 T* minVal = NULL; | 103 T* minVal = NULL; |
96 int tileCount = tileIndices.count(); | 104 int tileCount = tileIndices.count(); |
97 int minIndex = tileCount; | 105 int minIndex = tileCount; |
98 int maxIndex = 0; | 106 int maxIndex = 0; |
99 // Find the next Datum; track where it's found so we reduce the size of the
second loop. | 107 // Find the next Datum; track where it's found so we reduce the size of the
second loop. |
100 for (int tile = 0; tile < tileCount; ++tile) { | 108 for (int tile = 0; tile < tileCount; ++tile) { |
101 int pos = tileIndices[tile]; | 109 int pos = tileIndices[tile]; |
102 if (pos != SkTileGrid::kTileFinished) { | 110 if (pos != SkTileGrid::kTileFinished) { |
103 T* candidate = (T*)(*tileData[tile])[pos]; | 111 T* candidate = (T*)(*tileData[tile])[pos]; |
104 if (NULL == minVal || (*candidate) < (*minVal)) { | 112 if (NULL == minVal || (*candidate) < (*minVal)) { |
(...skipping 16 matching lines...) Expand all Loading... |
121 tileIndices[tile] = SkTileGrid::kTileFinished; | 129 tileIndices[tile] = SkTileGrid::kTileFinished; |
122 } | 130 } |
123 } | 131 } |
124 } | 132 } |
125 return minVal; | 133 return minVal; |
126 } | 134 } |
127 return NULL; | 135 return NULL; |
128 } | 136 } |
129 | 137 |
130 #endif | 138 #endif |
OLD | NEW |