Compiler Explorer

Source code

//===----------------------------------------------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//

#ifndef _LIBCPP___UTILITY_POINTER_INT_PAIR_H
#define _LIBCPP___UTILITY_POINTER_INT_PAIR_H

#include <__assert>
#include <__bit/bit_log2.h>
#include <__concepts/derived_from.h>
#include <__config>
#include <__tuple_dir/tuple_element.h>
#include <__tuple_dir/tuple_size.h>
#include <__type_traits/is_pointer.h>
#include <__type_traits/is_unsigned.h>
#include <__type_traits/is_void.h>
#include <__type_traits/remove_pointer.h>
#include <__utility/swap.h>
#include <cstddef>
#include <cstdint>

#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
#  pragma GCC system_header
#endif

#if _LIBCPP_STD_VER >= 23

// A __pointer_int_pair is a pair of a pointer and an integral type. The lower bits of the pointer that are free
// due to the alignment requirement of the pointee are used to store the integral type.
//
// This imposes a constraint on the number of bits available for the integral type -- the integral type can use
// at most log2(alignof(T)) bits. This technique allows storing the integral type without additional storage
// beyond that of the pointer itself, at the cost of some bit twiddling.

_LIBCPP_BEGIN_NAMESPACE_STD

template <class>
struct _PointerLikeTraits;

template <class _Tp>
  requires(!is_void_v<_Tp>)
struct _PointerLikeTraits<_Tp*> {
  static constexpr size_t __low_bits_available = std::__bit_log2(alignof(_Tp));

static _LIBCPP_HIDE_FROM_ABI uintptr_t __to_uintptr(_Tp* __ptr) { return reinterpret_cast<uintptr_t>(__ptr); }
  static _LIBCPP_HIDE_FROM_ABI _Tp* __to_pointer(uintptr_t __ptr) { return reinterpret_cast<_Tp*>(__ptr); }
};

template <class _Tp>
  requires is_void_v<_Tp>
struct _PointerLikeTraits<_Tp*> {
  static constexpr size_t __low_bits_available = 0;

template <class _Pointer,
          size_t __int_bit_count,
          class _IntType       = size_t,
          class _PointerTraits = _PointerLikeTraits<_Pointer>>
class __pointer_int_pair {
  static_assert(__int_bit_count <= _PointerTraits::__low_bits_available,
                "Not enough bits available for requested bit count");
  static_assert(is_integral_v<_IntType>, "_IntType has to be an integral type");
  static_assert(is_unsigned_v<_IntType>, "__pointer_int_pair doesn't work for signed types");

static constexpr size_t __extra_bits  = _PointerTraits::__low_bits_available - __int_bit_count;
  static constexpr uintptr_t __int_mask = static_cast<uintptr_t>(1 << _PointerTraits::__low_bits_available) - 1;
  static constexpr uintptr_t __ptr_mask = ~__int_mask;

uintptr_t __value_ = 0;

public:
  __pointer_int_pair()                                     = default;
  __pointer_int_pair(const __pointer_int_pair&)            = default;
  __pointer_int_pair(__pointer_int_pair&&)                 = default;
  __pointer_int_pair& operator=(const __pointer_int_pair&) = default;
  __pointer_int_pair& operator=(__pointer_int_pair&&)      = default;
  ~__pointer_int_pair()                                    = default;

_LIBCPP_HIDE_FROM_ABI __pointer_int_pair(_Pointer __ptr_value, _IntType __int_value)
      : __value_(_PointerTraits::__to_uintptr(__ptr_value) | (__int_value << __extra_bits)) {
    _LIBCPP_ASSERT((__int_value & (__int_mask >> __extra_bits)) == __int_value, "integer is too large!");
    _LIBCPP_ASSERT(
        (_PointerTraits::__to_uintptr(__ptr_value) & __ptr_mask) == _PointerTraits::__to_uintptr(__ptr_value),
        "Pointer alignment is too low!");
  }

constexpr _LIBCPP_HIDE_FROM_ABI _IntType __get_value() const { return (__value_ & __int_mask) >> __extra_bits; }

_LIBCPP_HIDE_FROM_ABI _Pointer __get_ptr() const { return _PointerTraits::__to_pointer(__value_ & __ptr_mask); }

template <class>
  friend struct _PointerLikeTraits;
};

template <class _Pointer>
using __pointer_bool_pair = __pointer_int_pair<_Pointer, 1, bool>;

template <class _Pointer, size_t __int_bit_count, class _IntType, class _PointerTraits>
struct _PointerLikeTraits<__pointer_int_pair<_Pointer, __int_bit_count, _IntType, _PointerTraits>> {
private:
  using _PointerIntPair = __pointer_int_pair<_Pointer, __int_bit_count, _IntType, _PointerTraits>;
  static constexpr size_t __pointer_low_bits_available = _PointerLikeTraits<_Pointer>::__low_bits_available;
  static_assert(__pointer_low_bits_available >= __int_bit_count);

public:
  static constexpr size_t __low_bits_available = __pointer_low_bits_available - __int_bit_count;

static _LIBCPP_HIDE_FROM_ABI uintptr_t __to_uintptr(_PointerIntPair __ptr) { return __ptr.__value_; }

static _LIBCPP_HIDE_FROM_ABI _PointerIntPair __to_pointer(uintptr_t __ptr) {
    _PointerIntPair __tmp{};
    __tmp.__value_ = __ptr;
    return __tmp;
  }
};

// Make __pointer_int_pair tuple-like

template <class _Pointer, size_t __int_bit_count, class _IntType, class _PointerTraits>
struct tuple_size<__pointer_int_pair<_Pointer, __int_bit_count, _IntType, _PointerTraits>>
    : integral_constant<size_t, 2> {};

template <class _Pointer, size_t __int_bit_count, class _IntType, class _PointerTraits>
struct tuple_element<0, __pointer_int_pair<_Pointer, __int_bit_count, _IntType, _PointerTraits>> {
  using type = _Pointer;
};

template <class _Pointer, size_t __int_bit_count, class _IntType, class _PointerTraits>
struct tuple_element<1, __pointer_int_pair<_Pointer, __int_bit_count, _IntType, _PointerTraits>> {
  using type = _IntType;
};

template <size_t __i, class _Pointer, size_t __int_bit_count, class _IntType, class _PointerTraits>
_LIBCPP_HIDE_FROM_ABI auto get(__pointer_int_pair<_Pointer, __int_bit_count, _IntType, _PointerTraits> __pair) {
  if constexpr (__i == 0) {
    return __pair.__get_ptr();
  } else if constexpr (__i == 1) {
    return __pair.__get_value();
  } else {
    static_assert(__i == 0, "Index out of bounds");
  }
}

_LIBCPP_END_NAMESPACE_STD

#endif // _LIBCPP_STD_VER >= 23

#endif // _LIBCPP___UTILITY_POINTER_INT_PAIR_H

// -*- C++ -*-
//===----------------------------------------------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//

#ifndef _LIBCPP___RANGES_SPLIT_VIEW_H
#define _LIBCPP___RANGES_SPLIT_VIEW_H

#include <__algorithm/ranges_search.h>
#include <__concepts/constructible.h>
#include <__config>
#include <__functional/bind_back.h>
#include <__functional/ranges_operations.h>
#include <__iterator/indirectly_comparable.h>
#include <__iterator/iterator_traits.h>
#include <__memory/addressof.h>
#include <__ranges/access.h>
#include <__ranges/all.h>
#include <__ranges/concepts.h>
#include <__ranges/empty.h>
#include <__ranges/non_propagating_cache.h>
#include <__ranges/range_adaptor.h>
#include <__ranges/single_view.h>
#include <__ranges/subrange.h>
#include <__ranges/view_interface.h>
#include <__type_traits/decay.h>
#include <__type_traits/is_nothrow_constructible.h>
#include <__utility/forward.h>
#include <__utility/move.h>

#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
#  pragma GCC system_header
#endif

_LIBCPP_BEGIN_NAMESPACE_STD

#if _LIBCPP_STD_VER >= 20

namespace ranges {

template <class _View, class _Pattern>
struct __split_view_iterator;

template <class _View, class _Pattern>
struct __split_view_sentinel;

template <forward_range _View, forward_range _Pattern>
  requires view<_View> && view<_Pattern> &&
           indirectly_comparable<iterator_t<_View>, iterator_t<_Pattern>, ranges::equal_to>
class split_view : public view_interface<split_view<_View, _Pattern>> {
private:
  _LIBCPP_NO_UNIQUE_ADDRESS _View __base_       = _View();
  _LIBCPP_NO_UNIQUE_ADDRESS _Pattern __pattern_ = _Pattern();
  using _Cache                                  = __non_propagating_cache<subrange<iterator_t<_View>>>;
  _Cache __cached_begin_                        = _Cache();

template <class, class>
  friend struct __split_view_iterator;

template <class, class>
  friend struct __split_view_sentinel;

using __iterator = __split_view_iterator<_View, _Pattern>;
  using __sentinel = __split_view_sentinel<_View, _Pattern>;

_LIBCPP_HIDE_FROM_ABI constexpr subrange<iterator_t<_View>> __find_next(iterator_t<_View> __it) {
    auto [__begin, __end] = ranges::search(subrange(__it, ranges::end(__base_)), __pattern_);
    if (__begin != ranges::end(__base_) && ranges::empty(__pattern_)) {
      ++__begin;
      ++__end;
    }
    return {__begin, __end};
  }

public:
  _LIBCPP_HIDE_FROM_ABI split_view()
    requires default_initializable<_View> && default_initializable<_Pattern>
  = default;

_LIBCPP_HIDE_FROM_ABI constexpr split_view(_View __base, _Pattern __pattern)
      : __base_(std::move(__base)), __pattern_(std::move((__pattern))) {}

template <forward_range _Range>
    requires constructible_from<_View, views::all_t<_Range>> &&
                 constructible_from<_Pattern, single_view<range_value_t<_Range>>>
  _LIBCPP_HIDE_FROM_ABI constexpr split_view(_Range&& __range, range_value_t<_Range> __elem)
      : __base_(views::all(std::forward<_Range>(__range))), __pattern_(views::single(std::move(__elem))) {}

_LIBCPP_HIDE_FROM_ABI constexpr _View base() const&
    requires copy_constructible<_View>
  {
    return __base_;
  }

_LIBCPP_HIDE_FROM_ABI constexpr _View base() && { return std::move(__base_); }

_LIBCPP_HIDE_FROM_ABI constexpr __iterator begin() {
    if (!__cached_begin_.__has_value()) {
      __cached_begin_.__emplace(__find_next(ranges::begin(__base_)));
    }
    return {*this, ranges::begin(__base_), *__cached_begin_};
  }

_LIBCPP_HIDE_FROM_ABI constexpr auto end() {
    if constexpr (common_range<_View>) {
      return __iterator{*this, ranges::end(__base_), {}};
    } else {
      return __sentinel{*this};
    }
  }
};

template <class _Range, class _Pattern>
split_view(_Range&&, _Pattern&&) -> split_view<views::all_t<_Range>, views::all_t<_Pattern>>;

template <forward_range _Range>
split_view(_Range&&, range_value_t<_Range>) -> split_view<views::all_t<_Range>, single_view<range_value_t<_Range>>>;

template <class _View, class _Pattern>
struct __split_view_iterator {
private:
  _LIBCPP_NO_UNIQUE_ADDRESS iterator_t<_View> __cur_            = iterator_t<_View>();
  _LIBCPP_NO_UNIQUE_ADDRESS subrange<iterator_t<_View>> __next_ = subrange<iterator_t<_View>>();
  __pointer_int_pair<split_view<_View, _Pattern>*, 1, bool> __parent_ = {nullptr, false};

template <class, class>
  friend struct __split_view_sentinel;

public:
  using iterator_concept  = forward_iterator_tag;
  using iterator_category = input_iterator_tag;
  using value_type        = subrange<iterator_t<_View>>;
  using difference_type   = range_difference_t<_View>;

_LIBCPP_HIDE_FROM_ABI __split_view_iterator() = default;

_LIBCPP_HIDE_FROM_ABI constexpr __split_view_iterator(
      split_view<_View, _Pattern>& __parent, iterator_t<_View> __current, subrange<iterator_t<_View>> __next)
      : __cur_(std::move(__current)), __next_(std::move(__next)), __parent_(std::addressof(__parent), false) {}

_LIBCPP_HIDE_FROM_ABI constexpr iterator_t<_View> base() const { return __cur_; }

_LIBCPP_HIDE_FROM_ABI constexpr value_type operator*() const { return {__cur_, __next_.begin()}; }

_LIBCPP_HIDE_FROM_ABI constexpr __split_view_iterator& operator++() {
    __cur_ = __next_.begin();
    if (__cur_ != ranges::end(__parent_.__get_ptr()->__base_)) {
      __cur_ = __next_.end();
      if (__cur_ == ranges::end(__parent_.__get_ptr()->__base_)) {
        __parent_ = {__parent_.__get_ptr(), true};
        __next_           = {__cur_, __cur_};
      } else {
        __next_ = __parent_.__get_ptr()->__find_next(__cur_);
      }
    } else {
      __parent_ = {__parent_.__get_ptr(), false};
    }
    return *this;
  }

_LIBCPP_HIDE_FROM_ABI constexpr __split_view_iterator operator++(int) {
    auto __tmp = *this;
    ++*this;
    return __tmp;
  }

_LIBCPP_HIDE_FROM_ABI friend constexpr bool
  operator==(const __split_view_iterator& __x, const __split_view_iterator& __y) {
    return __x.__cur_ == __y.__cur_ && __x.__parent_.__get_value() == __y.__parent_.__get_value();
  }
};

template <class _View, class _Pattern>
struct __split_view_sentinel {
private:
  _LIBCPP_NO_UNIQUE_ADDRESS sentinel_t<_View> __end_ = sentinel_t<_View>();

_LIBCPP_HIDE_FROM_ABI static constexpr bool
  __equals(const __split_view_iterator<_View, _Pattern>& __x, const __split_view_sentinel& __y) {
    return __x.__cur_ == __y.__end_ && !__x.__trailing_empty_;
  }

public:
  _LIBCPP_HIDE_FROM_ABI __split_view_sentinel() = default;

_LIBCPP_HIDE_FROM_ABI constexpr explicit __split_view_sentinel(split_view<_View, _Pattern>& __parent)
      : __end_(ranges::end(__parent.__base_)) {}

_LIBCPP_HIDE_FROM_ABI friend constexpr bool
  operator==(const __split_view_iterator<_View, _Pattern>& __x, const __split_view_sentinel& __y) {
    return __equals(__x, __y);
  }
};

namespace views {
namespace __split_view {
struct __fn : __range_adaptor_closure<__fn> {
  // clang-format off
  template <class _Range, class _Pattern>
  _LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI
  constexpr auto operator()(_Range&& __range, _Pattern&& __pattern) const
    noexcept(noexcept(split_view(std::forward<_Range>(__range), std::forward<_Pattern>(__pattern))))
    -> decltype(      split_view(std::forward<_Range>(__range), std::forward<_Pattern>(__pattern)))
    { return          split_view(std::forward<_Range>(__range), std::forward<_Pattern>(__pattern)); }
  // clang-format on

template <class _Pattern>
    requires constructible_from<decay_t<_Pattern>, _Pattern>
  _LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI constexpr auto operator()(_Pattern&& __pattern) const
      noexcept(is_nothrow_constructible_v<decay_t<_Pattern>, _Pattern>) {
    return __range_adaptor_closure_t(std::__bind_back(*this, std::forward<_Pattern>(__pattern)));
  }
};
} // namespace __split_view

inline namespace __cpo {
inline constexpr auto split = __split_view::__fn{};
} // namespace __cpo
} // namespace views

} // namespace ranges

#endif // _LIBCPP_STD_VER >= 20

_LIBCPP_END_NAMESPACE_STD

#endif // _LIBCPP___RANGES_SPLIT_VIEW_H

#include <algorithm>
#include <span>

void clobber(auto&&);

void for_each(std::ranges::split_view<std::span<int>, std::ranges::single_view<int>> view) {
  std::ranges::for_each(view, [](auto el) { clobber(el); });
}