Simple BlinkGC heap compaction.

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

+// 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.
+
+#include "platform/heap/SparseHeapBitmap.h"
+
+#include "wtf/PtrUtil.h"
+
+namespace blink {
+
+// Return the subtree/bitmap that covers the
+// [address, address + size) range.  Null if there is none.
+SparseHeapBitmap* SparseHeapBitmap::hasRange(Address address, size_t size) {
+  SparseHeapBitmap* bitmap = this;
+  while (bitmap) {
+    // Interval starts after, |m_right| handles.
+    if (address > bitmap->end()) {
+      bitmap = bitmap->m_right.get();
+      continue;
+    }
+    // Interval starts within, |bitmap| is included in the resulting range.
+    if (address >= bitmap->base())
+      break;
+
+    Address right = address + size - 1;
+    // Interval starts before, but intersects with |bitmap|'s range.
+    if (right >= bitmap->base())
+      break;
+
+    // Interval is before entirely, for |m_left| to handle.
+    bitmap = bitmap->m_left.get();
+  }
+  return bitmap;
+}
+
+bool SparseHeapBitmap::isSet(Address address) {
+  SparseHeapBitmap* bitmap = this;
+  while (bitmap) {
+    if (address > bitmap->end()) {
+      bitmap = bitmap->m_right.get();
+      continue;
+    }
+    if (address >= bitmap->base()) {
+      if (bitmap->m_bitmap)
+        return bitmap->m_bitmap->test(address - bitmap->base());
+      return bitmap->m_size == 1;
+    }
+    bitmap = bitmap->m_left.get();
+  }
+  return false;
+}
+
+void SparseHeapBitmap::add(Address address) {
+  // |address| is beyond the maximum that this SparseHeapBitmap node can
+  // encompass.
+  if (address >= maxEnd()) {
+    if (!m_right) {
+      m_right = SparseHeapBitmap::create(address);
+      return;
+    }
+    m_right->add(address);
+    return;
+  }
+  // Same on the other side.
+  if (address < minStart()) {
+    if (!m_left) {
+      m_left = SparseHeapBitmap::create(address);
+      return;
+    }
+    m_left->add(address);
+    return;
+  }
+  if (address == base())
+    return;
+  // |address| can be encompassed by |this| by expanding its size.
+  if (address > base()) {
+    if (!m_bitmap)
+      createBitmap();
+    m_bitmap->set(address - base());
+    return;
+  }
+  // Use |address| as the new base for this interval.
+  Address oldBase = swapBase(address);
+  createBitmap();
+  m_bitmap->set(oldBase - address);
+}
+
+void SparseHeapBitmap::createBitmap() {
+  DCHECK(!m_bitmap && m_size == 1);
+  m_bitmap = makeUnique<std::bitset<s_maxRange>>();
+  m_size = s_maxRange;
+  m_bitmap->set(0);
+}
+
+size_t SparseHeapBitmap::intervalCount() const {
+  size_t count = 1;
+  if (m_left)
+    count += m_left->intervalCount();
+  if (m_right)
+    count += m_right->intervalCount();
+  return count;
+}
+
+}  // namespace blink