1 // Copyright 2015 The Chromium 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 "third_party/blink/renderer/platform/graphics/contiguous_container.h"
6
7 #include <algorithm>
8 #include <memory>
9
10 #include "base/macros.h"
11 #include "third_party/blink/renderer/platform/wtf/allocator/allocator.h"
12 #include "third_party/blink/renderer/platform/wtf/allocator/partitions.h"
13 #include "third_party/blink/renderer/platform/wtf/container_annotations.h"
14
15 namespace blink {
16
17 // Default number of max-sized elements to allocate space for, if there is no
18 // initial buffer.
19 static const unsigned kDefaultInitialBufferSize = 32;
20
21 class ContiguousContainerBase::Buffer {
22 USING_FAST_MALLOC(Buffer);
23
24 public:
Buffer(wtf_size_t buffer_size,const char * type_name)25 Buffer(wtf_size_t buffer_size, const char* type_name) {
26 capacity_ = WTF::Partitions::BufferActualSize(buffer_size);
27 begin_ = end_ =
28 static_cast<char*>(WTF::Partitions::BufferMalloc(capacity_, type_name));
29 ANNOTATE_NEW_BUFFER(begin_, capacity_, 0);
30 }
31
~Buffer()32 ~Buffer() {
33 ANNOTATE_DELETE_BUFFER(begin_, capacity_, UsedCapacity());
34 WTF::Partitions::BufferFree(begin_);
35 }
36
Capacity() const37 wtf_size_t Capacity() const { return capacity_; }
UsedCapacity() const38 wtf_size_t UsedCapacity() const { return end_ - begin_; }
UnusedCapacity() const39 wtf_size_t UnusedCapacity() const { return Capacity() - UsedCapacity(); }
IsEmpty() const40 bool IsEmpty() const { return UsedCapacity() == 0; }
41
Allocate(wtf_size_t object_size)42 void* Allocate(wtf_size_t object_size) {
43 DCHECK_GE(UnusedCapacity(), object_size);
44 ANNOTATE_CHANGE_SIZE(begin_, capacity_, UsedCapacity(),
45 UsedCapacity() + object_size);
46 void* result = end_;
47 end_ += object_size;
48 return result;
49 }
50
DeallocateLastObject(void * object)51 void DeallocateLastObject(void* object) {
52 CHECK_LE(begin_, object);
53 CHECK_LT(object, end_);
54 ANNOTATE_CHANGE_SIZE(begin_, capacity_, UsedCapacity(),
55 static_cast<char*>(object) - begin_);
56 end_ = static_cast<char*>(object);
57 }
58
59 private:
60 // m_begin <= m_end <= m_begin + m_capacity
61 char* begin_;
62 char* end_;
63 wtf_size_t capacity_;
64
65 DISALLOW_COPY_AND_ASSIGN(Buffer);
66 };
67
ContiguousContainerBase(wtf_size_t max_object_size)68 ContiguousContainerBase::ContiguousContainerBase(wtf_size_t max_object_size)
69 : end_index_(0), max_object_size_(max_object_size) {}
70
ContiguousContainerBase(ContiguousContainerBase && source)71 ContiguousContainerBase::ContiguousContainerBase(
72 ContiguousContainerBase&& source)
73 : ContiguousContainerBase(source.max_object_size_) {
74 Swap(source);
75 }
76
77 ContiguousContainerBase::~ContiguousContainerBase() = default;
78
operator =(ContiguousContainerBase && source)79 ContiguousContainerBase& ContiguousContainerBase::operator=(
80 ContiguousContainerBase&& source) {
81 Swap(source);
82 return *this;
83 }
84
CapacityInBytes() const85 wtf_size_t ContiguousContainerBase::CapacityInBytes() const {
86 wtf_size_t capacity = 0;
87 for (const auto& buffer : buffers_)
88 capacity += buffer->Capacity();
89 return capacity;
90 }
91
UsedCapacityInBytes() const92 wtf_size_t ContiguousContainerBase::UsedCapacityInBytes() const {
93 wtf_size_t used_capacity = 0;
94 for (const auto& buffer : buffers_)
95 used_capacity += buffer->UsedCapacity();
96 return used_capacity;
97 }
98
MemoryUsageInBytes() const99 wtf_size_t ContiguousContainerBase::MemoryUsageInBytes() const {
100 return sizeof(*this) + CapacityInBytes() +
101 elements_.capacity() * sizeof(elements_[0]);
102 }
103
ReserveInitialCapacity(wtf_size_t buffer_size,const char * type_name)104 void ContiguousContainerBase::ReserveInitialCapacity(wtf_size_t buffer_size,
105 const char* type_name) {
106 AllocateNewBufferForNextAllocation(buffer_size, type_name);
107 }
108
Allocate(wtf_size_t object_size,const char * type_name)109 void* ContiguousContainerBase::Allocate(wtf_size_t object_size,
110 const char* type_name) {
111 DCHECK_LE(object_size, max_object_size_);
112
113 Buffer* buffer_for_alloc = nullptr;
114 if (!buffers_.IsEmpty()) {
115 Buffer* end_buffer = buffers_[end_index_].get();
116 if (end_buffer->UnusedCapacity() >= object_size)
117 buffer_for_alloc = end_buffer;
118 else if (end_index_ + 1 < buffers_.size())
119 buffer_for_alloc = buffers_[++end_index_].get();
120 }
121
122 if (!buffer_for_alloc) {
123 wtf_size_t new_buffer_size =
124 buffers_.IsEmpty() ? kDefaultInitialBufferSize * max_object_size_
125 : 2 * buffers_.back()->Capacity();
126 buffer_for_alloc =
127 AllocateNewBufferForNextAllocation(new_buffer_size, type_name);
128 }
129
130 void* element = buffer_for_alloc->Allocate(object_size);
131 elements_.push_back(element);
132 return element;
133 }
134
RemoveLast()135 void ContiguousContainerBase::RemoveLast() {
136 void* object = elements_.back();
137 elements_.pop_back();
138
139 Buffer* end_buffer = buffers_[end_index_].get();
140 end_buffer->DeallocateLastObject(object);
141
142 if (end_buffer->IsEmpty()) {
143 if (end_index_ > 0)
144 end_index_--;
145 if (end_index_ + 2 < buffers_.size())
146 buffers_.pop_back();
147 }
148 }
149
Clear()150 void ContiguousContainerBase::Clear() {
151 elements_.clear();
152 buffers_.clear();
153 end_index_ = 0;
154 }
155
Swap(ContiguousContainerBase & other)156 void ContiguousContainerBase::Swap(ContiguousContainerBase& other) {
157 elements_.swap(other.elements_);
158 buffers_.swap(other.buffers_);
159 std::swap(end_index_, other.end_index_);
160 std::swap(max_object_size_, other.max_object_size_);
161 }
162
ShrinkToFit()163 void ContiguousContainerBase::ShrinkToFit() {
164 while (end_index_ < buffers_.size() - 1) {
165 DCHECK(buffers_.back()->IsEmpty());
166 buffers_.pop_back();
167 }
168 }
169
170 ContiguousContainerBase::Buffer*
AllocateNewBufferForNextAllocation(wtf_size_t buffer_size,const char * type_name)171 ContiguousContainerBase::AllocateNewBufferForNextAllocation(
172 wtf_size_t buffer_size,
173 const char* type_name) {
174 DCHECK(buffers_.IsEmpty() || end_index_ == buffers_.size() - 1);
175 std::unique_ptr<Buffer> new_buffer =
176 std::make_unique<Buffer>(buffer_size, type_name);
177 Buffer* buffer_to_return = new_buffer.get();
178 buffers_.push_back(std::move(new_buffer));
179 end_index_ = buffers_.size() - 1;
180 return buffer_to_return;
181 }
182
183 } // namespace blink
184