aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorBoris Kolpackov <boris@codesynthesis.com>2016-11-19 18:04:00 +0200
committerBoris Kolpackov <boris@codesynthesis.com>2016-11-19 18:04:00 +0200
commit499a78602432c4926004f859d5fe957c313adc09 (patch)
treee94ac38a2d8572444c94ad12b0118936c7290b2e
parent834f0df3850c2b115e2febbf5b6bdafbe88651e2 (diff)
Add small_vector<T, N> class template
It has a (mostly) std::vector interface (it derives from it) and will store up to N elements in the same storage as the vector instance itself.
-rw-r--r--butl/small-vector257
-rw-r--r--tests/buildfile2
-rw-r--r--tests/small-vector/buildfile8
-rw-r--r--tests/small-vector/driver.cxx132
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));
+ }
+}