diff options
author | Boris Kolpackov <boris@codesynthesis.com> | 2018-01-04 09:49:34 +0200 |
---|---|---|
committer | Boris Kolpackov <boris@codesynthesis.com> | 2018-01-04 14:27:16 +0200 |
commit | b62ccc5d017e54beecd72d64d2074473c49192a7 (patch) | |
tree | 3497d3b6da5d9feb29fa5edc8a0713f391ac209d /libbutl/small-forward-list.mxx | |
parent | 496aee483a5ccfa9c396de84dc0cedd234930ddc (diff) |
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).
Diffstat (limited to 'libbutl/small-forward-list.mxx')
-rw-r--r-- | libbutl/small-forward-list.mxx | 158 |
1 files changed, 158 insertions, 0 deletions
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; + }; +} |