diff options
Diffstat (limited to 'src/google/protobuf/extension_set.cc')
| -rw-r--r-- | src/google/protobuf/extension_set.cc | 531 |
1 files changed, 346 insertions, 185 deletions
diff --git a/src/google/protobuf/extension_set.cc b/src/google/protobuf/extension_set.cc index cf6b6fb4..b587b38f 100644 --- a/src/google/protobuf/extension_set.cc +++ b/src/google/protobuf/extension_set.cc @@ -33,6 +33,8 @@ // Sanjay Ghemawat, Jeff Dean, and others. #include <google/protobuf/stubs/hash.h> +#include <tuple> +#include <utility> #include <google/protobuf/stubs/common.h> #include <google/protobuf/stubs/once.h> #include <google/protobuf/extension_set.h> @@ -178,20 +180,29 @@ void ExtensionSet::RegisterMessageExtension(const MessageLite* containing_type, // Constructors and basic methods. ExtensionSet::ExtensionSet(::google::protobuf::Arena* arena) - : arena_(arena) { - if (arena_ != NULL) { - arena_->OwnDestructor(&extensions_); - } -} - -ExtensionSet::ExtensionSet() : arena_(NULL) {} + : arena_(arena), + flat_capacity_(0), + flat_size_(0), + map_{flat_capacity_ == 0 ? NULL + : ::google::protobuf::Arena::CreateArray<KeyValue>( + arena_, flat_capacity_)} {} + +ExtensionSet::ExtensionSet() + : arena_(NULL), + flat_capacity_(0), + flat_size_(0), + map_{flat_capacity_ == 0 ? NULL + : ::google::protobuf::Arena::CreateArray<KeyValue>( + arena_, flat_capacity_)} {} ExtensionSet::~ExtensionSet() { // Deletes all allocated extensions. if (arena_ == NULL) { - for (ExtensionMap::iterator iter = extensions_.begin(); - iter != extensions_.end(); ++iter) { - iter->second.Free(); + ForEach([](int /* number */, Extension& ext) { ext.Free(); }); + if (GOOGLE_PREDICT_FALSE(is_large())) { + delete map_.large; + } else { + delete[] map_.flat; } } } @@ -202,45 +213,43 @@ ExtensionSet::~ExtensionSet() { // vector<const FieldDescriptor*>* output) const bool ExtensionSet::Has(int number) const { - ExtensionMap::const_iterator iter = extensions_.find(number); - if (iter == extensions_.end()) return false; - GOOGLE_DCHECK(!iter->second.is_repeated); - return !iter->second.is_cleared; + const Extension* ext = FindOrNull(number); + if (ext == NULL) return false; + GOOGLE_DCHECK(!ext->is_repeated); + return !ext->is_cleared; } int ExtensionSet::NumExtensions() const { int result = 0; - for (ExtensionMap::const_iterator iter = extensions_.begin(); - iter != extensions_.end(); ++iter) { - if (!iter->second.is_cleared) { + ForEach([&result](int /* number */, const Extension& ext) { + if (!ext.is_cleared) { ++result; } - } + }); return result; } int ExtensionSet::ExtensionSize(int number) const { - ExtensionMap::const_iterator iter = extensions_.find(number); - if (iter == extensions_.end()) return 0; - return iter->second.GetSize(); + const Extension* ext = FindOrNull(number); + return ext == NULL ? 0 : ext->GetSize(); } FieldType ExtensionSet::ExtensionType(int number) const { - ExtensionMap::const_iterator iter = extensions_.find(number); - if (iter == extensions_.end()) { + const Extension* ext = FindOrNull(number); + if (ext == NULL) { GOOGLE_LOG(DFATAL) << "Don't lookup extension types if they aren't present (1). "; return 0; } - if (iter->second.is_cleared) { + if (ext->is_cleared) { GOOGLE_LOG(DFATAL) << "Don't lookup extension types if they aren't present (2). "; } - return iter->second.type; + return ext->type; } void ExtensionSet::ClearExtension(int number) { - ExtensionMap::iterator iter = extensions_.find(number); - if (iter == extensions_.end()) return; - iter->second.Clear(); + Extension* ext = FindOrNull(number); + if (ext == NULL) return; + ext->Clear(); } // =================================================================== @@ -266,12 +275,12 @@ enum Cardinality { \ LOWERCASE ExtensionSet::Get##CAMELCASE(int number, \ LOWERCASE default_value) const { \ - ExtensionMap::const_iterator iter = extensions_.find(number); \ - if (iter == extensions_.end() || iter->second.is_cleared) { \ + const Extension* extension = FindOrNull(number); \ + if (extension == NULL || extension->is_cleared) { \ return default_value; \ } else { \ - GOOGLE_DCHECK_TYPE(iter->second, OPTIONAL, UPPERCASE); \ - return iter->second.LOWERCASE##_value; \ + GOOGLE_DCHECK_TYPE(*extension, OPTIONAL, UPPERCASE); \ + return extension->LOWERCASE##_value; \ } \ } \ \ @@ -291,18 +300,18 @@ void ExtensionSet::Set##CAMELCASE(int number, FieldType type, \ } \ \ LOWERCASE ExtensionSet::GetRepeated##CAMELCASE(int number, int index) const { \ - ExtensionMap::const_iterator iter = extensions_.find(number); \ - GOOGLE_CHECK(iter != extensions_.end()) << "Index out-of-bounds (field is empty)."; \ - GOOGLE_DCHECK_TYPE(iter->second, REPEATED, UPPERCASE); \ - return iter->second.repeated_##LOWERCASE##_value->Get(index); \ + const Extension* extension = FindOrNull(number); \ + GOOGLE_CHECK(extension != NULL) << "Index out-of-bounds (field is empty)."; \ + GOOGLE_DCHECK_TYPE(*extension, REPEATED, UPPERCASE); \ + return extension->repeated_##LOWERCASE##_value->Get(index); \ } \ \ void ExtensionSet::SetRepeated##CAMELCASE( \ int number, int index, LOWERCASE value) { \ - ExtensionMap::iterator iter = extensions_.find(number); \ - GOOGLE_CHECK(iter != extensions_.end()) << "Index out-of-bounds (field is empty)."; \ - GOOGLE_DCHECK_TYPE(iter->second, REPEATED, UPPERCASE); \ - iter->second.repeated_##LOWERCASE##_value->Set(index, value); \ + Extension* extension = FindOrNull(number); \ + GOOGLE_CHECK(extension != NULL) << "Index out-of-bounds (field is empty)."; \ + GOOGLE_DCHECK_TYPE(*extension, REPEATED, UPPERCASE); \ + extension->repeated_##LOWERCASE##_value->Set(index, value); \ } \ \ void ExtensionSet::Add##CAMELCASE(int number, FieldType type, \ @@ -335,13 +344,13 @@ PRIMITIVE_ACCESSORS( BOOL, bool, Bool) const void* ExtensionSet::GetRawRepeatedField(int number, const void* default_value) const { - ExtensionMap::const_iterator iter = extensions_.find(number); - if (iter == extensions_.end()) { + const Extension* extension = FindOrNull(number); + if (extension == NULL) { return default_value; } // We assume that all the RepeatedField<>* pointers have the same // size and alignment within the anonymous union in Extension. - return iter->second.repeated_int32_value; + return extension->repeated_int32_value; } void* ExtensionSet::MutableRawRepeatedField(int number, FieldType field_type, @@ -392,7 +401,7 @@ void* ExtensionSet::MutableRawRepeatedField(int number, FieldType field_type, break; case WireFormatLite::CPPTYPE_STRING: extension->repeated_string_value = - Arena::CreateMessage<RepeatedPtrField< ::std::string> >(arena_); + Arena::CreateMessage<RepeatedPtrField<::std::string> >(arena_); break; case WireFormatLite::CPPTYPE_MESSAGE: extension->repeated_message_value = @@ -409,11 +418,11 @@ void* ExtensionSet::MutableRawRepeatedField(int number, FieldType field_type, // Compatible version using old call signature. Does not create extensions when // the don't already exist; instead, just GOOGLE_CHECK-fails. void* ExtensionSet::MutableRawRepeatedField(int number) { - ExtensionMap::iterator iter = extensions_.find(number); - GOOGLE_CHECK(iter == extensions_.end()) << "Extension not found."; + Extension* extension = FindOrNull(number); + GOOGLE_CHECK(extension != NULL) << "Extension not found."; // We assume that all the RepeatedField<>* pointers have the same // size and alignment within the anonymous union in Extension. - return iter->second.repeated_int32_value; + return extension->repeated_int32_value; } @@ -421,13 +430,13 @@ void* ExtensionSet::MutableRawRepeatedField(int number) { // Enums int ExtensionSet::GetEnum(int number, int default_value) const { - ExtensionMap::const_iterator iter = extensions_.find(number); - if (iter == extensions_.end() || iter->second.is_cleared) { + const Extension* extension = FindOrNull(number); + if (extension == NULL || extension->is_cleared) { // Not present. Return the default value. return default_value; } else { - GOOGLE_DCHECK_TYPE(iter->second, OPTIONAL, ENUM); - return iter->second.enum_value; + GOOGLE_DCHECK_TYPE(*extension, OPTIONAL, ENUM); + return extension->enum_value; } } @@ -446,17 +455,17 @@ void ExtensionSet::SetEnum(int number, FieldType type, int value, } int ExtensionSet::GetRepeatedEnum(int number, int index) const { - ExtensionMap::const_iterator iter = extensions_.find(number); - GOOGLE_CHECK(iter != extensions_.end()) << "Index out-of-bounds (field is empty)."; - GOOGLE_DCHECK_TYPE(iter->second, REPEATED, ENUM); - return iter->second.repeated_enum_value->Get(index); + const Extension* extension = FindOrNull(number); + GOOGLE_CHECK(extension != NULL) << "Index out-of-bounds (field is empty)."; + GOOGLE_DCHECK_TYPE(*extension, REPEATED, ENUM); + return extension->repeated_enum_value->Get(index); } void ExtensionSet::SetRepeatedEnum(int number, int index, int value) { - ExtensionMap::iterator iter = extensions_.find(number); - GOOGLE_CHECK(iter != extensions_.end()) << "Index out-of-bounds (field is empty)."; - GOOGLE_DCHECK_TYPE(iter->second, REPEATED, ENUM); - iter->second.repeated_enum_value->Set(index, value); + Extension* extension = FindOrNull(number); + GOOGLE_CHECK(extension != NULL) << "Index out-of-bounds (field is empty)."; + GOOGLE_DCHECK_TYPE(*extension, REPEATED, ENUM); + extension->repeated_enum_value->Set(index, value); } void ExtensionSet::AddEnum(int number, FieldType type, @@ -482,13 +491,13 @@ void ExtensionSet::AddEnum(int number, FieldType type, const string& ExtensionSet::GetString(int number, const string& default_value) const { - ExtensionMap::const_iterator iter = extensions_.find(number); - if (iter == extensions_.end() || iter->second.is_cleared) { + const Extension* extension = FindOrNull(number); + if (extension == NULL || extension->is_cleared) { // Not present. Return the default value. return default_value; } else { - GOOGLE_DCHECK_TYPE(iter->second, OPTIONAL, STRING); - return *iter->second.string_value; + GOOGLE_DCHECK_TYPE(*extension, OPTIONAL, STRING); + return *extension->string_value; } } @@ -508,17 +517,17 @@ string* ExtensionSet::MutableString(int number, FieldType type, } const string& ExtensionSet::GetRepeatedString(int number, int index) const { - ExtensionMap::const_iterator iter = extensions_.find(number); - GOOGLE_CHECK(iter != extensions_.end()) << "Index out-of-bounds (field is empty)."; - GOOGLE_DCHECK_TYPE(iter->second, REPEATED, STRING); - return iter->second.repeated_string_value->Get(index); + const Extension* extension = FindOrNull(number); + GOOGLE_CHECK(extension != NULL) << "Index out-of-bounds (field is empty)."; + GOOGLE_DCHECK_TYPE(*extension, REPEATED, STRING); + return extension->repeated_string_value->Get(index); } string* ExtensionSet::MutableRepeatedString(int number, int index) { - ExtensionMap::iterator iter = extensions_.find(number); - GOOGLE_CHECK(iter != extensions_.end()) << "Index out-of-bounds (field is empty)."; - GOOGLE_DCHECK_TYPE(iter->second, REPEATED, STRING); - return iter->second.repeated_string_value->Mutable(index); + Extension* extension = FindOrNull(number); + GOOGLE_CHECK(extension != NULL) << "Index out-of-bounds (field is empty)."; + GOOGLE_DCHECK_TYPE(*extension, REPEATED, STRING); + return extension->repeated_string_value->Mutable(index); } string* ExtensionSet::AddString(int number, FieldType type, @@ -542,16 +551,16 @@ string* ExtensionSet::AddString(int number, FieldType type, const MessageLite& ExtensionSet::GetMessage( int number, const MessageLite& default_value) const { - ExtensionMap::const_iterator iter = extensions_.find(number); - if (iter == extensions_.end()) { + const Extension* extension = FindOrNull(number); + if (extension == NULL) { // Not present. Return the default value. return default_value; } else { - GOOGLE_DCHECK_TYPE(iter->second, OPTIONAL, MESSAGE); - if (iter->second.is_lazy) { - return iter->second.lazymessage_value->GetMessage(default_value); + GOOGLE_DCHECK_TYPE(*extension, OPTIONAL, MESSAGE); + if (extension->is_lazy) { + return extension->lazymessage_value->GetMessage(default_value); } else { - return *iter->second.message_value; + return *extension->message_value; } } } @@ -662,55 +671,53 @@ void ExtensionSet::UnsafeArenaSetAllocatedMessage( extension->is_cleared = false; } - MessageLite* ExtensionSet::ReleaseMessage(int number, const MessageLite& prototype) { - ExtensionMap::iterator iter = extensions_.find(number); - if (iter == extensions_.end()) { + Extension* extension = FindOrNull(number); + if (extension == NULL) { // Not present. Return NULL. return NULL; } else { - GOOGLE_DCHECK_TYPE(iter->second, OPTIONAL, MESSAGE); + GOOGLE_DCHECK_TYPE(*extension, OPTIONAL, MESSAGE); MessageLite* ret = NULL; - if (iter->second.is_lazy) { - ret = iter->second.lazymessage_value->ReleaseMessage(prototype); + if (extension->is_lazy) { + ret = extension->lazymessage_value->ReleaseMessage(prototype); if (arena_ == NULL) { - delete iter->second.lazymessage_value; + delete extension->lazymessage_value; } } else { if (arena_ == NULL) { - ret = iter->second.message_value; + ret = extension->message_value; } else { // ReleaseMessage() always returns a heap-allocated message, and we are // on an arena, so we need to make a copy of this message to return. - ret = (iter->second.message_value)->New(); - ret->CheckTypeAndMergeFrom(*iter->second.message_value); + ret = extension->message_value->New(); + ret->CheckTypeAndMergeFrom(*extension->message_value); } } - extensions_.erase(number); + Erase(number); return ret; } } MessageLite* ExtensionSet::UnsafeArenaReleaseMessage( int number, const MessageLite& prototype) { - ExtensionMap::iterator iter = extensions_.find(number); - if (iter == extensions_.end()) { + Extension* extension = FindOrNull(number); + if (extension == NULL) { // Not present. Return NULL. return NULL; } else { - GOOGLE_DCHECK_TYPE(iter->second, OPTIONAL, MESSAGE); + GOOGLE_DCHECK_TYPE(*extension, OPTIONAL, MESSAGE); MessageLite* ret = NULL; - if (iter->second.is_lazy) { - ret = - iter->second.lazymessage_value->UnsafeArenaReleaseMessage(prototype); + if (extension->is_lazy) { + ret = extension->lazymessage_value->UnsafeArenaReleaseMessage(prototype); if (arena_ == NULL) { - delete iter->second.lazymessage_value; + delete extension->lazymessage_value; } } else { - ret = iter->second.message_value; + ret = extension->message_value; } - extensions_.erase(number); + Erase(number); return ret; } } @@ -721,17 +728,17 @@ MessageLite* ExtensionSet::UnsafeArenaReleaseMessage( const MessageLite& ExtensionSet::GetRepeatedMessage( int number, int index) const { - ExtensionMap::const_iterator iter = extensions_.find(number); - GOOGLE_CHECK(iter != extensions_.end()) << "Index out-of-bounds (field is empty)."; - GOOGLE_DCHECK_TYPE(iter->second, REPEATED, MESSAGE); - return iter->second.repeated_message_value->Get(index); + const Extension* extension = FindOrNull(number); + GOOGLE_CHECK(extension != NULL) << "Index out-of-bounds (field is empty)."; + GOOGLE_DCHECK_TYPE(*extension, REPEATED, MESSAGE); + return extension->repeated_message_value->Get(index); } MessageLite* ExtensionSet::MutableRepeatedMessage(int number, int index) { - ExtensionMap::iterator iter = extensions_.find(number); - GOOGLE_CHECK(iter != extensions_.end()) << "Index out-of-bounds (field is empty)."; - GOOGLE_DCHECK_TYPE(iter->second, REPEATED, MESSAGE); - return iter->second.repeated_message_value->Mutable(index); + Extension* extension = FindOrNull(number); + GOOGLE_CHECK(extension != NULL) << "Index out-of-bounds (field is empty)."; + GOOGLE_DCHECK_TYPE(*extension, REPEATED, MESSAGE); + return extension->repeated_message_value->Mutable(index); } MessageLite* ExtensionSet::AddMessage(int number, FieldType type, @@ -750,8 +757,10 @@ MessageLite* ExtensionSet::AddMessage(int number, FieldType type, // RepeatedPtrField<MessageLite> does not know how to Add() since it cannot // allocate an abstract object, so we have to be tricky. - MessageLite* result = extension->repeated_message_value - ->AddFromCleared<GenericTypeHandler<MessageLite> >(); + MessageLite* result = + reinterpret_cast<::google::protobuf::internal::RepeatedPtrFieldBase*>( + extension->repeated_message_value) + ->AddFromCleared<GenericTypeHandler<MessageLite> >(); if (result == NULL) { result = prototype.New(arena_); extension->repeated_message_value->AddAllocated(result); @@ -767,10 +776,8 @@ MessageLite* ExtensionSet::AddMessage(int number, FieldType type, #undef GOOGLE_DCHECK_TYPE void ExtensionSet::RemoveLast(int number) { - ExtensionMap::iterator iter = extensions_.find(number); - GOOGLE_CHECK(iter != extensions_.end()) << "Index out-of-bounds (field is empty)."; - - Extension* extension = &iter->second; + Extension* extension = FindOrNull(number); + GOOGLE_CHECK(extension != NULL) << "Index out-of-bounds (field is empty)."; GOOGLE_DCHECK(extension->is_repeated); switch(cpp_type(extension->type)) { @@ -808,20 +815,16 @@ void ExtensionSet::RemoveLast(int number) { } MessageLite* ExtensionSet::ReleaseLast(int number) { - ExtensionMap::iterator iter = extensions_.find(number); - GOOGLE_CHECK(iter != extensions_.end()) << "Index out-of-bounds (field is empty)."; - - Extension* extension = &iter->second; + Extension* extension = FindOrNull(number); + GOOGLE_CHECK(extension != NULL) << "Index out-of-bounds (field is empty)."; GOOGLE_DCHECK(extension->is_repeated); GOOGLE_DCHECK(cpp_type(extension->type) == WireFormatLite::CPPTYPE_MESSAGE); return extension->repeated_message_value->ReleaseLast(); } void ExtensionSet::SwapElements(int number, int index1, int index2) { - ExtensionMap::iterator iter = extensions_.find(number); - GOOGLE_CHECK(iter != extensions_.end()) << "Index out-of-bounds (field is empty)."; - - Extension* extension = &iter->second; + Extension* extension = FindOrNull(number); + GOOGLE_CHECK(extension != NULL) << "Index out-of-bounds (field is empty)."; GOOGLE_DCHECK(extension->is_repeated); switch(cpp_type(extension->type)) { @@ -861,18 +864,45 @@ void ExtensionSet::SwapElements(int number, int index1, int index2) { // =================================================================== void ExtensionSet::Clear() { - for (ExtensionMap::iterator iter = extensions_.begin(); - iter != extensions_.end(); ++iter) { - iter->second.Clear(); + ForEach([](int /* number */, Extension& ext) { ext.Clear(); }); +} + +namespace { +// Computes the size of a std::set_union without constructing the union. +template <typename ItX, typename ItY> +size_t SizeOfUnion(ItX it_xs, ItX end_xs, ItY it_ys, ItY end_ys) { + size_t result = 0; + while (it_xs != end_xs && it_ys != end_ys) { + ++result; + if (it_xs->first < it_ys->first) { + ++it_xs; + } else if (it_xs->first == it_ys->first) { + ++it_xs; + ++it_ys; + } else { + ++it_ys; + } } + result += std::distance(it_xs, end_xs); + result += std::distance(it_ys, end_ys); + return result; } +} // namespace void ExtensionSet::MergeFrom(const ExtensionSet& other) { - for (ExtensionMap::const_iterator iter = other.extensions_.begin(); - iter != other.extensions_.end(); ++iter) { - const Extension& other_extension = iter->second; - InternalExtensionMergeFrom(iter->first, other_extension); + if (GOOGLE_PREDICT_TRUE(!is_large())) { + if (GOOGLE_PREDICT_TRUE(!other.is_large())) { + GrowCapacity(SizeOfUnion(flat_begin(), flat_end(), other.flat_begin(), + other.flat_end())); + } else { + GrowCapacity(SizeOfUnion(flat_begin(), flat_end(), + other.map_.large->begin(), + other.map_.large->end())); + } } + other.ForEach([this](int number, const Extension& ext) { + this->InternalExtensionMergeFrom(number, ext); + }); } void ExtensionSet::InternalExtensionMergeFrom( @@ -925,8 +955,10 @@ void ExtensionSet::InternalExtensionMergeFrom( other_extension.repeated_message_value; for (int i = 0; i < other_repeated_message->size(); i++) { const MessageLite& other_message = other_repeated_message->Get(i); - MessageLite* target = extension->repeated_message_value - ->AddFromCleared<GenericTypeHandler<MessageLite> >(); + MessageLite* target = + reinterpret_cast<::google::protobuf::internal::RepeatedPtrFieldBase*>( + extension->repeated_message_value) + ->AddFromCleared<GenericTypeHandler<MessageLite> >(); if (target == NULL) { target = other_message.New(arena_); extension->repeated_message_value->AddAllocated(target); @@ -1015,7 +1047,10 @@ void ExtensionSet::InternalExtensionMergeFrom( void ExtensionSet::Swap(ExtensionSet* x) { if (GetArenaNoVirtual() == x->GetArenaNoVirtual()) { - extensions_.swap(x->extensions_); + using std::swap; + swap(flat_capacity_, x->flat_capacity_); + swap(flat_size_, x->flat_size_); + swap(map_, x->map_); } else { // TODO(cfallin, rohananil): We maybe able to optimize a case where we are // swapping from heap to arena-allocated extension set, by just Own()'ing @@ -1032,19 +1067,17 @@ void ExtensionSet::Swap(ExtensionSet* x) { void ExtensionSet::SwapExtension(ExtensionSet* other, int number) { if (this == other) return; - ExtensionMap::iterator this_iter = extensions_.find(number); - ExtensionMap::iterator other_iter = other->extensions_.find(number); + Extension* this_ext = FindOrNull(number); + Extension* other_ext = other->FindOrNull(number); - if (this_iter == extensions_.end() && - other_iter == other->extensions_.end()) { + if (this_ext == NULL && other_ext == NULL) { return; } - if (this_iter != extensions_.end() && - other_iter != other->extensions_.end()) { + if (this_ext != NULL && other_ext != NULL) { if (GetArenaNoVirtual() == other->GetArenaNoVirtual()) { using std::swap; - swap(this_iter->second, other_iter->second); + swap(*this_ext, *other_ext); } else { // TODO(cfallin, rohananil): We could further optimize these cases, // especially avoid creation of ExtensionSet, and move MergeFrom logic @@ -1052,33 +1085,33 @@ void ExtensionSet::SwapExtension(ExtensionSet* other, // We do it this way to reuse the copy-across-arenas logic already // implemented in ExtensionSet's MergeFrom. ExtensionSet temp; - temp.InternalExtensionMergeFrom(number, other_iter->second); - ExtensionMap::iterator temp_iter = temp.extensions_.find(number); - other_iter->second.Clear(); - other->InternalExtensionMergeFrom(number, this_iter->second); - this_iter->second.Clear(); - InternalExtensionMergeFrom(number, temp_iter->second); + temp.InternalExtensionMergeFrom(number, *other_ext); + Extension* temp_ext = temp.FindOrNull(number); + other_ext->Clear(); + other->InternalExtensionMergeFrom(number, *this_ext); + this_ext->Clear(); + InternalExtensionMergeFrom(number, *temp_ext); } return; } - if (this_iter == extensions_.end()) { + if (this_ext == NULL) { if (GetArenaNoVirtual() == other->GetArenaNoVirtual()) { - extensions_.insert(std::make_pair(number, other_iter->second)); + *Insert(number).first = *other_ext; } else { - InternalExtensionMergeFrom(number, other_iter->second); + InternalExtensionMergeFrom(number, *other_ext); } - other->extensions_.erase(number); + other->Erase(number); return; } - if (other_iter == other->extensions_.end()) { + if (other_ext == NULL) { if (GetArenaNoVirtual() == other->GetArenaNoVirtual()) { - other->extensions_.insert(std::make_pair(number, this_iter->second)); + *other->Insert(number).first = *this_ext; } else { - other->InternalExtensionMergeFrom(number, this_iter->second); + other->InternalExtensionMergeFrom(number, *this_ext); } - extensions_.erase(number); + Erase(number); return; } } @@ -1086,28 +1119,15 @@ void ExtensionSet::SwapExtension(ExtensionSet* other, bool ExtensionSet::IsInitialized() const { // Extensions are never required. However, we need to check that all // embedded messages are initialized. - for (ExtensionMap::const_iterator iter = extensions_.begin(); - iter != extensions_.end(); ++iter) { - const Extension& extension = iter->second; - if (cpp_type(extension.type) == WireFormatLite::CPPTYPE_MESSAGE) { - if (extension.is_repeated) { - for (int i = 0; i < extension.repeated_message_value->size(); i++) { - if (!extension.repeated_message_value->Get(i).IsInitialized()) { - return false; - } - } - } else { - if (!extension.is_cleared) { - if (extension.is_lazy) { - if (!extension.lazymessage_value->IsInitialized()) return false; - } else { - if (!extension.message_value->IsInitialized()) return false; - } - } - } + if (GOOGLE_PREDICT_FALSE(is_large())) { + for (const auto& kv : *map_.large) { + if (!kv.second.IsInitialized()) return false; } + return true; + } + for (const KeyValue* it = flat_begin(); it != flat_end(); ++it) { + if (!it->second.IsInitialized()) return false; } - return true; } @@ -1346,22 +1366,27 @@ bool ExtensionSet::ParseField(uint32 tag, io::CodedInputStream* input, void ExtensionSet::SerializeWithCachedSizes( int start_field_number, int end_field_number, io::CodedOutputStream* output) const { - ExtensionMap::const_iterator iter; - for (iter = extensions_.lower_bound(start_field_number); - iter != extensions_.end() && iter->first < end_field_number; - ++iter) { - iter->second.SerializeFieldWithCachedSizes(iter->first, output); + if (GOOGLE_PREDICT_FALSE(is_large())) { + const auto& end = map_.large->end(); + for (auto it = map_.large->lower_bound(start_field_number); + it != end && it->first < end_field_number; ++it) { + it->second.SerializeFieldWithCachedSizes(it->first, output); + } + return; + } + const KeyValue* end = flat_end(); + for (const KeyValue* it = std::lower_bound( + flat_begin(), end, start_field_number, KeyValue::FirstComparator()); + it != end && it->first < end_field_number; ++it) { + it->second.SerializeFieldWithCachedSizes(it->first, output); } } size_t ExtensionSet::ByteSize() const { size_t total_size = 0; - - for (ExtensionMap::const_iterator iter = extensions_.begin(); - iter != extensions_.end(); ++iter) { - total_size += iter->second.ByteSize(iter->first); - } - + ForEach([&total_size](int number, const Extension& ext) { + total_size += ext.ByteSize(number); + }); return total_size; } @@ -1371,11 +1396,10 @@ size_t ExtensionSet::ByteSize() const { bool ExtensionSet::MaybeNewExtension(int number, const FieldDescriptor* descriptor, Extension** result) { - std::pair<ExtensionMap::iterator, bool> insert_result = - extensions_.insert(std::make_pair(number, Extension())); - *result = &insert_result.first->second; + bool extension_is_new = false; + std::tie(*result, extension_is_new) = Insert(number); (*result)->descriptor = descriptor; - return insert_result.second; + return extension_is_new; } // =================================================================== @@ -1747,6 +1771,143 @@ void ExtensionSet::Extension::Free() { // Defined in extension_set_heavy.cc. // int ExtensionSet::Extension::SpaceUsedExcludingSelf() const +bool ExtensionSet::Extension::IsInitialized() const { + if (cpp_type(type) == WireFormatLite::CPPTYPE_MESSAGE) { + if (is_repeated) { + for (int i = 0; i < repeated_message_value->size(); i++) { + if (!repeated_message_value->Get(i).IsInitialized()) { + return false; + } + } + } else { + if (!is_cleared) { + if (is_lazy) { + if (!lazymessage_value->IsInitialized()) return false; + } else { + if (!message_value->IsInitialized()) return false; + } + } + } + } + return true; +} + +// Dummy key method to avoid weak vtable. +void ExtensionSet::LazyMessageExtension::UnusedKeyMethod() {} + +const ExtensionSet::Extension* ExtensionSet::FindOrNull(int key) const { + if (GOOGLE_PREDICT_FALSE(is_large())) { + return FindOrNullInLargeMap(key); + } + const KeyValue* end = flat_end(); + const KeyValue* it = + std::lower_bound(flat_begin(), end, key, KeyValue::FirstComparator()); + if (it != end && it->first == key) { + return &it->second; + } + return NULL; +} + +const ExtensionSet::Extension* ExtensionSet::FindOrNullInLargeMap( + int key) const { + assert(is_large()); + LargeMap::const_iterator it = map_.large->find(key); + if (it != map_.large->end()) { + return &it->second; + } + return NULL; +} + +ExtensionSet::Extension* ExtensionSet::FindOrNull(int key) { + if (GOOGLE_PREDICT_FALSE(is_large())) { + return FindOrNullInLargeMap(key); + } + KeyValue* end = flat_end(); + KeyValue* it = + std::lower_bound(flat_begin(), end, key, KeyValue::FirstComparator()); + if (it != end && it->first == key) { + return &it->second; + } + return NULL; +} + +ExtensionSet::Extension* ExtensionSet::FindOrNullInLargeMap(int key) { + assert(is_large()); + LargeMap::iterator it = map_.large->find(key); + if (it != map_.large->end()) { + return &it->second; + } + return NULL; +} + +std::pair<ExtensionSet::Extension*, bool> ExtensionSet::Insert(int key) { + if (GOOGLE_PREDICT_FALSE(is_large())) { + auto maybe = map_.large->insert({key, Extension()}); + return {&maybe.first->second, maybe.second}; + } + KeyValue* end = flat_end(); + KeyValue* it = + std::lower_bound(flat_begin(), end, key, KeyValue::FirstComparator()); + if (it != end && it->first == key) { + return {&it->second, false}; + } + if (flat_size_ < flat_capacity_) { + std::copy_backward(it, end, end + 1); + ++flat_size_; + it->first = key; + it->second = Extension(); + return {&it->second, true}; + } + GrowCapacity(flat_size_ + 1); + return Insert(key); +} + +void ExtensionSet::GrowCapacity(size_t minimum_new_capacity) { + if (GOOGLE_PREDICT_FALSE(is_large())) { + return; // LargeMap does not have a "reserve" method. + } + if (flat_capacity_ >= minimum_new_capacity) { + return; + } + + do { + flat_capacity_ = flat_capacity_ == 0 ? 1 : flat_capacity_ * 4; + } while (flat_capacity_ < minimum_new_capacity); + + const KeyValue* begin = flat_begin(); + const KeyValue* end = flat_end(); + if (flat_capacity_ > kMaximumFlatCapacity) { + // Switch to LargeMap + map_.large = ::google::protobuf::Arena::Create<LargeMap>(arena_); + LargeMap::iterator hint = map_.large->begin(); + for (const KeyValue* it = begin; it != end; ++it) { + hint = map_.large->insert(hint, {it->first, it->second}); + } + flat_size_ = 0; + } else { + map_.flat = ::google::protobuf::Arena::CreateArray<KeyValue>(arena_, flat_capacity_); + std::copy(begin, end, map_.flat); + } + if (arena_ == NULL) delete[] begin; +} + +// static +constexpr uint16 ExtensionSet::kMaximumFlatCapacity; + +void ExtensionSet::Erase(int key) { + if (GOOGLE_PREDICT_FALSE(is_large())) { + map_.large->erase(key); + return; + } + KeyValue* end = flat_end(); + KeyValue* it = + std::lower_bound(flat_begin(), end, key, KeyValue::FirstComparator()); + if (it != end && it->first == key) { + std::copy(it + 1, end, it); + --flat_size_; + } +} + // ================================================================== // Default repeated field instances for iterator-compatible accessors |