Merge pull request #13676 from markdroth/inlined_vector
Implement InlinedVector independently of absl.
diff --git a/CMakeLists.txt b/CMakeLists.txt
index fa020e0..78ccfb2 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -594,6 +594,7 @@
add_dependencies(buildtests_cxx thread_manager_test)
add_dependencies(buildtests_cxx thread_stress_test)
add_dependencies(buildtests_cxx transport_pid_controller_test)
+add_dependencies(buildtests_cxx vector_test)
if(_gRPC_PLATFORM_LINUX OR _gRPC_PLATFORM_MAC OR _gRPC_PLATFORM_POSIX)
add_dependencies(buildtests_cxx writes_per_rpc_test)
endif()
@@ -12487,6 +12488,45 @@
endif (gRPC_BUILD_TESTS)
if (gRPC_BUILD_TESTS)
+
+add_executable(vector_test
+ test/core/support/vector_test.cc
+ third_party/googletest/googletest/src/gtest-all.cc
+ third_party/googletest/googlemock/src/gmock-all.cc
+)
+
+
+target_include_directories(vector_test
+ PRIVATE ${CMAKE_CURRENT_SOURCE_DIR}
+ PRIVATE ${CMAKE_CURRENT_SOURCE_DIR}/include
+ PRIVATE ${_gRPC_SSL_INCLUDE_DIR}
+ PRIVATE ${PROTOBUF_ROOT_DIR}/src
+ PRIVATE ${BENCHMARK_ROOT_DIR}/include
+ PRIVATE ${ZLIB_ROOT_DIR}
+ PRIVATE ${CMAKE_CURRENT_BINARY_DIR}/third_party/zlib
+ PRIVATE ${CARES_INCLUDE_DIR}
+ PRIVATE ${CMAKE_CURRENT_BINARY_DIR}/third_party/cares/cares
+ PRIVATE ${CMAKE_CURRENT_BINARY_DIR}/third_party/gflags/include
+ PRIVATE third_party/googletest/googletest/include
+ PRIVATE third_party/googletest/googletest
+ PRIVATE third_party/googletest/googlemock/include
+ PRIVATE third_party/googletest/googlemock
+ PRIVATE ${_gRPC_PROTO_GENS_DIR}
+)
+
+target_link_libraries(vector_test
+ ${_gRPC_PROTOBUF_LIBRARIES}
+ ${_gRPC_ALLTARGETS_LIBRARIES}
+ grpc_test_util
+ grpc++
+ grpc
+ gpr_test_util
+ gpr
+ ${_gRPC_GFLAGS_LIBRARIES}
+)
+
+endif (gRPC_BUILD_TESTS)
+if (gRPC_BUILD_TESTS)
if(_gRPC_PLATFORM_LINUX OR _gRPC_PLATFORM_MAC OR _gRPC_PLATFORM_POSIX)
add_executable(writes_per_rpc_test
diff --git a/Makefile b/Makefile
index 10c6530..f50163e 100644
--- a/Makefile
+++ b/Makefile
@@ -1180,6 +1180,7 @@
thread_manager_test: $(BINDIR)/$(CONFIG)/thread_manager_test
thread_stress_test: $(BINDIR)/$(CONFIG)/thread_stress_test
transport_pid_controller_test: $(BINDIR)/$(CONFIG)/transport_pid_controller_test
+vector_test: $(BINDIR)/$(CONFIG)/vector_test
writes_per_rpc_test: $(BINDIR)/$(CONFIG)/writes_per_rpc_test
public_headers_must_be_c89: $(BINDIR)/$(CONFIG)/public_headers_must_be_c89
gen_hpack_tables: $(BINDIR)/$(CONFIG)/gen_hpack_tables
@@ -1620,6 +1621,7 @@
$(BINDIR)/$(CONFIG)/thread_manager_test \
$(BINDIR)/$(CONFIG)/thread_stress_test \
$(BINDIR)/$(CONFIG)/transport_pid_controller_test \
+ $(BINDIR)/$(CONFIG)/vector_test \
$(BINDIR)/$(CONFIG)/writes_per_rpc_test \
$(BINDIR)/$(CONFIG)/boringssl_aes_test \
$(BINDIR)/$(CONFIG)/boringssl_asn1_test \
@@ -1749,6 +1751,7 @@
$(BINDIR)/$(CONFIG)/thread_manager_test \
$(BINDIR)/$(CONFIG)/thread_stress_test \
$(BINDIR)/$(CONFIG)/transport_pid_controller_test \
+ $(BINDIR)/$(CONFIG)/vector_test \
$(BINDIR)/$(CONFIG)/writes_per_rpc_test \
$(BINDIR)/$(CONFIG)/resolver_component_test_unsecure \
$(BINDIR)/$(CONFIG)/resolver_component_test \
@@ -2167,6 +2170,8 @@
$(Q) $(BINDIR)/$(CONFIG)/thread_stress_test || ( echo test thread_stress_test failed ; exit 1 )
$(E) "[RUN] Testing transport_pid_controller_test"
$(Q) $(BINDIR)/$(CONFIG)/transport_pid_controller_test || ( echo test transport_pid_controller_test failed ; exit 1 )
+ $(E) "[RUN] Testing vector_test"
+ $(Q) $(BINDIR)/$(CONFIG)/vector_test || ( echo test vector_test failed ; exit 1 )
$(E) "[RUN] Testing writes_per_rpc_test"
$(Q) $(BINDIR)/$(CONFIG)/writes_per_rpc_test || ( echo test writes_per_rpc_test failed ; exit 1 )
$(E) "[RUN] Testing resolver_component_tests_runner_invoker_unsecure"
@@ -17260,6 +17265,49 @@
endif
+VECTOR_TEST_SRC = \
+ test/core/support/vector_test.cc \
+
+VECTOR_TEST_OBJS = $(addprefix $(OBJDIR)/$(CONFIG)/, $(addsuffix .o, $(basename $(VECTOR_TEST_SRC))))
+ifeq ($(NO_SECURE),true)
+
+# You can't build secure targets if you don't have OpenSSL.
+
+$(BINDIR)/$(CONFIG)/vector_test: openssl_dep_error
+
+else
+
+
+
+
+ifeq ($(NO_PROTOBUF),true)
+
+# You can't build the protoc plugins or protobuf-enabled targets if you don't have protobuf 3.0.0+.
+
+$(BINDIR)/$(CONFIG)/vector_test: protobuf_dep_error
+
+else
+
+$(BINDIR)/$(CONFIG)/vector_test: $(PROTOBUF_DEP) $(VECTOR_TEST_OBJS) $(LIBDIR)/$(CONFIG)/libgrpc_test_util.a $(LIBDIR)/$(CONFIG)/libgrpc++.a $(LIBDIR)/$(CONFIG)/libgrpc.a $(LIBDIR)/$(CONFIG)/libgpr_test_util.a $(LIBDIR)/$(CONFIG)/libgpr.a
+ $(E) "[LD] Linking $@"
+ $(Q) mkdir -p `dirname $@`
+ $(Q) $(LDXX) $(LDFLAGS) $(VECTOR_TEST_OBJS) $(LIBDIR)/$(CONFIG)/libgrpc_test_util.a $(LIBDIR)/$(CONFIG)/libgrpc++.a $(LIBDIR)/$(CONFIG)/libgrpc.a $(LIBDIR)/$(CONFIG)/libgpr_test_util.a $(LIBDIR)/$(CONFIG)/libgpr.a $(LDLIBSXX) $(LDLIBS_PROTOBUF) $(LDLIBS) $(LDLIBS_SECURE) $(GTEST_LIB) -o $(BINDIR)/$(CONFIG)/vector_test
+
+endif
+
+endif
+
+$(OBJDIR)/$(CONFIG)/test/core/support/vector_test.o: $(LIBDIR)/$(CONFIG)/libgrpc_test_util.a $(LIBDIR)/$(CONFIG)/libgrpc++.a $(LIBDIR)/$(CONFIG)/libgrpc.a $(LIBDIR)/$(CONFIG)/libgpr_test_util.a $(LIBDIR)/$(CONFIG)/libgpr.a
+
+deps_vector_test: $(VECTOR_TEST_OBJS:.o=.dep)
+
+ifneq ($(NO_SECURE),true)
+ifneq ($(NO_DEPS),true)
+-include $(VECTOR_TEST_OBJS:.o=.dep)
+endif
+endif
+
+
WRITES_PER_RPC_TEST_SRC = \
test/cpp/performance/writes_per_rpc_test.cc \
diff --git a/build.yaml b/build.yaml
index 9aff558..db2ff88 100644
--- a/build.yaml
+++ b/build.yaml
@@ -399,6 +399,7 @@
- src/core/lib/support/debug_location.h
- src/core/lib/support/ref_counted.h
- src/core/lib/support/ref_counted_ptr.h
+ - src/core/lib/support/vector.h
- src/core/lib/surface/alarm_internal.h
- src/core/lib/surface/api_trace.h
- src/core/lib/surface/call.h
@@ -4797,6 +4798,20 @@
- grpc
- gpr_test_util
- gpr
+- name: vector_test
+ gtest: true
+ build: test
+ language: c++
+ src:
+ - test/core/support/vector_test.cc
+ deps:
+ - grpc_test_util
+ - grpc++
+ - grpc
+ - gpr_test_util
+ - gpr
+ uses:
+ - grpc++_test
- name: writes_per_rpc_test
gtest: true
cpu_cost: 0.5
diff --git a/gRPC-Core.podspec b/gRPC-Core.podspec
index c007348..358fad3 100644
--- a/gRPC-Core.podspec
+++ b/gRPC-Core.podspec
@@ -422,6 +422,7 @@
'src/core/lib/support/debug_location.h',
'src/core/lib/support/ref_counted.h',
'src/core/lib/support/ref_counted_ptr.h',
+ 'src/core/lib/support/vector.h',
'src/core/lib/surface/alarm_internal.h',
'src/core/lib/surface/api_trace.h',
'src/core/lib/surface/call.h',
@@ -902,6 +903,7 @@
'src/core/lib/support/debug_location.h',
'src/core/lib/support/ref_counted.h',
'src/core/lib/support/ref_counted_ptr.h',
+ 'src/core/lib/support/vector.h',
'src/core/lib/surface/alarm_internal.h',
'src/core/lib/surface/api_trace.h',
'src/core/lib/surface/call.h',
diff --git a/grpc.gemspec b/grpc.gemspec
index c730278..7547bc8 100644
--- a/grpc.gemspec
+++ b/grpc.gemspec
@@ -348,6 +348,7 @@
s.files += %w( src/core/lib/support/debug_location.h )
s.files += %w( src/core/lib/support/ref_counted.h )
s.files += %w( src/core/lib/support/ref_counted_ptr.h )
+ s.files += %w( src/core/lib/support/vector.h )
s.files += %w( src/core/lib/surface/alarm_internal.h )
s.files += %w( src/core/lib/surface/api_trace.h )
s.files += %w( src/core/lib/surface/call.h )
diff --git a/package.xml b/package.xml
index adc9833..ff3d079 100644
--- a/package.xml
+++ b/package.xml
@@ -360,6 +360,7 @@
<file baseinstalldir="/" name="src/core/lib/support/debug_location.h" role="src" />
<file baseinstalldir="/" name="src/core/lib/support/ref_counted.h" role="src" />
<file baseinstalldir="/" name="src/core/lib/support/ref_counted_ptr.h" role="src" />
+ <file baseinstalldir="/" name="src/core/lib/support/vector.h" role="src" />
<file baseinstalldir="/" name="src/core/lib/surface/alarm_internal.h" role="src" />
<file baseinstalldir="/" name="src/core/lib/surface/api_trace.h" role="src" />
<file baseinstalldir="/" name="src/core/lib/surface/call.h" role="src" />
diff --git a/src/core/lib/support/vector.h b/src/core/lib/support/vector.h
index 4a7db80..2f249a5 100644
--- a/src/core/lib/support/vector.h
+++ b/src/core/lib/support/vector.h
@@ -19,13 +19,93 @@
#ifndef GRPC_CORE_LIB_SUPPORT_VECTOR_H
#define GRPC_CORE_LIB_SUPPORT_VECTOR_H
-#include "absl/container/inlined_vector.h"
+#include <cassert>
+
#include "src/core/lib/support/memory.h"
namespace grpc_core {
+// NOTE: We eventually want to use absl::InlinedVector here. However,
+// there are currently build problems that prevent us from using absl.
+// In the interim, we define a custom implementation as a place-holder,
+// with the intent to eventually replace this with the absl
+// implementation.
+//
+// This place-holder implementation does not implement the full set of
+// functionality from the absl version; it has just the methods that we
+// currently happen to need in gRPC. If additional functionality is
+// needed before this gets replaced with the absl version, it can be
+// added, with the following proviso:
+//
+// ANY METHOD ADDED HERE MUST COMPLY WITH THE INTERFACE IN THE absl
+// IMPLEMENTATION!
+//
+// TODO(ctiller, nnoble, roth): Replace this with absl::InlinedVector
+// once we integrate absl into the gRPC build system in a usable way.
template <typename T, size_t N>
-using InlinedVector = absl::InlinedVector<T, N, Allocator<T>>;
+class InlinedVector {
+ public:
+ InlinedVector() {}
+ ~InlinedVector() {
+ for (size_t i = 0; i < size_ && i < N; ++i) {
+ T& value = *reinterpret_cast<T*>(inline_ + i);
+ value.~T();
+ }
+ if (size_ > N) { // Avoid subtracting two signed values.
+ for (size_t i = 0; i < size_ - N; ++i) {
+ dynamic_[i].~T();
+ }
+ }
+ gpr_free(dynamic_);
+ }
+
+ // For now, we do not support copying.
+ InlinedVector(const InlinedVector&) = delete;
+ InlinedVector& operator=(const InlinedVector&) = delete;
+
+ T& operator[](size_t offset) {
+ assert(offset < size_);
+ if (offset < N) {
+ return *reinterpret_cast<T*>(inline_ + offset);
+ } else {
+ return dynamic_[offset - N];
+ }
+ }
+
+ template <typename... Args>
+ void emplace_back(Args&&... args) {
+ if (size_ < N) {
+ new (&inline_[size_]) T(std::forward<Args>(args)...);
+ } else {
+ if (size_ - N == dynamic_capacity_) {
+ size_t new_capacity =
+ dynamic_capacity_ == 0 ? 2 : dynamic_capacity_ * 2;
+ T* new_dynamic = static_cast<T*>(gpr_malloc(sizeof(T) * new_capacity));
+ for (size_t i = 0; i < dynamic_capacity_; ++i) {
+ new (&new_dynamic[i]) T(std::move(dynamic_[i]));
+ dynamic_[i].~T();
+ }
+ gpr_free(dynamic_);
+ dynamic_ = new_dynamic;
+ dynamic_capacity_ = new_capacity;
+ }
+ new (&dynamic_[size_ - N]) T(std::forward<Args>(args)...);
+ }
+ ++size_;
+ }
+
+ void push_back(const T& value) { emplace_back(value); }
+
+ void push_back(T&& value) { emplace_back(std::move(value)); }
+
+ size_t size() const { return size_; }
+
+ private:
+ typename std::aligned_storage<sizeof(T)>::type inline_[N];
+ T* dynamic_ = nullptr;
+ size_t size_ = 0;
+ size_t dynamic_capacity_ = 0;
+};
} // namespace grpc_core
diff --git a/test/core/support/vector_test.cc b/test/core/support/vector_test.cc
index aad9f3b..82607a1 100644
--- a/test/core/support/vector_test.cc
+++ b/test/core/support/vector_test.cc
@@ -18,18 +18,50 @@
#include "src/core/lib/support/vector.h"
#include <gtest/gtest.h>
+#include "src/core/lib/support/memory.h"
#include "test/core/util/test_config.h"
namespace grpc_core {
namespace testing {
TEST(InlinedVectorTest, CreateAndIterate) {
- InlinedVector<int, 1> v{1, 2, 3};
- int sum = 0;
- for (auto i : v) {
- sum += i;
+ const int kNumElements = 9;
+ InlinedVector<int, 2> v;
+ for (int i = 0; i < kNumElements; ++i) {
+ v.push_back(i);
}
- EXPECT_EQ(6, sum);
+ EXPECT_EQ(static_cast<size_t>(kNumElements), v.size());
+ for (int i = 0; i < kNumElements; ++i) {
+ EXPECT_EQ(i, v[i]);
+ }
+}
+
+TEST(InlinedVectorTest, ValuesAreInlined) {
+ const int kNumElements = 5;
+ InlinedVector<int, 10> v;
+ for (int i = 0; i < kNumElements; ++i) {
+ v.push_back(i);
+ }
+ EXPECT_EQ(static_cast<size_t>(kNumElements), v.size());
+ for (int i = 0; i < kNumElements; ++i) {
+ EXPECT_EQ(i, v[i]);
+ }
+}
+
+TEST(InlinedVectorTest, PushBackWithMove) {
+ InlinedVector<UniquePtr<int>, 1> v;
+ UniquePtr<int> i = MakeUnique<int>(3);
+ v.push_back(std::move(i));
+ EXPECT_EQ(nullptr, i.get());
+ EXPECT_EQ(1UL, v.size());
+ EXPECT_EQ(3, *v[0]);
+}
+
+TEST(InlinedVectorTest, EmplaceBack) {
+ InlinedVector<UniquePtr<int>, 1> v;
+ v.emplace_back(New<int>(3));
+ EXPECT_EQ(1UL, v.size());
+ EXPECT_EQ(3, *v[0]);
}
} // namespace testing
diff --git a/tools/doxygen/Doxyfile.c++.internal b/tools/doxygen/Doxyfile.c++.internal
index b57674b..d9184f4 100644
--- a/tools/doxygen/Doxyfile.c++.internal
+++ b/tools/doxygen/Doxyfile.c++.internal
@@ -1046,6 +1046,7 @@
src/core/lib/support/thd_internal.h \
src/core/lib/support/time_precise.h \
src/core/lib/support/tmpfile.h \
+src/core/lib/support/vector.h \
src/core/lib/surface/alarm_internal.h \
src/core/lib/surface/api_trace.h \
src/core/lib/surface/call.h \
diff --git a/tools/doxygen/Doxyfile.core.internal b/tools/doxygen/Doxyfile.core.internal
index e41123a..3d3c671 100644
--- a/tools/doxygen/Doxyfile.core.internal
+++ b/tools/doxygen/Doxyfile.core.internal
@@ -1332,6 +1332,7 @@
src/core/lib/support/tmpfile_msys.cc \
src/core/lib/support/tmpfile_posix.cc \
src/core/lib/support/tmpfile_windows.cc \
+src/core/lib/support/vector.h \
src/core/lib/support/wrap_memcpy.cc \
src/core/lib/surface/README.md \
src/core/lib/surface/alarm.cc \
diff --git a/tools/run_tests/generated/sources_and_headers.json b/tools/run_tests/generated/sources_and_headers.json
index f7898a9..51f0ac7 100644
--- a/tools/run_tests/generated/sources_and_headers.json
+++ b/tools/run_tests/generated/sources_and_headers.json
@@ -4268,6 +4268,25 @@
"gpr_test_util",
"grpc",
"grpc++",
+ "grpc++_test",
+ "grpc_test_util"
+ ],
+ "headers": [],
+ "is_filegroup": false,
+ "language": "c++",
+ "name": "vector_test",
+ "src": [
+ "test/core/support/vector_test.cc"
+ ],
+ "third_party": false,
+ "type": "target"
+ },
+ {
+ "deps": [
+ "gpr",
+ "gpr_test_util",
+ "grpc",
+ "grpc++",
"grpc++_test_util",
"grpc_test_util"
],
@@ -8250,6 +8269,7 @@
"src/core/lib/support/debug_location.h",
"src/core/lib/support/ref_counted.h",
"src/core/lib/support/ref_counted_ptr.h",
+ "src/core/lib/support/vector.h",
"src/core/lib/surface/alarm_internal.h",
"src/core/lib/surface/api_trace.h",
"src/core/lib/surface/call.h",
@@ -8389,6 +8409,7 @@
"src/core/lib/support/debug_location.h",
"src/core/lib/support/ref_counted.h",
"src/core/lib/support/ref_counted_ptr.h",
+ "src/core/lib/support/vector.h",
"src/core/lib/surface/alarm_internal.h",
"src/core/lib/surface/api_trace.h",
"src/core/lib/surface/call.h",
diff --git a/tools/run_tests/generated/tests.json b/tools/run_tests/generated/tests.json
index 98517cb..6b83cec 100644
--- a/tools/run_tests/generated/tests.json
+++ b/tools/run_tests/generated/tests.json
@@ -4510,6 +4510,30 @@
"ci_platforms": [
"linux",
"mac",
+ "posix",
+ "windows"
+ ],
+ "cpu_cost": 1.0,
+ "exclude_configs": [],
+ "exclude_iomgrs": [],
+ "flaky": false,
+ "gtest": true,
+ "language": "c++",
+ "name": "vector_test",
+ "platforms": [
+ "linux",
+ "mac",
+ "posix",
+ "windows"
+ ],
+ "uses_polling": true
+ },
+ {
+ "args": [],
+ "benchmark": false,
+ "ci_platforms": [
+ "linux",
+ "mac",
"posix"
],
"cpu_cost": 0.5,