You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@marmotta.apache.org by ss...@apache.org on 2018/04/29 19:36:11 UTC
[42/51] [partial] marmotta git commit: * Replace gtest with upstream
version,
including LICENSE header. * Include absl library for faster and safer string
operations. * Update license headers where needed. * Removed custom code
replaced by absl.
http://git-wip-us.apache.org/repos/asf/marmotta/blob/0eb556da/libraries/ostrich/backend/3rdparty/abseil/absl/container/fixed_array_test.cc
----------------------------------------------------------------------
diff --git a/libraries/ostrich/backend/3rdparty/abseil/absl/container/fixed_array_test.cc b/libraries/ostrich/backend/3rdparty/abseil/absl/container/fixed_array_test.cc
new file mode 100644
index 0000000..2142132
--- /dev/null
+++ b/libraries/ostrich/backend/3rdparty/abseil/absl/container/fixed_array_test.cc
@@ -0,0 +1,659 @@
+// Copyright 2017 The Abseil Authors.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#include "absl/container/fixed_array.h"
+
+#include <stdio.h>
+#include <list>
+#include <memory>
+#include <numeric>
+#include <stdexcept>
+#include <string>
+#include <vector>
+
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+#include "absl/base/internal/exception_testing.h"
+#include "absl/memory/memory.h"
+
+using ::testing::ElementsAreArray;
+
+namespace {
+
+// Helper routine to determine if a absl::FixedArray used stack allocation.
+template <typename ArrayType>
+static bool IsOnStack(const ArrayType& a) {
+ return a.size() <= ArrayType::inline_elements;
+}
+
+class ConstructionTester {
+ public:
+ ConstructionTester()
+ : self_ptr_(this),
+ value_(0) {
+ constructions++;
+ }
+ ~ConstructionTester() {
+ assert(self_ptr_ == this);
+ self_ptr_ = nullptr;
+ destructions++;
+ }
+
+ // These are incremented as elements are constructed and destructed so we can
+ // be sure all elements are properly cleaned up.
+ static int constructions;
+ static int destructions;
+
+ void CheckConstructed() {
+ assert(self_ptr_ == this);
+ }
+
+ void set(int value) { value_ = value; }
+ int get() { return value_; }
+
+ private:
+ // self_ptr_ should always point to 'this' -- that's how we can be sure the
+ // constructor has been called.
+ ConstructionTester* self_ptr_;
+ int value_;
+};
+
+int ConstructionTester::constructions = 0;
+int ConstructionTester::destructions = 0;
+
+// ThreeInts will initialize its three ints to the value stored in
+// ThreeInts::counter. The constructor increments counter so that each object
+// in an array of ThreeInts will have different values.
+class ThreeInts {
+ public:
+ ThreeInts() {
+ x_ = counter;
+ y_ = counter;
+ z_ = counter;
+ ++counter;
+ }
+
+ static int counter;
+
+ int x_, y_, z_;
+};
+
+int ThreeInts::counter = 0;
+
+TEST(FixedArrayTest, CopyCtor) {
+ absl::FixedArray<int, 10> on_stack(5);
+ std::iota(on_stack.begin(), on_stack.end(), 0);
+ absl::FixedArray<int, 10> stack_copy = on_stack;
+ EXPECT_THAT(stack_copy, ElementsAreArray(on_stack));
+ EXPECT_TRUE(IsOnStack(stack_copy));
+
+ absl::FixedArray<int, 10> allocated(15);
+ std::iota(allocated.begin(), allocated.end(), 0);
+ absl::FixedArray<int, 10> alloced_copy = allocated;
+ EXPECT_THAT(alloced_copy, ElementsAreArray(allocated));
+ EXPECT_FALSE(IsOnStack(alloced_copy));
+}
+
+TEST(FixedArrayTest, MoveCtor) {
+ absl::FixedArray<std::unique_ptr<int>, 10> on_stack(5);
+ for (int i = 0; i < 5; ++i) {
+ on_stack[i] = absl::make_unique<int>(i);
+ }
+
+ absl::FixedArray<std::unique_ptr<int>, 10> stack_copy = std::move(on_stack);
+ for (int i = 0; i < 5; ++i) EXPECT_EQ(*(stack_copy[i]), i);
+ EXPECT_EQ(stack_copy.size(), on_stack.size());
+
+ absl::FixedArray<std::unique_ptr<int>, 10> allocated(15);
+ for (int i = 0; i < 15; ++i) {
+ allocated[i] = absl::make_unique<int>(i);
+ }
+
+ absl::FixedArray<std::unique_ptr<int>, 10> alloced_copy =
+ std::move(allocated);
+ for (int i = 0; i < 15; ++i) EXPECT_EQ(*(alloced_copy[i]), i);
+ EXPECT_EQ(allocated.size(), alloced_copy.size());
+}
+
+TEST(FixedArrayTest, SmallObjects) {
+ // Small object arrays
+ {
+ // Short arrays should be on the stack
+ absl::FixedArray<int> array(4);
+ EXPECT_TRUE(IsOnStack(array));
+ }
+
+ {
+ // Large arrays should be on the heap
+ absl::FixedArray<int> array(1048576);
+ EXPECT_FALSE(IsOnStack(array));
+ }
+
+ {
+ // Arrays of <= default size should be on the stack
+ absl::FixedArray<int, 100> array(100);
+ EXPECT_TRUE(IsOnStack(array));
+ }
+
+ {
+ // Arrays of > default size should be on the stack
+ absl::FixedArray<int, 100> array(101);
+ EXPECT_FALSE(IsOnStack(array));
+ }
+
+ {
+ // Arrays with different size elements should use approximately
+ // same amount of stack space
+ absl::FixedArray<int> array1(0);
+ absl::FixedArray<char> array2(0);
+ EXPECT_LE(sizeof(array1), sizeof(array2)+100);
+ EXPECT_LE(sizeof(array2), sizeof(array1)+100);
+ }
+
+ {
+ // Ensure that vectors are properly constructed inside a fixed array.
+ absl::FixedArray<std::vector<int> > array(2);
+ EXPECT_EQ(0, array[0].size());
+ EXPECT_EQ(0, array[1].size());
+ }
+
+ {
+ // Regardless of absl::FixedArray implementation, check that a type with a
+ // low alignment requirement and a non power-of-two size is initialized
+ // correctly.
+ ThreeInts::counter = 1;
+ absl::FixedArray<ThreeInts> array(2);
+ EXPECT_EQ(1, array[0].x_);
+ EXPECT_EQ(1, array[0].y_);
+ EXPECT_EQ(1, array[0].z_);
+ EXPECT_EQ(2, array[1].x_);
+ EXPECT_EQ(2, array[1].y_);
+ EXPECT_EQ(2, array[1].z_);
+ }
+}
+
+TEST(FixedArrayTest, AtThrows) {
+ absl::FixedArray<int> a = {1, 2, 3};
+ EXPECT_EQ(a.at(2), 3);
+ ABSL_BASE_INTERNAL_EXPECT_FAIL(a.at(3), std::out_of_range,
+ "failed bounds check");
+}
+
+TEST(FixedArrayRelationalsTest, EqualArrays) {
+ for (int i = 0; i < 10; ++i) {
+ absl::FixedArray<int, 5> a1(i);
+ std::iota(a1.begin(), a1.end(), 0);
+ absl::FixedArray<int, 5> a2(a1.begin(), a1.end());
+
+ EXPECT_TRUE(a1 == a2);
+ EXPECT_FALSE(a1 != a2);
+ EXPECT_TRUE(a2 == a1);
+ EXPECT_FALSE(a2 != a1);
+ EXPECT_FALSE(a1 < a2);
+ EXPECT_FALSE(a1 > a2);
+ EXPECT_FALSE(a2 < a1);
+ EXPECT_FALSE(a2 > a1);
+ EXPECT_TRUE(a1 <= a2);
+ EXPECT_TRUE(a1 >= a2);
+ EXPECT_TRUE(a2 <= a1);
+ EXPECT_TRUE(a2 >= a1);
+ }
+}
+
+TEST(FixedArrayRelationalsTest, UnequalArrays) {
+ for (int i = 1; i < 10; ++i) {
+ absl::FixedArray<int, 5> a1(i);
+ std::iota(a1.begin(), a1.end(), 0);
+ absl::FixedArray<int, 5> a2(a1.begin(), a1.end());
+ --a2[i / 2];
+
+ EXPECT_FALSE(a1 == a2);
+ EXPECT_TRUE(a1 != a2);
+ EXPECT_FALSE(a2 == a1);
+ EXPECT_TRUE(a2 != a1);
+ EXPECT_FALSE(a1 < a2);
+ EXPECT_TRUE(a1 > a2);
+ EXPECT_TRUE(a2 < a1);
+ EXPECT_FALSE(a2 > a1);
+ EXPECT_FALSE(a1 <= a2);
+ EXPECT_TRUE(a1 >= a2);
+ EXPECT_TRUE(a2 <= a1);
+ EXPECT_FALSE(a2 >= a1);
+ }
+}
+
+template <int stack_elements>
+static void TestArray(int n) {
+ SCOPED_TRACE(n);
+ SCOPED_TRACE(stack_elements);
+ ConstructionTester::constructions = 0;
+ ConstructionTester::destructions = 0;
+ {
+ absl::FixedArray<ConstructionTester, stack_elements> array(n);
+
+ EXPECT_THAT(array.size(), n);
+ EXPECT_THAT(array.memsize(), sizeof(ConstructionTester) * n);
+ EXPECT_THAT(array.begin() + n, array.end());
+
+ // Check that all elements were constructed
+ for (int i = 0; i < n; i++) {
+ array[i].CheckConstructed();
+ }
+ // Check that no other elements were constructed
+ EXPECT_THAT(ConstructionTester::constructions, n);
+
+ // Test operator[]
+ for (int i = 0; i < n; i++) {
+ array[i].set(i);
+ }
+ for (int i = 0; i < n; i++) {
+ EXPECT_THAT(array[i].get(), i);
+ EXPECT_THAT(array.data()[i].get(), i);
+ }
+
+ // Test data()
+ for (int i = 0; i < n; i++) {
+ array.data()[i].set(i + 1);
+ }
+ for (int i = 0; i < n; i++) {
+ EXPECT_THAT(array[i].get(), i+1);
+ EXPECT_THAT(array.data()[i].get(), i+1);
+ }
+ } // Close scope containing 'array'.
+
+ // Check that all constructed elements were destructed.
+ EXPECT_EQ(ConstructionTester::constructions,
+ ConstructionTester::destructions);
+}
+
+template <int elements_per_inner_array, int inline_elements>
+static void TestArrayOfArrays(int n) {
+ SCOPED_TRACE(n);
+ SCOPED_TRACE(inline_elements);
+ SCOPED_TRACE(elements_per_inner_array);
+ ConstructionTester::constructions = 0;
+ ConstructionTester::destructions = 0;
+ {
+ using InnerArray = ConstructionTester[elements_per_inner_array];
+ // Heap-allocate the FixedArray to avoid blowing the stack frame.
+ auto array_ptr =
+ absl::make_unique<absl::FixedArray<InnerArray, inline_elements>>(n);
+ auto& array = *array_ptr;
+
+ ASSERT_EQ(array.size(), n);
+ ASSERT_EQ(array.memsize(),
+ sizeof(ConstructionTester) * elements_per_inner_array * n);
+ ASSERT_EQ(array.begin() + n, array.end());
+
+ // Check that all elements were constructed
+ for (int i = 0; i < n; i++) {
+ for (int j = 0; j < elements_per_inner_array; j++) {
+ (array[i])[j].CheckConstructed();
+ }
+ }
+ // Check that no other elements were constructed
+ ASSERT_EQ(ConstructionTester::constructions, n * elements_per_inner_array);
+
+ // Test operator[]
+ for (int i = 0; i < n; i++) {
+ for (int j = 0; j < elements_per_inner_array; j++) {
+ (array[i])[j].set(i * elements_per_inner_array + j);
+ }
+ }
+ for (int i = 0; i < n; i++) {
+ for (int j = 0; j < elements_per_inner_array; j++) {
+ ASSERT_EQ((array[i])[j].get(), i * elements_per_inner_array + j);
+ ASSERT_EQ((array.data()[i])[j].get(), i * elements_per_inner_array + j);
+ }
+ }
+
+ // Test data()
+ for (int i = 0; i < n; i++) {
+ for (int j = 0; j < elements_per_inner_array; j++) {
+ (array.data()[i])[j].set((i + 1) * elements_per_inner_array + j);
+ }
+ }
+ for (int i = 0; i < n; i++) {
+ for (int j = 0; j < elements_per_inner_array; j++) {
+ ASSERT_EQ((array[i])[j].get(),
+ (i + 1) * elements_per_inner_array + j);
+ ASSERT_EQ((array.data()[i])[j].get(),
+ (i + 1) * elements_per_inner_array + j);
+ }
+ }
+ } // Close scope containing 'array'.
+
+ // Check that all constructed elements were destructed.
+ EXPECT_EQ(ConstructionTester::constructions,
+ ConstructionTester::destructions);
+}
+
+TEST(IteratorConstructorTest, NonInline) {
+ int const kInput[] = { 2, 3, 5, 7, 11, 13, 17 };
+ absl::FixedArray<int, ABSL_ARRAYSIZE(kInput) - 1> const fixed(
+ kInput, kInput + ABSL_ARRAYSIZE(kInput));
+ ASSERT_EQ(ABSL_ARRAYSIZE(kInput), fixed.size());
+ for (size_t i = 0; i < ABSL_ARRAYSIZE(kInput); ++i) {
+ ASSERT_EQ(kInput[i], fixed[i]);
+ }
+}
+
+TEST(IteratorConstructorTest, Inline) {
+ int const kInput[] = { 2, 3, 5, 7, 11, 13, 17 };
+ absl::FixedArray<int, ABSL_ARRAYSIZE(kInput)> const fixed(
+ kInput, kInput + ABSL_ARRAYSIZE(kInput));
+ ASSERT_EQ(ABSL_ARRAYSIZE(kInput), fixed.size());
+ for (size_t i = 0; i < ABSL_ARRAYSIZE(kInput); ++i) {
+ ASSERT_EQ(kInput[i], fixed[i]);
+ }
+}
+
+TEST(IteratorConstructorTest, NonPod) {
+ char const* kInput[] =
+ { "red", "orange", "yellow", "green", "blue", "indigo", "violet" };
+ absl::FixedArray<std::string> const fixed(kInput, kInput + ABSL_ARRAYSIZE(kInput));
+ ASSERT_EQ(ABSL_ARRAYSIZE(kInput), fixed.size());
+ for (size_t i = 0; i < ABSL_ARRAYSIZE(kInput); ++i) {
+ ASSERT_EQ(kInput[i], fixed[i]);
+ }
+}
+
+TEST(IteratorConstructorTest, FromEmptyVector) {
+ std::vector<int> const empty;
+ absl::FixedArray<int> const fixed(empty.begin(), empty.end());
+ EXPECT_EQ(0, fixed.size());
+ EXPECT_EQ(empty.size(), fixed.size());
+}
+
+TEST(IteratorConstructorTest, FromNonEmptyVector) {
+ int const kInput[] = { 2, 3, 5, 7, 11, 13, 17 };
+ std::vector<int> const items(kInput, kInput + ABSL_ARRAYSIZE(kInput));
+ absl::FixedArray<int> const fixed(items.begin(), items.end());
+ ASSERT_EQ(items.size(), fixed.size());
+ for (size_t i = 0; i < items.size(); ++i) {
+ ASSERT_EQ(items[i], fixed[i]);
+ }
+}
+
+TEST(IteratorConstructorTest, FromBidirectionalIteratorRange) {
+ int const kInput[] = { 2, 3, 5, 7, 11, 13, 17 };
+ std::list<int> const items(kInput, kInput + ABSL_ARRAYSIZE(kInput));
+ absl::FixedArray<int> const fixed(items.begin(), items.end());
+ EXPECT_THAT(fixed, testing::ElementsAreArray(kInput));
+}
+
+TEST(InitListConstructorTest, InitListConstruction) {
+ absl::FixedArray<int> fixed = {1, 2, 3};
+ EXPECT_THAT(fixed, testing::ElementsAreArray({1, 2, 3}));
+}
+
+TEST(FillConstructorTest, NonEmptyArrays) {
+ absl::FixedArray<int> stack_array(4, 1);
+ EXPECT_THAT(stack_array, testing::ElementsAreArray({1, 1, 1, 1}));
+
+ absl::FixedArray<int, 0> heap_array(4, 1);
+ EXPECT_THAT(stack_array, testing::ElementsAreArray({1, 1, 1, 1}));
+}
+
+TEST(FillConstructorTest, EmptyArray) {
+ absl::FixedArray<int> empty_fill(0, 1);
+ absl::FixedArray<int> empty_size(0);
+ EXPECT_EQ(empty_fill, empty_size);
+}
+
+TEST(FillConstructorTest, NotTriviallyCopyable) {
+ std::string str = "abcd";
+ absl::FixedArray<std::string> strings = {str, str, str, str};
+
+ absl::FixedArray<std::string> array(4, str);
+ EXPECT_EQ(array, strings);
+}
+
+TEST(FillConstructorTest, Disambiguation) {
+ absl::FixedArray<size_t> a(1, 2);
+ EXPECT_THAT(a, testing::ElementsAre(2));
+}
+
+TEST(FixedArrayTest, ManySizedArrays) {
+ std::vector<int> sizes;
+ for (int i = 1; i < 100; i++) sizes.push_back(i);
+ for (int i = 100; i <= 1000; i += 100) sizes.push_back(i);
+ for (int n : sizes) {
+ TestArray<0>(n);
+ TestArray<1>(n);
+ TestArray<64>(n);
+ TestArray<1000>(n);
+ }
+}
+
+TEST(FixedArrayTest, ManySizedArraysOfArraysOf1) {
+ for (int n = 1; n < 1000; n++) {
+ ASSERT_NO_FATAL_FAILURE((TestArrayOfArrays<1, 0>(n)));
+ ASSERT_NO_FATAL_FAILURE((TestArrayOfArrays<1, 1>(n)));
+ ASSERT_NO_FATAL_FAILURE((TestArrayOfArrays<1, 64>(n)));
+ ASSERT_NO_FATAL_FAILURE((TestArrayOfArrays<1, 1000>(n)));
+ }
+}
+
+TEST(FixedArrayTest, ManySizedArraysOfArraysOf2) {
+ for (int n = 1; n < 1000; n++) {
+ TestArrayOfArrays<2, 0>(n);
+ TestArrayOfArrays<2, 1>(n);
+ TestArrayOfArrays<2, 64>(n);
+ TestArrayOfArrays<2, 1000>(n);
+ }
+}
+
+// If value_type is put inside of a struct container,
+// we might evoke this error in a hardened build unless data() is carefully
+// written, so check on that.
+// error: call to int __builtin___sprintf_chk(etc...)
+// will always overflow destination buffer [-Werror]
+TEST(FixedArrayTest, AvoidParanoidDiagnostics) {
+ absl::FixedArray<char, 32> buf(32);
+ sprintf(buf.data(), "foo"); // NOLINT(runtime/printf)
+}
+
+TEST(FixedArrayTest, TooBigInlinedSpace) {
+ struct TooBig {
+ char c[1 << 20];
+ }; // too big for even one on the stack
+
+ // Simulate the data members of absl::FixedArray, a pointer and a size_t.
+ struct Data {
+ TooBig* p;
+ size_t size;
+ };
+
+ // Make sure TooBig objects are not inlined for 0 or default size.
+ static_assert(sizeof(absl::FixedArray<TooBig, 0>) == sizeof(Data),
+ "0-sized absl::FixedArray should have same size as Data.");
+ static_assert(alignof(absl::FixedArray<TooBig, 0>) == alignof(Data),
+ "0-sized absl::FixedArray should have same alignment as Data.");
+ static_assert(sizeof(absl::FixedArray<TooBig>) == sizeof(Data),
+ "default-sized absl::FixedArray should have same size as Data");
+ static_assert(
+ alignof(absl::FixedArray<TooBig>) == alignof(Data),
+ "default-sized absl::FixedArray should have same alignment as Data.");
+}
+
+// PickyDelete EXPECTs its class-scope deallocation funcs are unused.
+struct PickyDelete {
+ PickyDelete() {}
+ ~PickyDelete() {}
+ void operator delete(void* p) {
+ EXPECT_TRUE(false) << __FUNCTION__;
+ ::operator delete(p);
+ }
+ void operator delete[](void* p) {
+ EXPECT_TRUE(false) << __FUNCTION__;
+ ::operator delete[](p);
+ }
+};
+
+TEST(FixedArrayTest, UsesGlobalAlloc) { absl::FixedArray<PickyDelete, 0> a(5); }
+
+
+TEST(FixedArrayTest, Data) {
+ static const int kInput[] = { 2, 3, 5, 7, 11, 13, 17 };
+ absl::FixedArray<int> fa(std::begin(kInput), std::end(kInput));
+ EXPECT_EQ(fa.data(), &*fa.begin());
+ EXPECT_EQ(fa.data(), &fa[0]);
+
+ const absl::FixedArray<int>& cfa = fa;
+ EXPECT_EQ(cfa.data(), &*cfa.begin());
+ EXPECT_EQ(cfa.data(), &cfa[0]);
+}
+
+TEST(FixedArrayTest, Empty) {
+ absl::FixedArray<int> empty(0);
+ absl::FixedArray<int> inline_filled(1);
+ absl::FixedArray<int, 0> heap_filled(1);
+ EXPECT_TRUE(empty.empty());
+ EXPECT_FALSE(inline_filled.empty());
+ EXPECT_FALSE(heap_filled.empty());
+}
+
+TEST(FixedArrayTest, FrontAndBack) {
+ absl::FixedArray<int, 3 * sizeof(int)> inlined = {1, 2, 3};
+ EXPECT_EQ(inlined.front(), 1);
+ EXPECT_EQ(inlined.back(), 3);
+
+ absl::FixedArray<int, 0> allocated = {1, 2, 3};
+ EXPECT_EQ(allocated.front(), 1);
+ EXPECT_EQ(allocated.back(), 3);
+
+ absl::FixedArray<int> one_element = {1};
+ EXPECT_EQ(one_element.front(), one_element.back());
+}
+
+TEST(FixedArrayTest, ReverseIteratorInlined) {
+ absl::FixedArray<int, 5 * sizeof(int)> a = {0, 1, 2, 3, 4};
+
+ int counter = 5;
+ for (absl::FixedArray<int>::reverse_iterator iter = a.rbegin();
+ iter != a.rend(); ++iter) {
+ counter--;
+ EXPECT_EQ(counter, *iter);
+ }
+ EXPECT_EQ(counter, 0);
+
+ counter = 5;
+ for (absl::FixedArray<int>::const_reverse_iterator iter = a.rbegin();
+ iter != a.rend(); ++iter) {
+ counter--;
+ EXPECT_EQ(counter, *iter);
+ }
+ EXPECT_EQ(counter, 0);
+
+ counter = 5;
+ for (auto iter = a.crbegin(); iter != a.crend(); ++iter) {
+ counter--;
+ EXPECT_EQ(counter, *iter);
+ }
+ EXPECT_EQ(counter, 0);
+}
+
+TEST(FixedArrayTest, ReverseIteratorAllocated) {
+ absl::FixedArray<int, 0> a = {0, 1, 2, 3, 4};
+
+ int counter = 5;
+ for (absl::FixedArray<int>::reverse_iterator iter = a.rbegin();
+ iter != a.rend(); ++iter) {
+ counter--;
+ EXPECT_EQ(counter, *iter);
+ }
+ EXPECT_EQ(counter, 0);
+
+ counter = 5;
+ for (absl::FixedArray<int>::const_reverse_iterator iter = a.rbegin();
+ iter != a.rend(); ++iter) {
+ counter--;
+ EXPECT_EQ(counter, *iter);
+ }
+ EXPECT_EQ(counter, 0);
+
+ counter = 5;
+ for (auto iter = a.crbegin(); iter != a.crend(); ++iter) {
+ counter--;
+ EXPECT_EQ(counter, *iter);
+ }
+ EXPECT_EQ(counter, 0);
+}
+
+TEST(FixedArrayTest, Fill) {
+ absl::FixedArray<int, 5 * sizeof(int)> inlined(5);
+ int fill_val = 42;
+ inlined.fill(fill_val);
+ for (int i : inlined) EXPECT_EQ(i, fill_val);
+
+ absl::FixedArray<int, 0> allocated(5);
+ allocated.fill(fill_val);
+ for (int i : allocated) EXPECT_EQ(i, fill_val);
+
+ // It doesn't do anything, just make sure this compiles.
+ absl::FixedArray<int> empty(0);
+ empty.fill(fill_val);
+}
+
+#ifdef ADDRESS_SANITIZER
+TEST(FixedArrayTest, AddressSanitizerAnnotations1) {
+ absl::FixedArray<int, 32> a(10);
+ int *raw = a.data();
+ raw[0] = 0;
+ raw[9] = 0;
+ EXPECT_DEATH(raw[-2] = 0, "container-overflow");
+ EXPECT_DEATH(raw[-1] = 0, "container-overflow");
+ EXPECT_DEATH(raw[10] = 0, "container-overflow");
+ EXPECT_DEATH(raw[31] = 0, "container-overflow");
+}
+
+TEST(FixedArrayTest, AddressSanitizerAnnotations2) {
+ absl::FixedArray<char, 17> a(12);
+ char *raw = a.data();
+ raw[0] = 0;
+ raw[11] = 0;
+ EXPECT_DEATH(raw[-7] = 0, "container-overflow");
+ EXPECT_DEATH(raw[-1] = 0, "container-overflow");
+ EXPECT_DEATH(raw[12] = 0, "container-overflow");
+ EXPECT_DEATH(raw[17] = 0, "container-overflow");
+}
+
+TEST(FixedArrayTest, AddressSanitizerAnnotations3) {
+ absl::FixedArray<uint64_t, 20> a(20);
+ uint64_t *raw = a.data();
+ raw[0] = 0;
+ raw[19] = 0;
+ EXPECT_DEATH(raw[-1] = 0, "container-overflow");
+ EXPECT_DEATH(raw[20] = 0, "container-overflow");
+}
+
+TEST(FixedArrayTest, AddressSanitizerAnnotations4) {
+ absl::FixedArray<ThreeInts> a(10);
+ ThreeInts *raw = a.data();
+ raw[0] = ThreeInts();
+ raw[9] = ThreeInts();
+ // Note: raw[-1] is pointing to 12 bytes before the container range. However,
+ // there is only a 8-byte red zone before the container range, so we only
+ // access the last 4 bytes of the struct to make sure it stays within the red
+ // zone.
+ EXPECT_DEATH(raw[-1].z_ = 0, "container-overflow");
+ EXPECT_DEATH(raw[10] = ThreeInts(), "container-overflow");
+ // The actual size of storage is kDefaultBytes=256, 21*12 = 252,
+ // so reading raw[21] should still trigger the correct warning.
+ EXPECT_DEATH(raw[21] = ThreeInts(), "container-overflow");
+}
+#endif // ADDRESS_SANITIZER
+
+} // namespace
http://git-wip-us.apache.org/repos/asf/marmotta/blob/0eb556da/libraries/ostrich/backend/3rdparty/abseil/absl/container/inlined_vector.h
----------------------------------------------------------------------
diff --git a/libraries/ostrich/backend/3rdparty/abseil/absl/container/inlined_vector.h b/libraries/ostrich/backend/3rdparty/abseil/absl/container/inlined_vector.h
new file mode 100644
index 0000000..78f78ea
--- /dev/null
+++ b/libraries/ostrich/backend/3rdparty/abseil/absl/container/inlined_vector.h
@@ -0,0 +1,1384 @@
+// Copyright 2017 The Abseil Authors.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+//
+// -----------------------------------------------------------------------------
+// File: inlined_vector.h
+// -----------------------------------------------------------------------------
+//
+// This header file contains the declaration and definition of an "inlined
+// vector" which behaves in an equivalent fashion to a `std::vector`, except
+// that storage for small sequences of the vector are provided inline without
+// requiring any heap allocation.
+
+// An `absl::InlinedVector<T,N>` specifies the size N at which to inline as one
+// of its template parameters. Vectors of length <= N are provided inline.
+// Typically N is very small (e.g., 4) so that sequences that are expected to be
+// short do not require allocations.
+
+// An `absl::InlinedVector` does not usually require a specific allocator; if
+// the inlined vector grows beyond its initial constraints, it will need to
+// allocate (as any normal `std::vector` would) and it will generally use the
+// default allocator in that case; optionally, a custom allocator may be
+// specified using an `absl::InlinedVector<T,N,A>` construction.
+
+#ifndef ABSL_CONTAINER_INLINED_VECTOR_H_
+#define ABSL_CONTAINER_INLINED_VECTOR_H_
+
+#include <algorithm>
+#include <cassert>
+#include <cstddef>
+#include <cstdlib>
+#include <cstring>
+#include <initializer_list>
+#include <iterator>
+#include <memory>
+#include <type_traits>
+#include <utility>
+
+#include "absl/algorithm/algorithm.h"
+#include "absl/base/internal/throw_delegate.h"
+#include "absl/base/optimization.h"
+#include "absl/base/port.h"
+#include "absl/memory/memory.h"
+
+namespace absl {
+
+// -----------------------------------------------------------------------------
+// InlinedVector
+// -----------------------------------------------------------------------------
+//
+// An `absl::InlinedVector` is designed to be a drop-in replacement for
+// `std::vector` for use cases where the vector's size is sufficiently small
+// that it can be inlined. If the inlined vector does grow beyond its estimated
+// size, it will trigger an initial allocation on the heap, and will behave as a
+// `std:vector`. The API of the `absl::InlinedVector` within this file is
+// designed to cover the same API footprint as covered by `std::vector`.
+template <typename T, size_t N, typename A = std::allocator<T> >
+class InlinedVector {
+ using AllocatorTraits = std::allocator_traits<A>;
+
+ public:
+ using allocator_type = A;
+ using value_type = typename allocator_type::value_type;
+ using pointer = typename allocator_type::pointer;
+ using const_pointer = typename allocator_type::const_pointer;
+ using reference = typename allocator_type::reference;
+ using const_reference = typename allocator_type::const_reference;
+ using size_type = typename allocator_type::size_type;
+ using difference_type = typename allocator_type::difference_type;
+ using iterator = pointer;
+ using const_iterator = const_pointer;
+ using reverse_iterator = std::reverse_iterator<iterator>;
+ using const_reverse_iterator = std::reverse_iterator<const_iterator>;
+
+ InlinedVector() noexcept(noexcept(allocator_type()))
+ : allocator_and_tag_(allocator_type()) {}
+
+ explicit InlinedVector(const allocator_type& alloc) noexcept
+ : allocator_and_tag_(alloc) {}
+
+ // Create a vector with n copies of value_type().
+ explicit InlinedVector(size_type n) : allocator_and_tag_(allocator_type()) {
+ InitAssign(n);
+ }
+
+ // Create a vector with n copies of elem
+ InlinedVector(size_type n, const value_type& elem,
+ const allocator_type& alloc = allocator_type())
+ : allocator_and_tag_(alloc) {
+ InitAssign(n, elem);
+ }
+
+ // Create and initialize with the elements [first .. last).
+ // The unused enable_if argument restricts this constructor so that it is
+ // elided when value_type is an integral type. This prevents ambiguous
+ // interpretation between a call to this constructor with two integral
+ // arguments and a call to the preceding (n, elem) constructor.
+ template <typename InputIterator>
+ InlinedVector(
+ InputIterator first, InputIterator last,
+ const allocator_type& alloc = allocator_type(),
+ typename std::enable_if<!std::is_integral<InputIterator>::value>::type* =
+ nullptr)
+ : allocator_and_tag_(alloc) {
+ AppendRange(first, last);
+ }
+
+ InlinedVector(std::initializer_list<value_type> init,
+ const allocator_type& alloc = allocator_type())
+ : allocator_and_tag_(alloc) {
+ AppendRange(init.begin(), init.end());
+ }
+
+ InlinedVector(const InlinedVector& v);
+ InlinedVector(const InlinedVector& v, const allocator_type& alloc);
+
+ // This move constructor does not allocate and only moves the underlying
+ // objects, so its `noexcept` specification depends on whether moving the
+ // underlying objects can throw or not. We assume
+ // a) move constructors should only throw due to allocation failure and
+ // b) if `value_type`'s move constructor allocates, it uses the same
+ // allocation function as the `InlinedVector`'s allocator, so the move
+ // constructor is non-throwing if the allocator is non-throwing or
+ // `value_type`'s move constructor is specified as `noexcept`.
+ InlinedVector(InlinedVector&& v) noexcept(
+ absl::allocator_is_nothrow<allocator_type>::value ||
+ std::is_nothrow_move_constructible<value_type>::value);
+
+ // This move constructor allocates and also moves the underlying objects, so
+ // its `noexcept` specification depends on whether the allocation can throw
+ // and whether moving the underlying objects can throw. Based on the same
+ // assumptions above, the `noexcept` specification is dominated by whether the
+ // allocation can throw regardless of whether `value_type`'s move constructor
+ // is specified as `noexcept`.
+ InlinedVector(InlinedVector&& v, const allocator_type& alloc) noexcept(
+ absl::allocator_is_nothrow<allocator_type>::value);
+
+ ~InlinedVector() { clear(); }
+
+ InlinedVector& operator=(const InlinedVector& v) {
+ if (this == &v) {
+ return *this;
+ }
+ // Optimized to avoid reallocation.
+ // Prefer reassignment to copy construction for elements.
+ if (size() < v.size()) { // grow
+ reserve(v.size());
+ std::copy(v.begin(), v.begin() + size(), begin());
+ std::copy(v.begin() + size(), v.end(), std::back_inserter(*this));
+ } else { // maybe shrink
+ erase(begin() + v.size(), end());
+ std::copy(v.begin(), v.end(), begin());
+ }
+ return *this;
+ }
+
+ InlinedVector& operator=(InlinedVector&& v) {
+ if (this == &v) {
+ return *this;
+ }
+ if (v.allocated()) {
+ clear();
+ tag().set_allocated_size(v.size());
+ init_allocation(v.allocation());
+ v.tag() = Tag();
+ } else {
+ if (allocated()) clear();
+ // Both are inlined now.
+ if (size() < v.size()) {
+ auto mid = std::make_move_iterator(v.begin() + size());
+ std::copy(std::make_move_iterator(v.begin()), mid, begin());
+ UninitializedCopy(mid, std::make_move_iterator(v.end()), end());
+ } else {
+ auto new_end = std::copy(std::make_move_iterator(v.begin()),
+ std::make_move_iterator(v.end()), begin());
+ Destroy(new_end, end());
+ }
+ tag().set_inline_size(v.size());
+ }
+ return *this;
+ }
+
+ InlinedVector& operator=(std::initializer_list<value_type> init) {
+ AssignRange(init.begin(), init.end());
+ return *this;
+ }
+
+ // InlinedVector::assign()
+ //
+ // Replaces the contents of the inlined vector with copies of those in the
+ // iterator range [first, last).
+ template <typename InputIterator>
+ void assign(
+ InputIterator first, InputIterator last,
+ typename std::enable_if<!std::is_integral<InputIterator>::value>::type* =
+ nullptr) {
+ AssignRange(first, last);
+ }
+
+ // Overload of `InlinedVector::assign()` to take values from elements of an
+ // initializer list
+ void assign(std::initializer_list<value_type> init) {
+ AssignRange(init.begin(), init.end());
+ }
+
+ // Overload of `InlinedVector::assign()` to replace the first `n` elements of
+ // the inlined vector with `elem` values.
+ void assign(size_type n, const value_type& elem) {
+ if (n <= size()) { // Possibly shrink
+ std::fill_n(begin(), n, elem);
+ erase(begin() + n, end());
+ return;
+ }
+ // Grow
+ reserve(n);
+ std::fill_n(begin(), size(), elem);
+ if (allocated()) {
+ UninitializedFill(allocated_space() + size(), allocated_space() + n,
+ elem);
+ tag().set_allocated_size(n);
+ } else {
+ UninitializedFill(inlined_space() + size(), inlined_space() + n, elem);
+ tag().set_inline_size(n);
+ }
+ }
+
+ // InlinedVector::size()
+ //
+ // Returns the number of elements in the inlined vector.
+ size_type size() const noexcept { return tag().size(); }
+
+ // InlinedVector::empty()
+ //
+ // Checks if the inlined vector has no elements.
+ bool empty() const noexcept { return (size() == 0); }
+
+ // InlinedVector::capacity()
+ //
+ // Returns the number of elements that can be stored in an inlined vector
+ // without requiring a reallocation of underlying memory. Note that for
+ // most inlined vectors, `capacity()` should equal its initial size `N`; for
+ // inlined vectors which exceed this capacity, they will no longer be inlined,
+ // and `capacity()` will equal its capacity on the allocated heap.
+ size_type capacity() const noexcept {
+ return allocated() ? allocation().capacity() : N;
+ }
+
+ // InlinedVector::max_size()
+ //
+ // Returns the maximum number of elements the vector can hold.
+ size_type max_size() const noexcept {
+ // One bit of the size storage is used to indicate whether the inlined
+ // vector is allocated; as a result, the maximum size of the container that
+ // we can express is half of the max for our size type.
+ return std::numeric_limits<size_type>::max() / 2;
+ }
+
+ // InlinedVector::data()
+ //
+ // Returns a const T* pointer to elements of the inlined vector. This pointer
+ // can be used to access (but not modify) the contained elements.
+ // Only results within the range `[0,size())` are defined.
+ const_pointer data() const noexcept {
+ return allocated() ? allocated_space() : inlined_space();
+ }
+
+ // Overload of InlinedVector::data() to return a T* pointer to elements of the
+ // inlined vector. This pointer can be used to access and modify the contained
+ // elements.
+ pointer data() noexcept {
+ return allocated() ? allocated_space() : inlined_space();
+ }
+
+ // InlinedVector::clear()
+ //
+ // Removes all elements from the inlined vector.
+ void clear() noexcept {
+ size_type s = size();
+ if (allocated()) {
+ Destroy(allocated_space(), allocated_space() + s);
+ allocation().Dealloc(allocator());
+ } else if (s != 0) { // do nothing for empty vectors
+ Destroy(inlined_space(), inlined_space() + s);
+ }
+ tag() = Tag();
+ }
+
+ // InlinedVector::at()
+ //
+ // Returns the ith element of an inlined vector.
+ const value_type& at(size_type i) const {
+ if (ABSL_PREDICT_FALSE(i >= size())) {
+ base_internal::ThrowStdOutOfRange(
+ "InlinedVector::at failed bounds check");
+ }
+ return data()[i];
+ }
+
+ // InlinedVector::operator[]
+ //
+ // Returns the ith element of an inlined vector using the array operator.
+ const value_type& operator[](size_type i) const {
+ assert(i < size());
+ return data()[i];
+ }
+
+ // Overload of InlinedVector::at() to return the ith element of an inlined
+ // vector.
+ value_type& at(size_type i) {
+ if (i >= size()) {
+ base_internal::ThrowStdOutOfRange(
+ "InlinedVector::at failed bounds check");
+ }
+ return data()[i];
+ }
+
+ // Overload of InlinedVector::operator[] to return the ith element of an
+ // inlined vector.
+ value_type& operator[](size_type i) {
+ assert(i < size());
+ return data()[i];
+ }
+
+ // InlinedVector::back()
+ //
+ // Returns a reference to the last element of an inlined vector.
+ value_type& back() {
+ assert(!empty());
+ return at(size() - 1);
+ }
+
+ // Overload of InlinedVector::back() returns a reference to the last element
+ // of an inlined vector of const values.
+ const value_type& back() const {
+ assert(!empty());
+ return at(size() - 1);
+ }
+
+ // InlinedVector::front()
+ //
+ // Returns a reference to the first element of an inlined vector.
+ value_type& front() {
+ assert(!empty());
+ return at(0);
+ }
+
+ // Overload of InlinedVector::front() returns a reference to the first element
+ // of an inlined vector of const values.
+ const value_type& front() const {
+ assert(!empty());
+ return at(0);
+ }
+
+ // InlinedVector::emplace_back()
+ //
+ // Constructs and appends an object to the inlined vector.
+ //
+ // Returns a reference to the inserted element.
+ template <typename... Args>
+ value_type& emplace_back(Args&&... args) {
+ size_type s = size();
+ assert(s <= capacity());
+ if (ABSL_PREDICT_FALSE(s == capacity())) {
+ return GrowAndEmplaceBack(std::forward<Args>(args)...);
+ }
+ assert(s < capacity());
+
+ value_type* space;
+ if (allocated()) {
+ tag().set_allocated_size(s + 1);
+ space = allocated_space();
+ } else {
+ tag().set_inline_size(s + 1);
+ space = inlined_space();
+ }
+ return Construct(space + s, std::forward<Args>(args)...);
+ }
+
+ // InlinedVector::push_back()
+ //
+ // Appends a const element to the inlined vector.
+ void push_back(const value_type& t) { emplace_back(t); }
+
+ // Overload of InlinedVector::push_back() to append a move-only element to the
+ // inlined vector.
+ void push_back(value_type&& t) { emplace_back(std::move(t)); }
+
+ // InlinedVector::pop_back()
+ //
+ // Removes the last element (which is destroyed) in the inlined vector.
+ void pop_back() {
+ assert(!empty());
+ size_type s = size();
+ if (allocated()) {
+ Destroy(allocated_space() + s - 1, allocated_space() + s);
+ tag().set_allocated_size(s - 1);
+ } else {
+ Destroy(inlined_space() + s - 1, inlined_space() + s);
+ tag().set_inline_size(s - 1);
+ }
+ }
+
+ // InlinedVector::resize()
+ //
+ // Resizes the inlined vector to contain `n` elements. If `n` is smaller than
+ // the inlined vector's current size, extra elements are destroyed. If `n` is
+ // larger than the initial size, new elements are value-initialized.
+ void resize(size_type n);
+
+ // Overload of InlinedVector::resize() to resize the inlined vector to contain
+ // `n` elements. If `n` is larger than the current size, enough copies of
+ // `elem` are appended to increase its size to `n`.
+ void resize(size_type n, const value_type& elem);
+
+ // InlinedVector::begin()
+ //
+ // Returns an iterator to the beginning of the inlined vector.
+ iterator begin() noexcept { return data(); }
+
+ // Overload of InlinedVector::begin() for returning a const iterator to the
+ // beginning of the inlined vector.
+ const_iterator begin() const noexcept { return data(); }
+
+ // InlinedVector::cbegin()
+ //
+ // Returns a const iterator to the beginning of the inlined vector.
+ const_iterator cbegin() const noexcept { return begin(); }
+
+ // InlinedVector::end()
+ //
+ // Returns an iterator to the end of the inlined vector.
+ iterator end() noexcept { return data() + size(); }
+
+ // Overload of InlinedVector::end() for returning a const iterator to the end
+ // of the inlined vector.
+ const_iterator end() const noexcept { return data() + size(); }
+
+ // InlinedVector::cend()
+ //
+ // Returns a const iterator to the end of the inlined vector.
+ const_iterator cend() const noexcept { return end(); }
+
+ // InlinedVector::rbegin()
+ //
+ // Returns a reverse iterator from the end of the inlined vector.
+ reverse_iterator rbegin() noexcept { return reverse_iterator(end()); }
+
+ // Overload of InlinedVector::rbegin() for returning a const reverse iterator
+ // from the end of the inlined vector.
+ const_reverse_iterator rbegin() const noexcept {
+ return const_reverse_iterator(end());
+ }
+
+ // InlinedVector::crbegin()
+ //
+ // Returns a const reverse iterator from the end of the inlined vector.
+ const_reverse_iterator crbegin() const noexcept { return rbegin(); }
+
+ // InlinedVector::rend()
+ //
+ // Returns a reverse iterator from the beginning of the inlined vector.
+ reverse_iterator rend() noexcept { return reverse_iterator(begin()); }
+
+ // Overload of InlinedVector::rend() for returning a const reverse iterator
+ // from the beginning of the inlined vector.
+ const_reverse_iterator rend() const noexcept {
+ return const_reverse_iterator(begin());
+ }
+
+ // InlinedVector::crend()
+ //
+ // Returns a reverse iterator from the beginning of the inlined vector.
+ const_reverse_iterator crend() const noexcept { return rend(); }
+
+ // InlinedVector::emplace()
+ //
+ // Constructs and inserts an object to the inlined vector at the given
+ // `position`, returning an iterator pointing to the newly emplaced element.
+ template <typename... Args>
+ iterator emplace(const_iterator position, Args&&... args);
+
+ // InlinedVector::insert()
+ //
+ // Inserts an element of the specified value at `position`, returning an
+ // iterator pointing to the newly inserted element.
+ iterator insert(const_iterator position, const value_type& v) {
+ return emplace(position, v);
+ }
+
+ // Overload of InlinedVector::insert() for inserting an element of the
+ // specified rvalue, returning an iterator pointing to the newly inserted
+ // element.
+ iterator insert(const_iterator position, value_type&& v) {
+ return emplace(position, std::move(v));
+ }
+
+ // Overload of InlinedVector::insert() for inserting `n` elements of the
+ // specified value at `position`, returning an iterator pointing to the first
+ // of the newly inserted elements.
+ iterator insert(const_iterator position, size_type n, const value_type& v) {
+ return InsertWithCount(position, n, v);
+ }
+
+ // Overload of `InlinedVector::insert()` to disambiguate the two
+ // three-argument overloads of `insert()`, returning an iterator pointing to
+ // the first of the newly inserted elements.
+ template <typename InputIterator,
+ typename = typename std::enable_if<std::is_convertible<
+ typename std::iterator_traits<InputIterator>::iterator_category,
+ std::input_iterator_tag>::value>::type>
+ iterator insert(const_iterator position, InputIterator first,
+ InputIterator last) {
+ using IterType =
+ typename std::iterator_traits<InputIterator>::iterator_category;
+ return InsertWithRange(position, first, last, IterType());
+ }
+
+ // Overload of InlinedVector::insert() for inserting a list of elements at
+ // `position`, returning an iterator pointing to the first of the newly
+ // inserted elements.
+ iterator insert(const_iterator position,
+ std::initializer_list<value_type> init) {
+ return insert(position, init.begin(), init.end());
+ }
+
+ // InlinedVector::erase()
+ //
+ // Erases the element at `position` of the inlined vector, returning an
+ // iterator pointing to the following element or the container's end if the
+ // last element was erased.
+ iterator erase(const_iterator position) {
+ assert(position >= begin());
+ assert(position < end());
+
+ iterator pos = const_cast<iterator>(position);
+ std::move(pos + 1, end(), pos);
+ pop_back();
+ return pos;
+ }
+
+ // Overload of InlinedVector::erase() for erasing all elements in the
+ // iterator range [first, last) in the inlined vector, returning an iterator
+ // pointing to the first element following the range erased, or the
+ // container's end if range included the container's last element.
+ iterator erase(const_iterator first, const_iterator last);
+
+ // InlinedVector::reserve()
+ //
+ // Enlarges the underlying representation of the inlined vector so it can hold
+ // at least `n` elements. This method does not change `size()` or the actual
+ // contents of the vector.
+ //
+ // Note that if `n` does not exceed the inlined vector's initial size `N`,
+ // `reserve()` will have no effect; if it does exceed its initial size,
+ // `reserve()` will trigger an initial allocation and move the inlined vector
+ // onto the heap. If the vector already exists on the heap and the requested
+ // size exceeds it, a reallocation will be performed.
+ void reserve(size_type n) {
+ if (n > capacity()) {
+ // Make room for new elements
+ EnlargeBy(n - size());
+ }
+ }
+
+ // InlinedVector::shrink_to_fit()
+ //
+ // Reduces memory usage by freeing unused memory.
+ // After this call `capacity()` will be equal to `max(N, size())`.
+ //
+ // If `size() <= N` and the elements are currently stored on the heap, they
+ // will be moved to the inlined storage and the heap memory deallocated.
+ // If `size() > N` and `size() < capacity()` the elements will be moved to
+ // a reallocated storage on heap.
+ void shrink_to_fit() {
+ const auto s = size();
+ if (!allocated() || s == capacity()) {
+ // There's nothing to deallocate.
+ return;
+ }
+
+ if (s <= N) {
+ // Move the elements to the inlined storage.
+ // We have to do this using a temporary, because inlined_storage and
+ // allocation_storage are in a union field.
+ auto temp = std::move(*this);
+ assign(std::make_move_iterator(temp.begin()),
+ std::make_move_iterator(temp.end()));
+ return;
+ }
+
+ // Reallocate storage and move elements.
+ // We can't simply use the same approach as above, because assign() would
+ // call into reserve() internally and reserve larger capacity than we need.
+ Allocation new_allocation(allocator(), s);
+ UninitializedCopy(std::make_move_iterator(allocated_space()),
+ std::make_move_iterator(allocated_space() + s),
+ new_allocation.buffer());
+ ResetAllocation(new_allocation, s);
+ }
+
+ // InlinedVector::swap()
+ //
+ // Swaps the contents of this inlined vector with the contents of `other`.
+ void swap(InlinedVector& other);
+
+ // InlinedVector::get_allocator()
+ //
+ // Returns the allocator of this inlined vector.
+ allocator_type get_allocator() const { return allocator(); }
+
+ private:
+ static_assert(N > 0, "inlined vector with nonpositive size");
+
+ // It holds whether the vector is allocated or not in the lowest bit.
+ // The size is held in the high bits:
+ // size_ = (size << 1) | is_allocated;
+ class Tag {
+ public:
+ Tag() : size_(0) {}
+ size_type size() const { return size_ >> 1; }
+ void add_size(size_type n) { size_ += n << 1; }
+ void set_inline_size(size_type n) { size_ = n << 1; }
+ void set_allocated_size(size_type n) { size_ = (n << 1) | 1; }
+ bool allocated() const { return size_ & 1; }
+
+ private:
+ size_type size_;
+ };
+
+ // Derives from allocator_type to use the empty base class optimization.
+ // If the allocator_type is stateless, we can 'store'
+ // our instance of it for free.
+ class AllocatorAndTag : private allocator_type {
+ public:
+ explicit AllocatorAndTag(const allocator_type& a, Tag t = Tag())
+ : allocator_type(a), tag_(t) {
+ }
+ Tag& tag() { return tag_; }
+ const Tag& tag() const { return tag_; }
+ allocator_type& allocator() { return *this; }
+ const allocator_type& allocator() const { return *this; }
+ private:
+ Tag tag_;
+ };
+
+ class Allocation {
+ public:
+ Allocation(allocator_type& a, // NOLINT(runtime/references)
+ size_type capacity)
+ : capacity_(capacity),
+ buffer_(AllocatorTraits::allocate(a, capacity_)) {}
+
+ void Dealloc(allocator_type& a) { // NOLINT(runtime/references)
+ AllocatorTraits::deallocate(a, buffer(), capacity());
+ }
+
+ size_type capacity() const { return capacity_; }
+ const value_type* buffer() const { return buffer_; }
+ value_type* buffer() { return buffer_; }
+
+ private:
+ size_type capacity_;
+ value_type* buffer_;
+ };
+
+ const Tag& tag() const { return allocator_and_tag_.tag(); }
+ Tag& tag() { return allocator_and_tag_.tag(); }
+
+ Allocation& allocation() {
+ return reinterpret_cast<Allocation&>(rep_.allocation_storage.allocation);
+ }
+ const Allocation& allocation() const {
+ return reinterpret_cast<const Allocation&>(
+ rep_.allocation_storage.allocation);
+ }
+ void init_allocation(const Allocation& allocation) {
+ new (&rep_.allocation_storage.allocation) Allocation(allocation);
+ }
+
+ value_type* inlined_space() {
+ return reinterpret_cast<value_type*>(&rep_.inlined_storage.inlined);
+ }
+ const value_type* inlined_space() const {
+ return reinterpret_cast<const value_type*>(&rep_.inlined_storage.inlined);
+ }
+
+ value_type* allocated_space() {
+ return allocation().buffer();
+ }
+ const value_type* allocated_space() const {
+ return allocation().buffer();
+ }
+
+ const allocator_type& allocator() const {
+ return allocator_and_tag_.allocator();
+ }
+ allocator_type& allocator() {
+ return allocator_and_tag_.allocator();
+ }
+
+ bool allocated() const { return tag().allocated(); }
+
+ // Enlarge the underlying representation so we can store size_ + delta elems.
+ // The size is not changed, and any newly added memory is not initialized.
+ void EnlargeBy(size_type delta);
+
+ // Shift all elements from position to end() n places to the right.
+ // If the vector needs to be enlarged, memory will be allocated.
+ // Returns iterators pointing to the start of the previously-initialized
+ // portion and the start of the uninitialized portion of the created gap.
+ // The number of initialized spots is pair.second - pair.first;
+ // the number of raw spots is n - (pair.second - pair.first).
+ //
+ // Updates the size of the InlinedVector internally.
+ std::pair<iterator, iterator> ShiftRight(const_iterator position,
+ size_type n);
+
+ void ResetAllocation(Allocation new_allocation, size_type new_size) {
+ if (allocated()) {
+ Destroy(allocated_space(), allocated_space() + size());
+ assert(begin() == allocated_space());
+ allocation().Dealloc(allocator());
+ allocation() = new_allocation;
+ } else {
+ Destroy(inlined_space(), inlined_space() + size());
+ init_allocation(new_allocation); // bug: only init once
+ }
+ tag().set_allocated_size(new_size);
+ }
+
+ template <typename... Args>
+ value_type& GrowAndEmplaceBack(Args&&... args) {
+ assert(size() == capacity());
+ const size_type s = size();
+
+ Allocation new_allocation(allocator(), 2 * capacity());
+
+ value_type& new_element =
+ Construct(new_allocation.buffer() + s, std::forward<Args>(args)...);
+ UninitializedCopy(std::make_move_iterator(data()),
+ std::make_move_iterator(data() + s),
+ new_allocation.buffer());
+
+ ResetAllocation(new_allocation, s + 1);
+
+ return new_element;
+ }
+
+ void InitAssign(size_type n);
+ void InitAssign(size_type n, const value_type& t);
+
+ template <typename... Args>
+ value_type& Construct(pointer p, Args&&... args) {
+ AllocatorTraits::construct(allocator(), p, std::forward<Args>(args)...);
+ return *p;
+ }
+
+ template <typename Iter>
+ void UninitializedCopy(Iter src, Iter src_last, value_type* dst) {
+ for (; src != src_last; ++dst, ++src) Construct(dst, *src);
+ }
+
+ template <typename... Args>
+ void UninitializedFill(value_type* dst, value_type* dst_last,
+ const Args&... args) {
+ for (; dst != dst_last; ++dst) Construct(dst, args...);
+ }
+
+ // Destroy [ptr, ptr_last) in place.
+ void Destroy(value_type* ptr, value_type* ptr_last);
+
+ template <typename Iter>
+ void AppendRange(Iter first, Iter last, std::input_iterator_tag) {
+ std::copy(first, last, std::back_inserter(*this));
+ }
+
+ // Faster path for forward iterators.
+ template <typename Iter>
+ void AppendRange(Iter first, Iter last, std::forward_iterator_tag);
+
+ template <typename Iter>
+ void AppendRange(Iter first, Iter last) {
+ using IterTag = typename std::iterator_traits<Iter>::iterator_category;
+ AppendRange(first, last, IterTag());
+ }
+
+ template <typename Iter>
+ void AssignRange(Iter first, Iter last, std::input_iterator_tag);
+
+ // Faster path for forward iterators.
+ template <typename Iter>
+ void AssignRange(Iter first, Iter last, std::forward_iterator_tag);
+
+ template <typename Iter>
+ void AssignRange(Iter first, Iter last) {
+ using IterTag = typename std::iterator_traits<Iter>::iterator_category;
+ AssignRange(first, last, IterTag());
+ }
+
+ iterator InsertWithCount(const_iterator position, size_type n,
+ const value_type& v);
+
+ template <typename InputIter>
+ iterator InsertWithRange(const_iterator position, InputIter first,
+ InputIter last, std::input_iterator_tag);
+ template <typename ForwardIter>
+ iterator InsertWithRange(const_iterator position, ForwardIter first,
+ ForwardIter last, std::forward_iterator_tag);
+
+ AllocatorAndTag allocator_and_tag_;
+
+ // Either the inlined or allocated representation
+ union Rep {
+ // Use struct to perform indirection that solves a bizarre compilation
+ // error on Visual Studio (all known versions).
+ struct {
+ typename std::aligned_storage<sizeof(value_type),
+ alignof(value_type)>::type inlined[N];
+ } inlined_storage;
+ struct {
+ typename std::aligned_storage<sizeof(Allocation),
+ alignof(Allocation)>::type allocation;
+ } allocation_storage;
+ } rep_;
+};
+
+// -----------------------------------------------------------------------------
+// InlinedVector Non-Member Functions
+// -----------------------------------------------------------------------------
+
+// swap()
+//
+// Swaps the contents of two inlined vectors. This convenience function
+// simply calls InlinedVector::swap(other_inlined_vector).
+template <typename T, size_t N, typename A>
+void swap(InlinedVector<T, N, A>& a,
+ InlinedVector<T, N, A>& b) noexcept(noexcept(a.swap(b))) {
+ a.swap(b);
+}
+
+// operator==()
+//
+// Tests the equivalency of the contents of two inlined vectors.
+template <typename T, size_t N, typename A>
+bool operator==(const InlinedVector<T, N, A>& a,
+ const InlinedVector<T, N, A>& b) {
+ return absl::equal(a.begin(), a.end(), b.begin(), b.end());
+}
+
+// operator!=()
+//
+// Tests the inequality of the contents of two inlined vectors.
+template <typename T, size_t N, typename A>
+bool operator!=(const InlinedVector<T, N, A>& a,
+ const InlinedVector<T, N, A>& b) {
+ return !(a == b);
+}
+
+// operator<()
+//
+// Tests whether the contents of one inlined vector are less than the contents
+// of another through a lexicographical comparison operation.
+template <typename T, size_t N, typename A>
+bool operator<(const InlinedVector<T, N, A>& a,
+ const InlinedVector<T, N, A>& b) {
+ return std::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end());
+}
+
+// operator>()
+//
+// Tests whether the contents of one inlined vector are greater than the
+// contents of another through a lexicographical comparison operation.
+template <typename T, size_t N, typename A>
+bool operator>(const InlinedVector<T, N, A>& a,
+ const InlinedVector<T, N, A>& b) {
+ return b < a;
+}
+
+// operator<=()
+//
+// Tests whether the contents of one inlined vector are less than or equal to
+// the contents of another through a lexicographical comparison operation.
+template <typename T, size_t N, typename A>
+bool operator<=(const InlinedVector<T, N, A>& a,
+ const InlinedVector<T, N, A>& b) {
+ return !(b < a);
+}
+
+// operator>=()
+//
+// Tests whether the contents of one inlined vector are greater than or equal to
+// the contents of another through a lexicographical comparison operation.
+template <typename T, size_t N, typename A>
+bool operator>=(const InlinedVector<T, N, A>& a,
+ const InlinedVector<T, N, A>& b) {
+ return !(a < b);
+}
+
+// -----------------------------------------------------------------------------
+// Implementation of InlinedVector
+// -----------------------------------------------------------------------------
+//
+// Do not depend on any implementation details below this line.
+
+template <typename T, size_t N, typename A>
+InlinedVector<T, N, A>::InlinedVector(const InlinedVector& v)
+ : allocator_and_tag_(v.allocator()) {
+ reserve(v.size());
+ if (allocated()) {
+ UninitializedCopy(v.begin(), v.end(), allocated_space());
+ tag().set_allocated_size(v.size());
+ } else {
+ UninitializedCopy(v.begin(), v.end(), inlined_space());
+ tag().set_inline_size(v.size());
+ }
+}
+
+template <typename T, size_t N, typename A>
+InlinedVector<T, N, A>::InlinedVector(const InlinedVector& v,
+ const allocator_type& alloc)
+ : allocator_and_tag_(alloc) {
+ reserve(v.size());
+ if (allocated()) {
+ UninitializedCopy(v.begin(), v.end(), allocated_space());
+ tag().set_allocated_size(v.size());
+ } else {
+ UninitializedCopy(v.begin(), v.end(), inlined_space());
+ tag().set_inline_size(v.size());
+ }
+}
+
+template <typename T, size_t N, typename A>
+InlinedVector<T, N, A>::InlinedVector(InlinedVector&& v) noexcept(
+ absl::allocator_is_nothrow<allocator_type>::value ||
+ std::is_nothrow_move_constructible<value_type>::value)
+ : allocator_and_tag_(v.allocator_and_tag_) {
+ if (v.allocated()) {
+ // We can just steal the underlying buffer from the source.
+ // That leaves the source empty, so we clear its size.
+ init_allocation(v.allocation());
+ v.tag() = Tag();
+ } else {
+ UninitializedCopy(std::make_move_iterator(v.inlined_space()),
+ std::make_move_iterator(v.inlined_space() + v.size()),
+ inlined_space());
+ }
+}
+
+template <typename T, size_t N, typename A>
+InlinedVector<T, N, A>::InlinedVector(
+ InlinedVector&& v,
+ const allocator_type&
+ alloc) noexcept(absl::allocator_is_nothrow<allocator_type>::value)
+ : allocator_and_tag_(alloc) {
+ if (v.allocated()) {
+ if (alloc == v.allocator()) {
+ // We can just steal the allocation from the source.
+ tag() = v.tag();
+ init_allocation(v.allocation());
+ v.tag() = Tag();
+ } else {
+ // We need to use our own allocator
+ reserve(v.size());
+ UninitializedCopy(std::make_move_iterator(v.begin()),
+ std::make_move_iterator(v.end()), allocated_space());
+ tag().set_allocated_size(v.size());
+ }
+ } else {
+ UninitializedCopy(std::make_move_iterator(v.inlined_space()),
+ std::make_move_iterator(v.inlined_space() + v.size()),
+ inlined_space());
+ tag().set_inline_size(v.size());
+ }
+}
+
+template <typename T, size_t N, typename A>
+void InlinedVector<T, N, A>::InitAssign(size_type n, const value_type& t) {
+ if (n > static_cast<size_type>(N)) {
+ Allocation new_allocation(allocator(), n);
+ init_allocation(new_allocation);
+ UninitializedFill(allocated_space(), allocated_space() + n, t);
+ tag().set_allocated_size(n);
+ } else {
+ UninitializedFill(inlined_space(), inlined_space() + n, t);
+ tag().set_inline_size(n);
+ }
+}
+
+template <typename T, size_t N, typename A>
+void InlinedVector<T, N, A>::InitAssign(size_type n) {
+ if (n > static_cast<size_type>(N)) {
+ Allocation new_allocation(allocator(), n);
+ init_allocation(new_allocation);
+ UninitializedFill(allocated_space(), allocated_space() + n);
+ tag().set_allocated_size(n);
+ } else {
+ UninitializedFill(inlined_space(), inlined_space() + n);
+ tag().set_inline_size(n);
+ }
+}
+
+template <typename T, size_t N, typename A>
+void InlinedVector<T, N, A>::resize(size_type n) {
+ size_type s = size();
+ if (n < s) {
+ erase(begin() + n, end());
+ return;
+ }
+ reserve(n);
+ assert(capacity() >= n);
+
+ // Fill new space with elements constructed in-place.
+ if (allocated()) {
+ UninitializedFill(allocated_space() + s, allocated_space() + n);
+ tag().set_allocated_size(n);
+ } else {
+ UninitializedFill(inlined_space() + s, inlined_space() + n);
+ tag().set_inline_size(n);
+ }
+}
+
+template <typename T, size_t N, typename A>
+void InlinedVector<T, N, A>::resize(size_type n, const value_type& elem) {
+ size_type s = size();
+ if (n < s) {
+ erase(begin() + n, end());
+ return;
+ }
+ reserve(n);
+ assert(capacity() >= n);
+
+ // Fill new space with copies of 'elem'.
+ if (allocated()) {
+ UninitializedFill(allocated_space() + s, allocated_space() + n, elem);
+ tag().set_allocated_size(n);
+ } else {
+ UninitializedFill(inlined_space() + s, inlined_space() + n, elem);
+ tag().set_inline_size(n);
+ }
+}
+
+template <typename T, size_t N, typename A>
+template <typename... Args>
+typename InlinedVector<T, N, A>::iterator InlinedVector<T, N, A>::emplace(
+ const_iterator position, Args&&... args) {
+ assert(position >= begin());
+ assert(position <= end());
+ if (position == end()) {
+ emplace_back(std::forward<Args>(args)...);
+ return end() - 1;
+ }
+
+ T new_t = T(std::forward<Args>(args)...);
+
+ auto range = ShiftRight(position, 1);
+ if (range.first == range.second) {
+ // constructing into uninitialized memory
+ Construct(range.first, std::move(new_t));
+ } else {
+ // assigning into moved-from object
+ *range.first = T(std::move(new_t));
+ }
+
+ return range.first;
+}
+
+template <typename T, size_t N, typename A>
+typename InlinedVector<T, N, A>::iterator InlinedVector<T, N, A>::erase(
+ const_iterator first, const_iterator last) {
+ assert(begin() <= first);
+ assert(first <= last);
+ assert(last <= end());
+
+ iterator range_start = const_cast<iterator>(first);
+ iterator range_end = const_cast<iterator>(last);
+
+ size_type s = size();
+ ptrdiff_t erase_gap = std::distance(range_start, range_end);
+ if (erase_gap > 0) {
+ pointer space;
+ if (allocated()) {
+ space = allocated_space();
+ tag().set_allocated_size(s - erase_gap);
+ } else {
+ space = inlined_space();
+ tag().set_inline_size(s - erase_gap);
+ }
+ std::move(range_end, space + s, range_start);
+ Destroy(space + s - erase_gap, space + s);
+ }
+ return range_start;
+}
+
+template <typename T, size_t N, typename A>
+void InlinedVector<T, N, A>::swap(InlinedVector& other) {
+ using std::swap; // Augment ADL with std::swap.
+ if (&other == this) {
+ return;
+ }
+ if (allocated() && other.allocated()) {
+ // Both out of line, so just swap the tag, allocation, and allocator.
+ swap(tag(), other.tag());
+ swap(allocation(), other.allocation());
+ swap(allocator(), other.allocator());
+ return;
+ }
+ if (!allocated() && !other.allocated()) {
+ // Both inlined: swap up to smaller size, then move remaining elements.
+ InlinedVector* a = this;
+ InlinedVector* b = &other;
+ if (size() < other.size()) {
+ swap(a, b);
+ }
+
+ const size_type a_size = a->size();
+ const size_type b_size = b->size();
+ assert(a_size >= b_size);
+ // 'a' is larger. Swap the elements up to the smaller array size.
+ std::swap_ranges(a->inlined_space(),
+ a->inlined_space() + b_size,
+ b->inlined_space());
+
+ // Move the remaining elements: A[b_size,a_size) -> B[b_size,a_size)
+ b->UninitializedCopy(a->inlined_space() + b_size,
+ a->inlined_space() + a_size,
+ b->inlined_space() + b_size);
+ a->Destroy(a->inlined_space() + b_size, a->inlined_space() + a_size);
+
+ swap(a->tag(), b->tag());
+ swap(a->allocator(), b->allocator());
+ assert(b->size() == a_size);
+ assert(a->size() == b_size);
+ return;
+ }
+ // One is out of line, one is inline.
+ // We first move the elements from the inlined vector into the
+ // inlined space in the other vector. We then put the other vector's
+ // pointer/capacity into the originally inlined vector and swap
+ // the tags.
+ InlinedVector* a = this;
+ InlinedVector* b = &other;
+ if (a->allocated()) {
+ swap(a, b);
+ }
+ assert(!a->allocated());
+ assert(b->allocated());
+ const size_type a_size = a->size();
+ const size_type b_size = b->size();
+ // In an optimized build, b_size would be unused.
+ (void)b_size;
+
+ // Made Local copies of size(), don't need tag() accurate anymore
+ swap(a->tag(), b->tag());
+
+ // Copy b_allocation out before b's union gets clobbered by inline_space.
+ Allocation b_allocation = b->allocation();
+
+ b->UninitializedCopy(a->inlined_space(), a->inlined_space() + a_size,
+ b->inlined_space());
+ a->Destroy(a->inlined_space(), a->inlined_space() + a_size);
+
+ a->allocation() = b_allocation;
+
+ if (a->allocator() != b->allocator()) {
+ swap(a->allocator(), b->allocator());
+ }
+
+ assert(b->size() == a_size);
+ assert(a->size() == b_size);
+}
+
+template <typename T, size_t N, typename A>
+void InlinedVector<T, N, A>::EnlargeBy(size_type delta) {
+ const size_type s = size();
+ assert(s <= capacity());
+
+ size_type target = std::max(static_cast<size_type>(N), s + delta);
+
+ // Compute new capacity by repeatedly doubling current capacity
+ // TODO(psrc): Check and avoid overflow?
+ size_type new_capacity = capacity();
+ while (new_capacity < target) {
+ new_capacity <<= 1;
+ }
+
+ Allocation new_allocation(allocator(), new_capacity);
+
+ UninitializedCopy(std::make_move_iterator(data()),
+ std::make_move_iterator(data() + s),
+ new_allocation.buffer());
+
+ ResetAllocation(new_allocation, s);
+}
+
+template <typename T, size_t N, typename A>
+auto InlinedVector<T, N, A>::ShiftRight(const_iterator position, size_type n)
+ -> std::pair<iterator, iterator> {
+ iterator start_used = const_cast<iterator>(position);
+ iterator start_raw = const_cast<iterator>(position);
+ size_type s = size();
+ size_type required_size = s + n;
+
+ if (required_size > capacity()) {
+ // Compute new capacity by repeatedly doubling current capacity
+ size_type new_capacity = capacity();
+ while (new_capacity < required_size) {
+ new_capacity <<= 1;
+ }
+ // Move everyone into the new allocation, leaving a gap of n for the
+ // requested shift.
+ Allocation new_allocation(allocator(), new_capacity);
+ size_type index = position - begin();
+ UninitializedCopy(std::make_move_iterator(data()),
+ std::make_move_iterator(data() + index),
+ new_allocation.buffer());
+ UninitializedCopy(std::make_move_iterator(data() + index),
+ std::make_move_iterator(data() + s),
+ new_allocation.buffer() + index + n);
+ ResetAllocation(new_allocation, s);
+
+ // New allocation means our iterator is invalid, so we'll recalculate.
+ // Since the entire gap is in new space, there's no used space to reuse.
+ start_raw = begin() + index;
+ start_used = start_raw;
+ } else {
+ // If we had enough space, it's a two-part move. Elements going into
+ // previously-unoccupied space need an UninitializedCopy. Elements
+ // going into a previously-occupied space are just a move.
+ iterator pos = const_cast<iterator>(position);
+ iterator raw_space = end();
+ size_type slots_in_used_space = raw_space - pos;
+ size_type new_elements_in_used_space = std::min(n, slots_in_used_space);
+ size_type new_elements_in_raw_space = n - new_elements_in_used_space;
+ size_type old_elements_in_used_space =
+ slots_in_used_space - new_elements_in_used_space;
+
+ UninitializedCopy(std::make_move_iterator(pos + old_elements_in_used_space),
+ std::make_move_iterator(raw_space),
+ raw_space + new_elements_in_raw_space);
+ std::move_backward(pos, pos + old_elements_in_used_space, raw_space);
+
+ // If the gap is entirely in raw space, the used space starts where the raw
+ // space starts, leaving no elements in used space. If the gap is entirely
+ // in used space, the raw space starts at the end of the gap, leaving all
+ // elements accounted for within the used space.
+ start_used = pos;
+ start_raw = pos + new_elements_in_used_space;
+ }
+ tag().add_size(n);
+ return std::make_pair(start_used, start_raw);
+}
+
+template <typename T, size_t N, typename A>
+void InlinedVector<T, N, A>::Destroy(value_type* ptr, value_type* ptr_last) {
+ for (value_type* p = ptr; p != ptr_last; ++p) {
+ AllocatorTraits::destroy(allocator(), p);
+ }
+
+ // Overwrite unused memory with 0xab so we can catch uninitialized usage.
+ // Cast to void* to tell the compiler that we don't care that we might be
+ // scribbling on a vtable pointer.
+#ifndef NDEBUG
+ if (ptr != ptr_last) {
+ memset(reinterpret_cast<void*>(ptr), 0xab,
+ sizeof(*ptr) * (ptr_last - ptr));
+ }
+#endif
+}
+
+template <typename T, size_t N, typename A>
+template <typename Iter>
+void InlinedVector<T, N, A>::AppendRange(Iter first, Iter last,
+ std::forward_iterator_tag) {
+ using Length = typename std::iterator_traits<Iter>::difference_type;
+ Length length = std::distance(first, last);
+ reserve(size() + length);
+ if (allocated()) {
+ UninitializedCopy(first, last, allocated_space() + size());
+ tag().set_allocated_size(size() + length);
+ } else {
+ UninitializedCopy(first, last, inlined_space() + size());
+ tag().set_inline_size(size() + length);
+ }
+}
+
+template <typename T, size_t N, typename A>
+template <typename Iter>
+void InlinedVector<T, N, A>::AssignRange(Iter first, Iter last,
+ std::input_iterator_tag) {
+ // Optimized to avoid reallocation.
+ // Prefer reassignment to copy construction for elements.
+ iterator out = begin();
+ for ( ; first != last && out != end(); ++first, ++out)
+ *out = *first;
+ erase(out, end());
+ std::copy(first, last, std::back_inserter(*this));
+}
+
+template <typename T, size_t N, typename A>
+template <typename Iter>
+void InlinedVector<T, N, A>::AssignRange(Iter first, Iter last,
+ std::forward_iterator_tag) {
+ using Length = typename std::iterator_traits<Iter>::difference_type;
+ Length length = std::distance(first, last);
+ // Prefer reassignment to copy construction for elements.
+ if (static_cast<size_type>(length) <= size()) {
+ erase(std::copy(first, last, begin()), end());
+ return;
+ }
+ reserve(length);
+ iterator out = begin();
+ for (; out != end(); ++first, ++out) *out = *first;
+ if (allocated()) {
+ UninitializedCopy(first, last, out);
+ tag().set_allocated_size(length);
+ } else {
+ UninitializedCopy(first, last, out);
+ tag().set_inline_size(length);
+ }
+}
+
+template <typename T, size_t N, typename A>
+auto InlinedVector<T, N, A>::InsertWithCount(const_iterator position,
+ size_type n, const value_type& v)
+ -> iterator {
+ assert(position >= begin() && position <= end());
+ if (n == 0) return const_cast<iterator>(position);
+
+ value_type copy = v;
+ std::pair<iterator, iterator> it_pair = ShiftRight(position, n);
+ std::fill(it_pair.first, it_pair.second, copy);
+ UninitializedFill(it_pair.second, it_pair.first + n, copy);
+
+ return it_pair.first;
+}
+
+template <typename T, size_t N, typename A>
+template <typename InputIter>
+auto InlinedVector<T, N, A>::InsertWithRange(const_iterator position,
+ InputIter first, InputIter last,
+ std::input_iterator_tag)
+ -> iterator {
+ assert(position >= begin() && position <= end());
+ size_type index = position - cbegin();
+ size_type i = index;
+ while (first != last) insert(begin() + i++, *first++);
+ return begin() + index;
+}
+
+// Overload of InlinedVector::InsertWithRange()
+template <typename T, size_t N, typename A>
+template <typename ForwardIter>
+auto InlinedVector<T, N, A>::InsertWithRange(const_iterator position,
+ ForwardIter first,
+ ForwardIter last,
+ std::forward_iterator_tag)
+ -> iterator {
+ assert(position >= begin() && position <= end());
+ if (first == last) {
+ return const_cast<iterator>(position);
+ }
+ using Length = typename std::iterator_traits<ForwardIter>::difference_type;
+ Length n = std::distance(first, last);
+ std::pair<iterator, iterator> it_pair = ShiftRight(position, n);
+ size_type used_spots = it_pair.second - it_pair.first;
+ ForwardIter open_spot = std::next(first, used_spots);
+ std::copy(first, open_spot, it_pair.first);
+ UninitializedCopy(open_spot, last, it_pair.second);
+ return it_pair.first;
+}
+
+} // namespace absl
+
+#endif // ABSL_CONTAINER_INLINED_VECTOR_H_