1238 lines
39 KiB
C++
1238 lines
39 KiB
C++
/*
|
|
* This Source Code Form is subject to the terms of the Mozilla Public
|
|
* License, v. 2.0. If a copy of the MPL was not distributed with this
|
|
* file, You can obtain one at http://mozilla.org/MPL/2.0/.
|
|
*
|
|
* Copyright 2015-2019 Danny Robson <danny@nerdcruft.net>
|
|
*/
|
|
|
|
#pragma once
|
|
|
|
#include "annotation.hpp"
|
|
#include "cast.hpp"
|
|
#include "debug/assert.hpp"
|
|
#include "maths.hpp"
|
|
#include "platform.hpp"
|
|
#include "types/traits.hpp"
|
|
|
|
#include <cstdlib>
|
|
#include <iosfwd>
|
|
#include <string>
|
|
#include <cstring>
|
|
#include <stdexcept>
|
|
#include <iterator>
|
|
#include <type_traits>
|
|
#include <concepts>
|
|
#include <iterator>
|
|
|
|
|
|
namespace cruft {
|
|
template <typename BeginT, typename EndT = BeginT>
|
|
struct view {
|
|
public:
|
|
using begin_type = BeginT;
|
|
using end_type = EndT;
|
|
|
|
using iterator = begin_type;
|
|
|
|
//---------------------------------------------------------------------
|
|
using value_type = typename std::iterator_traits<
|
|
remove_restrict_t<BeginT>
|
|
>::value_type;
|
|
|
|
using size_type = size_t;
|
|
|
|
//---------------------------------------------------------------------
|
|
constexpr
|
|
view (const BeginT &first, const EndT &last) noexcept:
|
|
m_begin (first),
|
|
m_end (last)
|
|
{
|
|
if constexpr (cruft::is_lteq_orderable_v<BeginT,EndT>) {
|
|
CHECK (m_begin <= m_end);
|
|
}
|
|
}
|
|
|
|
|
|
template <
|
|
typename ContainerT,
|
|
typename = std::void_t<
|
|
decltype (std::declval<ContainerT&> ().begin ()),
|
|
decltype (std::declval<ContainerT&> ().end ())
|
|
>
|
|
>
|
|
view (ContainerT &rhs) noexcept (
|
|
noexcept (std::declval<ContainerT> ().begin ()) &&
|
|
noexcept (std::declval<ContainerT> ().end ())
|
|
)
|
|
: view (rhs.begin (), rhs.end ())
|
|
{ ; }
|
|
|
|
|
|
template <
|
|
typename ContainerT,
|
|
typename = std::void_t<
|
|
decltype (std::declval<ContainerT const&> ().begin ()),
|
|
decltype (std::declval<ContainerT const&> ().end ())
|
|
>
|
|
>
|
|
view (const ContainerT &rhs):
|
|
view (rhs.begin (), rhs.end ())
|
|
{ ; }
|
|
|
|
|
|
//---------------------------------------------------------------------
|
|
// Construction from pointer/size representations for ease of use with
|
|
// legacy C code.
|
|
template <
|
|
typename CountT,
|
|
typename = std::enable_if_t<std::is_integral_v<CountT>,void>
|
|
>
|
|
constexpr view (
|
|
const BeginT &_begin,
|
|
CountT _size
|
|
) : view (_begin, _begin + _size)
|
|
{ ; }
|
|
|
|
|
|
//---------------------------------------------------------------------
|
|
// implicit conversion from const pointer const views to const pointer views
|
|
template <
|
|
typename ValueT,
|
|
typename = std::enable_if_t<
|
|
std::is_same_v<BeginT, const ValueT**> &&
|
|
std::is_same_v<EndT, const ValueT**>
|
|
>
|
|
>
|
|
view (const view<const ValueT*const*,const ValueT*const*> &rhs):
|
|
view (
|
|
const_cast<const ValueT**> (rhs.begin ()),
|
|
const_cast<const ValueT**> (rhs.end ())
|
|
)
|
|
{ ; }
|
|
|
|
//---------------------------------------------------------------------
|
|
// implicit conversion from pointer views to const pointer views
|
|
template <
|
|
typename ValueT,
|
|
typename = std::enable_if_t<
|
|
std::is_same_v<BeginT, const ValueT*> &&
|
|
std::is_same_v<EndT, const ValueT*>
|
|
>
|
|
>
|
|
view (const view<ValueT*,ValueT*> &rhs):
|
|
view (rhs.begin (), rhs.end ())
|
|
{ ; }
|
|
|
|
|
|
//---------------------------------------------------------------------
|
|
// explicitly cater for the char array case so that we don't
|
|
// accidentally include the trailing null in the data.
|
|
template <std::size_t N>
|
|
view (const char (&value)[N]):
|
|
view {std::begin (value), std::begin (value) + N - 1}
|
|
{
|
|
static_assert (N > 0);
|
|
}
|
|
|
|
|
|
//---------------------------------------------------------------------
|
|
view (const char *str):
|
|
view { str, str + strlen (str) }
|
|
{ ; }
|
|
|
|
|
|
//---------------------------------------------------------------------
|
|
view (char *str):
|
|
view (str, str + strlen (str))
|
|
{ ; }
|
|
|
|
|
|
//---------------------------------------------------------------------
|
|
template <std::size_t N>
|
|
view (char (&value)[N]):
|
|
view {std::begin (value), std::begin (value) + N - 1}
|
|
{
|
|
static_assert (N > 0);
|
|
}
|
|
|
|
|
|
//---------------------------------------------------------------------
|
|
template <std::size_t N, typename ValueT>
|
|
view (const ValueT(&value)[N]):
|
|
view {std::begin (value), std::end (value)}
|
|
{ ; }
|
|
|
|
|
|
//---------------------------------------------------------------------
|
|
template <std::size_t N, typename ValueT>
|
|
view (ValueT(&value)[N]):
|
|
view {std::begin (value), std::end (value)}
|
|
{ ; }
|
|
|
|
|
|
//---------------------------------------------------------------------
|
|
constexpr view (const view &) noexcept (
|
|
std::is_nothrow_copy_constructible_v<BeginT> && std::is_nothrow_copy_constructible_v<EndT>
|
|
) = default;
|
|
|
|
|
|
constexpr view (view &&) noexcept (
|
|
std::is_nothrow_move_constructible_v<BeginT> && std::is_nothrow_move_constructible_v<EndT>
|
|
) = default;
|
|
|
|
|
|
view& operator= (view const &rhs) noexcept (
|
|
std::is_nothrow_copy_assignable_v<BeginT> && std::is_nothrow_copy_assignable_v<EndT>
|
|
) = default;
|
|
|
|
|
|
view& operator= (view &&rhs) noexcept (
|
|
std::is_nothrow_move_assignable_v<BeginT> && std::is_nothrow_move_assignable_v<EndT>
|
|
) = default;
|
|
|
|
|
|
//---------------------------------------------------------------------
|
|
// allow null construction of views where IteratorT is constructible
|
|
// from nullptr_t
|
|
//
|
|
// ideally we would avoid exposing this as it promotes use of nulls but
|
|
// it simplifies construction of views that are data members of classes
|
|
// when we may not immediately know the values we should contain.
|
|
constexpr view (std::nullptr_t) noexcept:
|
|
view {nullptr,nullptr}
|
|
{ ; }
|
|
|
|
|
|
//---------------------------------------------------------------------
|
|
template <typename CharT, typename Traits, typename Allocator>
|
|
view (std::basic_string<CharT,Traits,Allocator> &val):
|
|
view (std::data (val), std::size (val))
|
|
{ ; }
|
|
|
|
|
|
//---------------------------------------------------------------------
|
|
template <typename CharT, typename Traits, typename Allocator>
|
|
view (const std::basic_string<CharT,Traits,Allocator> &val):
|
|
view (std::data (val), std::size (val))
|
|
{ ; }
|
|
|
|
|
|
//---------------------------------------------------------------------
|
|
template <typename ValueT, typename AllocatorT>
|
|
view (const std::vector<ValueT,AllocatorT> &rhs):
|
|
view (std::data (rhs), std::size (rhs))
|
|
{ ; }
|
|
|
|
|
|
//---------------------------------------------------------------------
|
|
template <typename ValueT, typename AllocatorT>
|
|
view (std::vector<ValueT,AllocatorT> &rhs):
|
|
view (std::data (rhs), std::size (rhs))
|
|
{ ; }
|
|
|
|
|
|
//---------------------------------------------------------------------
|
|
template <typename ValueT, std::size_t N>
|
|
view (std::array<ValueT,N> &rhs):
|
|
view (std::data (rhs), std::size (rhs))
|
|
{ ; }
|
|
|
|
|
|
//---------------------------------------------------------------------
|
|
template <typename ValueT, std::size_t N>
|
|
view (const std::array<ValueT,N> &rhs):
|
|
view (std::data (rhs), std::size (rhs))
|
|
{ ; }
|
|
|
|
|
|
///////////////////////////////////////////////////////////////////////
|
|
constexpr BeginT begin (void) noexcept { return m_begin; }
|
|
constexpr EndT end (void) noexcept { return m_end; }
|
|
constexpr BeginT begin (void) const noexcept { return m_begin; }
|
|
constexpr EndT end (void) const noexcept { return m_end; }
|
|
|
|
//---------------------------------------------------------------------
|
|
constexpr BeginT cbegin (void) const noexcept { return m_begin; }
|
|
constexpr EndT cend (void) const noexcept { return m_end; }
|
|
|
|
//---------------------------------------------------------------------
|
|
auto data (void) noexcept { return begin (); }
|
|
auto data (void) const noexcept { return begin (); }
|
|
|
|
//---------------------------------------------------------------------
|
|
auto& front (void) noexcept { return *m_begin; }
|
|
auto& front (void) const noexcept { return *m_begin; }
|
|
|
|
//---------------------------------------------------------------------
|
|
auto& back (void) noexcept { return *(m_end - 1); }
|
|
auto& back (void) const noexcept { return *(m_end - 1); }
|
|
|
|
|
|
///////////////////////////////////////////////////////////////////////
|
|
/// Returns true if the size of the view is zero.
|
|
constexpr bool
|
|
empty (void) const noexcept
|
|
{
|
|
return m_begin == m_end;
|
|
}
|
|
|
|
|
|
///--------------------------------------------------------------------
|
|
/// Returns true if the view is not empty; ie, there is data remaining.
|
|
explicit constexpr operator bool () const noexcept
|
|
{
|
|
return not empty ();
|
|
}
|
|
|
|
|
|
///--------------------------------------------------------------------
|
|
/// Returns the number of items in the view.
|
|
constexpr auto
|
|
size (void) const noexcept
|
|
{
|
|
return static_cast<size_type> (std::distance (m_begin, m_end));
|
|
}
|
|
|
|
|
|
///--------------------------------------------------------------------
|
|
/// Returns a signed count of items in the view.
|
|
constexpr ssize_t
|
|
ssize (void) const noexcept
|
|
{
|
|
return std::distance (m_begin, m_end);
|
|
}
|
|
|
|
|
|
///--------------------------------------------------------------------
|
|
/// Returns a subview of the first `count` elements of this view.
|
|
[[nodiscard]] constexpr auto
|
|
redim (size_type count) const
|
|
{
|
|
if constexpr (std::is_signed_v<size_type>)
|
|
assert (count >= 0);
|
|
|
|
if (count > size ())
|
|
throw std::invalid_argument ("redim to higher size not allowed");
|
|
return view { m_begin, m_begin + count };
|
|
};
|
|
|
|
|
|
///--------------------------------------------------------------------
|
|
/// Returns two subviews split at `pos`.
|
|
///
|
|
/// The first view extends from `begin` to `pos`, and the second view
|
|
/// extends from `pos` to `end`.
|
|
[[nodiscard]] constexpr std::pair<
|
|
view<BeginT,BeginT>,
|
|
view<BeginT,EndT>
|
|
>
|
|
split (BeginT pos) const
|
|
{
|
|
CHECK_GE (pos, m_begin);
|
|
CHECK_LE (pos, m_end );
|
|
|
|
return {
|
|
{ m_begin, pos },
|
|
{ pos, m_end }
|
|
};
|
|
}
|
|
|
|
|
|
///--------------------------------------------------------------------
|
|
template <
|
|
typename IndexT,
|
|
typename = std::enable_if_t<std::is_integral_v<IndexT>>
|
|
>
|
|
[[nodiscard]] constexpr auto
|
|
split (IndexT idx) const
|
|
{
|
|
// It's ok if `idx` points to the end iterator; this just means the
|
|
// second element of the returned pair is an empty view.
|
|
static_assert (
|
|
std::numeric_limits<IndexT>::max () <= std::numeric_limits<size_type>::max ()
|
|
);
|
|
CHECK_GE (idx, IndexT {0});
|
|
CHECK_LE (cruft::cast::lossless<size_type> (idx), size ());
|
|
|
|
auto last = m_begin;
|
|
std::advance (last, idx);
|
|
return split (last);
|
|
}
|
|
|
|
|
|
//---------------------------------------------------------------------
|
|
// slices a view using python indexing semantics. ie,
|
|
// "abc".slice(0, 3) == "abc"
|
|
// "abc".slice(0, -1) == "abc"
|
|
// "abc".slice(0, -2) == "ab"
|
|
template <typename IndexA, typename IndexB>
|
|
[[nodiscard]] constexpr
|
|
auto
|
|
slice (IndexA a, IndexB b) const
|
|
{
|
|
CHECK_INCLUSIVE (cruft::abs (a), IndexA {0}, cruft::cast::lossless<IndexA> (size ()));
|
|
CHECK_INCLUSIVE (cruft::abs (b), IndexB {0}, cruft::cast::lossless<IndexB> (size ()));
|
|
|
|
auto first = m_begin;
|
|
auto last = m_begin;
|
|
|
|
std::advance (first, a < 0 ? size () + a + 1 : a);
|
|
std::advance (last, b < 0 ? size () + b + 1 : b);
|
|
|
|
return view { first, last };
|
|
}
|
|
|
|
|
|
//---------------------------------------------------------------------
|
|
template <
|
|
typename IndexT,
|
|
typename = std::enable_if_t<std::is_integral_v<IndexT>>
|
|
>
|
|
[[nodiscard]] constexpr auto
|
|
head (IndexT idx) const
|
|
{
|
|
return std::get<0> (split (idx));
|
|
}
|
|
|
|
|
|
//---------------------------------------------------------------------
|
|
template <
|
|
typename IndexT,
|
|
typename = std::enable_if_t<std::is_integral_v<IndexT>>
|
|
>
|
|
[[nodiscard]] constexpr auto
|
|
tail (IndexT idx) const
|
|
{
|
|
return std::get<1> (split (idx));
|
|
}
|
|
|
|
|
|
//---------------------------------------------------------------------
|
|
template <
|
|
typename IndexT,
|
|
typename = std::enable_if_t<std::is_integral_v<IndexT>>
|
|
>
|
|
[[nodiscard]] constexpr auto
|
|
consume (IndexT count) const
|
|
{
|
|
auto [a,b] = split (count);
|
|
(void)a;
|
|
return b;
|
|
}
|
|
|
|
|
|
//---------------------------------------------------------------------
|
|
[[nodiscard]] constexpr view<BeginT,EndT>
|
|
consume (view<BeginT,EndT> prefix) const
|
|
{
|
|
assert (prefix.begin () == begin ());
|
|
assert (prefix.end () < end ());
|
|
|
|
return { prefix.end (), end () };
|
|
}
|
|
|
|
|
|
[[nodiscard]] constexpr view<BeginT,EndT>
|
|
consume (const BeginT pos) const
|
|
{
|
|
return { pos, end () };
|
|
}
|
|
|
|
|
|
///////////////////////////////////////////////////////////////////////
|
|
/// Explicitly cast to a view with different iterator types.
|
|
///
|
|
/// The source and destination iterator types must be:
|
|
/// * pointers
|
|
/// * alignable
|
|
///
|
|
/// It is undefined behaviour to cast with begin and/or end iterators
|
|
/// that do not have natural alignment. Instrumented builds _may_
|
|
/// provide diagnostics or assertions in this case.
|
|
///
|
|
/// \tparam ValueT The new iterator type
|
|
/// \return A view that uses the new iterator type
|
|
template <
|
|
typename ValueT,
|
|
typename = std::enable_if_t<
|
|
// We can only convert views that use pointer iterators
|
|
std::is_pointer_v<BeginT> &&
|
|
std::is_pointer_v<EndT> &&
|
|
std::is_same_v<BeginT,EndT> &&
|
|
std::is_pointer_v<ValueT>
|
|
>
|
|
>
|
|
view<ValueT>
|
|
cast (void) const
|
|
{
|
|
// The values they point to must allow for alignment in one
|
|
// direction or another.
|
|
//
|
|
// We prefer a static_assert over SFINAE because it reduces the
|
|
// header burden for users (they do not need to include the
|
|
// implementation of the pointer values to satisfy
|
|
// iterator_traits), and it is quite unlikely we want to disable
|
|
// this only if alignment is incompatible).
|
|
static_assert (
|
|
sizeof (typename std::iterator_traits<BeginT>::value_type) %
|
|
sizeof (typename std::iterator_traits<ValueT>::value_type) == 0 ||
|
|
sizeof (typename std::iterator_traits<ValueT>::value_type) %
|
|
sizeof (typename std::iterator_traits<BeginT>::value_type) == 0
|
|
);
|
|
|
|
return {
|
|
cast::alignment<ValueT> (m_begin),
|
|
cast::alignment<ValueT> (m_end)
|
|
};
|
|
}
|
|
|
|
|
|
///////////////////////////////////////////////////////////////////////
|
|
constexpr decltype(auto)
|
|
operator[] (size_t idx) noexcept
|
|
{
|
|
CHECK_GE (idx, 0u);
|
|
CHECK_LT (idx, size ());
|
|
|
|
return *std::next (begin (), idx);
|
|
}
|
|
|
|
//---------------------------------------------------------------------
|
|
constexpr decltype(auto)
|
|
operator[] (size_t idx) const noexcept
|
|
{
|
|
CHECK_GE (idx, 0u);
|
|
CHECK_LT (idx, size ());
|
|
return *std::next (begin (), idx);
|
|
}
|
|
|
|
|
|
private:
|
|
///////////////////////////////////////////////////////////////////////
|
|
BeginT m_begin;
|
|
EndT m_end;
|
|
};
|
|
|
|
|
|
//-------------------------------------------------------------------------
|
|
template <typename ValueT, std::size_t N>
|
|
view (ValueT(&)[N]) -> view<ValueT*,ValueT*>;
|
|
|
|
|
|
//-------------------------------------------------------------------------
|
|
view (const char*) -> view<const char*, const char*>;
|
|
|
|
view (char*) -> view<char*>;
|
|
|
|
|
|
//-------------------------------------------------------------------------
|
|
template <
|
|
typename IteratorT,
|
|
typename SizeT,
|
|
typename = std::enable_if_t<
|
|
std::is_integral_v<SizeT>
|
|
>
|
|
>
|
|
view (IteratorT, SizeT) -> view<IteratorT,IteratorT>;
|
|
|
|
|
|
template <typename CharT, typename Traits, typename Allocator>
|
|
view (
|
|
std::basic_string<CharT,Traits,Allocator> &
|
|
) -> view<
|
|
typename std::allocator_traits<Allocator>::pointer
|
|
>;
|
|
|
|
|
|
template <typename CharT, typename Traits, typename Allocator>
|
|
view (
|
|
const std::basic_string<CharT,Traits,Allocator> &
|
|
) -> view<
|
|
typename std::allocator_traits<Allocator>::const_pointer
|
|
>;
|
|
|
|
template <typename ValueT, typename AllocatorT>
|
|
view (
|
|
std::vector<ValueT,AllocatorT>&
|
|
) -> view<typename std::allocator_traits<AllocatorT>::pointer>;
|
|
|
|
|
|
template <typename ValueT, typename AllocatorT>
|
|
view (
|
|
const std::vector<ValueT,AllocatorT>&
|
|
) -> view<
|
|
typename std::allocator_traits<AllocatorT>::const_pointer
|
|
>;
|
|
|
|
template <typename ValueT, std::size_t N>
|
|
view (std::array<ValueT,N>&) -> view<ValueT*>;
|
|
|
|
template <typename ValueT, std::size_t N>
|
|
view (const std::array<ValueT,N>&) -> view<const ValueT*>;
|
|
|
|
template <typename ContainerT>
|
|
view (ContainerT&) -> view<
|
|
decltype (std::declval<ContainerT&> ().begin ()),
|
|
decltype (std::declval<ContainerT&> ().end ())
|
|
>;
|
|
|
|
template <typename ContainerT>
|
|
view (const ContainerT&) -> view<
|
|
decltype (std::declval<ContainerT const&> ().begin ()),
|
|
decltype (std::declval<ContainerT const&> ().end ())
|
|
>;
|
|
|
|
// base + count constructor
|
|
template <typename BeginT>
|
|
view (BeginT, std::uint64_t count) -> view<BeginT,BeginT>;
|
|
|
|
template <typename BeginT>
|
|
view (BeginT, std::uint32_t count) -> view<BeginT,BeginT>;
|
|
|
|
template <typename IteratorT>
|
|
view (IteratorT, int) -> view<IteratorT, IteratorT>;
|
|
|
|
|
|
|
|
///////////////////////////////////////////////////////////////////////////
|
|
template <typename ValueT, size_t N>
|
|
auto
|
|
make_view (const ValueT (&arr)[N])
|
|
{
|
|
return view<const ValueT*> (arr + 0, arr + N);
|
|
}
|
|
|
|
//-------------------------------------------------------------------------
|
|
template <typename ContainerT>
|
|
auto
|
|
make_view (ContainerT &t)
|
|
{
|
|
return view { std::begin (t), std::end (t) };
|
|
}
|
|
|
|
//-------------------------------------------------------------------------
|
|
template <typename ContainerT>
|
|
auto
|
|
make_view (const ContainerT &t)
|
|
{
|
|
return view { std::cbegin (t), std::cend (t) };
|
|
}
|
|
|
|
|
|
//-------------------------------------------------------------------------
|
|
// disable the possibility of creating a view to a temporary. note that
|
|
// this only works if an lval version has already been defined otherwise
|
|
// universal reference rules will capture both lval and rval here.
|
|
template <typename ContainerT>
|
|
auto
|
|
make_view (ContainerT&&) = delete;
|
|
|
|
|
|
///////////////////////////////////////////////////////////////////////////
|
|
template <typename ContainerT>
|
|
auto
|
|
make_cview (const ContainerT &t)
|
|
{
|
|
return make_view (t);
|
|
//return view<decltype(std::cbegin (t))> { std::cbegin (t), std::cend (t) };
|
|
}
|
|
|
|
|
|
//-------------------------------------------------------------------------
|
|
template <typename BeginT, typename EndT>
|
|
auto
|
|
make_view (BeginT first, EndT last)
|
|
{
|
|
return view<BeginT, EndT> {first, last};
|
|
}
|
|
|
|
//-------------------------------------------------------------------------
|
|
template <typename ValueT>
|
|
auto
|
|
make_cview (ValueT *first, ValueT *last)
|
|
{
|
|
return view<const ValueT*> {first, last};
|
|
}
|
|
|
|
///////////////////////////////////////////////////////////////////////////
|
|
inline
|
|
view<const char*> make_view (const char *str)
|
|
{
|
|
return { str, str + strlen (str) };
|
|
}
|
|
|
|
|
|
//-------------------------------------------------------------------------
|
|
inline
|
|
view<char*> make_view (char *str)
|
|
{
|
|
return { str, str + strlen (str) };
|
|
}
|
|
|
|
|
|
//-------------------------------------------------------------------------
|
|
template <typename CharT, typename TraitsT, typename AllocT>
|
|
view<const CharT*>
|
|
make_view (const std::basic_string<CharT,TraitsT,AllocT> &str)
|
|
{
|
|
return {
|
|
std::data (str),
|
|
std::data (str) + std::size (str)
|
|
};
|
|
}
|
|
|
|
|
|
//-------------------------------------------------------------------------
|
|
template <typename CharT, typename TraitsT, typename AllocT>
|
|
view<CharT*>
|
|
make_view (std::basic_string<CharT,TraitsT,AllocT> &str)
|
|
{
|
|
return {
|
|
std::data (str),
|
|
std::data (str) + std::size (str)
|
|
};
|
|
}
|
|
|
|
|
|
//-------------------------------------------------------------------------
|
|
template <typename CharT, typename TraitsT, typename AllocT>
|
|
view<const CharT*>
|
|
make_view (const std::basic_string<CharT,TraitsT,AllocT>&&) = delete;
|
|
|
|
|
|
//-------------------------------------------------------------------------
|
|
template <typename CharT, typename TraitsT, typename AllocT>
|
|
view<CharT*>
|
|
make_view (std::basic_string<CharT,TraitsT,AllocT>&&) = delete;
|
|
|
|
|
|
///////////////////////////////////////////////////////////////////////////
|
|
/// Calculates a word oriented view over an arbitrary type
|
|
///
|
|
/// Useful for passing in memory structures to file descriptors and the
|
|
/// like. but the consequences of endian conversion is on the user...
|
|
///
|
|
/// We have to be careful that rval-references and other temporaries aren't
|
|
/// accepted in this signature.
|
|
template <
|
|
typename WordT = std::byte const,
|
|
typename T
|
|
>
|
|
cruft::view<WordT*>
|
|
make_byte_view (T &t)
|
|
{
|
|
static_assert (sizeof (T) % sizeof (WordT) == 0);
|
|
static_assert (std::is_const_v<T> ? std::is_const_v<WordT> : true);
|
|
|
|
return view {
|
|
cast::alignment<WordT*> (&t),
|
|
sizeof (T) / sizeof (WordT)
|
|
};
|
|
}
|
|
|
|
|
|
///////////////////////////////////////////////////////////////////////////
|
|
template <std::bidirectional_iterator IteratorT>
|
|
cruft::view<IteratorT>&
|
|
operator-= (
|
|
cruft::view<IteratorT> &val,
|
|
typename std::iterator_traits<IteratorT>::difference_type offset
|
|
) {
|
|
return val = {
|
|
val.begin () - offset,
|
|
val.end () - offset
|
|
};
|
|
}
|
|
|
|
|
|
//-------------------------------------------------------------------------
|
|
template <std::incrementable IteratorT>
|
|
cruft::view<IteratorT>&
|
|
operator+= (
|
|
cruft::view<IteratorT> &val,
|
|
typename std::iterator_traits<IteratorT>::difference_type offset
|
|
) {
|
|
return val = {
|
|
val.begin () + offset,
|
|
val.end () + offset
|
|
};
|
|
}
|
|
|
|
|
|
///////////////////////////////////////////////////////////////////////////
|
|
template <typename BeginT, typename EndT, typename FunctionT>
|
|
view<BeginT, EndT>
|
|
trim_if [[nodiscard]] (
|
|
view<BeginT, EndT> const buffer,
|
|
FunctionT &&test
|
|
) {
|
|
auto const first = std::find_if_not (
|
|
std::begin (buffer),
|
|
std::end (buffer),
|
|
test
|
|
);
|
|
|
|
auto const last = std::find_if_not (
|
|
std::make_reverse_iterator (buffer.end ()),
|
|
std::make_reverse_iterator (first),
|
|
test
|
|
);
|
|
|
|
return view (first, last.base ());
|
|
}
|
|
|
|
|
|
///////////////////////////////////////////////////////////////////////////
|
|
template <typename IteratorT>
|
|
std::pair<view<IteratorT>, view<IteratorT>>
|
|
split_on (
|
|
view<IteratorT> const buffer,
|
|
typename std::iterator_traits<IteratorT>::value_type const value
|
|
) {
|
|
auto const pos = std::find (std::begin (buffer), std::end (buffer), value);
|
|
if (pos == std::end (buffer))
|
|
return {
|
|
buffer,
|
|
{std::end (buffer), std::end (buffer)}
|
|
};
|
|
|
|
return {
|
|
{ buffer.begin (), pos, },
|
|
{ pos + 1, buffer.end () }
|
|
};
|
|
}
|
|
|
|
|
|
///////////////////////////////////////////////////////////////////////////
|
|
/// Split a view at the first occurrence of the sub-string `value`.
|
|
///
|
|
/// If no occurrence was found the returned pair will be the original view
|
|
/// and an empty view.
|
|
template <typename IteratorT, std::size_t N>
|
|
std::pair<view<IteratorT>, view<IteratorT>>
|
|
split_on (
|
|
view<IteratorT> const buffer,
|
|
typename std::iterator_traits<IteratorT>::value_type (&value)[N]
|
|
) {
|
|
auto const pos = std::search (
|
|
std::begin (buffer),
|
|
std::end (buffer),
|
|
std::begin (value),
|
|
std::end (value)
|
|
);
|
|
|
|
if (pos == std::end (buffer))
|
|
return {
|
|
buffer,
|
|
{std::end (buffer), std::end (buffer)}
|
|
};
|
|
|
|
return {
|
|
{ buffer.begin (), pos, },
|
|
{ pos + N, buffer.end () }
|
|
};
|
|
}
|
|
|
|
|
|
///////////////////////////////////////////////////////////////////////////
|
|
/// Returns a reference to a value of the designated type at the front of
|
|
/// the word-view. if there is insufficient data for the extraction an
|
|
/// exception will be thrown.
|
|
///
|
|
/// There are no validity or other checks performed on the returned data
|
|
/// this is deliberate, so that the function is safe to call on user
|
|
/// supplied data during parsing routines. it is up to the user to ensure
|
|
/// the object is valid.
|
|
///
|
|
/// The buffer object is advanced in place so that it no longer covers
|
|
/// the extract value
|
|
///
|
|
/// It is assumed the user has taken care of alignment concerns
|
|
template <
|
|
typename ValueT,
|
|
typename WordT
|
|
>
|
|
ValueT&
|
|
extract (view<WordT*> &buffer)
|
|
{
|
|
// Only allow calls if the value is a multiple of the word size.
|
|
// It's useful to allow non-unit words for areas like TCP/IP which
|
|
// tend to include protocols that utilise u16 words.
|
|
static_assert (
|
|
sizeof (ValueT) % sizeof (WordT) == 0,
|
|
"The value type must be a multiple of the word size"
|
|
);
|
|
|
|
static_assert (
|
|
!std::is_const_v<WordT> or std::is_const_v<ValueT>,
|
|
"buffer and output types must have matching constness"
|
|
);
|
|
|
|
if (unlikely (sizeof (ValueT) > buffer.size () * sizeof (WordT)))
|
|
throw std::runtime_error ("insufficient data for extraction");
|
|
|
|
auto ptr = cast::alignment<ValueT*> (buffer.data ());
|
|
buffer = buffer.consume (sizeof (ValueT) / sizeof (WordT));
|
|
return *ptr;
|
|
}
|
|
|
|
|
|
///------------------------------------------------------------------------
|
|
/// Returns a view of the specified type cast from the front of a
|
|
/// byte-view.
|
|
///
|
|
/// There may be runtime checks for alignment under debug builds.
|
|
///
|
|
/// It is safe to use this on untrusted input. However absolutely no
|
|
/// validation is performed on the result data.
|
|
template <
|
|
typename ValueT,
|
|
typename WordT,
|
|
typename = std::enable_if_t<sizeof (ValueT) % sizeof(WordT) == 0>
|
|
>
|
|
cruft::view<ValueT*>
|
|
extract_array (view<WordT*> &src, std::size_t count)
|
|
{
|
|
static_assert (
|
|
std::is_const_v<ValueT> == std::is_const_v<WordT>,
|
|
"src and dst types must have matching constness"
|
|
);
|
|
|
|
auto const src_size = sizeof (ValueT) / sizeof (WordT) * count;
|
|
if (unlikely (src.size () < src_size))
|
|
throw std::runtime_error ("Insufficient data for extraction");
|
|
|
|
auto res = src.template cast<ValueT*> ().redim (count);
|
|
src = src.consume (src_size);
|
|
return res;
|
|
}
|
|
|
|
|
|
///////////////////////////////////////////////////////////////////////////
|
|
/// extracts an object of a specified type from the front of a byte-view.
|
|
///
|
|
/// in contrast to 'extract' this will always copy the bytes out from the
|
|
/// view, making the operation alignment safe.
|
|
///
|
|
/// It is safe to use this on untrusted input.
|
|
template <
|
|
typename ValueT,
|
|
typename WordT,
|
|
typename = std::enable_if_t<sizeof (ValueT) % sizeof(WordT) == 0>
|
|
>
|
|
ValueT
|
|
read (view<WordT*> &buffer)
|
|
{
|
|
// We're going to use memcpy which requires that the type is
|
|
// trivially copyable.
|
|
static_assert (std::is_trivially_copyable_v<ValueT>);
|
|
|
|
if (unlikely (sizeof (ValueT) > buffer.size () * sizeof (WordT)))
|
|
throw std::runtime_error ("insufficient data for extraction");
|
|
|
|
std::aligned_storage_t<sizeof(ValueT),alignof(ValueT)> bytes;
|
|
memcpy (&bytes, buffer.data (), sizeof (ValueT));
|
|
buffer = buffer.consume (sizeof (ValueT) / sizeof (WordT));
|
|
return *reinterpret_cast<ValueT const*> (&bytes);
|
|
}
|
|
|
|
|
|
/// Copy N elements of ValueT from a view over WordT into a supplied
|
|
/// std::array.
|
|
///
|
|
/// Throws if there is insufficient data in the src view.
|
|
template <
|
|
typename ValueT,
|
|
typename WordT,
|
|
std::size_t N,
|
|
typename = std::enable_if_t<sizeof (ValueT) % sizeof(WordT) == 0>
|
|
>
|
|
std::array<ValueT, N>&
|
|
read_array (view<WordT*> &src, std::array<ValueT, N> &dst)
|
|
{
|
|
static_assert (std::is_trivially_copyable_v<ValueT>);
|
|
|
|
if (unlikely (src.size () * sizeof (WordT) < sizeof (dst)))
|
|
throw std::runtime_error ("insufficient data for extraction");
|
|
|
|
memcpy (dst.data (), src.data(), N * sizeof (ValueT));
|
|
src = src.consume (sizeof (ValueT) / sizeof (WordT) * N);
|
|
return dst;
|
|
}
|
|
|
|
|
|
///////////////////////////////////////////////////////////////////////////
|
|
template <
|
|
typename ValueT,
|
|
typename WordT,
|
|
typename = std::enable_if_t<sizeof (ValueT) % sizeof (WordT) == 0>
|
|
>
|
|
view<WordT*>
|
|
write [[nodiscard]] (view<WordT*> const &dst, ValueT const &src)
|
|
{
|
|
static_assert (std::is_trivially_copyable_v<ValueT>);
|
|
|
|
if (unlikely (sizeof (ValueT) > dst.size () * sizeof (WordT)))
|
|
throw std::runtime_error ("insufficient data for extraction");
|
|
|
|
memcpy (dst.data (), &src, sizeof (ValueT));
|
|
return {
|
|
dst.begin () + sizeof (ValueT) / sizeof (WordT),
|
|
dst.end (),
|
|
};
|
|
}
|
|
|
|
|
|
template <
|
|
typename ValueT,
|
|
typename WordT,
|
|
typename = std::enable_if_t<sizeof (ValueT) % sizeof (WordT) == 0>
|
|
>
|
|
view<WordT*>
|
|
write [[nodiscard]] (view<WordT*> const &dst, cruft::view<ValueT const*> src)
|
|
{
|
|
static_assert (std::is_trivially_copyable_v<ValueT>);
|
|
|
|
if (unlikely (src.size () * sizeof (ValueT) > dst.size () * sizeof (WordT)))
|
|
throw std::runtime_error ("insufficient data for extraction");
|
|
|
|
memcpy (
|
|
dst.data (),
|
|
src.data (),
|
|
src.size () * sizeof (ValueT)
|
|
);
|
|
|
|
return {
|
|
dst.begin () + (sizeof (ValueT) / sizeof (WordT)) * src.size (),
|
|
dst.end (),
|
|
};
|
|
}
|
|
|
|
|
|
///////////////////////////////////////////////////////////////////////////
|
|
/// Tests whether an iterator falls within a given view.
|
|
template <typename IteratorT>
|
|
constexpr bool
|
|
intersects (view<IteratorT> a, IteratorT b)
|
|
{
|
|
return b >= a.begin () && b < a.end ();
|
|
}
|
|
|
|
|
|
///------------------------------------------------------------------------
|
|
/// Tests whether view `a` inclusively contains view `b`.
|
|
template <typename IteratorA, typename IteratorB>
|
|
constexpr bool
|
|
covers (
|
|
view<IteratorA,IteratorB> const &a,
|
|
view<IteratorA,IteratorB> const &b
|
|
) {
|
|
return a.begin () <= b.begin () && a.end () >= b.end ();
|
|
}
|
|
|
|
|
|
///////////////////////////////////////////////////////////////////////////
|
|
template <
|
|
typename IteratorA,
|
|
typename IteratorB,
|
|
typename ValueT
|
|
>
|
|
requires (
|
|
std::equality_comparable_with<
|
|
typename std::iterator_traits<IteratorA>::value_type,
|
|
ValueT
|
|
>
|
|
)
|
|
bool
|
|
contains (view<IteratorA, IteratorB> container, ValueT &&value)
|
|
{
|
|
for (auto const &inner: container)
|
|
if (inner == value)
|
|
return true;
|
|
return false;
|
|
}
|
|
|
|
|
|
///////////////////////////////////////////////////////////////////////////
|
|
template <
|
|
typename BeginA, typename EndA,
|
|
typename BeginB, typename EndB,
|
|
typename ComparatorT
|
|
>
|
|
decltype(auto)
|
|
equal (
|
|
view<BeginA,EndA> const &a,
|
|
view<BeginB,EndB> const &b,
|
|
ComparatorT &&cmp
|
|
) {
|
|
return std::equal (
|
|
std::begin (a), std::end (a),
|
|
std::begin (b), std::end (b),
|
|
std::forward<ComparatorT> (cmp)
|
|
);
|
|
}
|
|
|
|
//-------------------------------------------------------------------------
|
|
template <
|
|
typename BeginA, typename EndA,
|
|
typename BeginB, typename EndB
|
|
>
|
|
constexpr bool
|
|
equal (const view<BeginA,EndA> &a, const view<BeginB,EndB> &b)
|
|
{
|
|
return ::cruft::equal (a, b, std::equal_to<void> {});
|
|
}
|
|
|
|
|
|
//-------------------------------------------------------------------------
|
|
// defer equality to the view/view operator by way of make_view
|
|
template <
|
|
typename IteratorA,
|
|
typename IteratorB,
|
|
typename ValueT,
|
|
typename = std::enable_if_t<
|
|
!std::is_same_v<ValueT, view<IteratorA,IteratorB>>,
|
|
void
|
|
>
|
|
>
|
|
constexpr bool
|
|
equal (const view<IteratorA,IteratorB> &a, const ValueT &b)
|
|
{
|
|
return equal (a, make_view (b));
|
|
}
|
|
|
|
|
|
//-------------------------------------------------------------------------
|
|
// reverse the arguments and forward to the above operator. we formumlate
|
|
// equality this way to avoid implementing the operator twice for each
|
|
// weird case.
|
|
template <
|
|
typename IteratorA,
|
|
typename IteratorB,
|
|
typename ValueT,
|
|
typename = std::enable_if_t<
|
|
!std::is_same_v<ValueT, view<IteratorA,IteratorB>>,
|
|
void
|
|
>
|
|
>
|
|
constexpr bool
|
|
equal (const ValueT &a, const view<IteratorA,IteratorB> &b)
|
|
{
|
|
return equal (b, a);
|
|
}
|
|
|
|
|
|
///////////////////////////////////////////////////////////////////////////
|
|
template <typename IteratorA, typename IteratorB>
|
|
constexpr bool
|
|
operator== (const view<IteratorA,IteratorB> &a, const view<IteratorA,IteratorB> &b)
|
|
{
|
|
return a.begin () == b.begin () && a.end () == b.end ();
|
|
}
|
|
|
|
|
|
//-------------------------------------------------------------------------
|
|
template <typename IteratorA, typename IteratorB>
|
|
constexpr bool
|
|
operator!= (const view<IteratorA,IteratorB> &a, const view<IteratorA,IteratorB> &b)
|
|
{
|
|
return !(a == b);
|
|
}
|
|
|
|
|
|
//-------------------------------------------------------------------------
|
|
template <
|
|
typename IteratorA,
|
|
typename IteratorB,
|
|
typename ValueT,
|
|
typename = std::enable_if_t<
|
|
!std::is_same_v<ValueT, view<IteratorA,IteratorB>>,
|
|
void
|
|
>
|
|
>
|
|
constexpr bool
|
|
operator!= (const view<IteratorA,IteratorB> &a, const ValueT &b)
|
|
{
|
|
return !(a == b);
|
|
}
|
|
|
|
|
|
//-------------------------------------------------------------------------
|
|
template <
|
|
typename IteratorA,
|
|
typename IteratorB,
|
|
typename ValueT,
|
|
typename = std::enable_if_t<
|
|
!std::is_same_v<ValueT, view<IteratorA,IteratorB>>,
|
|
void
|
|
>
|
|
>
|
|
constexpr bool
|
|
operator!= (const ValueT &a, const view<IteratorA,IteratorB> &b)
|
|
{
|
|
return !(a == b);
|
|
}
|
|
|
|
|
|
///////////////////////////////////////////////////////////////////////////
|
|
template <typename BeginT, typename EndT>
|
|
std::ostream&
|
|
operator<< (std::ostream &os, view<BeginT, EndT> val)
|
|
{
|
|
std::copy (
|
|
std::cbegin (val),
|
|
std::cend (val),
|
|
std::ostream_iterator<typename decltype(val)::value_type> (os)
|
|
);
|
|
|
|
return os;
|
|
}
|
|
|
|
|
|
///////////////////////////////////////////////////////////////////////////
|
|
/// a basic stringlike comparison operator that behaves as
|
|
/// std::string::compare would.
|
|
///
|
|
/// provided so that the common case of stringlike views can be used in a
|
|
/// std::map and similar without a great deal of work.
|
|
inline bool
|
|
operator< (view<const char*> a, view<const char*> b)
|
|
{
|
|
const auto la = std::size (a);
|
|
const auto lb = std::size (b);
|
|
|
|
const auto res = strncmp (
|
|
std::data (a),
|
|
std::data (b),
|
|
min (la, lb)
|
|
);
|
|
|
|
return res < 0 || (res == 0 && la < lb);
|
|
}
|
|
}
|
|
|
|
|
|
#include "debug/validate.hpp"
|
|
|
|
namespace cruft::debug {
|
|
///////////////////////////////////////////////////////////////////////////
|
|
template <typename IteratorT, typename ...ArgsT>
|
|
struct validator<
|
|
view<IteratorT>,
|
|
ArgsT&&...
|
|
> {
|
|
static bool
|
|
is_valid (view<IteratorT> data, ArgsT &&...args)
|
|
{
|
|
return std::all_of (
|
|
std::begin (data),
|
|
std::end (data),
|
|
[&] (auto const &i)
|
|
{
|
|
return ::cruft::debug::is_valid (i, args...);
|
|
});
|
|
}
|
|
};
|
|
};
|