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