libcxx/include/__iterator/segmented_iterator.h

   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 #include <__type_traits/integral_constant.h>
  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