Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(1300)

Side by Side Diff: src/core/SkRTree.h

Issue 617393004: BBHs: void* data -> unsigned data (Closed) Base URL: https://skia.googlesource.com/skia.git@master
Patch Set: The rest Created 6 years, 2 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
« no previous file with comments | « src/core/SkBBoxHierarchy.h ('k') | src/core/SkRTree.cpp » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
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 SkRTree_DEFINED 9 #ifndef SkRTree_DEFINED
10 #define SkRTree_DEFINED 10 #define SkRTree_DEFINED
(...skipping 45 matching lines...) Expand 10 before | Expand all | Expand 10 after
56 * better proportioned tiles of rectangles. 56 * better proportioned tiles of rectangles.
57 */ 57 */
58 static SkRTree* Create(int minChildren, int maxChildren, SkScalar aspectRati o = 1, 58 static SkRTree* Create(int minChildren, int maxChildren, SkScalar aspectRati o = 1,
59 bool orderWhenBulkLoading = true); 59 bool orderWhenBulkLoading = true);
60 virtual ~SkRTree(); 60 virtual ~SkRTree();
61 61
62 /** 62 /**
63 * Insert a node, consisting of bounds and a data value into the tree, if we don't immediately 63 * Insert a node, consisting of bounds and a data value into the tree, if we don't immediately
64 * need to use the tree; we may allow the insert to be deferred (this can al low us to bulk-load 64 * need to use the tree; we may allow the insert to be deferred (this can al low us to bulk-load
65 * a large batch of nodes at once, which tends to be faster and produce a be tter tree). 65 * a large batch of nodes at once, which tends to be faster and produce a be tter tree).
66 * @param data The data value 66 * @param opIndex The data value
67 * @param bounds The corresponding bounding box 67 * @param bounds The corresponding bounding box
68 * @param defer Can this insert be deferred? (this may be ignored) 68 * @param defer Can this insert be deferred? (this may be ignored)
69 */ 69 */
70 virtual void insert(void* data, const SkRect& bounds, bool defer = false) SK _OVERRIDE; 70 virtual void insert(unsigned opIndex, const SkRect& bounds, bool defer = fal se) SK_OVERRIDE;
71 71
72 /** 72 /**
73 * If any inserts have been deferred, this will add them into the tree 73 * If any inserts have been deferred, this will add them into the tree
74 */ 74 */
75 virtual void flushDeferredInserts() SK_OVERRIDE; 75 virtual void flushDeferredInserts() SK_OVERRIDE;
76 76
77 /** 77 /**
78 * Given a query rectangle, populates the passed-in array with the elements it intersects 78 * Given a query rectangle, populates the passed-in array with the elements it intersects
79 */ 79 */
80 virtual void search(const SkRect& query, SkTDArray<void*>* results) const SK _OVERRIDE; 80 virtual void search(const SkRect& query, SkTDArray<unsigned>* results) const SK_OVERRIDE;
81 81
82 virtual void clear() SK_OVERRIDE; 82 virtual void clear() SK_OVERRIDE;
83 bool isEmpty() const { return 0 == fCount; } 83 bool isEmpty() const { return 0 == fCount; }
84 84
85 /** 85 /**
86 * Gets the depth of the tree structure 86 * Gets the depth of the tree structure
87 */ 87 */
88 virtual int getDepth() const SK_OVERRIDE { 88 virtual int getDepth() const SK_OVERRIDE {
89 return this->isEmpty() ? 0 : fRoot.fChild.subtree->fLevel + 1; 89 return this->isEmpty() ? 0 : fRoot.fChild.subtree->fLevel + 1;
90 } 90 }
91 91
92 /** 92 /**
93 * This gets the insertion count (rather than the node count) 93 * This gets the insertion count (rather than the node count)
94 */ 94 */
95 virtual int getCount() const SK_OVERRIDE { return fCount; } 95 virtual int getCount() const SK_OVERRIDE { return fCount; }
96 96
97 virtual void rewindInserts() SK_OVERRIDE;
98
99 private: 97 private:
100 98
101 struct Node; 99 struct Node;
102 100
103 /** 101 /**
104 * A branch of the tree, this may contain a pointer to another interior node , or a data value 102 * A branch of the tree, this may contain a pointer to another interior node , or a data value
105 */ 103 */
106 struct Branch { 104 struct Branch {
107 union { 105 union {
108 Node* subtree; 106 Node* subtree;
109 void* data; 107 unsigned opIndex;
110 } fChild; 108 } fChild;
111 SkIRect fBounds; 109 SkIRect fBounds;
112 }; 110 };
113 111
114 /** 112 /**
115 * A node in the tree, has between fMinChildren and fMaxChildren (the root i s a special case) 113 * A node in the tree, has between fMinChildren and fMaxChildren (the root i s a special case)
116 */ 114 */
117 struct Node { 115 struct Node {
118 uint16_t fNumChildren; 116 uint16_t fNumChildren;
119 uint16_t fLevel; 117 uint16_t fLevel;
(...skipping 35 matching lines...) Expand 10 before | Expand all | Expand 10 after
155 153
156 /** 154 /**
157 * Recursively descend the tree to find an insertion position for 'branch', updates 155 * Recursively descend the tree to find an insertion position for 'branch', updates
158 * bounding boxes on the way up. 156 * bounding boxes on the way up.
159 */ 157 */
160 Branch* insert(Node* root, Branch* branch, uint16_t level = 0); 158 Branch* insert(Node* root, Branch* branch, uint16_t level = 0);
161 159
162 int chooseSubtree(Node* root, Branch* branch); 160 int chooseSubtree(Node* root, Branch* branch);
163 SkIRect computeBounds(Node* n); 161 SkIRect computeBounds(Node* n);
164 int distributeChildren(Branch* children); 162 int distributeChildren(Branch* children);
165 void search(Node* root, const SkIRect query, SkTDArray<void*>* results) cons t; 163 void search(Node* root, const SkIRect query, SkTDArray<unsigned>* results) c onst;
166 164
167 /** 165 /**
168 * This performs a bottom-up bulk load using the STR (sort-tile-recursive) a lgorithm, this 166 * This performs a bottom-up bulk load using the STR (sort-tile-recursive) a lgorithm, this
169 * seems to generally produce better, more consistent trees at significantly lower cost than 167 * seems to generally produce better, more consistent trees at significantly lower cost than
170 * repeated insertions. 168 * repeated insertions.
171 * 169 *
172 * This consumes the input array. 170 * This consumes the input array.
173 * 171 *
174 * TODO: Experiment with other bulk-load algorithms (in particular the Hilbe rt pack variant, 172 * TODO: Experiment with other bulk-load algorithms (in particular the Hilbe rt pack variant,
175 * which groups rects by position on the Hilbert curve, is probably worth a look). There also 173 * which groups rects by position on the Hilbert curve, is probably worth a look). There also
(...skipping 16 matching lines...) Expand all
192 SkTDArray<Branch> fDeferredInserts; 190 SkTDArray<Branch> fDeferredInserts;
193 SkScalar fAspectRatio; 191 SkScalar fAspectRatio;
194 bool fSortWhenBulkLoading; 192 bool fSortWhenBulkLoading;
195 193
196 Node* allocateNode(uint16_t level); 194 Node* allocateNode(uint16_t level);
197 195
198 typedef SkBBoxHierarchy INHERITED; 196 typedef SkBBoxHierarchy INHERITED;
199 }; 197 };
200 198
201 #endif 199 #endif
OLDNEW
« no previous file with comments | « src/core/SkBBoxHierarchy.h ('k') | src/core/SkRTree.cpp » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698