1 // Protocol Buffers - Google's data interchange format
2 // Copyright 2008 Google Inc. All rights reserved.
3 //
4 // Use of this source code is governed by a BSD-style
5 // license that can be found in the LICENSE file or at
6 // https://developers.google.com/open-source/licenses/bsd
7
8 // Author: kenton@google.com (Kenton Varda)
9 // Based on original Protocol Buffers design by
10 // Sanjay Ghemawat, Jeff Dean, and others.
11
12 #include "google/protobuf/repeated_ptr_field.h"
13
14 #include <algorithm>
15 #include <cstddef>
16 #include <cstdint>
17 #include <cstring>
18 #include <limits>
19 #include <new>
20 #include <string>
21
22 #include "absl/log/absl_check.h"
23 #include "google/protobuf/arena.h"
24 #include "google/protobuf/message_lite.h"
25 #include "google/protobuf/port.h"
26 #include "google/protobuf/repeated_field.h"
27
28 // Must be included last.
29 #include "google/protobuf/port_def.inc"
30
31 namespace google {
32 namespace protobuf {
33
34 namespace internal {
35
InternalExtend(int extend_amount)36 void** RepeatedPtrFieldBase::InternalExtend(int extend_amount) {
37 ABSL_DCHECK(extend_amount > 0);
38 constexpr size_t kPtrSize = sizeof(rep()->elements[0]);
39 constexpr size_t kMaxSize = std::numeric_limits<size_t>::max();
40 constexpr size_t kMaxCapacity = (kMaxSize - kRepHeaderSize) / kPtrSize;
41 const int old_capacity = Capacity();
42 Arena* arena = GetArena();
43 Rep* new_rep = nullptr;
44 {
45 int new_capacity = internal::CalculateReserveSize<void*, kRepHeaderSize>(
46 old_capacity, old_capacity + extend_amount);
47 ABSL_DCHECK_LE(new_capacity, kMaxCapacity)
48 << "New capacity is too large to fit into internal representation";
49 const size_t new_size = kRepHeaderSize + kPtrSize * new_capacity;
50 if (arena == nullptr) {
51 const internal::SizedPtr alloc = internal::AllocateAtLeast(new_size);
52 new_capacity = static_cast<int>((alloc.n - kRepHeaderSize) / kPtrSize);
53 new_rep = reinterpret_cast<Rep*>(alloc.p);
54 } else {
55 auto* alloc = Arena::CreateArray<char>(arena, new_size);
56 new_rep = reinterpret_cast<Rep*>(alloc);
57 }
58 capacity_proxy_ = new_capacity - kSSOCapacity;
59 }
60
61 if (using_sso()) {
62 new_rep->allocated_size = tagged_rep_or_elem_ != nullptr ? 1 : 0;
63 new_rep->elements[0] = tagged_rep_or_elem_;
64 } else {
65 Rep* old_rep = rep();
66 memcpy(new_rep, old_rep,
67 old_rep->allocated_size * kPtrSize + kRepHeaderSize);
68 size_t old_size = old_capacity * kPtrSize + kRepHeaderSize;
69 if (arena == nullptr) {
70 internal::SizedDelete(old_rep, old_size);
71 } else {
72 arena->ReturnArrayMemory(old_rep, old_size);
73 }
74 }
75
76 tagged_rep_or_elem_ =
77 reinterpret_cast<void*>(reinterpret_cast<uintptr_t>(new_rep) + 1);
78
79 return &new_rep->elements[current_size_];
80 }
81
Reserve(int capacity)82 void RepeatedPtrFieldBase::Reserve(int capacity) {
83 int delta = capacity - Capacity();
84 if (delta > 0) {
85 InternalExtend(delta);
86 }
87 }
88
DestroyProtos()89 void RepeatedPtrFieldBase::DestroyProtos() {
90 PROTOBUF_ALWAYS_INLINE_CALL Destroy<GenericTypeHandler<MessageLite>>();
91
92 // TODO: Eliminate this store when invoked from the destructor,
93 // since it is dead.
94 tagged_rep_or_elem_ = nullptr;
95 }
96
AddMessageLite(ElementFactory factory)97 void* RepeatedPtrFieldBase::AddMessageLite(ElementFactory factory) {
98 return AddInternal(factory);
99 }
100
AddString()101 void* RepeatedPtrFieldBase::AddString() {
102 return AddInternal([](Arena* arena) { return NewStringElement(arena); });
103 }
104
CloseGap(int start,int num)105 void RepeatedPtrFieldBase::CloseGap(int start, int num) {
106 if (using_sso()) {
107 if (start == 0 && num == 1) {
108 tagged_rep_or_elem_ = nullptr;
109 }
110 } else {
111 // Close up a gap of "num" elements starting at offset "start".
112 Rep* r = rep();
113 for (int i = start + num; i < r->allocated_size; ++i)
114 r->elements[i - num] = r->elements[i];
115 r->allocated_size -= num;
116 }
117 ExchangeCurrentSize(current_size_ - num);
118 }
119
AddMessage(const MessageLite * prototype)120 MessageLite* RepeatedPtrFieldBase::AddMessage(const MessageLite* prototype) {
121 return static_cast<MessageLite*>(
122 AddInternal([prototype](Arena* a) { return prototype->New(a); }));
123 }
124
InternalOutOfLineDeleteMessageLite(MessageLite * message)125 void InternalOutOfLineDeleteMessageLite(MessageLite* message) {
126 delete message;
127 }
128
129 template PROTOBUF_EXPORT_TEMPLATE_DEFINE void
130 memswap<ArenaOffsetHelper<RepeatedPtrFieldBase>::value>(
131 char* PROTOBUF_RESTRICT, char* PROTOBUF_RESTRICT);
132
133 template <>
MergeFrom(const RepeatedPtrFieldBase & from)134 void RepeatedPtrFieldBase::MergeFrom<std::string>(
135 const RepeatedPtrFieldBase& from) {
136 Prefetch5LinesFrom1Line(&from);
137 ABSL_DCHECK_NE(&from, this);
138 int new_size = current_size_ + from.current_size_;
139 auto dst = reinterpret_cast<std::string**>(InternalReserve(new_size));
140 auto src = reinterpret_cast<std::string* const*>(from.elements());
141 auto end = src + from.current_size_;
142 auto end_assign = src + std::min(ClearedCount(), from.current_size_);
143 for (; src < end_assign; ++dst, ++src) {
144 (*dst)->assign(**src);
145 }
146 if (Arena* const arena = arena_) {
147 for (; src < end; ++dst, ++src) {
148 *dst = Arena::Create<std::string>(arena, **src);
149 }
150 } else {
151 for (; src < end; ++dst, ++src) {
152 *dst = new std::string(**src);
153 }
154 }
155 ExchangeCurrentSize(new_size);
156 if (new_size > allocated_size()) {
157 rep()->allocated_size = new_size;
158 }
159 }
160
161
MergeIntoClearedMessages(const RepeatedPtrFieldBase & from)162 int RepeatedPtrFieldBase::MergeIntoClearedMessages(
163 const RepeatedPtrFieldBase& from) {
164 Prefetch5LinesFrom1Line(&from);
165 auto dst = reinterpret_cast<MessageLite**>(elements() + current_size_);
166 auto src = reinterpret_cast<MessageLite* const*>(from.elements());
167 int count = std::min(ClearedCount(), from.current_size_);
168 for (int i = 0; i < count; ++i) {
169 ABSL_DCHECK(src[i] != nullptr);
170 ABSL_DCHECK(TypeId::Get(*src[i]) == TypeId::Get(*src[0]))
171 << src[i]->GetTypeName() << " vs " << src[0]->GetTypeName();
172 dst[i]->CheckTypeAndMergeFrom(*src[i]);
173 }
174 return count;
175 }
176
MergeFromConcreteMessage(const RepeatedPtrFieldBase & from,CopyFn copy_fn)177 void RepeatedPtrFieldBase::MergeFromConcreteMessage(
178 const RepeatedPtrFieldBase& from, CopyFn copy_fn) {
179 Prefetch5LinesFrom1Line(&from);
180 ABSL_DCHECK_NE(&from, this);
181 int new_size = current_size_ + from.current_size_;
182 void** dst = InternalReserve(new_size);
183 const void* const* src = from.elements();
184 auto end = src + from.current_size_;
185 if (PROTOBUF_PREDICT_FALSE(ClearedCount() > 0)) {
186 int recycled = MergeIntoClearedMessages(from);
187 dst += recycled;
188 src += recycled;
189 }
190 Arena* arena = GetArena();
191 for (; src < end; ++src, ++dst) {
192 *dst = copy_fn(arena, *src);
193 }
194 ExchangeCurrentSize(new_size);
195 if (new_size > allocated_size()) {
196 rep()->allocated_size = new_size;
197 }
198 }
199
200 template <>
MergeFrom(const RepeatedPtrFieldBase & from)201 void RepeatedPtrFieldBase::MergeFrom<MessageLite>(
202 const RepeatedPtrFieldBase& from) {
203 Prefetch5LinesFrom1Line(&from);
204 ABSL_DCHECK_NE(&from, this);
205 ABSL_DCHECK(from.current_size_ > 0);
206 int new_size = current_size_ + from.current_size_;
207 auto dst = reinterpret_cast<MessageLite**>(InternalReserve(new_size));
208 auto src = reinterpret_cast<MessageLite const* const*>(from.elements());
209 auto end = src + from.current_size_;
210 const MessageLite* prototype = src[0];
211 ABSL_DCHECK(prototype != nullptr);
212 if (PROTOBUF_PREDICT_FALSE(ClearedCount() > 0)) {
213 int recycled = MergeIntoClearedMessages(from);
214 dst += recycled;
215 src += recycled;
216 }
217 Arena* arena = GetArena();
218 for (; src < end; ++src, ++dst) {
219 ABSL_DCHECK(*src != nullptr);
220 ABSL_DCHECK(TypeId::Get(**src) == TypeId::Get(*prototype))
221 << (**src).GetTypeName() << " vs " << prototype->GetTypeName();
222 *dst = prototype->New(arena);
223 (*dst)->CheckTypeAndMergeFrom(**src);
224 }
225 ExchangeCurrentSize(new_size);
226 if (new_size > allocated_size()) {
227 rep()->allocated_size = new_size;
228 }
229 }
230
NewStringElement(Arena * arena)231 void* NewStringElement(Arena* arena) {
232 return Arena::Create<std::string>(arena);
233 }
234
235 } // namespace internal
236 } // namespace protobuf
237 } // namespace google
238
239 #include "google/protobuf/port_undef.inc"
240