From 5068d34c08f951a7ea6257d305a1627b09a95817 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sat, 4 May 2024 19:44:55 +0200 Subject: Adding upstream version 0.11.1. Signed-off-by: Daniel Baumann --- src/ring_span.hh | 946 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 946 insertions(+) create mode 100644 src/ring_span.hh (limited to 'src/ring_span.hh') diff --git a/src/ring_span.hh b/src/ring_span.hh new file mode 100644 index 0000000..0bd07a6 --- /dev/null +++ b/src/ring_span.hh @@ -0,0 +1,946 @@ +// +// Copyright (c) 2015 Arthur O'Dwyer +// Copyright 2017-2018 by Martin Moene +// +// https://github.com/martinmoene/ring-span-lite +// +// Distributed under the Boost Software License, Version 1.0. +// (See accompanying file LICENSE.txt or copy at +// http://www.boost.org/LICENSE_1_0.txt) + +#pragma once + +#ifndef NONSTD_RING_SPAN_LITE_HPP +# define NONSTD_RING_SPAN_LITE_HPP + +# define ring_span_lite_MAJOR 0 +# define ring_span_lite_MINOR 2 +# define ring_span_lite_PATCH 0 + +# define ring_span_lite_VERSION \ + nsrs_STRINGIFY(ring_span_lite_MAJOR) "." nsrs_STRINGIFY( \ + ring_span_lite_MINOR) "." nsrs_STRINGIFY(ring_span_lite_PATCH) + +# define nsrs_STRINGIFY(x) nsrs_STRINGIFY_(x) +# define nsrs_STRINGIFY_(x) # x + +// ring-span-lite configuration: + +# define nsrs_RING_SPAN_DEFAULT 0 +# define nsrs_RING_SPAN_NONSTD 1 +# define nsrs_RING_SPAN_STD 2 + +# if !defined(nsrs_CONFIG_SELECT_RING_SPAN) +# define nsrs_CONFIG_SELECT_RING_SPAN \ + (nsrs_HAVE_STD_RING_SPAN ? nsrs_RING_SPAN_STD \ + : nsrs_RING_SPAN_NONSTD) +# endif + +# ifndef nsrs_CONFIG_STRICT_P0059 +# define nsrs_CONFIG_STRICT_P0059 0 +# endif + +# define nsrs_RING_SPAN_LITE_EXTENSION (!nsrs_CONFIG_STRICT_P0059) + +# ifndef nsrs_CONFIG_CONFIRMS_COMPILATION_ERRORS +# define nsrs_CONFIG_CONFIRMS_COMPILATION_ERRORS 0 +# endif + +// C++ language version detection (C++20 is speculative): +// Note: VC14.0/1900 (VS2015) lacks too much from C++14. + +# ifndef nsrs_CPLUSPLUS +# if defined(_MSVC_LANG) && !defined(__clang__) +# define nsrs_CPLUSPLUS (_MSC_VER == 1900 ? 201103L : _MSVC_LANG) +# else +# define nsrs_CPLUSPLUS __cplusplus +# endif +# endif + +# define nsrs_CPP98_OR_GREATER (nsrs_CPLUSPLUS >= 199711L) +# define nsrs_CPP11_OR_GREATER (nsrs_CPLUSPLUS >= 201103L) +# define nsrs_CPP11_OR_GREATER_ (nsrs_CPLUSPLUS >= 201103L) +# define nsrs_CPP14_OR_GREATER (nsrs_CPLUSPLUS >= 201402L) +# define nsrs_CPP17_OR_GREATER (nsrs_CPLUSPLUS >= 201703L) +# define nsrs_CPP20_OR_GREATER (nsrs_CPLUSPLUS >= 202000L) + +// Use C++XX std::ring_span if available and requested: + +# define nsrs_HAVE_STD_RING_SPAN 0 + +//#if nsrs_CPP17_OR_GREATER && defined(__has_include ) +//# if __has_include( ) +//# define nsrs_HAVE_STD_RING_SPAN 1 +//# else +//# define nsrs_HAVE_STD_RING_SPAN 0 +//# endif +//#else +//# define nsrs_HAVE_STD_RING_SPAN 0 +//#endif + +# define nsrs_USES_STD_RING_SPAN \ + ((nsrs_CONFIG_SELECT_RING_SPAN == nsrs_RING_SPAN_STD) \ + || ((nsrs_CONFIG_SELECT_RING_SPAN == nsrs_RING_SPAN_DEFAULT) \ + && nsrs_HAVE_STD_RING_SPAN)) + +// Compiler versions: +// +// MSVC++ 6.0 _MSC_VER == 1200 (Visual Studio 6.0) +// MSVC++ 7.0 _MSC_VER == 1300 (Visual Studio .NET 2002) +// MSVC++ 7.1 _MSC_VER == 1310 (Visual Studio .NET 2003) +// MSVC++ 8.0 _MSC_VER == 1400 (Visual Studio 2005) +// MSVC++ 9.0 _MSC_VER == 1500 (Visual Studio 2008) +// MSVC++ 10.0 _MSC_VER == 1600 (Visual Studio 2010) +// MSVC++ 11.0 _MSC_VER == 1700 (Visual Studio 2012) +// MSVC++ 12.0 _MSC_VER == 1800 (Visual Studio 2013) +// MSVC++ 14.0 _MSC_VER == 1900 (Visual Studio 2015) +// ............_MSVC_LANG: 201402 for -std:c++14, default +// MSVC++ 14.1 _MSC_VER >= 1910 (Visual Studio 2017) +// ............_MSVC_LANG: 201402 for -std:c++14, default +// ............_MSVC_LANG: 201703 for -std:c++17 + +# if defined(_MSC_VER) && !defined(__clang__) +# define nsrs_COMPILER_MSVC_VER (_MSC_VER) +# define nsrs_COMPILER_MSVC_VERSION \ + (_MSC_VER / 10 - 10 * (5 + (_MSC_VER < 1900))) +# else +# define nsrs_COMPILER_MSVC_VER 0 +# define nsrs_COMPILER_MSVC_VERSION 0 +# endif + +# define nsrs_COMPILER_VERSION(major, minor, patch) \ + (10 * (10 * major + minor) + patch) + +# if defined(__clang__) +# define nsrs_COMPILER_CLANG_VERSION \ + nsrs_COMPILER_VERSION( \ + __clang_major__, __clang_minor__, __clang_patchlevel__) +# else +# define nsrs_COMPILER_CLANG_VERSION 0 +# endif + +# if defined(__GNUC__) && !defined(__clang__) +# define nsrs_COMPILER_GNUC_VERSION \ + nsrs_COMPILER_VERSION(__GNUC__, __GNUC_MINOR__, __GNUC_PATCHLEVEL__) +# else +# define nsrs_COMPILER_GNUC_VERSION 0 +# endif + +// half-open range [lo..hi): +//#define nsrs_BETWEEN( v, lo, hi ) ( (lo) <= (v) && (v) < (hi) ) + +// Presence of language and library features: + +# ifdef _HAS_CPP0X +# define nsrs_HAS_CPP0X _HAS_CPP0X +# else +# define nsrs_HAS_CPP0X 0 +# endif + +// Unless defined otherwise below, consider VC14 as C++11 for ring-span-lite: + +# if nsrs_COMPILER_MSVC_VER >= 1900 +# undef nsrs_CPP11_OR_GREATER +# define nsrs_CPP11_OR_GREATER 1 +# endif + +# define nsrs_CPP11_90 \ + (nsrs_CPP11_OR_GREATER_ || nsrs_COMPILER_MSVC_VER >= 1500) +# define nsrs_CPP11_100 \ + (nsrs_CPP11_OR_GREATER_ || nsrs_COMPILER_MSVC_VER >= 1600) +# define nsrs_CPP11_110 \ + (nsrs_CPP11_OR_GREATER_ || nsrs_COMPILER_MSVC_VER >= 1700) +# define nsrs_CPP11_120 \ + (nsrs_CPP11_OR_GREATER_ || nsrs_COMPILER_MSVC_VER >= 1800) +# define nsrs_CPP11_140 \ + (nsrs_CPP11_OR_GREATER_ || nsrs_COMPILER_MSVC_VER >= 1900) + +# define nsrs_CPP14_000 (nsrs_CPP14_OR_GREATER) +# define nsrs_CPP17_000 (nsrs_CPP17_OR_GREATER) + +// Presence of C++11 language features: + +// half-open range [lo..hi): +# define nsrs_BETWEEN(v, lo, hi) ((lo) <= (v) && (v) < (hi)) + +// Presence of C++11 language features: + +# define nsrs_HAVE_CONSTEXPR_11 nsrs_CPP11_140 +# define nsrs_HAVE_IS_DEFAULT nsrs_CPP11_140 +# define nsrs_HAVE_IS_DELETE nsrs_CPP11_140 +# define nsrs_HAVE_NOEXCEPT nsrs_CPP11_140 +# define nsrs_HAVE_NULLPTR nsrs_CPP11_100 + +// Presence of C++14 language features: + +# define nsrs_HAVE_CONSTEXPR_14 nsrs_CPP14_000 + +// Presence of C++17 language features: +// no tag + +// Presence of C++ library features: +// no tag + +// Compiler warning suppression: + +# if defined(__clang__) +# pragma clang diagnostic push +# pragma clang diagnostic ignored "-Wundef" +# define nsrs_RESTORE_WARNINGS() _Pragma("clang diagnostic pop") + +# elif defined __GNUC__ +# pragma GCC diagnostic push +# pragma GCC diagnostic ignored "-Wundef" +# define nsrs_RESTORE_WARNINGS() _Pragma("GCC diagnostic pop") + +# elif nsrs_COMPILER_MSVC_VERSION >= 140 +# define nsrs_DISABLE_MSVC_WARNINGS(codes) \ + __pragma(warning(push)) __pragma(warning(disable : codes)) +# define nsrs_RESTORE_WARNINGS() __pragma(warning(pop)) + +// Suppress the following MSVC warnings: +// - C4345: initialization behavior changed +// +// Suppress the following MSVC GSL warnings: +// - C26439, gsl::f.6 : special function 'function' can be declared 'noexcept' +// - C26440, gsl::f.6 : function 'function' can be declared 'noexcept' +// - C26472, gsl::t.1 : don't use a static_cast for arithmetic conversions; +// use brace initialization, gsl::narrow_cast or +// gsl::narrow +// - C26473: gsl::t.1 : don't cast between pointer types where the source type +// and the target type are the same +// - C26481: gsl::b.1 : don't use pointer arithmetic. Use span instead +// - C26490: gsl::t.1 : don't use reinterpret_cast + +nsrs_DISABLE_MSVC_WARNINGS(4345 26439 26440 26472 26473 26481 26490) + +# else +# define nsrs_RESTORE_WARNINGS() /*empty*/ +# endif + +// C++ feature usage: + +# if nsrs_HAVE_CONSTEXPR_11 +# define nsrs_constexpr constexpr +# else +# define nsrs_constexpr /*constexpr*/ +# endif + +# if nsrs_HAVE_CONSTEXPR_14 +# define nsrs_constexpr14 constexpr +# else +# define nsrs_constexpr14 /*constexpr*/ +# endif + +# if nsrs_HAVE_NOEXCEPT +# define nsrs_noexcept noexcept +# define nsrs_noexcept_op noexcept +# else +# define nsrs_noexcept /*noexcept*/ +# define nsrs_noexcept_op(expr) /*noexcept(expr)*/ +# endif + +# if nsrs_HAVE_NULLPTR +# define nsrs_nullptr nullptr +# else +# define nsrs_nullptr NULL +# endif + +// includes: + +# include +# include +# include + +// additional includes: + +# if !nsrs_CPP11_OR_GREATER +# include // std::swap() until C++11 +# endif + +namespace nonstd { + +# if nsrs_CPP11_OR_GREATER +using std::move; +# else +template +T const& +move(T const& t) +{ + return t; +} +# endif + +template +struct conditional { + typedef T type; +}; + +template +struct conditional { + typedef F type; +}; + +# if nsrs_CPP11_OR_GREATER + +template +using conditional_t = typename conditional::type; + +template +using enable_if_t = typename std::enable_if::type; + +# endif + +// +// element extraction policies: +// + +template +struct null_popper { + typedef void return_type; + + void operator()(T&) const nsrs_noexcept {} +}; + +template +struct default_popper { + typedef T return_type; + + T operator()(T& t) const + { + return nonstd::move(t); + } +}; + +template +struct copy_popper { + typedef T return_type; + +# if nsrs_RING_SPAN_LITE_EXTENSION +# if nsrs_CPP11_OR_GREATER + copy_popper(T t) : m_copy(std::move(t)) {} +# else + copy_popper(T const& t) : m_copy(t) {} +# endif +# else + copy_popper(T&& t) : copy(std::move(t)) {} +# endif + + T operator()(T& t) const + { + using std::swap; + T result(m_copy); + swap(t, result); + return result; + } + + T m_copy; +}; + +// forward-declare iterator: + +namespace ring_detail { + +template +class ring_iterator; + +} + +// +// ring span: +// +template > +class ring_span { +public: + typedef T value_type; + typedef T* pointer; + typedef T& reference; + typedef T const& const_reference; + + typedef std::size_t size_type; + + typedef ring_span type; + + typedef ring_detail::ring_iterator iterator; + typedef ring_detail::ring_iterator const_iterator; + +# if nsrs_RING_SPAN_LITE_EXTENSION + typedef std::reverse_iterator reverse_iterator; + typedef std::reverse_iterator const_reverse_iterator; +# endif + + // construction: + + template + ring_span(ContiguousIterator begin, + ContiguousIterator end, + Popper popper = Popper()) nsrs_noexcept + : m_data(&*begin) + , m_size(0) + , m_capacity(static_cast(end - begin)) + , m_front_idx(0) + , m_popper(nonstd::move(popper)) + { + } + + template + ring_span(ContiguousIterator begin, + ContiguousIterator end, + ContiguousIterator first, + size_type size, + Popper popper = Popper()) nsrs_noexcept + : m_data(&*begin) + , m_size(size) + , m_capacity(static_cast(end - begin)) + , m_front_idx(static_cast(first - begin)) + , m_popper(nonstd::move(popper)) + { + } + +# if nsrs_HAVE_IS_DEFAULT + ring_span(ring_span&&) = default; + ring_span& operator=(ring_span&&) = default; +# else +private: + ring_span(ring_span const&); + ring_span& operator=(ring_span const&); + +public: +# endif + + // observers: + + bool empty() const nsrs_noexcept + { + return m_size == 0; + } + + bool full() const nsrs_noexcept + { + return m_size == m_capacity; + } + + size_type size() const nsrs_noexcept + { + return m_size; + } + + size_type capacity() const nsrs_noexcept + { + return m_capacity; + } + + // element access: + + reference front() nsrs_noexcept + { + return *begin(); + } + + const_reference front() const nsrs_noexcept + { + return *begin(); + } + + reference back() nsrs_noexcept + { + return *(--end()); + } + + const_reference back() const nsrs_noexcept + { + return *(--end()); + } + + // iteration: + + iterator begin() nsrs_noexcept + { + return iterator(0, this); + } + + const_iterator begin() const nsrs_noexcept + { + return cbegin(); + } + + const_iterator cbegin() const nsrs_noexcept + { + return const_iterator(0, this); + } + + iterator end() nsrs_noexcept + { + return iterator(size(), this); + } + + const_iterator end() const nsrs_noexcept + { + return cend(); + } + + const_iterator cend() const nsrs_noexcept + { + return const_iterator(size(), this); + } + +# if nsrs_RING_SPAN_LITE_EXTENSION + + reverse_iterator rbegin() nsrs_noexcept + { + return reverse_iterator(end()); + } + + reverse_iterator rend() nsrs_noexcept + { + return reverse_iterator(begin()); + } + + const_reverse_iterator rbegin() const nsrs_noexcept + { + return crbegin(); + } + + const_reverse_iterator rend() const nsrs_noexcept + { + return crend(); + } + + const_reverse_iterator crbegin() const nsrs_noexcept + { + return const_reverse_iterator(cend()); + } + + const_reverse_iterator crend() const nsrs_noexcept + { + return const_reverse_iterator(cbegin()); + } +# endif + + void erase_from(iterator first) + { + m_size = static_cast(std::distance(begin(), first)); + } + + // element insertion, extraction: + + typename Popper::return_type pop_front() + { + assert(!empty()); + + reference element = front_(); + increment_front_(); + + return m_popper(element); + } + +# if nsrs_RING_SPAN_LITE_EXTENSION + typename Popper::return_type pop_back() + { + assert(!empty()); + + reference element = back_(); + decrement_back_(); + + return m_popper(element); + } +# endif + +# if nsrs_CPP11_OR_GREATER + template::value> > + void push_back(value_type const& value) + nsrs_noexcept_op((std::is_nothrow_copy_assignable::value)) +# else + void push_back(value_type const& value) +# endif + { + if (full()) + increment_front_and_back_(); + else + increment_back_(); + + back_() = value; + } + +# if nsrs_CPP11_OR_GREATER + template::value> > + void push_back(value_type&& value) + nsrs_noexcept_op((std::is_nothrow_move_assignable::value)) + { + if (full()) + increment_front_and_back_(); + else + increment_back_(); + + back_() = std::move(value); + } + + template + void emplace_back(Args&&... args) + nsrs_noexcept_op((std::is_nothrow_constructible::value + && std::is_nothrow_move_assignable::value)) + { + if (full()) + increment_front_and_back_(); + else + increment_back_(); + + back_() = T(std::forward(args)...); + } +# endif + +# if nsrs_RING_SPAN_LITE_EXTENSION + +# if nsrs_CPP11_OR_GREATER + template::value> > + void push_front(T const& value) + nsrs_noexcept_op((std::is_nothrow_copy_assignable::value)) +# else + void push_front(T const& value) +# endif + { + if (full()) + decrement_front_and_back_(); + else + decrement_front_(); + + front_() = value; + } + +# if nsrs_CPP11_OR_GREATER + template::value> > + void push_front(T&& value) + nsrs_noexcept_op((std::is_nothrow_move_assignable::value)) + { + if (full()) + decrement_front_and_back_(); + else + decrement_front_(); + + front_() = std::move(value); + } + + template + void emplace_front(Args&&... args) + nsrs_noexcept_op((std::is_nothrow_constructible::value + && std::is_nothrow_move_assignable::value)) + { + if (full()) + decrement_front_and_back_(); + else + decrement_front_(); + + front_() = T(std::forward(args)...); + } +# endif +# endif // nsrs_RING_SPAN_LITE_EXTENSION + + // swap: + + void swap(type& rhs) + nsrs_noexcept // nsrs_noexcept_op(std::is_nothrow_swappable::value); + { + using std::swap; + swap(m_data, rhs.m_data); + swap(m_size, rhs.m_size); + swap(m_capacity, rhs.m_capacity); + swap(m_front_idx, rhs.m_front_idx); + swap(m_popper, rhs.m_popper); + } + +private: + friend class ring_detail::ring_iterator; // const_iterator; + friend class ring_detail::ring_iterator; // iterator; + + size_type normalize_(size_type const idx) const nsrs_noexcept + { + return idx % m_capacity; + } + + reference at(size_type idx) nsrs_noexcept + { + return m_data[normalize_(m_front_idx + idx)]; + } + + const_reference at(size_type idx) const nsrs_noexcept + { + return m_data[normalize_(m_front_idx + idx)]; + } + + reference front_() nsrs_noexcept + { + return *(m_data + m_front_idx); + } + + const_reference front_() const nsrs_noexcept + { + return *(m_data + m_front_idx); + } + + reference back_() nsrs_noexcept + { + return *(m_data + normalize_(m_front_idx + m_size - 1)); + } + + const_reference back_() const nsrs_noexcept + { + return *(m_data + normalize_(m_front_idx + m_size - 1)); + } + + void increment_front_() nsrs_noexcept + { + m_front_idx = normalize_(m_front_idx + 1); + --m_size; + } + + void decrement_front_() nsrs_noexcept + { + m_front_idx = normalize_(m_front_idx + m_capacity - 1); + ++m_size; + } + + void increment_back_() nsrs_noexcept + { + ++m_size; + } + + void decrement_back_() nsrs_noexcept + { + --m_size; + } + + void increment_front_and_back_() nsrs_noexcept + { + m_front_idx = normalize_(m_front_idx + 1); + } + + void decrement_front_and_back_() nsrs_noexcept + { + m_front_idx = normalize_(m_front_idx + m_capacity - 1); + } + +private: + pointer m_data; + size_type m_size; + size_type m_capacity; + size_type m_front_idx; + Popper m_popper; +}; + +// swap: + +template +inline void +swap(ring_span& lhs, ring_span& rhs) + nsrs_noexcept_op(nsrs_noexcept_op(lhs.swap(rhs))) +{ + lhs.swap(rhs); +} + +namespace ring_detail { + +// +// ring iterator: +// +# if 0 +template< class RS, bool is_const > +class ring_iterator : public std::iterator +< + std::random_access_iterator_tag + , typename nonstd::conditional::type +> +# endif + +template +class ring_iterator { +public: + typedef ring_iterator type; + + typedef std::ptrdiff_t difference_type; + typedef typename RS::value_type value_type; + + typedef typename nonstd:: + conditional::type* pointer; + typedef typename nonstd:: + conditional::type& reference; + typedef std::random_access_iterator_tag iterator_category; + +# if nsrs_CPP11_OR_GREATER + ring_iterator() = default; +# else + ring_iterator() : m_idx(), m_rs() {} +# endif + +# if nsrs_RING_SPAN_LITE_EXTENSION + // conversion to const iterator: + + operator ring_iterator() const nsrs_noexcept + { + return ring_iterator(m_idx, m_rs); + } +# endif + + // access content: + + reference operator*() const nsrs_noexcept + { + return m_rs->at(m_idx); + } + + // advance iterator: + + type& operator++() nsrs_noexcept + { + ++m_idx; + return *this; + } + + type operator++(int) nsrs_noexcept + { + type r(*this); + ++*this; + return r; + } + + type& operator--() nsrs_noexcept + { + --m_idx; + return *this; + } + + type operator--(int) nsrs_noexcept + { + type r(*this); + --*this; + return r; + } + +# if defined(__clang__) || defined(__GNUC__) +# pragma GCC diagnostic push +# pragma GCC diagnostic ignored "-Wsign-conversion" +# endif + + type& operator+=(int i) nsrs_noexcept + { + m_idx += i; + return *this; + } + + type& operator-=(int i) nsrs_noexcept + { + m_idx -= i; + return *this; + } + +# if defined(__clang__) || defined(__GNUC__) +# pragma GCC diagnostic pop +# endif + +# if nsrs_RING_SPAN_LITE_EXTENSION + + template + difference_type operator-(ring_iterator const& rhs) const + nsrs_noexcept + { + return static_cast(this->m_idx) + - static_cast(rhs.m_idx); + } +# endif + + // comparison: + + template + bool operator<(ring_iterator const& rhs) const nsrs_noexcept + { + assert(this->m_rs == rhs.m_rs); + return (this->m_idx < rhs.m_idx); + } + + template + bool operator==(ring_iterator const& rhs) const nsrs_noexcept + { + assert(this->m_rs == rhs.m_rs); + return (this->m_idx == rhs.m_idx); + } + + // other comparisons expressed in <, ==: + + template + inline bool operator!=(ring_iterator const& rhs) const nsrs_noexcept + { + return !(*this == rhs); + } + + template + inline bool operator<=(ring_iterator const& rhs) const nsrs_noexcept + { + return !(rhs < *this); + } + + template + inline bool operator>(ring_iterator const& rhs) const nsrs_noexcept + { + return rhs < *this; + } + + template + inline bool operator>=(ring_iterator const& rhs) const nsrs_noexcept + { + return !(*this < rhs); + } + +private: + friend RS; // clang: non-class friend type 'RS' is a C++11 extension + // [-Wc++11-extensions] + friend class ring_iterator; + + typedef typename RS::size_type size_type; + typedef + typename nonstd::conditional::type ring_type; + + ring_iterator(size_type idx, + typename nonstd::conditional::type* + rs) nsrs_noexcept + : m_idx(idx) + , m_rs(rs) + { + } + +private: + size_type m_idx; + ring_type* m_rs; +}; + +// advanced iterator: + +template +inline ring_iterator +operator+(ring_iterator it, int i) nsrs_noexcept +{ + it += i; + return it; +} + +template +inline ring_iterator +operator-(ring_iterator it, int i) nsrs_noexcept +{ + it -= i; + return it; +} + +} // namespace ring_detail +} // namespace nonstd + +nsrs_RESTORE_WARNINGS() + +#endif // NONSTD_RING_SPAN_LITE_HPP -- cgit v1.2.3