Implement small_list, small_forward_list

Note that with VC small_list is never "small" because of the extra "headnode"
that this implementation allocates (see notes in small-list.mxx for details).

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