The Tor Browser / file comparison
comparison: gfx/skia/trunk/src/core/SkQuadTree.h
gfx/skia/trunk/src/core/SkQuadTree.h
- branch
- TOR_BUG_3246
- changeset 6
- 8bccb770b82d
equal
deleted
inserted
replaced
| -1:000000000000 | 0:73af84797567 |
|---|---|
| 1 /* | |
| 2 * Copyright 2014 Google Inc. | |
| 3 * | |
| 4 * Use of this source code is governed by a BSD-style license that can be | |
| 5 * found in the LICENSE file. | |
| 6 */ | |
| 7 | |
| 8 #ifndef SkQuadTree_DEFINED | |
| 9 #define SkQuadTree_DEFINED | |
| 10 | |
| 11 #include "SkRect.h" | |
| 12 #include "SkTDArray.h" | |
| 13 #include "SkBBoxHierarchy.h" | |
| 14 #include "SkTInternalSList.h" | |
| 15 #include "SkTObjectPool.h" | |
| 16 | |
| 17 /** | |
| 18 * A QuadTree implementation. In short, it is a tree containing a hierarchy of bounding rectangles | |
| 19 * in which each internal node has exactly four children. | |
| 20 * | |
| 21 * For more details see: | |
| 22 * | |
| 23 * http://en.wikipedia.org/wiki/Quadtree | |
| 24 */ | |
| 25 class SkQuadTree : public SkBBoxHierarchy { | |
| 26 public: | |
| 27 SK_DECLARE_INST_COUNT(SkQuadTree) | |
| 28 | |
| 29 /** | |
| 30 * Quad tree constructor. | |
| 31 * @param bounds The bounding box for the root of the quad tree. | |
| 32 * giving the quad tree bounds that fall outside the root | |
| 33 * bounds may result in pathological but correct behavior. | |
| 34 */ | |
| 35 SkQuadTree(const SkIRect& bounds); | |
| 36 | |
| 37 virtual ~SkQuadTree(); | |
| 38 | |
| 39 /** | |
| 40 * Insert a node, consisting of bounds and a data value into the tree, if we don't immediately | |
| 41 * need to use the tree; we may allow the insert to be deferred (this can allow us to bulk-load | |
| 42 * a large batch of nodes at once, which tends to be faster and produce a better tree). | |
| 43 * @param data The data value | |
| 44 * @param bounds The corresponding bounding box | |
| 45 * @param defer Can this insert be deferred? (this may be ignored) | |
| 46 */ | |
| 47 virtual void insert(void* data, const SkIRect& bounds, bool defer = false) SK_OVERRIDE; | |
| 48 | |
| 49 /** | |
| 50 * If any inserts have been deferred, this will add them into the tree | |
| 51 */ | |
| 52 virtual void flushDeferredInserts() SK_OVERRIDE; | |
| 53 | |
| 54 /** | |
| 55 * Given a query rectangle, populates the passed-in array with the elements it intersects | |
| 56 */ | |
| 57 virtual void search(const SkIRect& query, SkTDArray<void*>* results) SK_OVERRIDE; | |
| 58 | |
| 59 virtual void clear() SK_OVERRIDE; | |
| 60 | |
| 61 /** | |
| 62 * Gets the depth of the tree structure | |
| 63 */ | |
| 64 virtual int getDepth() const SK_OVERRIDE; | |
| 65 | |
| 66 /** | |
| 67 * This gets the insertion count (rather than the node count) | |
| 68 */ | |
| 69 virtual int getCount() const SK_OVERRIDE { return fEntryCount; } | |
| 70 | |
| 71 virtual void rewindInserts() SK_OVERRIDE; | |
| 72 | |
| 73 private: | |
| 74 struct Entry { | |
| 75 Entry() : fData(NULL) {} | |
| 76 SkIRect fBounds; | |
| 77 void* fData; | |
| 78 SK_DECLARE_INTERNAL_SLIST_INTERFACE(Entry); | |
| 79 }; | |
| 80 | |
| 81 static const int kChildCount = 4; | |
| 82 | |
| 83 struct Node { | |
| 84 Node() { | |
| 85 for (int index=0; index<kChildCount; ++index) { | |
| 86 fChildren[index] = NULL; | |
| 87 } | |
| 88 } | |
| 89 SkTInternalSList<Entry> fEntries; | |
| 90 SkIRect fBounds; | |
| 91 SkIPoint fSplitPoint; // Only valid if the node has children. | |
| 92 Node* fChildren[kChildCount]; | |
| 93 SK_DECLARE_INTERNAL_SLIST_ADAPTER(Node, fChildren[0]); | |
| 94 }; | |
| 95 | |
| 96 SkTObjectPool<Entry> fEntryPool; | |
| 97 SkTObjectPool<Node> fNodePool; | |
| 98 int fEntryCount; | |
| 99 Node* fRoot; | |
| 100 SkTInternalSList<Entry> fDeferred; | |
| 101 | |
| 102 Node* pickChild(Node* node, const SkIRect& bounds) const; | |
| 103 void insert(Node* node, Entry* entry); | |
| 104 void search(Node* node, const SkIRect& query, SkTDArray<void*>* results) const; | |
| 105 void clear(Node* node); | |
| 106 int getDepth(Node* node) const; | |
| 107 | |
| 108 typedef SkBBoxHierarchy INHERITED; | |
| 109 }; | |
| 110 | |
| 111 #endif |
