1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
|
// Copyright 2016 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#include "third_party/blink/renderer/platform/heap/sparse_heap_bitmap.h"
#include "third_party/blink/renderer/platform/heap/heap.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) {
DCHECK(!(reinterpret_cast<uintptr_t>(address) & kPointerAlignmentMask));
SparseHeapBitmap* bitmap = this;
while (bitmap) {
// Interval starts after, |m_right| handles.
if (address > bitmap->end()) {
bitmap = bitmap->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->left_.get();
}
return bitmap;
}
bool SparseHeapBitmap::IsSet(Address address) {
DCHECK(!(reinterpret_cast<uintptr_t>(address) & kPointerAlignmentMask));
SparseHeapBitmap* bitmap = this;
while (bitmap) {
if (address > bitmap->end()) {
bitmap = bitmap->right_.get();
continue;
}
if (address >= bitmap->Base()) {
if (bitmap->bitmap_) {
return bitmap->bitmap_->test((address - bitmap->Base()) >>
kPointerAlignmentInBits);
}
DCHECK(address == bitmap->Base());
DCHECK_EQ(bitmap->size(), 1u);
return true;
}
bitmap = bitmap->left_.get();
}
return false;
}
void SparseHeapBitmap::Add(Address address) {
DCHECK(!(reinterpret_cast<uintptr_t>(address) & kPointerAlignmentMask));
// |address| is beyond the maximum that this SparseHeapBitmap node can
// encompass.
if (address >= MaxEnd()) {
if (!right_) {
right_ = SparseHeapBitmap::Create(address);
return;
}
right_->Add(address);
return;
}
// Same on the other side.
if (address < MinStart()) {
if (!left_) {
left_ = SparseHeapBitmap::Create(address);
return;
}
left_->Add(address);
return;
}
if (address == Base())
return;
// |address| can be encompassed by |this| by expanding its size.
if (address > Base()) {
if (!bitmap_)
CreateBitmap();
bitmap_->set((address - Base()) >> kPointerAlignmentInBits);
return;
}
// Use |address| as the new base for this interval.
Address old_base = SwapBase(address);
CreateBitmap();
bitmap_->set((old_base - address) >> kPointerAlignmentInBits);
}
void SparseHeapBitmap::CreateBitmap() {
DCHECK(!bitmap_ && size() == 1);
bitmap_ = std::make_unique<std::bitset<kBitmapChunkSize>>();
size_ = kBitmapChunkRange;
bitmap_->set(0);
}
size_t SparseHeapBitmap::IntervalCount() const {
size_t count = 1;
if (left_)
count += left_->IntervalCount();
if (right_)
count += right_->IntervalCount();
return count;
}
} // namespace blink
|
