1//===----------------------------------------------------------------------===// 2// 3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4// See https://llvm.org/LICENSE.txt for license information. 5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6// 7//===----------------------------------------------------------------------===// 8 9#ifndef _LIBCPP___SEGMENTED_ITERATOR_H 10#define _LIBCPP___SEGMENTED_ITERATOR_H 11 12// Segmented iterators are iterators over (not necessarily contiguous) sub-ranges. 13// 14// For example, std::deque stores its data into multiple blocks of contiguous memory, 15// which are not stored contiguously themselves. The concept of segmented iterators 16// allows algorithms to operate over these multi-level iterators natively, opening the 17// door to various optimizations. See http://lafstern.org/matt/segmented.pdf for details. 18// 19// If __segmented_iterator_traits can be instantiated, the following functions and associated types must be provided: 20// - Traits::__local_iterator 21// The type of iterators used to iterate inside a segment. 22// 23// - Traits::__segment_iterator 24// The type of iterators used to iterate over segments. 25// Segment iterators can be forward iterators or bidirectional iterators, depending on the 26// underlying data structure. 27// 28// - static __segment_iterator Traits::__segment(It __it) 29// Returns an iterator to the segment that the provided iterator is in. 30// 31// - static __local_iterator Traits::__local(It __it) 32// Returns the local iterator pointing to the element that the provided iterator points to. 33// 34// - static __local_iterator Traits::__begin(__segment_iterator __it) 35// Returns the local iterator to the beginning of the segment that the provided iterator is pointing into. 36// 37// - static __local_iterator Traits::__end(__segment_iterator __it) 38// Returns the one-past-the-end local iterator to the segment that the provided iterator is pointing into. 39// 40// - static It Traits::__compose(__segment_iterator, __local_iterator) 41// Returns the iterator composed of the segment iterator and local iterator. 42 43#include <__config> 44#include <__type_traits/integral_constant.h> 45#include <cstddef> 46 47#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 48# pragma GCC system_header 49#endif 50 51_LIBCPP_BEGIN_NAMESPACE_STD 52 53template <class _Iterator> 54struct __segmented_iterator_traits; 55/* exposition-only: 56{ 57 using __segment_iterator = ...; 58 using __local_iterator = ...; 59 60 static __segment_iterator __segment(_Iterator); 61 static __local_iterator __local(_Iterator); 62 static __local_iterator __begin(__segment_iterator); 63 static __local_iterator __end(__segment_iterator); 64 static _Iterator __compose(__segment_iterator, __local_iterator); 65}; 66*/ 67 68template <class _Tp, size_t = 0> 69struct __has_specialization : false_type {}; 70 71template <class _Tp> 72struct __has_specialization<_Tp, sizeof(_Tp) * 0> : true_type {}; 73 74template <class _Iterator> 75using __is_segmented_iterator = __has_specialization<__segmented_iterator_traits<_Iterator> >; 76 77_LIBCPP_END_NAMESPACE_STD 78 79#endif // _LIBCPP___SEGMENTED_ITERATOR_H 80