311 lines
11 KiB
C++
311 lines
11 KiB
C++
/** @file span.hpp
|
|
*
|
|
* @author Roland Conybeare, Jul 2024
|
|
**/
|
|
|
|
#pragma once
|
|
|
|
//#include "xo/indentlog/scope.hpp"
|
|
#include <cassert>
|
|
#include <cstdint>
|
|
#include <cstring>
|
|
#include <ranges>
|
|
#include <stdexcept>
|
|
#include <string>
|
|
#include <string_view>
|
|
|
|
namespace xo {
|
|
namespace mm {
|
|
/** @class span compression/span.hpp
|
|
*
|
|
* @brief A contiguous range of characters, without ownership.
|
|
*
|
|
* @tparam CharT type for elements referred to by this span.
|
|
**/
|
|
template <typename CharT>
|
|
class span {
|
|
public:
|
|
/** @defgroup span-type-traits span type traits **/
|
|
///@{
|
|
|
|
/** typealias for span size (in units of CharT) **/
|
|
using size_type = std::uint64_t;
|
|
|
|
/** typealias for span elements **/
|
|
using value_type = CharT;
|
|
|
|
/** typealias for span iterators. a raw pointer, which models
|
|
* std::contiguous_iterator; that (with size()) is what makes
|
|
* span a std::ranges::contiguous_range.
|
|
**/
|
|
using iterator = CharT *;
|
|
|
|
///@}
|
|
|
|
public:
|
|
/** @defgroup span-ctors span constructors **/
|
|
///@{
|
|
|
|
/** null span **/
|
|
span() : lo_{nullptr}, hi_{nullptr} {}
|
|
|
|
/** Create span for the contiguous memory range [@p lo, @p hi) **/
|
|
span(CharT * lo, CharT * hi) : lo_{lo}, hi_{hi} {}
|
|
|
|
/** Create span for the contiguous memory range [@p lo, @p lo + z) **/
|
|
span(CharT * lo, size_t z) : lo_{lo}, hi_{lo + z} {}
|
|
|
|
/** explicit conversion from span<U> **/
|
|
template<typename CharU>
|
|
span(const span<CharU> & other,
|
|
std::enable_if_t<std::is_convertible_v<CharU*, CharT*>
|
|
&& !std::is_same_v<CharU, CharT>> * = nullptr)
|
|
: lo_{other.lo()}, hi_{other.hi()} {}
|
|
|
|
/** copy ctor (explicit to avoid ambiguity with template ctor) **/
|
|
span(const span & other) = default;
|
|
span & operator=(const span & other) = default;
|
|
|
|
/** Create a null span (i.e. with null @p lo, @p hi pointers)
|
|
* A null span can be concatenated with any other span
|
|
* without triggering matching-endpoint asserts.
|
|
**/
|
|
static span make_null() { return span(static_cast<CharT*>(nullptr),
|
|
static_cast<CharT*>(nullptr)); }
|
|
|
|
/** @brief create span for C-style string @p cstr **/
|
|
static span from_cstr(const CharT * cstr) {
|
|
CharT * lo = cstr;
|
|
CharT * hi = cstr ? cstr + strlen(cstr) : nullptr;
|
|
|
|
return span(lo, hi);
|
|
}
|
|
|
|
/** @brief create span from std::string @p str **/
|
|
static span from_string(const std::string & str) {
|
|
CharT * lo = &(*str.begin());
|
|
CharT * hi = &(*str.end());
|
|
|
|
return span(lo, hi);
|
|
}
|
|
|
|
/** @brief create span from std::string @p str **/
|
|
static span from_string_view(const std::string_view & sv) {
|
|
CharT * lo = &(*sv.begin());
|
|
CharT * hi = &(*sv.end());
|
|
|
|
return span(lo, hi);
|
|
}
|
|
|
|
/** @brief create span from raw memory **/
|
|
static span from_memory(span<std::byte> span_memory) {
|
|
CharT * lo = (CharT *)span_memory.lo();
|
|
CharT * hi = (CharT *)span_memory.hi();
|
|
|
|
return span(lo, hi);
|
|
}
|
|
|
|
/** @brief concatenate two contiguous spans */
|
|
static span concat(const span & span1, const span & span2) {
|
|
if (span1.is_null())
|
|
return span2;
|
|
if (span2.is_null())
|
|
return span1;
|
|
|
|
// if (span1.hi() != span2.lo()) {
|
|
// scope log(XO_DEBUG(true));
|
|
//
|
|
// log && log(xtag("span1.hi", (void*)span1.hi()), xtag("span2.lo", (void*)span2.lo()));
|
|
// }
|
|
|
|
assert(span1.hi() == span2.lo());
|
|
|
|
CharT * lo = span1.lo();
|
|
CharT * hi = span2.hi();
|
|
|
|
return span(lo, hi);
|
|
}
|
|
|
|
///@}
|
|
|
|
/** @defgroup span-access-methods **/
|
|
///@{
|
|
|
|
CharT * lo() const { return lo_; } /* get member span::lo_ */
|
|
CharT * hi() const { return hi_; } /* get member span::hi_ */
|
|
|
|
/* begin()/end()/data() make span model
|
|
* std::ranges::contiguous_range, so it works with ranged-for,
|
|
* <algorithm> and std::ranges.
|
|
*
|
|
* These return CharT* from a const method, exactly like lo()/hi():
|
|
* constness of the span does not propagate to its elements.
|
|
* Same semantics as std::span.
|
|
*
|
|
* data() is strictly redundant -- std::ranges::data already works
|
|
* once begin() returns a pointer -- but it is the spelling generic
|
|
* code reaches for directly.
|
|
*/
|
|
iterator begin() const { return lo_; } /* first element */
|
|
iterator end() const { return hi_; } /* one past last element */
|
|
CharT * data() const { return lo_; } /* start of the range */
|
|
|
|
/** true iff this span is null. distinct from empty. **/
|
|
bool is_null() const { return lo_ == nullptr && hi_ == nullptr; }
|
|
/** true iff this span is empty (comprises 0 elements). **/
|
|
bool empty() const { return lo_ == hi_; }
|
|
/** report the number of elements (of type CharT) in this span. **/
|
|
size_type size() const { return hi_ - lo_; }
|
|
|
|
/** true iff this span is a subspan of @p other.
|
|
* i.e. other.lo() <= this->lo() && this->hi() <= other.hi()
|
|
**/
|
|
bool is_subspan_of(const span & other) const noexcept {
|
|
return (other.lo() <= lo_) && (hi_ <= other.hi());
|
|
}
|
|
|
|
/** convert to string view **/
|
|
std::string_view to_string_view() const {
|
|
return std::string_view((const char *)lo_, (const char *)hi_);
|
|
}
|
|
|
|
///@}
|
|
|
|
/** @defgroup span-general-methods **/
|
|
///@{
|
|
|
|
/** @brief strip prefix until first occurence of '\n', including the newline **/
|
|
void discard_until_newline() {
|
|
for (const CharT * p = lo_; p < hi_; ++p) {
|
|
if (*p == '\n') {
|
|
lo_ = p + 1;
|
|
return;
|
|
}
|
|
}
|
|
|
|
lo_ = hi_;
|
|
}
|
|
|
|
/** Create new span over supplied type,
|
|
* with identical (possibly misaligned) endpoints.
|
|
*
|
|
* @warning
|
|
* 1. New span uses exactly the same memory addresses.
|
|
* Endpoint pointers may not be aligned.
|
|
* 2. Implementation assumes code compiled with
|
|
* @code -fno-strict-aliasing @endcode enabled.
|
|
*
|
|
* @tparam OtherT element type for new span
|
|
**/
|
|
template <typename OtherT>
|
|
span<OtherT>
|
|
cast() const { return span<OtherT>(reinterpret_cast<OtherT *>(lo_),
|
|
reinterpret_cast<OtherT *>(hi_)); }
|
|
|
|
/** @brief create span including the first @p z members of this span. **/
|
|
span prefix(size_type z) const { return span(lo_, lo_ + z); }
|
|
|
|
/** @brief create span representing prefix up to (but not including) @p *p
|
|
**/
|
|
span prefix_upto(CharT * p) const {
|
|
if (p <= hi_)
|
|
return span(lo_, p);
|
|
else
|
|
return span(lo_, hi_);
|
|
}
|
|
|
|
/** @brief create span with first @p z members of this span removed **/
|
|
span after_prefix(size_type z) const {
|
|
if (lo_ + z > hi_)
|
|
z = hi_ - lo_;
|
|
|
|
return span(lo_ + z, hi_);
|
|
}
|
|
|
|
/** @brief create span with @p prefix of this span removed **/
|
|
span after_prefix(const span & prefix) const {
|
|
if (!prefix.is_null() && (prefix.lo() != lo_)) {
|
|
throw std::runtime_error
|
|
("after_prefix: expected prefix of this span");
|
|
}
|
|
|
|
return after_prefix(prefix.size());
|
|
}
|
|
|
|
/** Create span starting with position @p p.
|
|
* Does boundary checking; will return empty span if @p p is outside @c [lo_,hi)
|
|
**/
|
|
span suffix_from(CharT * p) const {
|
|
if ((lo_ <= p) && (p <= hi_))
|
|
return span(p, hi_);
|
|
else
|
|
return span(hi_, hi_);
|
|
}
|
|
|
|
/** increase extent of this spans to include @p x.
|
|
* Requires @c hi() == @c x.lo()
|
|
**/
|
|
span & operator+=(const span & x) {
|
|
if (hi_ == x.lo_) {
|
|
hi_ = x.hi_;
|
|
} else if (!x.is_null()) {
|
|
assert(false);
|
|
}
|
|
|
|
return *this;
|
|
}
|
|
|
|
///@}
|
|
|
|
private:
|
|
/** @defgroup span-instance-vars **/
|
|
///@{
|
|
|
|
/** start of span.
|
|
Span comprises memory address between @p lo (inclusive) and @p hi (exclusive)
|
|
**/
|
|
CharT * lo_ = nullptr;
|
|
|
|
/** @brief end of span.
|
|
Span comprises memory address between @p lo (inclusive) and @p hi (exclusive)
|
|
**/
|
|
CharT * hi_ = nullptr;
|
|
|
|
///@}
|
|
}; /*span*/
|
|
|
|
/** @defgroup span-operators **/
|
|
///@{
|
|
|
|
/** compare spans for equality.
|
|
* Two spans are equal iff both endpoints match exactly.
|
|
**/
|
|
template <typename CharT>
|
|
inline bool
|
|
operator==(const span<CharT> & lhs, const span<CharT> & rhs) {
|
|
return ((lhs.lo() == rhs.lo())
|
|
&& (lhs.hi() == rhs.hi()));
|
|
}
|
|
|
|
/** compare spans for inequality.
|
|
* Two spans are unequal if either paired endpoint differs.
|
|
**/
|
|
template <typename CharT>
|
|
inline bool
|
|
operator!=(const span<CharT> & lhs, const span<CharT> & rhs) {
|
|
return ((lhs.lo() != rhs.lo())
|
|
|| (lhs.hi() != rhs.hi()));
|
|
}
|
|
|
|
///@}
|
|
} /*namespace mm*/
|
|
} /*namespace xo*/
|
|
|
|
/** span is a non-owning view: iterators obtained from it remain valid after
|
|
* the span object itself goes away. Without this specialization
|
|
* std::ranges::begin() on an rvalue span yields std::ranges::dangling, so
|
|
* e.g. std::ranges::find(make_span(..), c) fails to compile.
|
|
* std::span and std::string_view carry the same specialization.
|
|
**/
|
|
template <typename CharT>
|
|
inline constexpr bool std::ranges::enable_borrowed_range<xo::mm::span<CharT>> = true;
|