Yarn: Add Containers.hpp
The yarn::containers namespace holds STL-like container implementations that are optimized for avoiding heap allocations.
Bug: b/139010488
Change-Id: I9620488c607742132aff9dfdd35a7582a82bf687
Reviewed-on: https://swiftshader-review.googlesource.com/c/SwiftShader/+/34814
Tested-by: Ben Clayton <bclayton@google.com>
Reviewed-by: Nicolas Capens <nicolascapens@google.com>
Kokoro-Presubmit: kokoro <noreply+kokoro@google.com>
diff --git a/src/Yarn/Containers.hpp b/src/Yarn/Containers.hpp
new file mode 100644
index 0000000..b8b66a8
--- /dev/null
+++ b/src/Yarn/Containers.hpp
@@ -0,0 +1,255 @@
+// Copyright 2019 The SwiftShader Authors. All Rights Reserved.
+//
+// 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.
+
+// The yarn::containers namespace holds STL-like container implementations that
+// are optimized for avoiding heap allocations.
+// Note that unlike many other types in yarn, these containers offer no
+// protection for concurrent access and are considered 'thread-unsafe'.
+
+#ifndef yarn_containers_hpp
+#define yarn_containers_hpp
+
+#include "Debug.hpp"
+
+#include <algorithm> // std::max
+#include <type_traits> // std::aligned_storage
+#include <utility> // std::move
+
+#include <stddef.h> // size_t
+
+namespace yarn {
+namespace containers {
+
+////////////////////////////////////////////////////////////////////////////////
+// vector<T, BASE_CAPACITY>
+////////////////////////////////////////////////////////////////////////////////
+
+// vector is a container of contiguously stored elements.
+// Unlike std::vector, yarn::containers::vector keeps the first BASE_CAPACITY
+// elements internally, which will avoid dynamic heap allocations.
+// Once the vector exceeds BASE_CAPACITY elements, vector will allocate storage
+// from the heap.
+template <typename T, int BASE_CAPACITY>
+class vector
+{
+public:
+ inline vector() = default;
+
+ template <int BASE_CAPACITY_2>
+ inline vector(const vector<T, BASE_CAPACITY_2>& other);
+
+ template <int BASE_CAPACITY_2>
+ inline vector(vector<T, BASE_CAPACITY_2>&& other);
+
+ inline ~vector();
+
+ template <int BASE_CAPACITY_2>
+ inline vector<T, BASE_CAPACITY>& operator = (const vector<T, BASE_CAPACITY_2>&);
+
+ template <int BASE_CAPACITY_2>
+ inline vector<T, BASE_CAPACITY>& operator = (vector<T, BASE_CAPACITY_2>&&);
+
+ inline void push_back(const T& el);
+ inline void emplace_back(T&& el);
+ inline void pop_back();
+ inline T& front();
+ inline T& back();
+ inline T* begin();
+ inline T* end();
+ inline T& operator[] (size_t i);
+ inline const T& operator[] (size_t i) const;
+ inline size_t size() const;
+ inline size_t cap() const;
+ inline void resize(size_t n);
+ inline void reserve(size_t n);
+
+private:
+ using TStorage = typename std::aligned_storage<sizeof(T), alignof(T)>::type;
+
+ inline void free();
+
+ size_t count = 0;
+ size_t capacity = BASE_CAPACITY;
+ TStorage buffer[BASE_CAPACITY];
+ TStorage* elements = buffer;
+};
+
+template <typename T, int BASE_CAPACITY>
+template <int BASE_CAPACITY_2>
+vector<T, BASE_CAPACITY>::vector(const vector<T, BASE_CAPACITY_2>& other)
+{
+ *this = other;
+}
+
+template <typename T, int BASE_CAPACITY>
+template <int BASE_CAPACITY_2>
+vector<T, BASE_CAPACITY>::vector(vector<T, BASE_CAPACITY_2>&& other)
+{
+ *this = std::move(other);
+}
+
+template <typename T, int BASE_CAPACITY>
+vector<T, BASE_CAPACITY>::~vector()
+{
+ free();
+}
+
+template <typename T, int BASE_CAPACITY>
+template <int BASE_CAPACITY_2>
+vector<T, BASE_CAPACITY>& vector<T, BASE_CAPACITY>::operator = (const vector<T, BASE_CAPACITY_2>& other)
+{
+ free();
+ reserve(other.size());
+ count = other.size();
+ for (size_t i = 0; i < count; i++)
+ {
+ new (&reinterpret_cast<T*>(elements)[i]) T(other[i]);
+ }
+ return *this;
+}
+
+template <typename T, int BASE_CAPACITY>
+template <int BASE_CAPACITY_2>
+vector<T, BASE_CAPACITY>& vector<T, BASE_CAPACITY>::operator = (vector<T, BASE_CAPACITY_2>&& other)
+{
+ free();
+ reserve(other.size());
+ count = other.size();
+ for (size_t i = 0; i < count; i++)
+ {
+ new (&reinterpret_cast<T*>(elements)[i]) T(std::move(other[i]));
+ }
+ other.resize(0);
+ return *this;
+}
+
+template <typename T, int BASE_CAPACITY>
+void vector<T, BASE_CAPACITY>::push_back(const T& el)
+{
+ reserve(count + 1);
+ new (&reinterpret_cast<T*>(elements)[count]) T(el);
+ count++;
+}
+
+template <typename T, int BASE_CAPACITY>
+void vector<T, BASE_CAPACITY>::emplace_back(T&& el)
+{
+ reserve(count + 1);
+ new (&reinterpret_cast<T*>(elements)[count]) T(std::move(el));
+ count++;
+}
+
+template <typename T, int BASE_CAPACITY>
+void vector<T, BASE_CAPACITY>::pop_back()
+{
+ YARN_ASSERT(count > 0, "pop_back() called on empty vector");
+ count--;
+ reinterpret_cast<T*>(elements)[count].~T();
+}
+
+template <typename T, int BASE_CAPACITY>
+T& vector<T, BASE_CAPACITY>::front()
+{
+ YARN_ASSERT(count > 0, "front() called on empty vector");
+ return reinterpret_cast<T*>(elements)[0];
+}
+
+template <typename T, int BASE_CAPACITY>
+T& vector<T, BASE_CAPACITY>::back()
+{
+ YARN_ASSERT(count > 0, "back() called on empty vector");
+ return reinterpret_cast<T*>(elements)[count - 1];
+}
+
+template <typename T, int BASE_CAPACITY>
+T* vector<T, BASE_CAPACITY>::begin()
+{
+ return reinterpret_cast<T*>(elements);
+}
+
+template <typename T, int BASE_CAPACITY>
+T* vector<T, BASE_CAPACITY>::end()
+{
+ return reinterpret_cast<T*>(elements) + count;
+}
+
+template <typename T, int BASE_CAPACITY>
+T& vector<T, BASE_CAPACITY>::operator[] (size_t i)
+{
+ YARN_ASSERT(i < count, "index %d exceeds vector size %d", int(i), int(count));
+ return reinterpret_cast<T*>(elements)[i];
+}
+
+template <typename T, int BASE_CAPACITY>
+const T& vector<T, BASE_CAPACITY>::operator[] (size_t i) const
+{
+ YARN_ASSERT(i < count, "index %d exceeds vector size %d", int(i), int(count));
+ return reinterpret_cast<T*>(elements)[i];
+}
+
+template <typename T, int BASE_CAPACITY>
+size_t vector<T, BASE_CAPACITY>::size() const
+{
+ return count;
+}
+
+template <typename T, int BASE_CAPACITY>
+void vector<T, BASE_CAPACITY>::resize(size_t n)
+{
+ reserve(n);
+ while (count < n)
+ {
+ new (&reinterpret_cast<T*>(elements)[count++]) T();
+ }
+ while (n < count)
+ {
+ reinterpret_cast<T*>(elements)[--count].~T();
+ }
+}
+
+template <typename T, int BASE_CAPACITY>
+void vector<T, BASE_CAPACITY>::reserve(size_t n)
+{
+ if (n > capacity)
+ {
+ capacity = std::max<size_t>(n * 2, 8);
+ auto grown = new TStorage[capacity];
+ for (size_t i = 0; i < count; i++)
+ {
+ new (&reinterpret_cast<T*>(grown)[i]) T(std::move(reinterpret_cast<T*>(elements)[i]));
+ }
+ free();
+ elements = grown;
+ }
+}
+
+template <typename T, int BASE_CAPACITY>
+void vector<T, BASE_CAPACITY>::free()
+{
+ for (size_t i = 0; i < count; i++)
+ {
+ reinterpret_cast<T*>(elements)[i].~T();
+ }
+
+ if (elements != buffer)
+ {
+ delete []elements;
+ elements = nullptr;
+ }
+}
+
+} // namespace containers
+} // namespace yarn
+
+#endif // yarn_containers_hpp
diff --git a/src/Yarn/Containers_test.cpp b/src/Yarn/Containers_test.cpp
new file mode 100644
index 0000000..d677606
--- /dev/null
+++ b/src/Yarn/Containers_test.cpp
@@ -0,0 +1,201 @@
+// Copyright 2019 The SwiftShader Authors. All Rights Reserved.
+//
+// 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 "Containers.hpp"
+
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+
+#include <string>
+
+class ContainersVectorTest : public testing::Test {};
+
+TEST(ContainersVectorTest, Empty)
+{
+ yarn::containers::vector<std::string, 4> vector;
+ ASSERT_EQ(vector.size(), size_t(0));
+}
+
+TEST(ContainersVectorTest, WithinFixedCapIndex)
+{
+ yarn::containers::vector<std::string, 4> vector;
+ vector.resize(4);
+ vector[0] = "A";
+ vector[1] = "B";
+ vector[2] = "C";
+ vector[3] = "D";
+
+ ASSERT_EQ(vector[0], "A");
+ ASSERT_EQ(vector[1], "B");
+ ASSERT_EQ(vector[2], "C");
+ ASSERT_EQ(vector[3], "D");
+}
+
+TEST(ContainersVectorTest, BeyondFixedCapIndex)
+{
+ yarn::containers::vector<std::string, 1> vector;
+ vector.resize(4);
+ vector[0] = "A";
+ vector[1] = "B";
+ vector[2] = "C";
+ vector[3] = "D";
+
+ ASSERT_EQ(vector[0], "A");
+ ASSERT_EQ(vector[1], "B");
+ ASSERT_EQ(vector[2], "C");
+ ASSERT_EQ(vector[3], "D");
+}
+
+TEST(ContainersVectorTest, WithinFixedCapPushPop)
+{
+ yarn::containers::vector<std::string, 4> vector;
+ vector.push_back("A");
+ vector.push_back("B");
+ vector.push_back("C");
+ vector.push_back("D");
+
+ ASSERT_EQ(vector.size(), size_t(4));
+ ASSERT_EQ(vector.end() - vector.begin(), ptrdiff_t(4));
+
+ ASSERT_EQ(vector.front(), "A");
+ ASSERT_EQ(vector.back(), "D");
+ vector.pop_back();
+ ASSERT_EQ(vector.size(), size_t(3));
+ ASSERT_EQ(vector.end() - vector.begin(), ptrdiff_t(3));
+
+ ASSERT_EQ(vector.front(), "A");
+ ASSERT_EQ(vector.back(), "C");
+ vector.pop_back();
+ ASSERT_EQ(vector.size(), size_t(2));
+ ASSERT_EQ(vector.end() - vector.begin(), ptrdiff_t(2));
+
+ ASSERT_EQ(vector.front(), "A");
+ ASSERT_EQ(vector.back(), "B");
+ vector.pop_back();
+ ASSERT_EQ(vector.size(), size_t(1));
+ ASSERT_EQ(vector.end() - vector.begin(), ptrdiff_t(1));
+
+ ASSERT_EQ(vector.front(), "A");
+ ASSERT_EQ(vector.back(), "A");
+ vector.pop_back();
+ ASSERT_EQ(vector.size(), size_t(0));
+}
+
+TEST(ContainersVectorTest, BeyondFixedCapPushPop)
+{
+ yarn::containers::vector<std::string, 2> vector;
+ vector.push_back("A");
+ vector.push_back("B");
+ vector.push_back("C");
+ vector.push_back("D");
+
+ ASSERT_EQ(vector.size(), size_t(4));
+ ASSERT_EQ(vector.end() - vector.begin(), ptrdiff_t(4));
+
+ ASSERT_EQ(vector.front(), "A");
+ ASSERT_EQ(vector.back(), "D");
+ vector.pop_back();
+ ASSERT_EQ(vector.size(), size_t(3));
+ ASSERT_EQ(vector.end() - vector.begin(), ptrdiff_t(3));
+
+ ASSERT_EQ(vector.front(), "A");
+ ASSERT_EQ(vector.back(), "C");
+ vector.pop_back();
+ ASSERT_EQ(vector.size(), size_t(2));
+ ASSERT_EQ(vector.end() - vector.begin(), ptrdiff_t(2));
+
+ ASSERT_EQ(vector.front(), "A");
+ ASSERT_EQ(vector.back(), "B");
+ vector.pop_back();
+ ASSERT_EQ(vector.size(), size_t(1));
+ ASSERT_EQ(vector.end() - vector.begin(), ptrdiff_t(1));
+
+ ASSERT_EQ(vector.front(), "A");
+ ASSERT_EQ(vector.back(), "A");
+ vector.pop_back();
+ ASSERT_EQ(vector.size(), size_t(0));
+}
+
+TEST(ContainersVectorTest, CopyConstruct)
+{
+ yarn::containers::vector<std::string, 4> vectorA;
+
+ vectorA.resize(3);
+ vectorA[0] = "A";
+ vectorA[1] = "B";
+ vectorA[2] = "C";
+
+ yarn::containers::vector<std::string, 2> vectorB(vectorA);
+ ASSERT_EQ(vectorB.size(), size_t(3));
+ ASSERT_EQ(vectorB[0], "A");
+ ASSERT_EQ(vectorB[1], "B");
+ ASSERT_EQ(vectorB[2], "C");
+}
+
+TEST(ContainersVectorTest, MoveConstruct)
+{
+ yarn::containers::vector<std::string, 4> vectorA;
+
+ vectorA.resize(3);
+ vectorA[0] = "A";
+ vectorA[1] = "B";
+ vectorA[2] = "C";
+
+ yarn::containers::vector<std::string, 2> vectorB(std::move(vectorA));
+ ASSERT_EQ(vectorB.size(), size_t(3));
+ ASSERT_EQ(vectorB[0], "A");
+ ASSERT_EQ(vectorB[1], "B");
+ ASSERT_EQ(vectorB[2], "C");
+}
+
+TEST(ContainersVectorTest, Copy)
+{
+ yarn::containers::vector<std::string, 4> vectorA;
+ yarn::containers::vector<std::string, 2> vectorB;
+
+ vectorA.resize(3);
+ vectorA[0] = "A";
+ vectorA[1] = "B";
+ vectorA[2] = "C";
+
+ vectorB.resize(1);
+ vectorB[0] = "Z";
+
+ vectorB = vectorA;
+ ASSERT_EQ(vectorB.size(), size_t(3));
+ ASSERT_EQ(vectorB[0], "A");
+ ASSERT_EQ(vectorB[1], "B");
+ ASSERT_EQ(vectorB[2], "C");
+}
+
+TEST(ContainersVectorTest, Move)
+{
+ yarn::containers::vector<std::string, 4> vectorA;
+ yarn::containers::vector<std::string, 2> vectorB;
+
+ vectorA.resize(3);
+ vectorA[0] = "A";
+ vectorA[1] = "B";
+ vectorA[2] = "C";
+
+ vectorB.resize(1);
+ vectorB[0] = "Z";
+
+ vectorB = std::move(vectorA);
+ ASSERT_EQ(vectorA.size(), size_t(0));
+ ASSERT_EQ(vectorB.size(), size_t(3));
+ ASSERT_EQ(vectorB[0], "A");
+ ASSERT_EQ(vectorB[1], "B");
+ ASSERT_EQ(vectorB[2], "C");
+}
