diff options
Diffstat (limited to 'gsl/span.h')
-rw-r--r-- | gsl/span.h | 826 |
1 files changed, 826 insertions, 0 deletions
diff --git a/gsl/span.h b/gsl/span.h new file mode 100644 index 0000000..1405aa9 --- /dev/null +++ b/gsl/span.h @@ -0,0 +1,826 @@ + +/////////////////////////////////////////////////////////////////////////////// +// +// Copyright (c) 2015 Microsoft Corporation. All rights reserved. +// +// This code is licensed under the MIT License (MIT). +// +// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, +// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN +// THE SOFTWARE. +// +/////////////////////////////////////////////////////////////////////////////// + +#pragma once + +#ifndef GSL_SPAN_H +#define GSL_SPAN_H + +#include "gsl_assert.h" +#include "gsl_byte.h" +#include "gsl_util.h" +#include <array> +#include <iterator> +#include <limits> +#include <stdexcept> +#include <type_traits> +#include <utility> + +#ifdef _MSC_VER + +#pragma warning(push) + +// turn off some warnings that are noisy about our Expects statements +#pragma warning(disable : 4127) // conditional expression is constant + +// blanket turn off warnings from CppCoreCheck for now +// so people aren't annoyed by them when running the tool. +// more targeted suppressions will be added in a future update to the GSL +#pragma warning(disable : 26481 26482 26483 26485 26490 26491 26492 26493 26495) + +// No MSVC does constexpr fully yet +#pragma push_macro("constexpr") +#define constexpr + +// VS 2013 workarounds +#if _MSC_VER <= 1800 + +#define GSL_MSVC_HAS_VARIADIC_CTOR_BUG +#define GSL_MSVC_NO_DEFAULT_MOVE_CTOR +#define GSL_MSVC_NO_CPP14_STD_EQUAL + +// noexcept is not understood +#ifndef GSL_THROW_ON_CONTRACT_VIOLATION +#pragma push_macro("noexcept") +#define noexcept /* nothing */ +#endif + +#pragma push_macro("alignof") +#define alignof __alignof + +// turn off some misguided warnings +#pragma warning(push) +#pragma warning(disable : 4351) // warns about newly introduced aggregate initializer behavior +#pragma warning(disable : 4512) // warns that assignment op could not be generated + +#endif // _MSC_VER <= 1800 + +#endif // _MSC_VER + +#ifdef GSL_THROW_ON_CONTRACT_VIOLATION + +#ifdef _MSC_VER +#pragma push_macro("noexcept") +#endif + +#define noexcept /* nothing */ + +#endif // GSL_THROW_ON_CONTRACT_VIOLATION + +namespace gsl +{ + +// [views.constants], constants +constexpr const std::ptrdiff_t dynamic_extent = -1; + +template <class ElementType, std::ptrdiff_t Extent = dynamic_extent> +class span; + +// implementation details +namespace details +{ + template <class T> + struct is_span_oracle : std::false_type + { + }; + + template <class ElementType, std::ptrdiff_t Extent> + struct is_span_oracle<gsl::span<ElementType, Extent>> : std::true_type + { + }; + + template <class T> + struct is_span : public is_span_oracle<std::remove_cv_t<T>> + { + }; + + template <class T> + struct is_std_array_oracle : std::false_type + { + }; + + template <class ElementType, size_t Extent> + struct is_std_array_oracle<std::array<ElementType, Extent>> : std::true_type + { + }; + + template <class T> + struct is_std_array : public is_std_array_oracle<std::remove_cv_t<T>> + { + }; + + template <class From, class To> + struct is_allowed_pointer_conversion + : public std::integral_constant<bool, std::is_pointer<From>::value && + std::is_pointer<To>::value && + std::is_convertible<From, To>::value> + { + }; + + template <class From, class To> + struct is_allowed_integral_conversion + : public std::integral_constant< + bool, std::is_integral<From>::value && std::is_integral<To>::value && + sizeof(From) == sizeof(To) && alignof(From) == alignof(To) && + std::is_convertible<From, To>::value> + { + }; + + template <std::ptrdiff_t From, std::ptrdiff_t To> + struct is_allowed_extent_conversion + : public std::integral_constant<bool, From == To || From == gsl::dynamic_extent || + To == gsl::dynamic_extent> + { + }; + + template <class From, class To> + struct is_allowed_element_type_conversion + : public std::integral_constant<bool, std::is_same<From, std::remove_cv_t<To>>::value || + is_allowed_pointer_conversion<From, To>::value || + is_allowed_integral_conversion<From, To>::value> + { + }; + + template <class From> + struct is_allowed_element_type_conversion<From, byte> + : public std::integral_constant<bool, !std::is_const<From>::value> + { + }; + + template <class From> + struct is_allowed_element_type_conversion<From, const byte> : public std::true_type + { + }; + + template <class Span> + class const_span_iterator + { + public: + using iterator_category = std::random_access_iterator_tag; + using value_type = typename Span::element_type; + using difference_type = std::ptrdiff_t; + + using const_pointer = std::add_const_t<value_type*>; + using pointer = const_pointer; + + using const_reference = std::add_const_t<value_type&>; + using reference = const_reference; + + constexpr const_span_iterator() : const_span_iterator(nullptr, 0) {} + constexpr const_span_iterator(const Span* span, typename Span::index_type index) + : span_(span), index_(index) + { + Expects(span == nullptr || (index_ >= 0 && index <= span_->length())); + } + + constexpr reference operator*() const + { + Expects(span_); + return (*span_)[index_]; + } + + constexpr pointer operator->() const + { + Expects(span_); + return &((*span_)[index_]); + } + + constexpr const_span_iterator& operator++() noexcept + { + Expects(span_ && index_ >= 0 && index_ < span_->length()); + ++index_; + return *this; + } + + constexpr const_span_iterator operator++(int) noexcept + { + auto ret = *this; + ++(*this); + return ret; + } + + constexpr const_span_iterator& operator--() noexcept + { + Expects(span_ && index_ > 0 && index_ <= span_->length()); + --index_; + return *this; + } + + constexpr const_span_iterator operator--(int) noexcept + { + auto ret = *this; + --(*this); + return ret; + } + + constexpr const_span_iterator operator+(difference_type n) const noexcept + { + auto ret = *this; + return ret += n; + } + + constexpr const_span_iterator& operator+=(difference_type n) noexcept + { + Expects(span_ && (index_ + n) >= 0 && (index_ + n) <= span_->length()); + index_ += n; + return *this; + } + + constexpr const_span_iterator operator-(difference_type n) const noexcept + { + auto ret = *this; + return ret -= n; + } + + constexpr const_span_iterator& operator-=(difference_type n) noexcept + { + return *this += -n; + } + + constexpr difference_type operator-(const const_span_iterator& rhs) const noexcept + { + Expects(span_ == rhs.span_); + return index_ - rhs.index_; + } + + constexpr reference operator[](difference_type n) const noexcept { return *(*this + n); } + + constexpr bool operator==(const const_span_iterator& rhs) const noexcept + { + return span_ == rhs.span_ && index_ == rhs.index_; + } + + constexpr bool operator!=(const const_span_iterator& rhs) const noexcept + { + return !(*this == rhs); + } + + constexpr bool operator<(const const_span_iterator& rhs) const noexcept + { + Expects(span_ == rhs.span_); + return index_ < rhs.index_; + } + + constexpr bool operator<=(const const_span_iterator& rhs) const noexcept + { + return !(rhs < *this); + } + + constexpr bool operator>(const const_span_iterator& rhs) const noexcept + { + return rhs < *this; + } + + constexpr bool operator>=(const const_span_iterator& rhs) const noexcept + { + return !(rhs > *this); + } + + void swap(const_span_iterator& rhs) noexcept + { + std::swap(index_, rhs.index_); + std::swap(span_, rhs.span_); + } + + private: + const Span* span_; + std::ptrdiff_t index_; + }; + + template <class Span> + class span_iterator + { + public: + using iterator_category = std::random_access_iterator_tag; + using value_type = typename Span::element_type; + using difference_type = std::ptrdiff_t; + + using pointer = value_type*; + using reference = value_type&; + + constexpr span_iterator() : span_iterator(nullptr, 0) {} + constexpr span_iterator(const Span* span, typename Span::index_type index) + : span_(span), index_(index) + { + Expects(span == nullptr || (index_ >= 0 && index <= span_->length())); + } + + constexpr reference operator*() const + { + Expects(span_); + return (*span_)[index_]; + } + + constexpr pointer operator->() const + { + Expects(span_); + return &((*span_)[index_]); + } + + constexpr span_iterator& operator++() noexcept + { + Expects(span_ && index_ >= 0 && index_ < span_->length()); + ++index_; + return *this; + } + + constexpr span_iterator operator++(int) noexcept + { + auto ret = *this; + ++(*this); + return ret; + } + + constexpr span_iterator& operator--() noexcept + { + Expects(span_ && index_ > 0 && index_ <= span_->length()); + --index_; + return *this; + } + + constexpr span_iterator operator--(int) noexcept + { + auto ret = *this; + --(*this); + return ret; + } + + constexpr span_iterator operator+(difference_type n) const noexcept + { + auto ret = *this; + return ret += n; + } + + constexpr span_iterator& operator+=(difference_type n) noexcept + { + Expects(span_ && (index_ + n) >= 0 && (index_ + n) <= span_->length()); + index_ += n; + return *this; + } + + constexpr span_iterator operator-(difference_type n) const noexcept + { + auto ret = *this; + return ret -= n; + } + + constexpr span_iterator& operator-=(difference_type n) noexcept { return *this += -n; } + + constexpr difference_type operator-(const span_iterator& rhs) const noexcept + { + Expects(span_ == rhs.span_); + return index_ - rhs.index_; + } + + constexpr reference operator[](difference_type n) const noexcept { return *(*this + n); } + + constexpr bool operator==(const span_iterator& rhs) const noexcept + { + return span_ == rhs.span_ && index_ == rhs.index_; + } + + constexpr bool operator!=(const span_iterator& rhs) const noexcept + { + return !(*this == rhs); + } + + constexpr bool operator<(const span_iterator& rhs) const noexcept + { + Expects(span_ == rhs.span_); + return index_ < rhs.index_; + } + + constexpr bool operator<=(const span_iterator& rhs) const noexcept + { + return !(rhs < *this); + } + + constexpr bool operator>(const span_iterator& rhs) const noexcept { return rhs < *this; } + + constexpr bool operator>=(const span_iterator& rhs) const noexcept + { + return !(rhs > *this); + } + + void swap(span_iterator& rhs) noexcept + { + std::swap(index_, rhs.index_); + std::swap(span_, rhs.span_); + } + + private: + const Span* span_; + std::ptrdiff_t index_; + }; + + template <typename Span> + constexpr const_span_iterator<Span> + operator+(typename const_span_iterator<Span>::difference_type n, + const const_span_iterator<Span>& rhs) noexcept + { + return rhs + n; + } + + template <typename Span> + constexpr const_span_iterator<Span> + operator-(typename const_span_iterator<Span>::difference_type n, + const const_span_iterator<Span>& rhs) noexcept + { + return rhs - n; + } + + template <typename Span> + constexpr span_iterator<Span> operator+(typename span_iterator<Span>::difference_type n, + const span_iterator<Span>& rhs) noexcept + { + return rhs + n; + } + + template <typename Span> + constexpr span_iterator<Span> operator-(typename span_iterator<Span>::difference_type n, + const span_iterator<Span>& rhs) noexcept + { + return rhs - n; + } + + template <std::ptrdiff_t Ext> + class extent_type + { + public: + using index_type = std::ptrdiff_t; + + static_assert(Ext >= 0, "A fixed-size span must be >= 0 in size."); + + constexpr extent_type() noexcept {} + + template <index_type Other> + constexpr extent_type(extent_type<Other> ext) noexcept + { + static_assert(Other == Ext || Other == dynamic_extent, + "Mismatch between fixed-size extent and size of initializing data."); + Expects(ext.size() == Ext); + } + + constexpr extent_type(index_type size) { Expects(size == Ext); } + + constexpr inline index_type size() const noexcept { return Ext; } + }; + + template <> + class extent_type<dynamic_extent> + { + public: + using index_type = std::ptrdiff_t; + + template <index_type Other> + explicit constexpr extent_type(extent_type<Other> ext) : size_(ext.size()) + { + } + + explicit constexpr extent_type(index_type size) : size_(size) { Expects(size >= 0); } + + constexpr inline index_type size() const noexcept { return size_; } + + private: + index_type size_; + }; +} // namespace details + +// [span], class template span +template <class ElementType, std::ptrdiff_t Extent> +class span +{ +public: + // constants and types + using element_type = ElementType; + using index_type = std::ptrdiff_t; + using pointer = element_type*; + using reference = element_type&; + + using iterator = details::span_iterator<span<ElementType, Extent>>; + using const_iterator = details::const_span_iterator<span<ElementType, Extent>>; + using reverse_iterator = std::reverse_iterator<iterator>; + using const_reverse_iterator = std::reverse_iterator<const_iterator>; + + constexpr static const index_type extent = Extent; + + // [span.cons], span constructors, copy, assignment, and destructor + constexpr span() noexcept : storage_(nullptr, details::extent_type<0>()) {} + + constexpr span(std::nullptr_t) noexcept : span() {} + + constexpr span(pointer ptr, index_type count) : storage_(ptr, count) {} + + constexpr span(pointer firstElem, pointer lastElem) + : storage_(firstElem, std::distance(firstElem, lastElem)) + { + } + + template <size_t N> + constexpr span(element_type (&arr)[N]) noexcept : storage_(&arr[0], details::extent_type<N>()) + { + } + + template <size_t N, class ArrayElementType = std::remove_const_t<element_type>> + constexpr span(std::array<ArrayElementType, N>& arr) noexcept + : storage_(&arr[0], details::extent_type<N>()) + { + } + + template <size_t N> + constexpr span(const std::array<std::remove_const_t<element_type>, N>& arr) noexcept + : storage_(&arr[0], details::extent_type<N>()) + { + } + + // NB: the SFINAE here uses .data() as a incomplete/imperfect proxy for the requirement + // on Container to be a contiguous sequence container. + template <class Container, + class = std::enable_if_t< + !details::is_span<Container>::value && !details::is_std_array<Container>::value && + std::is_convertible<typename Container::pointer, pointer>::value && + std::is_convertible<typename Container::pointer, + decltype(std::declval<Container>().data())>::value>> + constexpr span(Container& cont) : span(cont.data(), cont.size()) + { + } + + template <class Container, + class = std::enable_if_t< + std::is_const<element_type>::value && !details::is_span<Container>::value && + std::is_convertible<typename Container::pointer, pointer>::value && + std::is_convertible<typename Container::pointer, + decltype(std::declval<Container>().data())>::value>> + constexpr span(const Container& cont) : span(cont.data(), cont.size()) + { + } + + constexpr span(const span& other) noexcept = default; +#ifndef GSL_MSVC_NO_DEFAULT_MOVE_CTOR + constexpr span(span&& other) noexcept = default; +#else + constexpr span(span&& other) noexcept : storage_(std::move(other.storage_)) {} +#endif + + template < + class OtherElementType, std::ptrdiff_t OtherExtent, + class = std::enable_if_t< + details::is_allowed_extent_conversion<OtherExtent, Extent>::value && + details::is_allowed_element_type_conversion<OtherElementType, element_type>::value>> + constexpr span(const span<OtherElementType, OtherExtent>& other) + : storage_(reinterpret_cast<pointer>(other.data()), + details::extent_type<OtherExtent>(other.size())) + { + } + + template < + class OtherElementType, std::ptrdiff_t OtherExtent, + class = std::enable_if_t< + details::is_allowed_extent_conversion<OtherExtent, Extent>::value && + details::is_allowed_element_type_conversion<OtherElementType, element_type>::value>> + constexpr span(span<OtherElementType, OtherExtent>&& other) + : storage_(reinterpret_cast<pointer>(other.data()), + details::extent_type<OtherExtent>(other.size())) + { + } + + ~span() noexcept = default; + constexpr span& operator=(const span& other) noexcept = default; + +#ifndef GSL_MSVC_NO_DEFAULT_MOVE_CTOR + constexpr span& operator=(span&& other) noexcept = default; +#else + constexpr span& operator=(span&& other) noexcept + { + storage_ = std::move(other.storage_); + return *this; + } +#endif + // [span.sub], span subviews + template <std::ptrdiff_t Count> + constexpr span<element_type, Count> first() const + { + Expects(Count >= 0 && Count <= size()); + return {data(), Count}; + } + + template <std::ptrdiff_t Count> + constexpr span<element_type, Count> last() const + { + Expects(Count >= 0 && Count <= size()); + return {data() + (size() - Count), Count}; + } + + template <std::ptrdiff_t Offset, std::ptrdiff_t Count = dynamic_extent> + constexpr span<element_type, Count> subspan() const + { + Expects((Offset == 0 || (Offset > 0 && Offset <= size())) && + (Count == dynamic_extent || (Count >= 0 && Offset + Count <= size()))); + return {data() + Offset, Count == dynamic_extent ? size() - Offset : Count}; + } + + constexpr span<element_type, dynamic_extent> first(index_type count) const + { + Expects(count >= 0 && count <= size()); + return {data(), count}; + } + + constexpr span<element_type, dynamic_extent> last(index_type count) const + { + Expects(count >= 0 && count <= size()); + return {data() + (size() - count), count}; + } + + constexpr span<element_type, dynamic_extent> subspan(index_type offset, + index_type count = dynamic_extent) const + { + Expects((offset == 0 || (offset > 0 && offset <= size())) && + (count == dynamic_extent || (count >= 0 && offset + count <= size()))); + return {data() + offset, count == dynamic_extent ? size() - offset : count}; + } + + // [span.obs], span observers + constexpr index_type length() const noexcept { return size(); } + constexpr index_type size() const noexcept { return storage_.size(); } + constexpr index_type length_bytes() const noexcept { return size_bytes(); } + constexpr index_type size_bytes() const noexcept { return size() * sizeof(element_type); } + constexpr bool empty() const noexcept { return size() == 0; } + + // [span.elem], span element access + constexpr reference operator[](index_type idx) const + { + Expects(idx >= 0 && idx < storage_.size()); + return data()[idx]; + } + constexpr reference operator()(index_type idx) const { return this->operator[](idx); } + constexpr pointer data() const noexcept { return storage_.data(); } + + // [span.iter], span iterator support + iterator begin() const noexcept { return {this, 0}; } + iterator end() const noexcept { return {this, length()}; } + + const_iterator cbegin() const noexcept { return {this, 0}; } + const_iterator cend() const noexcept { return {this, length()}; } + + reverse_iterator rbegin() const noexcept { return reverse_iterator{end()}; } + reverse_iterator rend() const noexcept { return reverse_iterator{begin()}; } + + const_reverse_iterator crbegin() const noexcept { return const_reverse_iterator{cend()}; } + const_reverse_iterator crend() const noexcept { return const_reverse_iterator{cbegin()}; } + +private: + // this implementation detail class lets us take advantage of the + // empty base class optimization to pay for only storage of a single + // pointer in the case of fixed-size spans + template <class ExtentType> + class storage_type : public ExtentType + { + public: + template <class OtherExtentType> + constexpr storage_type(pointer data, OtherExtentType ext) : ExtentType(ext), data_(data) + { + Expects((!data && ExtentType::size() == 0) || (data && ExtentType::size() >= 0)); + } + + constexpr inline pointer data() const noexcept { return data_; } + + private: + pointer data_; + }; + + storage_type<details::extent_type<Extent>> storage_; +}; + +// [span.comparison], span comparison operators +template <class ElementType, std::ptrdiff_t FirstExtent, std::ptrdiff_t SecondExtent> +constexpr bool operator==(const span<ElementType, FirstExtent>& l, + const span<ElementType, SecondExtent>& r) +{ +#ifdef GSL_MSVC_NO_CPP14_STD_EQUAL + return (l.size() == r.size()) && std::equal(l.begin(), l.end(), r.begin()); +#else + return std::equal(l.begin(), l.end(), r.begin(), r.end()); +#endif +} + +template <class ElementType, std::ptrdiff_t Extent> +constexpr bool operator!=(const span<ElementType, Extent>& l, const span<ElementType, Extent>& r) +{ + return !(l == r); +} + +template <class ElementType, std::ptrdiff_t Extent> +constexpr bool operator<(const span<ElementType, Extent>& l, const span<ElementType, Extent>& r) +{ + return std::lexicographical_compare(l.begin(), l.end(), r.begin(), r.end()); +} + +template <class ElementType, std::ptrdiff_t Extent> +constexpr bool operator<=(const span<ElementType, Extent>& l, const span<ElementType, Extent>& r) +{ + return !(l > r); +} + +template <class ElementType, std::ptrdiff_t Extent> +constexpr bool operator>(const span<ElementType, Extent>& l, const span<ElementType, Extent>& r) +{ + return r < l; +} + +template <class ElementType, std::ptrdiff_t Extent> +constexpr bool operator>=(const span<ElementType, Extent>& l, const span<ElementType, Extent>& r) +{ + return !(l < r); +} + +namespace details +{ + // if we only supported compilers with good constexpr support then + // this pair of classes could collapse down to a constexpr function + + // we should use a narrow_cast<> to go to size_t, but older compilers may not see it as + // constexpr + // and so will fail compilation of the template + template <class ElementType, std::ptrdiff_t Extent> + struct calculate_byte_size + : std::integral_constant<std::ptrdiff_t, + static_cast<std::ptrdiff_t>(sizeof(ElementType) * + static_cast<std::size_t>(Extent))> + { + }; + + template <class ElementType> + struct calculate_byte_size<ElementType, dynamic_extent> + : std::integral_constant<std::ptrdiff_t, dynamic_extent> + { + }; +} + +// [span.objectrep], views of object representation +template <class ElementType, std::ptrdiff_t Extent> +span<const byte, details::calculate_byte_size<ElementType, Extent>::value> +as_bytes(span<ElementType, Extent> s) noexcept +{ + return {reinterpret_cast<const byte*>(s.data()), s.size_bytes()}; +} + +template <class ElementType, std::ptrdiff_t Extent, + class = std::enable_if_t<!std::is_const<ElementType>::value>> +span<byte, details::calculate_byte_size<ElementType, Extent>::value> +as_writeable_bytes(span<ElementType, Extent> s) noexcept +{ + return {reinterpret_cast<byte*>(s.data()), s.size_bytes()}; +} + +} // namespace gsl + +#ifdef _MSC_VER + +#undef constexpr +#pragma pop_macro("constexpr") + +#if _MSC_VER <= 1800 +#pragma warning(pop) + +#ifndef GSL_THROW_ON_CONTRACT_VIOLATION +#undef noexcept +#pragma pop_macro("noexcept") +#endif // GSL_THROW_ON_CONTRACT_VIOLATION + +#pragma pop_macro("alignof") + +#undef GSL_MSVC_HAS_VARIADIC_CTOR_BUG + +#endif // _MSC_VER <= 1800 + +#endif // _MSC_VER + +#if defined(GSL_THROW_ON_CONTRACT_VIOLATION) + +#undef noexcept + +#ifdef _MSC_VER +#pragma pop_macro("noexcept") +#endif + +#endif // GSL_THROW_ON_CONTRACT_VIOLATION + +#ifdef _MSC_VER +#pragma warning(pop) +#endif + +#endif // GSL_SPAN_H |