diff options
| -rw-r--r-- | butl/small-vector | 257 | ||||
| -rw-r--r-- | tests/buildfile | 2 | ||||
| -rw-r--r-- | tests/small-vector/buildfile | 8 | ||||
| -rw-r--r-- | tests/small-vector/driver.cxx | 132 |
4 files changed, 398 insertions, 1 deletions
diff --git a/butl/small-vector b/butl/small-vector new file mode 100644 index 0000000..f09d91d --- /dev/null +++ b/butl/small-vector @@ -0,0 +1,257 @@ +// file : butl/small-vector -*- C++ -*- +// copyright : Copyright (c) 2014-2016 Code Synthesis Ltd +// license : MIT; see accompanying LICENSE file + +#ifndef BUTL_SMALL_VECTOR +#define BUTL_SMALL_VECTOR + +#include <vector> +#include <cassert> +#include <cstddef> // size_t +#include <utility> // more(), forward() + +namespace butl +{ + template <typename T, std::size_t N> + struct small_vector_buffer + { + // Size keeps track of the number of elements that are constructed in + // the buffer. Size equal N + 1 means the buffer is not allocated. + // + // Note that the names are decorated in order no to conflict with + // std::vector interface. + // + alignas (alignof (T)) char data_[sizeof (T) * N]; + bool free_ = true; + + // Note that the buffer should be constructed before std::vector and + // destroyed after (since std::vector's destructor will be destroying + // elements potentially residing in the buffer). This means that the + // buffer should be inherited from and before std::vector. + // + small_vector_buffer () = default; + + small_vector_buffer (small_vector_buffer&&) = delete; + small_vector_buffer (const small_vector_buffer&) = delete; + + small_vector_buffer& operator= (small_vector_buffer&&) = delete; + small_vector_buffer& operator= (const small_vector_buffer&) = delete; + }; + + template <typename T, std::size_t N> + class small_vector_allocator + { + public: + using buffer_type = small_vector_buffer<T, N>; + + explicit + small_vector_allocator (buffer_type* b) noexcept: buf_ (b) {} + + // Allocator interface. + // + public: + using value_type = T; + + T* + allocate(std::size_t n) + { + if (n <= N) + { + assert (buf_->free_); // Why would we need another small buffer? + buf_->free_ = false; + return reinterpret_cast<T*> (buf_->data_); + } + else + return static_cast<T*> (::operator new (sizeof (T) * n)); + } + + void + deallocate (void* p, std::size_t) noexcept + { + if (p == buf_->data_) + buf_->free_ = true; + else + ::operator delete (p); + } + + friend bool + operator== (small_vector_allocator x, small_vector_allocator y) noexcept + { + // We can use y to deallocate x's allocations if they use the same small + // buffer or neither uses its small buffer (which means all allocations, + // if any, have been from the shared heap). Of course this assumes no + // copy will be called to deallocate what has been allocated after said + // copy was made: + // + // A x; + // A y (x); + // p = x.allocate (); + // y.deallocate (p); // Ouch. + // + return (x.buf_ == y.buf_) || (x.buf_->free_ && y.buf_->free_); + } + + friend bool + operator!= (small_vector_allocator x, small_vector_allocator y) noexcept + { + return !(x == y); + } + + // It might get instantiated but should not be called. + // + small_vector_allocator + select_on_container_copy_construction () const noexcept + { + return small_vector_allocator (nullptr); + } + + // propagate_on_container_copy_assignment = false + // propagate_on_container_move_assignment = false + // propagate_on_container_swap = false + + // Shouldn't be needed except to satisfy some static_assert's. + // + template <typename U> + struct rebind {using other = small_vector_allocator<U, N>;}; + + private: + buffer_type* buf_; + }; + + // Issues and limitations. + // + // - vector::reserve() may allocate more per the spec. But the three main + // C++ runtimes (libstdc++, libc++, and msvc) all seem to do the right + // thing. + // + // - What if in most cases the vector is empty? How can we avoid initial + // reserve? Provide no_reserve flag or some such? Is it really worth it? + // + // - swap() is deleted (see notes below). + // + template <typename T, std::size_t N> + class small_vector: private small_vector_buffer<T, N>, + public std::vector<T, small_vector_allocator<T, N>> + { + public: + using allocator_type = small_vector_allocator<T, N>; + using buffer_type = small_vector_buffer<T, N>; + using base_type = std::vector<T, small_vector_allocator<T, N>>; + + small_vector () + : base_type (allocator_type (this)) + { + reserve (); + } + + small_vector (std::initializer_list<T> v) + : base_type (allocator_type (this)) + { + if (v.size () <= N) + reserve (); + + static_cast<base_type&> (*this) = v; + } + + template <typename I> + small_vector (I b, I e) + : base_type (allocator_type (this)) + { + // While we could optimize this for random access iterators, N will + // usually be pretty small. Let's hope the compiler sees this and does + // some magic for us. + // + std::size_t n (0); + for (I i (b); i != e && n <= N; ++i) ++n; + + if (n <= N) + reserve (); + + this->assign (b, e); + } + + explicit + small_vector (std::size_t n) + : base_type (allocator_type (this)) + { + if (n <= N) + reserve (); + + this->resize (n); + } + + small_vector (std::size_t n, const T& x) + : base_type (allocator_type (this)) + { + if (n <= N) + reserve (); + + this->assign (n, x); + } + + small_vector (const small_vector& v) + : buffer_type (), base_type (allocator_type (this)) + { + if (v.size () <= N) + reserve (); + + static_cast<base_type&> (*this) = v; + } + + small_vector (small_vector&& v) + : base_type (allocator_type (this)) + { + if (v.size () <= N) + reserve (); + + static_cast<base_type&> (*this) = std::move (v); + } + + small_vector& + operator= (const small_vector& v) + { + // Note: propagate_on_container_copy_assignment = false + // + static_cast<base_type&> (*this) = v; + return *this; + } + + small_vector& + operator= (small_vector&& v) + { + // Note: propagate_on_container_move_assignment = false + // + static_cast<base_type&> (*this) = std::move (v); + return *this; + } + + small_vector& + operator= (std::initializer_list<T> v) + { + static_cast<base_type&> (*this) = v; + return *this; + } + + // Implementing swap() under small buffer optimization is not trivial, to + // say the least (think of swapping two such buffers of different sizes). + // One easy option would be to force both in to the heap. + // + void + swap (small_vector&) = delete; + + void + reserve (std::size_t n = N) + { + base_type::reserve (n < N ? N : n); + } + + void + shrink_to_fit () + { + if (this->capacity () > N) + base_type::shrink_to_fit (); + } + }; +} + +#endif // BUTL_SMALL_VECTOR diff --git a/tests/buildfile b/tests/buildfile index 84a17aa..909432c 100644 --- a/tests/buildfile +++ b/tests/buildfile @@ -4,7 +4,7 @@ d = base64/ cpfile/ dir-iterator/ fdstream/ link/ manifest-parser/ \ manifest-serializer/ manifest-roundtrip/ pager/ path/ prefix-map/ \ - process/ sha256/ strcase/ timestamp/ triplet/ + process/ sha256/ small-vector/ strcase/ timestamp/ triplet/ ./: $d include $d diff --git a/tests/small-vector/buildfile b/tests/small-vector/buildfile new file mode 100644 index 0000000..78d2d06 --- /dev/null +++ b/tests/small-vector/buildfile @@ -0,0 +1,8 @@ +# file : tests/small-vector/buildfile +# copyright : Copyright (c) 2014-2016 Code Synthesis Ltd +# license : MIT; see accompanying LICENSE file + +exe{driver}: cxx{driver} ../../butl/lib{butl} +exe{driver}: test.arguments = $src_root + +include ../../butl/ diff --git a/tests/small-vector/driver.cxx b/tests/small-vector/driver.cxx new file mode 100644 index 0000000..5b7cfa6 --- /dev/null +++ b/tests/small-vector/driver.cxx @@ -0,0 +1,132 @@ +// file : tests/small-vector/driver.cxx -*- C++ -*- +// copyright : Copyright (c) 2014-2016 Code Synthesis Ltd +// license : MIT; see accompanying LICENSE file + +#include <string> +#include <cassert> +#include <iostream> + +#include <butl/small-vector> + +using namespace std; +using namespace butl; + +// Return if v.data() points to somewhere inside v. +// +template <typename T, size_t N> +inline bool +small (const small_vector<T, N>& v) +{ + const void* d (v.data ()); + return d >= &v && d < (&v + 1); +} + +int +main () +{ + using vector = small_vector<string, 1>; + + { + vector v; + assert (v.capacity () == 1 && small (v)); + + v.push_back ("abc"); + assert (v[0] == "abc" && v.capacity () == 1 && small (v)); + + string* d (v.data ()); // Small buffer... + + v.push_back ("xyz"); + assert (v[0] == "abc" && v.data () != d && !small (v)); + + v.pop_back (); + v.shrink_to_fit (); + assert (v[0] == "abc" && v.data () == d); + } + + // Allocator comparison. + // + { + vector v1, v2; + assert (v1.get_allocator () != v2.get_allocator ()); // stack/stack + + v1.assign ({"abc", "xyz"}); + assert (v1.get_allocator () != v2.get_allocator ()); // heap/stack + + v2.assign ({"abc", "xyz"}); + assert (v1.get_allocator () == v2.get_allocator ()); // heap/heap + + v1.pop_back (); + v1.shrink_to_fit (); + assert (v1.get_allocator () != v2.get_allocator ()); // stack/heap + + v2.pop_back (); + v2.shrink_to_fit (); + assert (v1.get_allocator () != v2.get_allocator ()); // stack/stack + } + + // Copy constructor. + // + { + vector s1 ({"abc"}), s2 (s1); + assert (s1 == s2 && s2.capacity () == 1 && small (s2)); + + vector l1 ({"abc", "xyz"}), l2 (l1); + assert (l1 == l2 && !small (l2)); + } + + // Move constructor. + // + { + struct mstring: string // Move-only string. + { + mstring () = default; + explicit mstring (const char* s): string (s) {} + + mstring (mstring&&) = default; + mstring& operator= (mstring&&) = default; + + mstring (const mstring&) = delete; + mstring& operator= (const mstring&) = delete; + }; + + using vector = small_vector<mstring, 1>; + + vector s1; s1.emplace_back ("abc"); + vector s2 (move (s1)); + assert (s2[0] == "abc" && s2.capacity () == 1 && small (s2)); + + vector l1; l1.emplace_back ("abc"); l1.emplace_back ("xyz"); + vector l2 (move (l1)); + assert (l2[0] == "abc" && l2[1] == "xyz" && !small (l2)); + } + + // Other constructors. + // + + { + const char* sa[] = {"abc"}; + const char* la[] = {"abc", "xyz"}; + + vector s (sa, sa + 1); + assert (s[0] == "abc" && s.capacity () == 1 && small (s)); + + vector l (la, la + 2); + assert (l[0] == "abc" && l[1] == "xyz" && !small (l)); + } + + { + vector s (1, "abc"); + assert (s[0] == "abc" && s.capacity () == 1 && small (s)); + + vector l (2, "abc"); + assert (l[0] == "abc" && l[1] == "abc" && !small (l)); + } + + { + vector s (1); + assert (s[0] == "" && s.capacity () == 1 && small (s)); + + vector l (2); + assert (l[0] == "" && l[1] == "" && !small (l)); + } +} |