gfx/skia/trunk/src/core/SkQuadTree.h@129ffea94266
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.
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 */
8 #ifndef SkQuadTree_DEFINED
9 #define SkQuadTree_DEFINED
11 #include "SkRect.h"
12 #include "SkTDArray.h"
13 #include "SkBBoxHierarchy.h"
14 #include "SkTInternalSList.h"
15 #include "SkTObjectPool.h"
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)
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);
37 virtual ~SkQuadTree();
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;
49 /**
50 * If any inserts have been deferred, this will add them into the tree
51 */
52 virtual void flushDeferredInserts() SK_OVERRIDE;
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;
59 virtual void clear() SK_OVERRIDE;
61 /**
62 * Gets the depth of the tree structure
63 */
64 virtual int getDepth() const SK_OVERRIDE;
66 /**
67 * This gets the insertion count (rather than the node count)
68 */
69 virtual int getCount() const SK_OVERRIDE { return fEntryCount; }
71 virtual void rewindInserts() SK_OVERRIDE;
73 private:
74 struct Entry {
75 Entry() : fData(NULL) {}
76 SkIRect fBounds;
77 void* fData;
78 SK_DECLARE_INTERNAL_SLIST_INTERFACE(Entry);
79 };
81 static const int kChildCount = 4;
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 };
96 SkTObjectPool<Entry> fEntryPool;
97 SkTObjectPool<Node> fNodePool;
98 int fEntryCount;
99 Node* fRoot;
100 SkTInternalSList<Entry> fDeferred;
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;
108 typedef SkBBoxHierarchy INHERITED;
109 };
111 #endif
