diff options
| -rw-r--r-- | libbutl/small-allocator.mxx | 196 | ||||
| -rw-r--r-- | libbutl/small-forward-list.mxx | 158 | ||||
| -rw-r--r-- | libbutl/small-list.mxx | 163 | ||||
| -rw-r--r-- | libbutl/small-vector.mxx | 147 | ||||
| -rw-r--r-- | tests/small-forward-list/buildfile | 8 | ||||
| -rw-r--r-- | tests/small-forward-list/driver.cxx | 164 | ||||
| -rw-r--r-- | tests/small-list/buildfile | 8 | ||||
| -rw-r--r-- | tests/small-list/driver.cxx | 162 | ||||
| -rw-r--r-- | tests/small-vector/driver.cxx | 3 |
9 files changed, 870 insertions, 139 deletions
diff --git a/libbutl/small-allocator.mxx b/libbutl/small-allocator.mxx new file mode 100644 index 0000000..2c61e1c --- /dev/null +++ b/libbutl/small-allocator.mxx @@ -0,0 +1,196 @@ +// file : libbutl/small-allocator.mxx -*- C++ -*- +// copyright : Copyright (c) 2014-2017 Code Synthesis Ltd +// license : MIT; see accompanying LICENSE file + +#ifndef __cpp_modules +#pragma once +#endif + +#include <cassert> + +#ifndef __cpp_lib_modules +#include <cstddef> // size_t +#include <utility> // move() +#include <type_traits> // true_type, is_same +#endif + +// Other includes. + +#ifdef __cpp_modules +export module butl.small_allocator; +#ifdef __cpp_lib_modules +import std.core; +#endif +#endif + +#include <libbutl/export.hxx> + +LIBBUTL_MODEXPORT namespace butl +{ + // Implementation of the allocator (and its buffer) for small containers. + // + template <typename T, std::size_t N> + struct small_allocator_buffer + { + using value_type = T; + + // Note that the names are decorated in order not to conflict with + // the container's interface. + + // If free_ is true then the buffer is not allocated. + // + alignas (alignof (value_type)) char data_[sizeof (value_type) * N]; + bool free_ = true; + + // Note that the buffer should be constructed before the container and + // destroyed after (since the container's destructor will be destroying + // elements potentially residing in the buffer). This means that the + // buffer should be inherited from and before the std:: container. + // + small_allocator_buffer () = default; + + small_allocator_buffer (small_allocator_buffer&&) = delete; + small_allocator_buffer (const small_allocator_buffer&) = delete; + + small_allocator_buffer& operator= (small_allocator_buffer&&) = delete; + small_allocator_buffer& operator= (const small_allocator_buffer&) = delete; + }; + + template <typename T, + std::size_t N, + typename B = small_allocator_buffer<T, N>> + class small_allocator + { + public: + using buffer_type = B; + + explicit + small_allocator (buffer_type* b) noexcept: buf_ (b) {} + + // Allocator interface. + // + public: + using value_type = T; + + // These shouldn't be required but as usual there are old/broken + // implementations (like std::list in GCC 4.9). + // + using pointer = value_type*; + using const_pointer = const value_type*; + using reference = value_type&; + using const_reference = const value_type&; + + static void destroy (T* p) {p->~T ();} + + template <typename... A> + static void construct (T* p, A&&... a) + { + ::new (static_cast<void*> (p)) T (std::forward<A> (a)...); + } + + // Allocator rebinding. + // + // We assume that only one of the rebound allocators will actually be + // doing allocations and that its value type is the same as buffer value + // type. This is needed, for instance, for std::list since what actually + // gets allocated is the node type, not T (see small_list for details). + // + template <typename U> + struct rebind {using other = small_allocator<U, N, B>;}; + + template <typename U> + explicit + small_allocator (const small_allocator<U, N, B>& x) noexcept + : buf_ (x.buf_) {} + + T* + allocate (std::size_t n) + { + // An implementation can rebind the allocator to something completely + // different. For example, VC15u3 with _ITERATOR_DEBUG_LEVEL != 0 + // allocates some extra stuff which cannot possibly come from the static + // buffer. + // + if (std::is_same<T, typename buffer_type::value_type>::value) + { + if (buf_->free_) + { + assert (n >= N); // We should never be asked for less than N. + + if (n == N) + { + buf_->free_ = false; + return reinterpret_cast<T*> (buf_->data_); + } + // Fall through. + } + } + + 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_allocator x, small_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). + // + // Things get trickier with rebinding. If A is allocator and B is its + // rebinding, then the following must hold true: + // + // A a1(a) => a1==a + // A a(b) => B(a)==b && A(b)==a + // + // As a result, the rebinding constructor above always copies the buffer + // pointer and we decide whether to use the small buffer by comparing + // allocator/buffer value types. + // + // We also expect that any copy of the original allocator made by the + // std:: implementation of the container is temporary (that is, it + // doesn't outlive the small buffer). + // + return (x.buf_ == y.buf_) || (x.buf_->free_ && y.buf_->free_); + } + + friend bool + operator!= (small_allocator x, small_allocator y) noexcept + { + return !(x == y); + } + + // It might get instantiated but should not be called. + // + small_allocator + select_on_container_copy_construction () const noexcept + { + assert (false); + return small_allocator (nullptr); + } + + // propagate_on_container_copy_assignment = false + // propagate_on_container_move_assignment = false + + // Swap is not supported (see explanation in small_vector::swap()). + // + using propagate_on_container_swap = std::true_type; + + void + swap (small_allocator&) = delete; + + private: + template <typename, std::size_t, typename> + friend class small_allocator; // For buffer access in rebind. + + buffer_type* buf_; // Must not be NULL. + }; +} diff --git a/libbutl/small-forward-list.mxx b/libbutl/small-forward-list.mxx new file mode 100644 index 0000000..9411367 --- /dev/null +++ b/libbutl/small-forward-list.mxx @@ -0,0 +1,158 @@ +// file : libbutl/small-forward-list.mxx -*- C++ -*- +// copyright : Copyright (c) 2014-2017 Code Synthesis Ltd +// license : MIT; see accompanying LICENSE file + +#ifndef __cpp_modules +#pragma once +#endif + +#ifndef __cpp_lib_modules +#include <cstddef> // size_t +#include <utility> // move() +#include <forward_list> +#endif + +// Other includes. + +#ifdef __cpp_modules +export module butl.small_forward_list; +#ifdef __cpp_lib_modules +import std.core; +#endif +import butl.small_allocator; +#else +#include <libbutl/small-allocator.mxx> +#endif + +#include <libbutl/export.hxx> + +LIBBUTL_MODEXPORT namespace butl +{ + // Issues and limitations. + // + // - Because small_allocator currently expects us to allocate the entire + // small buffer and there is no reserve() in std::forward_list, we + // currently only support N==1 (which we static_assert). + // + // - swap() is deleted (see notes below). + // + // - The implementation doesn't allocate T but rather a "node" that normally + // consists of a pointers (next) and T. + // + template <typename T> + using small_forward_list_node = +#if defined (_MSC_VER) + std::_Flist_node<T, void*>; +#elif defined (__GLIBCXX__) + std::_Fwd_list_node<T>; +#elif defined (_LIBCPP_VERSION) + std::__forward_list_node<T, void*>; +#else +#error unknown standard library implementation +#endif + + template <typename T, std::size_t N> + using small_forward_list_buffer = + small_allocator_buffer<small_forward_list_node<T>, N>; + + template <typename T, std::size_t N> + class small_forward_list: + private small_forward_list_buffer<T, N>, + public std::forward_list<T, + small_allocator<T, + N, + small_forward_list_buffer<T, N>>> + { + static_assert (N == 1, "only small_forward_list or 1 currently supported"); + + public: + using buffer_type = small_forward_list_buffer<T, N>; + using allocator_type = small_allocator<T, N, buffer_type>; + using base_type = std::forward_list<T, allocator_type>; + + small_forward_list () + : base_type (allocator_type (this)) {} + + small_forward_list (std::initializer_list<T> v) + : base_type (allocator_type (this)) + { + static_cast<base_type&> (*this) = v; + } + + template <typename I> + small_forward_list (I b, I e) + : base_type (allocator_type (this)) + { + this->assign (b, e); + } + + explicit + small_forward_list (std::size_t n) + : base_type (allocator_type (this)) + { + this->resize (n); + } + + small_forward_list (std::size_t n, const T& x) + : base_type (allocator_type (this)) + { + this->assign (n, x); + } + + small_forward_list (const small_forward_list& v) + : buffer_type (), base_type (allocator_type (this)) + { + static_cast<base_type&> (*this) = v; + } + + small_forward_list& + operator= (const small_forward_list& v) + { + // Note: propagate_on_container_copy_assignment = false + // + static_cast<base_type&> (*this) = v; + return *this; + } + + small_forward_list (small_forward_list&& v) + : base_type (allocator_type (this)) + { + *this = std::move (v); // Delegate to operator=(&&). + } + + small_forward_list& + operator= (small_forward_list&& v) + { + // VC14's implementation of operator=(&&) swaps pointers without regard + // for allocator (fixed in 15). + // +#if defined(_MSC_VER) && _MSC_VER <= 1900 + clear (); + for (T& x: v) + push_front (std::move (x)); + reverse (); + v.clear (); +#else + // Note: propagate_on_container_move_assignment = false + // + static_cast<base_type&> (*this) = std::move (v); +#endif + + return *this; + } + + small_forward_list& + 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_forward_list&) = delete; + }; +} diff --git a/libbutl/small-list.mxx b/libbutl/small-list.mxx new file mode 100644 index 0000000..0f572a3 --- /dev/null +++ b/libbutl/small-list.mxx @@ -0,0 +1,163 @@ +// file : libbutl/small-list.mxx -*- C++ -*- +// copyright : Copyright (c) 2014-2017 Code Synthesis Ltd +// license : MIT; see accompanying LICENSE file + +#ifndef __cpp_modules +#pragma once +#endif + +#ifndef __cpp_lib_modules +#include <list> +#include <cstddef> // size_t +#include <utility> // move() +#endif + +// Other includes. + +#ifdef __cpp_modules +export module butl.small_list; +#ifdef __cpp_lib_modules +import std.core; +#endif +import butl.small_allocator; +#else +#include <libbutl/small-allocator.mxx> +#endif + +#include <libbutl/export.hxx> + +LIBBUTL_MODEXPORT namespace butl +{ + // Issues and limitations. + // + // - VC's implementation of std::list allocates an extra "headnode" + // (something to do with additional iterator stability guarantees). Which + // means only empty small list will actually be "small". As a result, + // unless you don't care about VC, you should use small_forward_list + // instead. + // + // - Because small_allocator currently expects us to allocate the entire + // small buffer and there is no reserve() in std::list, we currently + // only support N==1 (which we static_assert). + // + // - swap() is deleted (see notes below). + // + // - The implementation doesn't allocate T but rather a "node" that normally + // consists of two pointers (prev/next) and T. + // + template <typename T> + using small_list_node = +#if defined (_MSC_VER) + std::_List_node<T, void*>; +#elif defined (__GLIBCXX__) + std::_List_node<T>; +#elif defined (_LIBCPP_VERSION) + std::__list_node<T, void*>; +#else +#error unknown standard library implementation +#endif + + template <typename T, std::size_t N> + using small_list_buffer = small_allocator_buffer<small_list_node<T>, N>; + + template <typename T, std::size_t N> + class small_list: + private small_list_buffer<T, N>, + public std::list<T, small_allocator<T, N, small_list_buffer<T, N>>> + { + static_assert (N == 1, "only small_list or 1 currently supported"); + + public: + using buffer_type = small_list_buffer<T, N>; + using allocator_type = small_allocator<T, N, buffer_type>; + using base_type = std::list<T, allocator_type>; + + small_list () + : base_type (allocator_type (this)) {} + + small_list (std::initializer_list<T> v) + : base_type (allocator_type (this)) + { + static_cast<base_type&> (*this) = v; + } + + template <typename I> + small_list (I b, I e) + : base_type (allocator_type (this)) + { + this->assign (b, e); + } + + explicit + small_list (std::size_t n) + : base_type (allocator_type (this)) + { + this->resize (n); + } + + small_list (std::size_t n, const T& x) + : base_type (allocator_type (this)) + { + this->assign (n, x); + } + + small_list (const small_list& v) + : buffer_type (), base_type (allocator_type (this)) + { + static_cast<base_type&> (*this) = v; + } + + small_list& + operator= (const small_list& v) + { + // Note: propagate_on_container_copy_assignment = false + // + static_cast<base_type&> (*this) = v; + return *this; + } + + small_list (small_list&& v) + : base_type (allocator_type (this)) + { + *this = std::move (v); // Delegate to operator=(&&). + } + + small_list& + operator= (small_list&& v) + { + // libstdc++'s implementation prior to GCC 6 is broken (calls swap()). + // Since there is no easy way to determine this library's version, for + // now this is always enabled. + // + // Similarly, VC14's implementation of operator=(&&) swaps pointers + // without regard for allocator (fixed in 15). + // +#if defined(__GLIBCXX__) || (defined(_MSC_VER) && _MSC_VER <= 1900) + this->clear (); + for (T& x: v) + this->push_back (std::move (x)); + v.clear (); +#else + // Note: propagate_on_container_move_assignment = false + // + static_cast<base_type&> (*this) = std::move (v); +#endif + + return *this; + } + + small_list& + 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_list&) = delete; + }; +} diff --git a/libbutl/small-vector.mxx b/libbutl/small-vector.mxx index fb77935..7996f72 100644 --- a/libbutl/small-vector.mxx +++ b/libbutl/small-vector.mxx @@ -6,13 +6,10 @@ #pragma once #endif -#include <cassert> - #ifndef __cpp_lib_modules #include <vector> #include <cstddef> // size_t -#include <utility> // move(), forward() -#include <type_traits> // true_type +#include <utility> // move() #endif // Other includes. @@ -22,139 +19,15 @@ export module butl.small_vector; #ifdef __cpp_lib_modules import std.core; #endif +import butl.small_allocator; +#else +#include <libbutl/small-allocator.mxx> #endif #include <libbutl/export.hxx> LIBBUTL_MODEXPORT 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 not 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) {} - - // Required by VC15u3 when _ITERATOR_DEBUG_LEVEL is not 0. It allocates - // some extra stuff which cannot possibly come from the static buffer. - // -#if defined(_MSC_VER) && _MSC_VER >= 1911 - template <typename U> - explicit - small_vector_allocator (const small_vector_allocator<U, N>&) noexcept - : buf_ (nullptr) {} -#endif - - // Allocator interface. - // - public: - using value_type = T; - - T* - allocate(std::size_t n) - { - if (buf_ != nullptr) - { - assert (n >= N); // We should never be asked for less than N. - - if (n == N) - { - buf_->free_ = false; - return reinterpret_cast<T*> (buf_->data_); - } - // Fall through. - } - - return static_cast<T*> (::operator new (sizeof (T) * n)); - } - - void - deallocate (void* p, std::size_t) noexcept - { - if (buf_ != nullptr && 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 - - // Swap is not supported (see explanation in small_vector::swap()). - // - using propagate_on_container_swap = std::true_type; - - void - swap (small_vector_allocator&) = delete; - - // 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 @@ -167,13 +40,13 @@ LIBBUTL_MODEXPORT namespace butl // - 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>> + class small_vector: private small_allocator_buffer<T, N>, + public std::vector<T, small_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>>; + using buffer_type = small_allocator_buffer<T, N>; + using allocator_type = small_allocator<T, N>; + using base_type = std::vector<T, allocator_type>; small_vector () : base_type (allocator_type (this)) @@ -263,7 +136,7 @@ LIBBUTL_MODEXPORT namespace butl // VC15U1). // #if defined(_MSC_VER) && _MSC_VER <= 1910 - if (v.size () < N) + if (v.size () <= N) { clear (); for (T& x: v) diff --git a/tests/small-forward-list/buildfile b/tests/small-forward-list/buildfile new file mode 100644 index 0000000..8a6c7d6 --- /dev/null +++ b/tests/small-forward-list/buildfile @@ -0,0 +1,8 @@ +# file : tests/small-forward-list/buildfile +# copyright : Copyright (c) 2014-2017 Code Synthesis Ltd +# license : MIT; see accompanying LICENSE file + +import libs = libbutl%lib{butl} +libs += $stdmod_lib + +exe{driver}: {hxx cxx}{*} $libs diff --git a/tests/small-forward-list/driver.cxx b/tests/small-forward-list/driver.cxx new file mode 100644 index 0000000..e6fc717 --- /dev/null +++ b/tests/small-forward-list/driver.cxx @@ -0,0 +1,164 @@ +// file : tests/small-forward-list/driver.cxx -*- C++ -*- +// copyright : Copyright (c) 2014-2017 Code Synthesis Ltd +// license : MIT; see accompanying LICENSE file + +#include <cassert> + +#ifndef __cpp_lib_modules +#include <string> +#include <iostream> +#endif + +// Other includes. + +#ifdef __cpp_modules +#ifdef __cpp_lib_modules +import std.core; +import std.io; +#endif +import butl.small_forward_list; +#else +#include <libbutl/small-forward-list.mxx> +#endif + +using namespace std; +using namespace butl; + +// Return true if the data is stored entirely inside l. +// +template <typename T, size_t N> +inline bool +small (const small_forward_list<T, N>& l) +{ + for (const T& x: l) + { + const void* p (&x); + + if (p < &l || p >= (&l + 1)) + return false; + } + + return true; +} + +template <typename T, size_t N> +inline const T& +front (const small_forward_list<T, N>& l) +{ + return l.front (); +} + +template <typename T, size_t N> +inline const T& +back (const small_forward_list<T, N>& l) +{ + auto i (l.begin ());; + for (auto j (i); ++j != l.end (); ) i = j; + return *i; +} + +int +main () +{ + using list = small_forward_list<string, 1>; + + { + list l; + + l.push_front ("abc"); + assert (front (l) == "abc" && small (l)); + + l.push_front ("ABC"); + assert (front (l) == "ABC" && back (l) == "abc" && !small (l)); + + l.pop_front (); + assert (front (l) == "abc" && small (l)); + + l.push_front ("ABC"); + l.reverse (); + l.pop_front (); + assert (front (l) == "ABC" && !small (l)); + + l.push_front ("abc"); + l.reverse (); + l.pop_front (); + assert (front (l) == "abc" && small (l)); + + l.clear (); + l.push_front ("abc"); + assert (front (l) == "abc" && small (l)); + } + + // Copy constructor. + // + { + list s1 ({"abc"}), s2 (s1); + assert (s1 == s2 && small (s2)); + + list l1 ({"abc", "ABC"}), 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 list = small_forward_list<mstring, 1>; + + { + list s1; + s1.emplace_front ("abc"); + list s2 (move (s1)); + assert (front (s2) == "abc" && small (s2)); + } + + { + list l1; + l1.emplace_front ("ABC"); + l1.emplace_front ("abc"); + list l2 (move (l1)); + assert (front (l2) == "abc" && back (l2) == "ABC" && !small (l2)); + } + } + + // Other constructors. + // + + { + const char* sa[] = {"abc"}; + const char* la[] = {"abc", "ABC"}; + + list s (sa, sa + 1); + assert (front (s) == "abc" && small (s)); + + list l (la, la + 2); + assert (front (l) == "abc" && back (l) == "ABC" && !small (l)); + } + + { + list s (1, "abc"); + assert (front (s) == "abc" && small (s)); + + list l (3, "abc"); + assert (front (l) == "abc" && back (l) == "abc" && !small (l)); + } + + { + list s (1); + assert (s.front () == "" && small (s)); + + list l (3); + assert (front (l) == "" && back (l) == "" && !small (l)); + } +} diff --git a/tests/small-list/buildfile b/tests/small-list/buildfile new file mode 100644 index 0000000..02a87ad --- /dev/null +++ b/tests/small-list/buildfile @@ -0,0 +1,8 @@ +# file : tests/small-list/buildfile +# copyright : Copyright (c) 2014-2017 Code Synthesis Ltd +# license : MIT; see accompanying LICENSE file + +import libs = libbutl%lib{butl} +libs += $stdmod_lib + +exe{driver}: {hxx cxx}{*} $libs diff --git a/tests/small-list/driver.cxx b/tests/small-list/driver.cxx new file mode 100644 index 0000000..970adc3 --- /dev/null +++ b/tests/small-list/driver.cxx @@ -0,0 +1,162 @@ +// file : tests/small-list/driver.cxx -*- C++ -*- +// copyright : Copyright (c) 2014-2017 Code Synthesis Ltd +// license : MIT; see accompanying LICENSE file + +#include <cassert> + +#ifndef __cpp_lib_modules +#include <string> +#include <iostream> +#endif + +// Other includes. + +#ifdef __cpp_modules +#ifdef __cpp_lib_modules +import std.core; +import std.io; +#endif +import butl.small_list; +#else +#include <libbutl/small-list.mxx> +#endif + +using namespace std; +using namespace butl; + +// Return true if the data is stored entirely inside l. +// +template <typename T, size_t N> +inline bool +small (const small_list<T, N>& l) +{ + // In VC it is always "large" (see note in small_list) so we omit this + // test. + // +#ifndef _MSC_VER + for (const T& x: l) + { + const void* p (&x); + + if (p < &l || p >= (&l + 1)) + return false; + } +#endif + + return true; +} + +template <typename T, size_t N> +inline bool +large (const small_list<T, N>& l) +{ +#ifndef _MSC_VER + return !small (l); +#else + return true; +#endif +} + +int +main () +{ + using list = small_list<string, 1>; + + { + list l; + + l.push_back ("abc"); + assert (l.front () == "abc" && small (l)); + + l.push_back ("ABC"); + assert (l.front () == "abc" && l.back () == "ABC" && large (l)); + + l.pop_back (); + assert (l.front () == "abc" && small (l)); + + l.push_back ("ABC"); + l.pop_front (); + assert (l.front () == "ABC" && large (l)); + + l.push_back ("abc"); + l.pop_front (); + assert (l.front () == "abc" && small (l)); + + l.clear (); + l.push_back ("abc"); + assert (l.front () == "abc" && small (l)); + } + + // Copy constructor. + // + { + list s1 ({"abc"}), s2 (s1); + assert (s1 == s2 && small (s2)); + + list l1 ({"abc", "ABC"}), l2 (l1); + assert (l1 == l2 && large (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 list = small_list<mstring, 1>; + + { + list s1; + s1.emplace_back ("abc"); + list s2 (move (s1)); + assert (s2.front () == "abc" && small (s2)); + } + + { + list l1; + l1.emplace_back ("abc"); + l1.emplace_back ("ABC"); + list l2 (move (l1)); + assert (l2.front () == "abc" && l2.back () == "ABC" && large (l2)); + } + } + + // Other constructors. + // + + { + const char* sa[] = {"abc"}; + const char* la[] = {"abc", "ABC"}; + + list s (sa, sa + 1); + assert (s.front () == "abc" && small (s)); + + list l (la, la + 2); + assert (l.front () == "abc" && l.back () == "ABC" && large (l)); + } + + { + list s (1, "abc"); + assert (s.front () == "abc" && small (s)); + + list l (3, "abc"); + assert (l.front () == "abc" && l.back () == "abc" && large (l)); + } + + { + list s (1); + assert (s.front () == "" && small (s)); + + list l (3); + assert (l.front () == "" && l.back () == "" && large (l)); + } +} diff --git a/tests/small-vector/driver.cxx b/tests/small-vector/driver.cxx index fe386a4..a9f1584 100644 --- a/tests/small-vector/driver.cxx +++ b/tests/small-vector/driver.cxx @@ -6,7 +6,6 @@ #ifndef __cpp_lib_modules #include <string> -#include <vector> #include <iostream> #endif @@ -25,7 +24,7 @@ import butl.small_vector; using namespace std; using namespace butl; -// Return if v.data() points to somewhere inside v. +// Return true if v.data() points to somewhere inside v. // template <typename T, size_t N> inline bool |