81 lines · c
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-exception6//7//===----------------------------------------------------------------------===//8 9#ifndef _LIBCPP___SEGMENTED_ITERATOR_H10#define _LIBCPP___SEGMENTED_ITERATOR_H11 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 iterators16// allows algorithms to operate over these multi-level iterators natively, opening the17// 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_iterator21// The type of iterators used to iterate inside a segment.22//23// - Traits::__segment_iterator24// The type of iterators used to iterate over segments.25// Segment iterators can be forward iterators or bidirectional iterators, depending on the26// 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 <__iterator/iterator_traits.h>46#include <__type_traits/integral_constant.h>47 48#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)49# pragma GCC system_header50#endif51 52_LIBCPP_BEGIN_NAMESPACE_STD53 54template <class _Iterator>55struct __segmented_iterator_traits;56/* exposition-only:57{58 using __segment_iterator = ...;59 using __local_iterator = ...;60 61 static __segment_iterator __segment(_Iterator);62 static __local_iterator __local(_Iterator);63 static __local_iterator __begin(__segment_iterator);64 static __local_iterator __end(__segment_iterator);65 static _Iterator __compose(__segment_iterator, __local_iterator);66};67*/68 69template <class _Tp, size_t = 0>70inline const bool __has_specialization_v = false;71 72template <class _Tp>73inline const bool __has_specialization_v<_Tp, sizeof(_Tp) * 0> = true;74 75template <class _Iterator>76inline const bool __is_segmented_iterator_v = __has_specialization_v<__segmented_iterator_traits<_Iterator> >;77 78_LIBCPP_END_NAMESPACE_STD79 80#endif // _LIBCPP___SEGMENTED_ITERATOR_H81