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 53 template <class _Iterator> 54 struct __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 68 template <class _Tp, size_t = 0> 69 struct __has_specialization : false_type {}; 70 71 template <class _Tp> 72 struct __has_specialization<_Tp, sizeof(_Tp) * 0> : true_type {}; 73 74 template <class _Iterator> 75 using __is_segmented_iterator = __has_specialization<__segmented_iterator_traits<_Iterator> >; 76 77 _LIBCPP_END_NAMESPACE_STD 78 79 #endif // _LIBCPP___SEGMENTED_ITERATOR_H 80