From f3f96c69481d5dd078e3563b13bf05903dba6517 Mon Sep 17 00:00:00 2001
From: Philip Pronin <philipp@fb.com>
Date: Tue, 14 Aug 2012 18:55:35 -0700
Subject: [PATCH] strings join

Summary: The same interface as ##facebook::strings::join##, but few times faster.

Test Plan: folly/test/StringTest.cpp

Reviewed By: tudorb@fb.com

FB internal diff: D548863
---
 folly/String-inl.h        | 67 +++++++++++++++++++++++++++++++++++++++
 folly/String.h            | 20 ++++++++++++
 folly/test/StringTest.cpp | 46 ++++++++++++++++++++++++---
 3 files changed, 129 insertions(+), 4 deletions(-)

diff --git a/folly/String-inl.h b/folly/String-inl.h
index 3829f1f8..02d376d8 100644
--- a/folly/String-inl.h
+++ b/folly/String-inl.h
@@ -18,6 +18,7 @@
 #define FOLLY_STRING_INL_H_
 
 #include <stdexcept>
+#include <iterator>
 
 #ifndef FOLLY_BASE_STRING_H_
 #error This file may only be included from String.h
@@ -298,6 +299,72 @@ void splitTo(const Delim& delimiter,
     ignoreEmpty);
 }
 
+namespace detail {
+
+template <class Iterator>
+struct IsStringContainerIterator :
+  IsSomeString<typename std::iterator_traits<Iterator>::value_type> {
+};
+
+template <class Delim, class Iterator, class String>
+void internalJoinAppend(Delim delimiter,
+                        Iterator begin,
+                        Iterator end,
+                        String& output) {
+  assert(begin != end);
+  toAppend(*begin, &output);
+  while (++begin != end) {
+    toAppend(delimiter, *begin, &output);
+  }
+}
+
+template <class Delim, class Iterator, class String>
+typename std::enable_if<IsStringContainerIterator<Iterator>::value>::type
+internalJoin(Delim delimiter,
+             Iterator begin,
+             Iterator end,
+             String& output) {
+  output.clear();
+  if (begin == end) {
+    return;
+  }
+  const size_t dsize = delimSize(delimiter);
+  Iterator it = begin;
+  size_t size = it->size();
+  while (++it != end) {
+    size += dsize + it->size();
+  }
+  output.reserve(size);
+  internalJoinAppend(delimiter, begin, end, output);
+}
+
+template <class Delim, class Iterator, class String>
+typename std::enable_if<!IsStringContainerIterator<Iterator>::value>::type
+internalJoin(Delim delimiter,
+             Iterator begin,
+             Iterator end,
+             String& output) {
+  output.clear();
+  if (begin == end) {
+    return;
+  }
+  internalJoinAppend(delimiter, begin, end, output);
+}
+
+}  // namespace detail
+
+template <class Delim, class Iterator, class String>
+void join(const Delim& delimiter,
+          Iterator begin,
+          Iterator end,
+          String& output) {
+  detail::internalJoin(
+    detail::prepareDelim(delimiter),
+    begin,
+    end,
+    output);
+}
+
 template <class String1, class String2>
 void backslashify(const String1& input, String2& output, bool hex_style) {
   static const char hexValues[] = "0123456789abcdef";
diff --git a/folly/String.h b/folly/String.h
index 604c0883..906a9f37 100644
--- a/folly/String.h
+++ b/folly/String.h
@@ -333,6 +333,26 @@ void splitTo(const Delim& delimiter,
              OutputIterator out,
              bool ignoreEmpty = false);
 
+/*
+ * Join list of tokens.
+ *
+ * Stores a string representation of tokens in the same order with
+ * deliminer between each element.
+ */
+
+template <class Delim, class Iterator, class String>
+void join(const Delim& delimiter,
+          Iterator begin,
+          Iterator end,
+          String& output);
+
+template <class Delim, class Container, class String>
+void join(const Delim& delimiter,
+          const Container& container,
+          String& output) {
+  join(delimiter, container.begin(), container.end(), output);
+}
+
 } // namespace folly
 
 // Hash functions for string and fbstring usable with e.g. hash_map
diff --git a/folly/test/StringTest.cpp b/folly/test/StringTest.cpp
index ec3b310b..df5c6891 100644
--- a/folly/test/StringTest.cpp
+++ b/folly/test/StringTest.cpp
@@ -634,6 +634,26 @@ TEST(Split, pieces_fbvector) {
   piecesTest<folly::fbvector>();
 }
 
+TEST(String, join) {
+  string output;
+
+  std::vector<int> empty = { };
+  join(":", empty, output);
+  EXPECT_TRUE(output.empty());
+
+  std::vector<std::string> input1 = { "1", "23", "456", "" };
+  join(':', input1, output);
+  EXPECT_EQ(output, "1:23:456:");
+
+  auto input2 = { 1, 23, 456 };
+  join("-*-", input2, output);
+  EXPECT_EQ(output, "1-*-23-*-456");
+
+  auto input3 = { 'f', 'a', 'c', 'e', 'b', 'o', 'o', 'k' };
+  join("", input3, output);
+  EXPECT_EQ(output, "facebook");
+}
+
 TEST(String, hexlify) {
   string input1 = "0123";
   string output1;
@@ -714,7 +734,7 @@ TEST(String, humanify) {
 //////////////////////////////////////////////////////////////////////
 
 BENCHMARK(splitOnSingleChar, iters) {
-  const std::string line = "one:two:three:four";
+  static const std::string line = "one:two:three:four";
   for (int i = 0; i < iters << 4; ++i) {
     std::vector<StringPiece> pieces;
     folly::split(':', line, pieces);
@@ -722,7 +742,7 @@ BENCHMARK(splitOnSingleChar, iters) {
 }
 
 BENCHMARK(splitStr, iters) {
-  const std::string line = "one-*-two-*-three-*-four";
+  static const std::string line = "one-*-two-*-three-*-four";
   for (int i = 0; i < iters << 4; ++i) {
     std::vector<StringPiece> pieces;
     folly::split("-*-", line, pieces);
@@ -730,13 +750,31 @@ BENCHMARK(splitStr, iters) {
 }
 
 BENCHMARK(boost_splitOnSingleChar, iters) {
-  std::string line = "one:two:three:four";
+  static const std::string line = "one:two:three:four";
   for (int i = 0; i < iters << 4; ++i) {
-    std::vector<boost::iterator_range<std::string::iterator>> pieces;
+    std::vector<boost::iterator_range<std::string::const_iterator> > pieces;
     boost::split(pieces, line, [] (char c) { return c == ':'; });
   }
 }
 
+BENCHMARK(joinStr, iters) {
+  static const std::vector<std::string> input = {
+    "one", "two", "three", "four", "five", "six", "seven" };
+  for (int i = 0; i < iters << 4; ++i) {
+    std::string output;
+    folly::join(":", input, output);
+  }
+}
+
+BENCHMARK(joinInt, iters) {
+  static const auto input = {
+    123, 456, 78910, 1112, 1314, 151, 61718 };
+  for (int i = 0; i < iters << 4; ++i) {
+    std::string output;
+    folly::join(":", input, output);
+  }
+}
+
 int main(int argc, char *argv[]) {
   testing::InitGoogleTest(&argc, argv);
   google::ParseCommandLineFlags(&argc, &argv, true);
-- 
2.34.1