Index: third_party/WebKit/Source/platform/heap/SparseHeapBitmap.h |
diff --git a/third_party/WebKit/Source/platform/heap/SparseHeapBitmap.h b/third_party/WebKit/Source/platform/heap/SparseHeapBitmap.h |
new file mode 100644 |
index 0000000000000000000000000000000000000000..e93863384c6fbc15298e7d32474ccee7ee3bbedc |
--- /dev/null |
+++ b/third_party/WebKit/Source/platform/heap/SparseHeapBitmap.h |
@@ -0,0 +1,111 @@ |
+// Copyright 2016 Opera Software AS. All rights reserved. |
+// Use of this source code is governed by a BSD-style license that can be |
+// found in the LICENSE file. |
+ |
+#ifndef SparseHeapBitmap_h |
+#define SparseHeapBitmap_h |
+ |
+#include "platform/heap/BlinkGC.h" |
+#include <bitset> |
+#include <memory> |
+ |
+namespace blink { |
+ |
+// A sparse bitmap of heap addresses where the (very few) addresses that are |
+// set are likely to be in small clusters. The abstraction is tailored to |
+// support heap compaction, assuming the following: |
+// |
+// - Addresses will be bitmap-marked from lower to higher addresses. |
+// - Bitmap lookups are performed for each object that is compacted |
+// and moved to some new location, supplying the (base, size) |
+// pair of the object's heap allocation. |
+// - If the sparse bitmap has any marked addresses in that range, it |
+// returns a sub-bitmap that can be quickly iterated over to check which |
+// addresses within the range are actually set. |
+// - The bitmap is needed to support something that is very rarely done |
+// by the current Blink codebase, which is to have nested collection |
+// part objects. Consequently, it is safe to assume sparseness. |
+// |
+// Support the above by having a sparse bitmap organized as a binary |
+// tree with nodes covering fixed size ranges via a simple bitmap/set. |
+// That is, each SparseHeapBitmap node will contain a bitmap/set for |
+// some fixed size range, along with pointers to SparseHeapBitmaps |
+// for addresses on each side its range. |
+// |
+// This bitmap tree isn't kept balanced across the Address additions |
+// made. |
+class PLATFORM_EXPORT SparseHeapBitmap { |
+ public: |
+ static std::unique_ptr<SparseHeapBitmap> create(Address base) { |
+ return std::unique_ptr<SparseHeapBitmap>(new SparseHeapBitmap(base)); |
+ } |
+ |
+ ~SparseHeapBitmap() {} |
+ |
+ // Return the sparse bitmap subtree that covers the [address, address + size) |
+ // range, if any. |
+ // |
+ // The returned SparseHeapBitmap can be used to quickly lookup what |
+ // addresses in that range are set or not; see |isSet()|. |
+ SparseHeapBitmap* hasRange(Address, size_t); |
+ |
+ // True iff |address| is set for this SparseHeapBitmap tree. |
+ bool isSet(Address); |
+ |
+ // Mark |address| as present/set. |
+ void add(Address); |
+ |
+ // Represent ranges in 0x100 chunks; a SparseHeapBitmap either contains a |
+ // single Address or a bitmap recording the mapping for |
+ // [base, base + s_maxRange). |
+ static const size_t s_maxRange = 0x100; |
+ |
+ // Return the number of nodes; needed debugging info only. |
+ size_t intervalCount() const; |
+ |
+ private: |
+ SparseHeapBitmap(Address base) : m_base(base), m_size(1) {} |
+ |
+ Address base() const { return m_base; } |
+ size_t size() const { return m_size; } |
+ Address end() const { return m_base + (m_size - 1); } |
+ |
+ Address maxEnd() const { return m_base + s_maxRange; } |
+ |
+ Address minStart() const { |
+ // If this bitmap node represents the sparse [m_base, s_maxRange) range, |
+ // do not allow it to be "left extended" as that would entail having |
+ // to shift down the contents of the std::bitset somehow. |
+ // |
+ // This shouldn't be a real problem as any clusters of set addresses |
+ // will be marked while iterating from lower to higher addresses, hence |
+ // "left extension" are unlikely to be common. |
+ if (m_bitmap) |
+ return m_base; |
+ return (m_base > reinterpret_cast<Address>(s_maxRange)) |
+ ? (m_base - s_maxRange + 1) |
+ : nullptr; |
+ } |
+ |
+ Address swapBase(Address address) { |
+ Address oldBase = m_base; |
+ m_base = address; |
+ return oldBase; |
+ } |
+ |
+ void createBitmap(); |
+ |
+ Address m_base; |
+ // Either 1 or |s_maxRange|. |
+ size_t m_size; |
+ |
+ // If non-null, contains a bitmap for addresses within [m_base, m_size) |
+ std::unique_ptr<std::bitset<s_maxRange>> m_bitmap; |
+ |
+ std::unique_ptr<SparseHeapBitmap> m_left; |
+ std::unique_ptr<SparseHeapBitmap> m_right; |
+}; |
+ |
+} // namespace blink |
+ |
+#endif // SparseHeapBitmap_h |