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

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

Issue 1300163002: unsigned -> int for counts and indices in picture-related code (Closed) Base URL: https://skia.googlesource.com/skia.git@master
Patch Set: (C) Created 5 years, 4 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/SkLayerInfo.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 13 matching lines...) Expand all
24 * which groups rects by position on the Hilbert curve, is probably worth a look ). There also 24 * which groups rects by position on the Hilbert curve, is probably worth a look ). There also
25 * exist top-down bulk load variants (VAMSplit, TopDownGreedy, etc). 25 * exist top-down bulk load variants (VAMSplit, TopDownGreedy, etc).
26 * 26 *
27 * For more details see: 27 * For more details see:
28 * 28 *
29 * Beckmann, N.; Kriegel, H. P.; Schneider, R.; Seeger, B. (1990). "The R*-tree : 29 * Beckmann, N.; Kriegel, H. P.; Schneider, R.; Seeger, B. (1990). "The R*-tree :
30 * an efficient and robust access method for points and rectangles" 30 * an efficient and robust access method for points and rectangles"
31 */ 31 */
32 class SkRTree : public SkBBoxHierarchy { 32 class SkRTree : public SkBBoxHierarchy {
33 public: 33 public:
34 34
35 35
36 /** 36 /**
37 * If you have some prior information about the distribution of bounds you'r e expecting, you 37 * If you have some prior information about the distribution of bounds you'r e expecting, you
38 * can provide an optional aspect ratio parameter. This allows the bulk-load algorithm to 38 * can provide an optional aspect ratio parameter. This allows the bulk-load algorithm to
39 * create better proportioned tiles of rectangles. 39 * create better proportioned tiles of rectangles.
40 */ 40 */
41 explicit SkRTree(SkScalar aspectRatio = 1); 41 explicit SkRTree(SkScalar aspectRatio = 1);
42 virtual ~SkRTree() {} 42 virtual ~SkRTree() {}
43 43
44 void insert(const SkRect[], int N) override; 44 void insert(const SkRect[], int N) override;
45 void search(const SkRect& query, SkTDArray<unsigned>* results) const overrid e; 45 void search(const SkRect& query, SkTDArray<int>* results) const override;
46 size_t bytesUsed() const override; 46 size_t bytesUsed() const override;
47 47
48 // Methods and constants below here are only public for tests. 48 // Methods and constants below here are only public for tests.
49 49
50 // Return the depth of the tree structure. 50 // Return the depth of the tree structure.
51 int getDepth() const { return fCount ? fRoot.fSubtree->fLevel + 1 : 0; } 51 int getDepth() const { return fCount ? fRoot.fSubtree->fLevel + 1 : 0; }
52 // Insertion count (not overall node count, which may be greater). 52 // Insertion count (not overall node count, which may be greater).
53 int getCount() const { return fCount; } 53 int getCount() const { return fCount; }
54 54
55 // Get the root bound. 55 // Get the root bound.
56 SkRect getRootBound() const override; 56 SkRect getRootBound() const override;
57 57
58 // These values were empirically determined to produce reasonable performanc e in most cases. 58 // These values were empirically determined to produce reasonable performanc e in most cases.
59 static const int kMinChildren = 6, 59 static const int kMinChildren = 6,
60 kMaxChildren = 11; 60 kMaxChildren = 11;
61 61
62 private: 62 private:
63 struct Node; 63 struct Node;
64 64
65 struct Branch { 65 struct Branch {
66 union { 66 union {
67 Node* fSubtree; 67 Node* fSubtree;
68 unsigned fOpIndex; 68 int fOpIndex;
69 }; 69 };
70 SkRect fBounds; 70 SkRect fBounds;
71 }; 71 };
72 72
73 struct Node { 73 struct Node {
74 uint16_t fNumChildren; 74 uint16_t fNumChildren;
75 uint16_t fLevel; 75 uint16_t fLevel;
76 Branch fChildren[kMaxChildren]; 76 Branch fChildren[kMaxChildren];
77 }; 77 };
78 78
79 void search(Node* root, const SkRect& query, SkTDArray<unsigned>* results) c onst; 79 void search(Node* root, const SkRect& query, SkTDArray<int>* results) const;
80 80
81 // Consumes the input array. 81 // Consumes the input array.
82 Branch bulkLoad(SkTDArray<Branch>* branches, int level = 0); 82 Branch bulkLoad(SkTDArray<Branch>* branches, int level = 0);
83 83
84 // How many times will bulkLoad() call allocateNodeAtLevel()? 84 // How many times will bulkLoad() call allocateNodeAtLevel()?
85 static int CountNodes(int branches, SkScalar aspectRatio); 85 static int CountNodes(int branches, SkScalar aspectRatio);
86 86
87 Node* allocateNodeAtLevel(uint16_t level); 87 Node* allocateNodeAtLevel(uint16_t level);
88 88
89 // This is the count of data elements (rather than total nodes in the tree) 89 // This is the count of data elements (rather than total nodes in the tree)
90 int fCount; 90 int fCount;
91 SkScalar fAspectRatio; 91 SkScalar fAspectRatio;
92 Branch fRoot; 92 Branch fRoot;
93 SkTDArray<Node> fNodes; 93 SkTDArray<Node> fNodes;
94 94
95 typedef SkBBoxHierarchy INHERITED; 95 typedef SkBBoxHierarchy INHERITED;
96 }; 96 };
97 97
98 #endif 98 #endif
OLDNEW
« no previous file with comments | « src/core/SkLayerInfo.h ('k') | src/core/SkRTree.cpp » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698