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 <__cstddef/size_t.h>
45
46#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
47# pragma GCC system_header
48#endif
49
50_LIBCPP_BEGIN_NAMESPACE_STD
51
52template <class _Iterator>
53struct __segmented_iterator_traits;
54/* exposition-only:
55{
56 using __segment_iterator = ...;
57 using __local_iterator = ...;
58
59 static __segment_iterator __segment(_Iterator);
60 static __local_iterator __local(_Iterator);
61 static __local_iterator __begin(__segment_iterator);
62 static __local_iterator __end(__segment_iterator);
63 static _Iterator __compose(__segment_iterator, __local_iterator);
64};
65*/
66
67template <class _Tp, size_t = 0>
68inline const bool __has_specialization_v = false;
69
70template <class _Tp>
71inline const bool __has_specialization_v<_Tp, sizeof(_Tp) * 0> = true;
72
73template <class _Iterator>
74inline const bool __is_segmented_iterator_v = __has_specialization_v<__segmented_iterator_traits<_Iterator> >;
75
76_LIBCPP_END_NAMESPACE_STD
77
78#endif // _LIBCPP___SEGMENTED_ITERATOR_H
79