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