1 // Copyright 2018 the V8 project authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include "src/heap/slot-set.h"
6
7 namespace v8 {
8 namespace internal {
9
~TypedSlots()10 TypedSlots::~TypedSlots() {
11 Chunk* chunk = head_;
12 while (chunk != nullptr) {
13 Chunk* next = chunk->next;
14 delete chunk;
15 chunk = next;
16 }
17 head_ = nullptr;
18 tail_ = nullptr;
19 }
20
Insert(SlotType type,uint32_t offset)21 void TypedSlots::Insert(SlotType type, uint32_t offset) {
22 TypedSlot slot = {TypeField::encode(type) | OffsetField::encode(offset)};
23 Chunk* chunk = EnsureChunk();
24 DCHECK_LT(chunk->buffer.size(), chunk->buffer.capacity());
25 chunk->buffer.push_back(slot);
26 }
27
Merge(TypedSlots * other)28 void TypedSlots::Merge(TypedSlots* other) {
29 if (other->head_ == nullptr) {
30 return;
31 }
32 if (head_ == nullptr) {
33 head_ = other->head_;
34 tail_ = other->tail_;
35 } else {
36 tail_->next = other->head_;
37 tail_ = other->tail_;
38 }
39 other->head_ = nullptr;
40 other->tail_ = nullptr;
41 }
42
EnsureChunk()43 TypedSlots::Chunk* TypedSlots::EnsureChunk() {
44 if (!head_) {
45 head_ = tail_ = NewChunk(nullptr, kInitialBufferSize);
46 }
47 if (head_->buffer.size() == head_->buffer.capacity()) {
48 head_ = NewChunk(head_, NextCapacity(head_->buffer.capacity()));
49 }
50 return head_;
51 }
52
NewChunk(Chunk * next,size_t capacity)53 TypedSlots::Chunk* TypedSlots::NewChunk(Chunk* next, size_t capacity) {
54 Chunk* chunk = new Chunk;
55 chunk->next = next;
56 chunk->buffer.reserve(capacity);
57 DCHECK_EQ(chunk->buffer.capacity(), capacity);
58 return chunk;
59 }
60
ClearInvalidSlots(const std::map<uint32_t,uint32_t> & invalid_ranges)61 void TypedSlotSet::ClearInvalidSlots(
62 const std::map<uint32_t, uint32_t>& invalid_ranges) {
63 Chunk* chunk = LoadHead();
64 while (chunk != nullptr) {
65 for (TypedSlot& slot : chunk->buffer) {
66 SlotType type = TypeField::decode(slot.type_and_offset);
67 if (type == CLEARED_SLOT) continue;
68 uint32_t offset = OffsetField::decode(slot.type_and_offset);
69 std::map<uint32_t, uint32_t>::const_iterator upper_bound =
70 invalid_ranges.upper_bound(offset);
71 if (upper_bound == invalid_ranges.begin()) continue;
72 // upper_bounds points to the invalid range after the given slot. Hence,
73 // we have to go to the previous element.
74 upper_bound--;
75 DCHECK_LE(upper_bound->first, offset);
76 if (upper_bound->second > offset) {
77 slot = ClearedTypedSlot();
78 }
79 }
80 chunk = LoadNext(chunk);
81 }
82 }
83
84 } // namespace internal
85 } // namespace v8
86