include/__string

// -*- C++ -*-
//===-------------------------- __string ----------------------------------===//
//
// The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//

#ifndef _LIBCPP___STRING
#define _LIBCPP___STRING

/*
 string synopsis

namespace std
{

template <class charT>
struct char_traits
{
 typedef charT char_type;
 typedef ... int_type;
 typedef streamoff off_type;
 typedef streampos pos_type;
 typedef mbstate_t state_type;

 static constexpr void assign(char_type& c1, const char_type& c2) noexcept;
 static constexpr bool eq(char_type c1, char_type c2) noexcept;
 static constexpr bool lt(char_type c1, char_type c2) noexcept;

 static constexpr int compare(const char_type* s1, const char_type* s2, size_t n);
 static constexpr size_t length(const char_type* s);
 static constexpr const char_type* 
 find(const char_type* s, size_t n, const char_type& a);
 static char_type* move(char_type* s1, const char_type* s2, size_t n);
 static char_type* copy(char_type* s1, const char_type* s2, size_t n);
 static char_type* assign(char_type* s, size_t n, char_type a);

 static constexpr int_type not_eof(int_type c) noexcept;
 static constexpr char_type to_char_type(int_type c) noexcept;
 static constexpr int_type to_int_type(char_type c) noexcept;
 static constexpr bool eq_int_type(int_type c1, int_type c2) noexcept;
 static constexpr int_type eof() noexcept;
};

template <> struct char_traits<char>;
template <> struct char_traits<wchar_t>;

} // std

*/

#include <__config>
#include <algorithm> // for search and min
#include <cstdio> // For EOF.
#include <memory> // for __murmur2_or_cityhash

#include <__undef_min_max>

#include <__debug>

#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
#pragma GCC system_header
#endif

_LIBCPP_BEGIN_NAMESPACE_STD

// char_traits

template <class _CharT>
struct _LIBCPP_TEMPLATE_VIS char_traits
{
 typedef _CharT char_type;
 typedef int int_type;
 typedef streamoff off_type;
 typedef streampos pos_type;
 typedef mbstate_t state_type;

 static inline void _LIBCPP_CONSTEXPR_AFTER_CXX14
 assign(char_type& __c1, const char_type& __c2) _NOEXCEPT {__c1 = __c2;}
 static inline _LIBCPP_CONSTEXPR bool eq(char_type __c1, char_type __c2) _NOEXCEPT
 {return __c1 == __c2;}
 static inline _LIBCPP_CONSTEXPR bool lt(char_type __c1, char_type __c2) _NOEXCEPT
 {return __c1 < __c2;}

 static _LIBCPP_CONSTEXPR_AFTER_CXX14
 int compare(const char_type* __s1, const char_type* __s2, size_t __n);
 _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14
 size_t length(const char_type* __s);
 _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14
 const char_type* find(const char_type* __s, size_t __n, const char_type& __a);
 static char_type* move(char_type* __s1, const char_type* __s2, size_t __n);
 _LIBCPP_INLINE_VISIBILITY
 static char_type* copy(char_type* __s1, const char_type* __s2, size_t __n);
 _LIBCPP_INLINE_VISIBILITY
 static char_type* assign(char_type* __s, size_t __n, char_type __a);

 static inline _LIBCPP_CONSTEXPR int_type not_eof(int_type __c) _NOEXCEPT
 {return eq_int_type(__c, eof()) ? ~eof() : __c;}
 static inline _LIBCPP_CONSTEXPR char_type to_char_type(int_type __c) _NOEXCEPT
 {return char_type(__c);}
 static inline _LIBCPP_CONSTEXPR int_type to_int_type(char_type __c) _NOEXCEPT
 {return int_type(__c);}
 static inline _LIBCPP_CONSTEXPR bool eq_int_type(int_type __c1, int_type __c2) _NOEXCEPT
 {return __c1 == __c2;}
 static inline _LIBCPP_CONSTEXPR int_type eof() _NOEXCEPT
 {return int_type(EOF);}
};

template <class _CharT>
_LIBCPP_CONSTEXPR_AFTER_CXX14 int
char_traits<_CharT>::compare(const char_type* __s1, const char_type* __s2, size_t __n)
{
 for (; __n; --__n, ++__s1, ++__s2)
 {
 if (lt(*__s1, *__s2))
 return -1;
 if (lt(*__s2, *__s1))
 return 1;
 }
 return 0;
}

template <class _CharT>
inline
_LIBCPP_CONSTEXPR_AFTER_CXX14 size_t
char_traits<_CharT>::length(const char_type* __s)
{
 size_t __len = 0;
 for (; !eq(*__s, char_type(0)); ++__s)
 ++__len;
 return __len;
}

template <class _CharT>
inline
_LIBCPP_CONSTEXPR_AFTER_CXX14 const _CharT*
char_traits<_CharT>::find(const char_type* __s, size_t __n, const char_type& __a)
{
 for (; __n; --__n)
 {
 if (eq(*__s, __a))
 return __s;
 ++__s;
 }
 return 0;
}

template <class _CharT>
_CharT*
char_traits<_CharT>::move(char_type* __s1, const char_type* __s2, size_t __n)
{
 char_type* __r = __s1;
 if (__s1 < __s2)
 {
 for (; __n; --__n, ++__s1, ++__s2)
 assign(*__s1, *__s2);
 }
 else if (__s2 < __s1)
 {
 __s1 += __n;
 __s2 += __n;
 for (; __n; --__n)
 assign(*--__s1, *--__s2);
 }
 return __r;
}

template <class _CharT>
inline
_CharT*
char_traits<_CharT>::copy(char_type* __s1, const char_type* __s2, size_t __n)
{
 _LIBCPP_ASSERT(__s2 < __s1 || __s2 >= __s1+__n, "char_traits::copy overlapped range");
 char_type* __r = __s1;
 for (; __n; --__n, ++__s1, ++__s2)
 assign(*__s1, *__s2);
 return __r;
}

template <class _CharT>
inline
_CharT*
char_traits<_CharT>::assign(char_type* __s, size_t __n, char_type __a)
{
 char_type* __r = __s;
 for (; __n; --__n, ++__s)
 assign(*__s, __a);
 return __r;
}

// char_traits<char>

template <>
struct _LIBCPP_TEMPLATE_VIS char_traits<char>
{
 typedef char char_type;
 typedef int int_type;
 typedef streamoff off_type;
 typedef streampos pos_type;
 typedef mbstate_t state_type;

 static inline _LIBCPP_CONSTEXPR_AFTER_CXX14
 void assign(char_type& __c1, const char_type& __c2) _NOEXCEPT {__c1 = __c2;}
 static inline _LIBCPP_CONSTEXPR bool eq(char_type __c1, char_type __c2) _NOEXCEPT
 {return __c1 == __c2;}
 static inline _LIBCPP_CONSTEXPR bool lt(char_type __c1, char_type __c2) _NOEXCEPT
 {return (unsigned char)__c1 < (unsigned char)__c2;}

 static _LIBCPP_CONSTEXPR_AFTER_CXX14
 int compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
 static inline size_t _LIBCPP_CONSTEXPR_AFTER_CXX14
 length(const char_type* __s) _NOEXCEPT {return __builtin_strlen(__s);}
 static _LIBCPP_CONSTEXPR_AFTER_CXX14
 const char_type* find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT;
 static inline char_type* move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
 {return __n == 0 ? __s1 : (char_type*) memmove(__s1, __s2, __n);}
 static inline char_type* copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
 {
 _LIBCPP_ASSERT(__s2 < __s1 || __s2 >= __s1+__n, "char_traits::copy overlapped range");
 return __n == 0 ? __s1 : (char_type*)memcpy(__s1, __s2, __n);
 }
 static inline char_type* assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT
 {return __n == 0 ? __s : (char_type*)memset(__s, to_int_type(__a), __n);}

 static inline _LIBCPP_CONSTEXPR int_type not_eof(int_type __c) _NOEXCEPT
 {return eq_int_type(__c, eof()) ? ~eof() : __c;}
 static inline _LIBCPP_CONSTEXPR char_type to_char_type(int_type __c) _NOEXCEPT
 {return char_type(__c);}
 static inline _LIBCPP_CONSTEXPR int_type to_int_type(char_type __c) _NOEXCEPT
 {return int_type((unsigned char)__c);}
 static inline _LIBCPP_CONSTEXPR bool eq_int_type(int_type __c1, int_type __c2) _NOEXCEPT
 {return __c1 == __c2;}
 static inline _LIBCPP_CONSTEXPR int_type eof() _NOEXCEPT
 {return int_type(EOF);}
};

inline _LIBCPP_CONSTEXPR_AFTER_CXX14
int
char_traits<char>::compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
{
 if (__n == 0)
 return 0;
#if __has_feature(cxx_constexpr_string_builtins)
 return __builtin_memcmp(__s1, __s2, __n);
#elif _LIBCPP_STD_VER <= 14
 return memcmp(__s1, __s2, __n);
#else
 for (; __n; --__n, ++__s1, ++__s2)
 {
 if (lt(*__s1, *__s2))
 return -1;
 if (lt(*__s2, *__s1))
 return 1;
 }
 return 0;
#endif
}

inline _LIBCPP_CONSTEXPR_AFTER_CXX14
const char*
char_traits<char>::find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT
{
 if (__n == 0)
 return NULL;
#if __has_feature(cxx_constexpr_string_builtins)
 return __builtin_char_memchr(__s, to_int_type(__a), __n);
#elif _LIBCPP_STD_VER <= 14
 return (const char_type*) memchr(__s, to_int_type(__a), __n);
#else
 for (; __n; --__n)
 {
 if (eq(*__s, __a))
 return __s;
 ++__s;
 }
 return NULL;
#endif
}


// char_traits<wchar_t>

template <>
struct _LIBCPP_TEMPLATE_VIS char_traits<wchar_t>
{
 typedef wchar_t char_type;
 typedef wint_t int_type;
 typedef streamoff off_type;
 typedef streampos pos_type;
 typedef mbstate_t state_type;

 static inline _LIBCPP_CONSTEXPR_AFTER_CXX14
 void assign(char_type& __c1, const char_type& __c2) _NOEXCEPT {__c1 = __c2;}
 static inline _LIBCPP_CONSTEXPR bool eq(char_type __c1, char_type __c2) _NOEXCEPT
 {return __c1 == __c2;}
 static inline _LIBCPP_CONSTEXPR bool lt(char_type __c1, char_type __c2) _NOEXCEPT
 {return __c1 < __c2;}

 static _LIBCPP_CONSTEXPR_AFTER_CXX14
 int compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
 static _LIBCPP_CONSTEXPR_AFTER_CXX14
 size_t length(const char_type* __s) _NOEXCEPT;
 static _LIBCPP_CONSTEXPR_AFTER_CXX14
 const char_type* find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT;
 static inline char_type* move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
 {return __n == 0 ? __s1 : (char_type*)wmemmove(__s1, __s2, __n);}
 static inline char_type* copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
 {
 _LIBCPP_ASSERT(__s2 < __s1 || __s2 >= __s1+__n, "char_traits::copy overlapped range");
 return __n == 0 ? __s1 : (char_type*)wmemcpy(__s1, __s2, __n);
 }
 static inline char_type* assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT
 {return __n == 0 ? __s : (char_type*)wmemset(__s, __a, __n);}

 static inline _LIBCPP_CONSTEXPR int_type not_eof(int_type __c) _NOEXCEPT
 {return eq_int_type(__c, eof()) ? ~eof() : __c;}
 static inline _LIBCPP_CONSTEXPR char_type to_char_type(int_type __c) _NOEXCEPT
 {return char_type(__c);}
 static inline _LIBCPP_CONSTEXPR int_type to_int_type(char_type __c) _NOEXCEPT
 {return int_type(__c);}
 static inline _LIBCPP_CONSTEXPR bool eq_int_type(int_type __c1, int_type __c2) _NOEXCEPT
 {return __c1 == __c2;}
 static inline _LIBCPP_CONSTEXPR int_type eof() _NOEXCEPT
 {return int_type(WEOF);}
};

inline _LIBCPP_CONSTEXPR_AFTER_CXX14
int
char_traits<wchar_t>::compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
{
 if (__n == 0)
 return 0;
#if __has_feature(cxx_constexpr_string_builtins)
 return __builtin_wmemcmp(__s1, __s2, __n);
#elif _LIBCPP_STD_VER <= 14
 return wmemcmp(__s1, __s2, __n);
#else
 for (; __n; --__n, ++__s1, ++__s2)
 {
 if (lt(*__s1, *__s2))
 return -1;
 if (lt(*__s2, *__s1))
 return 1;
 }
 return 0;
#endif
}

inline _LIBCPP_CONSTEXPR_AFTER_CXX14
size_t
char_traits<wchar_t>::length(const char_type* __s) _NOEXCEPT
{
#if __has_feature(cxx_constexpr_string_builtins)
 return __builtin_wcslen(__s);
#elif _LIBCPP_STD_VER <= 14
 return wcslen(__s);
#else
 size_t __len = 0;
 for (; !eq(*__s, char_type(0)); ++__s)
 ++__len;
 return __len;
#endif
}

inline _LIBCPP_CONSTEXPR_AFTER_CXX14
const wchar_t*
char_traits<wchar_t>::find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT
{
 if (__n == 0)
 return NULL;
#if __has_feature(cxx_constexpr_string_builtins)
 return __builtin_wmemchr(__s, __a, __n);
#elif _LIBCPP_STD_VER <= 14
 return wmemchr(__s, __a, __n);
#else
 for (; __n; --__n)
 {
 if (eq(*__s, __a))
 return __s;
 ++__s;
 }
 return NULL;
#endif
}


#ifndef _LIBCPP_HAS_NO_UNICODE_CHARS

template <>
struct _LIBCPP_TEMPLATE_VIS char_traits<char16_t>
{
 typedef char16_t char_type;
 typedef uint_least16_t int_type;
 typedef streamoff off_type;
 typedef u16streampos pos_type;
 typedef mbstate_t state_type;

 static inline _LIBCPP_CONSTEXPR_AFTER_CXX14
 void assign(char_type& __c1, const char_type& __c2) _NOEXCEPT {__c1 = __c2;}
 static inline _LIBCPP_CONSTEXPR bool eq(char_type __c1, char_type __c2) _NOEXCEPT
 {return __c1 == __c2;}
 static inline _LIBCPP_CONSTEXPR bool lt(char_type __c1, char_type __c2) _NOEXCEPT
 {return __c1 < __c2;}

 _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14
 int compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
 _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14
 size_t length(const char_type* __s) _NOEXCEPT;
 _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14
 const char_type* find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT;
 _LIBCPP_INLINE_VISIBILITY
 static char_type* move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
 _LIBCPP_INLINE_VISIBILITY
 static char_type* copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
 _LIBCPP_INLINE_VISIBILITY
 static char_type* assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT;

 static inline _LIBCPP_CONSTEXPR int_type not_eof(int_type __c) _NOEXCEPT
 {return eq_int_type(__c, eof()) ? ~eof() : __c;}
 static inline _LIBCPP_CONSTEXPR char_type to_char_type(int_type __c) _NOEXCEPT
 {return char_type(__c);}
 static inline _LIBCPP_CONSTEXPR int_type to_int_type(char_type __c) _NOEXCEPT
 {return int_type(__c);}
 static inline _LIBCPP_CONSTEXPR bool eq_int_type(int_type __c1, int_type __c2) _NOEXCEPT
 {return __c1 == __c2;}
 static inline _LIBCPP_CONSTEXPR int_type eof() _NOEXCEPT
 {return int_type(0xFFFF);}
};

inline _LIBCPP_CONSTEXPR_AFTER_CXX14
int
char_traits<char16_t>::compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
{
 for (; __n; --__n, ++__s1, ++__s2)
 {
 if (lt(*__s1, *__s2))
 return -1;
 if (lt(*__s2, *__s1))
 return 1;
 }
 return 0;
}

inline _LIBCPP_CONSTEXPR_AFTER_CXX14
size_t
char_traits<char16_t>::length(const char_type* __s) _NOEXCEPT
{
 size_t __len = 0;
 for (; !eq(*__s, char_type(0)); ++__s)
 ++__len;
 return __len;
}

inline _LIBCPP_CONSTEXPR_AFTER_CXX14
const char16_t*
char_traits<char16_t>::find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT
{
 for (; __n; --__n)
 {
 if (eq(*__s, __a))
 return __s;
 ++__s;
 }
 return 0;
}

inline
char16_t*
char_traits<char16_t>::move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
{
 char_type* __r = __s1;
 if (__s1 < __s2)
 {
 for (; __n; --__n, ++__s1, ++__s2)
 assign(*__s1, *__s2);
 }
 else if (__s2 < __s1)
 {
 __s1 += __n;
 __s2 += __n;
 for (; __n; --__n)
 assign(*--__s1, *--__s2);
 }
 return __r;
}

inline
char16_t*
char_traits<char16_t>::copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
{
 _LIBCPP_ASSERT(__s2 < __s1 || __s2 >= __s1+__n, "char_traits::copy overlapped range");
 char_type* __r = __s1;
 for (; __n; --__n, ++__s1, ++__s2)
 assign(*__s1, *__s2);
 return __r;
}

inline
char16_t*
char_traits<char16_t>::assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT
{
 char_type* __r = __s;
 for (; __n; --__n, ++__s)
 assign(*__s, __a);
 return __r;
}

template <>
struct _LIBCPP_TEMPLATE_VIS char_traits<char32_t>
{
 typedef char32_t char_type;
 typedef uint_least32_t int_type;
 typedef streamoff off_type;
 typedef u32streampos pos_type;
 typedef mbstate_t state_type;

 static inline _LIBCPP_CONSTEXPR_AFTER_CXX14
 void assign(char_type& __c1, const char_type& __c2) _NOEXCEPT {__c1 = __c2;}
 static inline _LIBCPP_CONSTEXPR bool eq(char_type __c1, char_type __c2) _NOEXCEPT
 {return __c1 == __c2;}
 static inline _LIBCPP_CONSTEXPR bool lt(char_type __c1, char_type __c2) _NOEXCEPT
 {return __c1 < __c2;}

 _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14
 int compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
 _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14
 size_t length(const char_type* __s) _NOEXCEPT;
 _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14
 const char_type* find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT;
 _LIBCPP_INLINE_VISIBILITY
 static char_type* move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
 _LIBCPP_INLINE_VISIBILITY
 static char_type* copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
 _LIBCPP_INLINE_VISIBILITY
 static char_type* assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT;

 static inline _LIBCPP_CONSTEXPR int_type not_eof(int_type __c) _NOEXCEPT
 {return eq_int_type(__c, eof()) ? ~eof() : __c;}
 static inline _LIBCPP_CONSTEXPR char_type to_char_type(int_type __c) _NOEXCEPT
 {return char_type(__c);}
 static inline _LIBCPP_CONSTEXPR int_type to_int_type(char_type __c) _NOEXCEPT
 {return int_type(__c);}
 static inline _LIBCPP_CONSTEXPR bool eq_int_type(int_type __c1, int_type __c2) _NOEXCEPT
 {return __c1 == __c2;}
 static inline _LIBCPP_CONSTEXPR int_type eof() _NOEXCEPT
 {return int_type(0xFFFFFFFF);}
};

inline _LIBCPP_CONSTEXPR_AFTER_CXX14
int
char_traits<char32_t>::compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
{
 for (; __n; --__n, ++__s1, ++__s2)
 {
 if (lt(*__s1, *__s2))
 return -1;
 if (lt(*__s2, *__s1))
 return 1;
 }
 return 0;
}

inline _LIBCPP_CONSTEXPR_AFTER_CXX14
size_t
char_traits<char32_t>::length(const char_type* __s) _NOEXCEPT
{
 size_t __len = 0;
 for (; !eq(*__s, char_type(0)); ++__s)
 ++__len;
 return __len;
}

inline _LIBCPP_CONSTEXPR_AFTER_CXX14
const char32_t*
char_traits<char32_t>::find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT
{
 for (; __n; --__n)
 {
 if (eq(*__s, __a))
 return __s;
 ++__s;
 }
 return 0;
}

inline
char32_t*
char_traits<char32_t>::move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
{
 char_type* __r = __s1;
 if (__s1 < __s2)
 {
 for (; __n; --__n, ++__s1, ++__s2)
 assign(*__s1, *__s2);
 }
 else if (__s2 < __s1)
 {
 __s1 += __n;
 __s2 += __n;
 for (; __n; --__n)
 assign(*--__s1, *--__s2);
 }
 return __r;
}

inline
char32_t*
char_traits<char32_t>::copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
{
 _LIBCPP_ASSERT(__s2 < __s1 || __s2 >= __s1+__n, "char_traits::copy overlapped range");
 char_type* __r = __s1;
 for (; __n; --__n, ++__s1, ++__s2)
 assign(*__s1, *__s2);
 return __r;
}

inline
char32_t*
char_traits<char32_t>::assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT
{
 char_type* __r = __s;
 for (; __n; --__n, ++__s)
 assign(*__s, __a);
 return __r;
}

#endif // _LIBCPP_HAS_NO_UNICODE_CHARS

// helper fns for basic_string and string_view

// __str_find
template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
__str_find(const _CharT *__p, _SizeT __sz, 
 _CharT __c, _SizeT __pos) _NOEXCEPT
{
 if (__pos >= __sz)
 return __npos;
 const _CharT* __r = _Traits::find(__p + __pos, __sz - __pos, __c);
 if (__r == 0)
 return __npos;
 return static_cast<_SizeT>(__r - __p);
}

template <class _CharT, class _Traits>
inline _LIBCPP_CONSTEXPR_AFTER_CXX11 const _CharT *
__search_substring(const _CharT *__first1, const _CharT *__last1,
 const _CharT *__first2, const _CharT *__last2) {
 // Take advantage of knowing source and pattern lengths.
 // Stop short when source is smaller than pattern.
 const ptrdiff_t __len2 = __last2 - __first2;
 if (__len2 == 0)
 return __first1;

 ptrdiff_t __len1 = __last1 - __first1;
 if (__len1 < __len2)
 return __last1;

 // First element of __first2 is loop invariant.
 _CharT __f2 = *__first2;
 while (true) {
 __len1 = __last1 - __first1;
 // Check whether __first1 still has at least __len2 bytes.
 if (__len1 < __len2)
 return __last1;

 // Find __f2 the first byte matching in __first1.
 __first1 = _Traits::find(__first1, __len1 - __len2 + 1, __f2);
 if (__first1 == 0)
 return __last1;

 // It is faster to compare from the first byte of __first1 even if we
 // already know that it matches the first byte of __first2: this is because
 // __first2 is most likely aligned, as it is user's "pattern" string, and
 // __first1 + 1 is most likely not aligned, as the match is in the middle of
 // the string.
 if (_Traits::compare(__first1, __first2, __len2) == 0)
 return __first1;

 ++__first1;
 }
}

template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
__str_find(const _CharT *__p, _SizeT __sz, 
 const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT
{
 if (__pos > __sz)
 return __npos;

 if (__n == 0) // There is nothing to search, just return __pos.
 return __pos;

 const _CharT *__r = __search_substring<_CharT, _Traits>(
 __p + __pos, __p + __sz, __s, __s + __n);

 if (__r == __p + __sz)
 return __npos;
 return static_cast<_SizeT>(__r - __p);
}


// __str_rfind

template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
__str_rfind(const _CharT *__p, _SizeT __sz, 
 _CharT __c, _SizeT __pos) _NOEXCEPT
{
 if (__sz < 1)
 return __npos;
 if (__pos < __sz)
 ++__pos;
 else
 __pos = __sz;
 for (const _CharT* __ps = __p + __pos; __ps != __p;)
 {
 if (_Traits::eq(*--__ps, __c))
 return static_cast<_SizeT>(__ps - __p);
 }
 return __npos;
}

template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
__str_rfind(const _CharT *__p, _SizeT __sz, 
 const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT
{
 __pos = _VSTD::min(__pos, __sz);
 if (__n < __sz - __pos)
 __pos += __n;
 else
 __pos = __sz;
 const _CharT* __r = _VSTD::__find_end(
 __p, __p + __pos, __s, __s + __n, _Traits::eq, 
 random_access_iterator_tag(), random_access_iterator_tag());
 if (__n > 0 && __r == __p + __pos)
 return __npos;
 return static_cast<_SizeT>(__r - __p);
}

// __str_find_first_of
template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
__str_find_first_of(const _CharT *__p, _SizeT __sz,
 const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT
{
 if (__pos >= __sz || __n == 0)
 return __npos;
 const _CharT* __r = _VSTD::__find_first_of_ce
 (__p + __pos, __p + __sz, __s, __s + __n, _Traits::eq );
 if (__r == __p + __sz)
 return __npos;
 return static_cast<_SizeT>(__r - __p);
}


// __str_find_last_of
template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
__str_find_last_of(const _CharT *__p, _SizeT __sz,
 const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT
 {
 if (__n != 0)
 {
 if (__pos < __sz)
 ++__pos;
 else
 __pos = __sz;
 for (const _CharT* __ps = __p + __pos; __ps != __p;)
 {
 const _CharT* __r = _Traits::find(__s, __n, *--__ps);
 if (__r)
 return static_cast<_SizeT>(__ps - __p);
 }
 }
 return __npos;
}


// __str_find_first_not_of
template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
__str_find_first_not_of(const _CharT *__p, _SizeT __sz,
 const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT
{
 if (__pos < __sz)
 {
 const _CharT* __pe = __p + __sz;
 for (const _CharT* __ps = __p + __pos; __ps != __pe; ++__ps)
 if (_Traits::find(__s, __n, *__ps) == 0)
 return static_cast<_SizeT>(__ps - __p);
 }
 return __npos;
}


template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
__str_find_first_not_of(const _CharT *__p, _SizeT __sz,
 _CharT __c, _SizeT __pos) _NOEXCEPT
{
 if (__pos < __sz)
 {
 const _CharT* __pe = __p + __sz;
 for (const _CharT* __ps = __p + __pos; __ps != __pe; ++__ps)
 if (!_Traits::eq(*__ps, __c))
 return static_cast<_SizeT>(__ps - __p);
 }
 return __npos;
}


// __str_find_last_not_of
template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
__str_find_last_not_of(const _CharT *__p, _SizeT __sz,
 const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT
{
 if (__pos < __sz)
 ++__pos;
 else
 __pos = __sz;
 for (const _CharT* __ps = __p + __pos; __ps != __p;)
 if (_Traits::find(__s, __n, *--__ps) == 0)
 return static_cast<_SizeT>(__ps - __p);
 return __npos;
}


template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
__str_find_last_not_of(const _CharT *__p, _SizeT __sz,
 _CharT __c, _SizeT __pos) _NOEXCEPT
{
 if (__pos < __sz)
 ++__pos;
 else
 __pos = __sz;
 for (const _CharT* __ps = __p + __pos; __ps != __p;)
 if (!_Traits::eq(*--__ps, __c))
 return static_cast<_SizeT>(__ps - __p);
 return __npos;
}

template<class _Ptr>
inline _LIBCPP_INLINE_VISIBILITY
size_t __do_string_hash(_Ptr __p, _Ptr __e)
{
 typedef typename iterator_traits<_Ptr>::value_type value_type;
 return __murmur2_or_cityhash<size_t>()(__p, (__e-__p)*sizeof(value_type));
}

template <class _CharT, class _Iter, class _Traits=char_traits<_CharT> >
struct __quoted_output_proxy
{
 _Iter __first;
 _Iter __last;
 _CharT __delim;
 _CharT __escape;

 __quoted_output_proxy(_Iter __f, _Iter __l, _CharT __d, _CharT __e)
 : __first(__f), __last(__l), __delim(__d), __escape(__e) {}
 // This would be a nice place for a string_ref 
};

_LIBCPP_END_NAMESPACE_STD

#endif // _LIBCPP___STRING