From b62ccc5d017e54beecd72d64d2074473c49192a7 Mon Sep 17 00:00:00 2001
From: Boris Kolpackov <boris@codesynthesis.com>
Date: Thu, 4 Jan 2018 09:49:34 +0200
Subject: 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).
---
 libbutl/small-list.mxx | 163 +++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 163 insertions(+)
 create mode 100644 libbutl/small-list.mxx

(limited to 'libbutl/small-list.mxx')

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;
+  };
+}
-- 
cgit v1.1