Merge pull request #13676 from markdroth/inlined_vector

Implement InlinedVector independently of absl.

12 files changed, 273 insertions, 7 deletions

diff --git a/CMakeLists.txt b/CMakeLists.txt
index fa020e009d..78ccfb2132 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -594,6 +594,7 @@ add_dependencies(buildtests_cxx stress_test)
 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 @@ target_link_libraries(transport_pid_controller_test
 
 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 10c6530313..f50163efdc 100644
--- a/Makefile
+++ b/Makefile
@@ -1180,6 +1180,7 @@ stress_test: $(BINDIR)/$(CONFIG)/stress_test
 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 @@ buildtests_cxx: privatelibs_cxx \
   $(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 @@ buildtests_cxx: privatelibs_cxx \
   $(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 @@ test_cxx: buildtests_cxx
 	$(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
 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 9aff5585e0..db2ff8828b 100644
--- a/build.yaml
+++ b/build.yaml
@@ -399,6 +399,7 @@ filegroups:
   - 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 @@ targets:
   - 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 c007348c81..358fad3d98 100644
--- a/gRPC-Core.podspec
+++ b/gRPC-Core.podspec
@@ -422,6 +422,7 @@ Pod::Spec.new do |s|
                       '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 @@ Pod::Spec.new do |s|
                               '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 c7302785c7..7547bc85de 100644
--- a/grpc.gemspec
+++ b/grpc.gemspec
@@ -348,6 +348,7 @@ Gem::Specification.new do |s|
   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 adc98330de..ff3d0797ab 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 4a7db80676..2f249a5b9e 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 aad9f3be90..82607a1b26 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 b57674ba8e..d9184f49a2 100644
--- a/tools/doxygen/Doxyfile.c++.internal
+++ b/tools/doxygen/Doxyfile.c++.internal
@@ -1046,6 +1046,7 @@ src/core/lib/support/string_windows.h \
 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 e41123abf6..3d3c6711d0 100644
--- a/tools/doxygen/Doxyfile.core.internal
+++ b/tools/doxygen/Doxyfile.core.internal
@@ -1332,6 +1332,7 @@ src/core/lib/support/tmpfile.h \
 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 f7898a90a9..51f0ac7ca6 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 98517cba2e..6b83cecd41 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,