Simple BlinkGC heap compaction.

third_party/WebKit/Source/platform/heap/SparseHeapBitmap.h

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..bbff3f82422b3231303f7309faa0f3c00fd58f45
--- /dev/null
+++ b/third_party/WebKit/Source/platform/heap/SparseHeapBitmap.h
@@ -0,0 +1,112 @@
+// 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 "wtf/PtrUtil.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 wrapUnique(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