1// -*- C++ -*-
2//===-------------------------- __string ----------------------------------===//
3//
4//                     The LLVM Compiler Infrastructure
5//
6// This file is distributed under the University of Illinois Open Source
7// License. See LICENSE.TXT for details.
8//
9//===----------------------------------------------------------------------===//
10
11#ifndef _LIBCPP___STRING
12#define _LIBCPP___STRING
13
14/*
15    string synopsis
16
17namespace std
18{
19
20template <class charT>
21struct char_traits
22{
23    typedef charT     char_type;
24    typedef ...       int_type;
25    typedef streamoff off_type;
26    typedef streampos pos_type;
27    typedef mbstate_t state_type;
28
29    static constexpr void assign(char_type& c1, const char_type& c2) noexcept;
30    static constexpr bool eq(char_type c1, char_type c2) noexcept;
31    static constexpr bool lt(char_type c1, char_type c2) noexcept;
32
33    static constexpr int    compare(const char_type* s1, const char_type* s2, size_t n);
34    static constexpr size_t length(const char_type* s);
35    static constexpr const char_type*
36                            find(const char_type* s, size_t n, const char_type& a);
37    static char_type*       move(char_type* s1, const char_type* s2, size_t n);
38    static char_type*       copy(char_type* s1, const char_type* s2, size_t n);
39    static char_type*       assign(char_type* s, size_t n, char_type a);
40
41    static constexpr int_type  not_eof(int_type c) noexcept;
42    static constexpr char_type to_char_type(int_type c) noexcept;
43    static constexpr int_type  to_int_type(char_type c) noexcept;
44    static constexpr bool      eq_int_type(int_type c1, int_type c2) noexcept;
45    static constexpr int_type  eof() noexcept;
46};
47
48template <> struct char_traits<char>;
49template <> struct char_traits<wchar_t>;
50
51}  // std
52
53*/
54
55#include <__config>
56#include <algorithm>  // for search and min
57#include <cstdio>     // For EOF.
58#include <memory>     // for __murmur2_or_cityhash
59
60#include <__debug>
61
62#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
63#pragma GCC system_header
64#endif
65
66_LIBCPP_PUSH_MACROS
67#include <__undef_macros>
68
69
70_LIBCPP_BEGIN_NAMESPACE_STD
71
72// char_traits
73
74template <class _CharT>
75struct _LIBCPP_TEMPLATE_VIS char_traits
76{
77    typedef _CharT    char_type;
78    typedef int       int_type;
79    typedef streamoff off_type;
80    typedef streampos pos_type;
81    typedef mbstate_t state_type;
82
83    static inline void _LIBCPP_CONSTEXPR_AFTER_CXX14
84        assign(char_type& __c1, const char_type& __c2) _NOEXCEPT {__c1 = __c2;}
85    static inline _LIBCPP_CONSTEXPR bool eq(char_type __c1, char_type __c2) _NOEXCEPT
86        {return __c1 == __c2;}
87    static inline _LIBCPP_CONSTEXPR bool lt(char_type __c1, char_type __c2) _NOEXCEPT
88        {return __c1 < __c2;}
89
90    static _LIBCPP_CONSTEXPR_AFTER_CXX14
91    int compare(const char_type* __s1, const char_type* __s2, size_t __n);
92    _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14
93    size_t length(const char_type* __s);
94    _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14
95    const char_type* find(const char_type* __s, size_t __n, const char_type& __a);
96    static char_type*       move(char_type* __s1, const char_type* __s2, size_t __n);
97    _LIBCPP_INLINE_VISIBILITY
98    static char_type*       copy(char_type* __s1, const char_type* __s2, size_t __n);
99    _LIBCPP_INLINE_VISIBILITY
100    static char_type*       assign(char_type* __s, size_t __n, char_type __a);
101
102    static inline _LIBCPP_CONSTEXPR int_type  not_eof(int_type __c) _NOEXCEPT
103        {return eq_int_type(__c, eof()) ? ~eof() : __c;}
104    static inline _LIBCPP_CONSTEXPR char_type to_char_type(int_type __c) _NOEXCEPT
105        {return char_type(__c);}
106    static inline _LIBCPP_CONSTEXPR int_type  to_int_type(char_type __c) _NOEXCEPT
107        {return int_type(__c);}
108    static inline _LIBCPP_CONSTEXPR bool      eq_int_type(int_type __c1, int_type __c2) _NOEXCEPT
109        {return __c1 == __c2;}
110    static inline _LIBCPP_CONSTEXPR int_type  eof() _NOEXCEPT
111        {return int_type(EOF);}
112};
113
114template <class _CharT>
115_LIBCPP_CONSTEXPR_AFTER_CXX14 int
116char_traits<_CharT>::compare(const char_type* __s1, const char_type* __s2, size_t __n)
117{
118    for (; __n; --__n, ++__s1, ++__s2)
119    {
120        if (lt(*__s1, *__s2))
121            return -1;
122        if (lt(*__s2, *__s1))
123            return 1;
124    }
125    return 0;
126}
127
128template <class _CharT>
129inline
130_LIBCPP_CONSTEXPR_AFTER_CXX14 size_t
131char_traits<_CharT>::length(const char_type* __s)
132{
133    size_t __len = 0;
134    for (; !eq(*__s, char_type(0)); ++__s)
135        ++__len;
136    return __len;
137}
138
139template <class _CharT>
140inline
141_LIBCPP_CONSTEXPR_AFTER_CXX14 const _CharT*
142char_traits<_CharT>::find(const char_type* __s, size_t __n, const char_type& __a)
143{
144    for (; __n; --__n)
145    {
146        if (eq(*__s, __a))
147            return __s;
148        ++__s;
149    }
150    return 0;
151}
152
153template <class _CharT>
154_CharT*
155char_traits<_CharT>::move(char_type* __s1, const char_type* __s2, size_t __n)
156{
157    char_type* __r = __s1;
158    if (__s1 < __s2)
159    {
160        for (; __n; --__n, ++__s1, ++__s2)
161            assign(*__s1, *__s2);
162    }
163    else if (__s2 < __s1)
164    {
165        __s1 += __n;
166        __s2 += __n;
167        for (; __n; --__n)
168            assign(*--__s1, *--__s2);
169    }
170    return __r;
171}
172
173template <class _CharT>
174inline
175_CharT*
176char_traits<_CharT>::copy(char_type* __s1, const char_type* __s2, size_t __n)
177{
178    _LIBCPP_ASSERT(__s2 < __s1 || __s2 >= __s1+__n, "char_traits::copy overlapped range");
179    char_type* __r = __s1;
180    for (; __n; --__n, ++__s1, ++__s2)
181        assign(*__s1, *__s2);
182    return __r;
183}
184
185template <class _CharT>
186inline
187_CharT*
188char_traits<_CharT>::assign(char_type* __s, size_t __n, char_type __a)
189{
190    char_type* __r = __s;
191    for (; __n; --__n, ++__s)
192        assign(*__s, __a);
193    return __r;
194}
195
196// char_traits<char>
197
198template <>
199struct _LIBCPP_TEMPLATE_VIS char_traits<char>
200{
201    typedef char      char_type;
202    typedef int       int_type;
203    typedef streamoff off_type;
204    typedef streampos pos_type;
205    typedef mbstate_t state_type;
206
207    static inline _LIBCPP_CONSTEXPR_AFTER_CXX14
208    void assign(char_type& __c1, const char_type& __c2) _NOEXCEPT {__c1 = __c2;}
209    static inline _LIBCPP_CONSTEXPR bool eq(char_type __c1, char_type __c2) _NOEXCEPT
210            {return __c1 == __c2;}
211    static inline _LIBCPP_CONSTEXPR bool lt(char_type __c1, char_type __c2) _NOEXCEPT
212        {return (unsigned char)__c1 < (unsigned char)__c2;}
213
214    static _LIBCPP_CONSTEXPR_AFTER_CXX14
215    int compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
216    static inline size_t _LIBCPP_CONSTEXPR_AFTER_CXX14
217    length(const char_type* __s)  _NOEXCEPT {return __builtin_strlen(__s);}
218    static _LIBCPP_CONSTEXPR_AFTER_CXX14
219    const char_type* find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT;
220    static inline char_type* move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
221        {return __n == 0 ? __s1 : (char_type*) memmove(__s1, __s2, __n);}
222    static inline char_type* copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
223        {
224            _LIBCPP_ASSERT(__s2 < __s1 || __s2 >= __s1+__n, "char_traits::copy overlapped range");
225            return __n == 0 ? __s1 : (char_type*)memcpy(__s1, __s2, __n);
226        }
227    static inline char_type* assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT
228        {return __n == 0 ? __s : (char_type*)memset(__s, to_int_type(__a), __n);}
229
230    static inline _LIBCPP_CONSTEXPR int_type  not_eof(int_type __c) _NOEXCEPT
231        {return eq_int_type(__c, eof()) ? ~eof() : __c;}
232    static inline _LIBCPP_CONSTEXPR char_type to_char_type(int_type __c) _NOEXCEPT
233        {return char_type(__c);}
234    static inline _LIBCPP_CONSTEXPR int_type to_int_type(char_type __c) _NOEXCEPT
235        {return int_type((unsigned char)__c);}
236    static inline _LIBCPP_CONSTEXPR bool eq_int_type(int_type __c1, int_type __c2) _NOEXCEPT
237        {return __c1 == __c2;}
238    static inline _LIBCPP_CONSTEXPR int_type  eof() _NOEXCEPT
239        {return int_type(EOF);}
240};
241
242inline _LIBCPP_CONSTEXPR_AFTER_CXX14
243int
244char_traits<char>::compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
245{
246    if (__n == 0)
247        return 0;
248#if __has_feature(cxx_constexpr_string_builtins)
249    return __builtin_memcmp(__s1, __s2, __n);
250#elif _LIBCPP_STD_VER <= 14
251    return memcmp(__s1, __s2, __n);
252#else
253    for (; __n; --__n, ++__s1, ++__s2)
254    {
255        if (lt(*__s1, *__s2))
256            return -1;
257        if (lt(*__s2, *__s1))
258            return 1;
259    }
260    return 0;
261#endif
262}
263
264inline _LIBCPP_CONSTEXPR_AFTER_CXX14
265const char*
266char_traits<char>::find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT
267{
268    if (__n == 0)
269        return nullptr;
270#if __has_feature(cxx_constexpr_string_builtins)
271    return __builtin_char_memchr(__s, to_int_type(__a), __n);
272#elif _LIBCPP_STD_VER <= 14
273    return (const char_type*) memchr(__s, to_int_type(__a), __n);
274#else
275    for (; __n; --__n)
276    {
277        if (eq(*__s, __a))
278            return __s;
279        ++__s;
280    }
281    return nullptr;
282#endif
283}
284
285
286// char_traits<wchar_t>
287
288template <>
289struct _LIBCPP_TEMPLATE_VIS char_traits<wchar_t>
290{
291    typedef wchar_t   char_type;
292    typedef wint_t    int_type;
293    typedef streamoff off_type;
294    typedef streampos pos_type;
295    typedef mbstate_t state_type;
296
297    static inline _LIBCPP_CONSTEXPR_AFTER_CXX14
298    void assign(char_type& __c1, const char_type& __c2) _NOEXCEPT {__c1 = __c2;}
299    static inline _LIBCPP_CONSTEXPR bool eq(char_type __c1, char_type __c2) _NOEXCEPT
300        {return __c1 == __c2;}
301    static inline _LIBCPP_CONSTEXPR bool lt(char_type __c1, char_type __c2) _NOEXCEPT
302        {return __c1 < __c2;}
303
304    static _LIBCPP_CONSTEXPR_AFTER_CXX14
305    int compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
306    static _LIBCPP_CONSTEXPR_AFTER_CXX14
307    size_t length(const char_type* __s) _NOEXCEPT;
308    static _LIBCPP_CONSTEXPR_AFTER_CXX14
309    const char_type* find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT;
310    static inline char_type* move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
311        {return __n == 0 ? __s1 : (char_type*)wmemmove(__s1, __s2, __n);}
312    static inline char_type* copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
313        {
314            _LIBCPP_ASSERT(__s2 < __s1 || __s2 >= __s1+__n, "char_traits::copy overlapped range");
315            return __n == 0 ? __s1 : (char_type*)wmemcpy(__s1, __s2, __n);
316        }
317    static inline char_type* assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT
318        {return __n == 0 ? __s : (char_type*)wmemset(__s, __a, __n);}
319
320    static inline _LIBCPP_CONSTEXPR int_type  not_eof(int_type __c) _NOEXCEPT
321        {return eq_int_type(__c, eof()) ? ~eof() : __c;}
322    static inline _LIBCPP_CONSTEXPR char_type to_char_type(int_type __c) _NOEXCEPT
323        {return char_type(__c);}
324    static inline _LIBCPP_CONSTEXPR int_type to_int_type(char_type __c) _NOEXCEPT
325        {return int_type(__c);}
326    static inline _LIBCPP_CONSTEXPR bool eq_int_type(int_type __c1, int_type __c2) _NOEXCEPT
327        {return __c1 == __c2;}
328    static inline _LIBCPP_CONSTEXPR int_type eof() _NOEXCEPT
329        {return int_type(WEOF);}
330};
331
332inline _LIBCPP_CONSTEXPR_AFTER_CXX14
333int
334char_traits<wchar_t>::compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
335{
336    if (__n == 0)
337        return 0;
338#if __has_feature(cxx_constexpr_string_builtins)
339    return __builtin_wmemcmp(__s1, __s2, __n);
340#elif _LIBCPP_STD_VER <= 14
341    return wmemcmp(__s1, __s2, __n);
342#else
343    for (; __n; --__n, ++__s1, ++__s2)
344    {
345        if (lt(*__s1, *__s2))
346            return -1;
347        if (lt(*__s2, *__s1))
348            return 1;
349    }
350    return 0;
351#endif
352}
353
354inline _LIBCPP_CONSTEXPR_AFTER_CXX14
355size_t
356char_traits<wchar_t>::length(const char_type* __s) _NOEXCEPT
357{
358#if __has_feature(cxx_constexpr_string_builtins)
359    return __builtin_wcslen(__s);
360#elif _LIBCPP_STD_VER <= 14
361    return wcslen(__s);
362#else
363    size_t __len = 0;
364    for (; !eq(*__s, char_type(0)); ++__s)
365        ++__len;
366    return __len;
367#endif
368}
369
370inline _LIBCPP_CONSTEXPR_AFTER_CXX14
371const wchar_t*
372char_traits<wchar_t>::find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT
373{
374    if (__n == 0)
375        return nullptr;
376#if __has_feature(cxx_constexpr_string_builtins)
377    return __builtin_wmemchr(__s, __a, __n);
378#elif _LIBCPP_STD_VER <= 14
379    return wmemchr(__s, __a, __n);
380#else
381    for (; __n; --__n)
382    {
383        if (eq(*__s, __a))
384            return __s;
385        ++__s;
386    }
387    return nullptr;
388#endif
389}
390
391
392#ifndef _LIBCPP_HAS_NO_UNICODE_CHARS
393
394template <>
395struct _LIBCPP_TEMPLATE_VIS char_traits<char16_t>
396{
397    typedef char16_t       char_type;
398    typedef uint_least16_t int_type;
399    typedef streamoff      off_type;
400    typedef u16streampos   pos_type;
401    typedef mbstate_t      state_type;
402
403    static inline _LIBCPP_CONSTEXPR_AFTER_CXX14
404    void assign(char_type& __c1, const char_type& __c2) _NOEXCEPT {__c1 = __c2;}
405    static inline _LIBCPP_CONSTEXPR bool eq(char_type __c1, char_type __c2) _NOEXCEPT
406        {return __c1 == __c2;}
407    static inline _LIBCPP_CONSTEXPR bool lt(char_type __c1, char_type __c2) _NOEXCEPT
408        {return __c1 < __c2;}
409
410    _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14
411    int              compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
412    _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14
413    size_t           length(const char_type* __s) _NOEXCEPT;
414    _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14
415    const char_type* find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT;
416    _LIBCPP_INLINE_VISIBILITY
417    static char_type*       move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
418    _LIBCPP_INLINE_VISIBILITY
419    static char_type*       copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
420    _LIBCPP_INLINE_VISIBILITY
421    static char_type*       assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT;
422
423    static inline _LIBCPP_CONSTEXPR int_type  not_eof(int_type __c) _NOEXCEPT
424        {return eq_int_type(__c, eof()) ? ~eof() : __c;}
425    static inline _LIBCPP_CONSTEXPR char_type to_char_type(int_type __c) _NOEXCEPT
426        {return char_type(__c);}
427    static inline _LIBCPP_CONSTEXPR int_type to_int_type(char_type __c) _NOEXCEPT
428        {return int_type(__c);}
429    static inline _LIBCPP_CONSTEXPR bool eq_int_type(int_type __c1, int_type __c2) _NOEXCEPT
430        {return __c1 == __c2;}
431    static inline _LIBCPP_CONSTEXPR int_type eof() _NOEXCEPT
432        {return int_type(0xFFFF);}
433};
434
435inline _LIBCPP_CONSTEXPR_AFTER_CXX14
436int
437char_traits<char16_t>::compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
438{
439    for (; __n; --__n, ++__s1, ++__s2)
440    {
441        if (lt(*__s1, *__s2))
442            return -1;
443        if (lt(*__s2, *__s1))
444            return 1;
445    }
446    return 0;
447}
448
449inline _LIBCPP_CONSTEXPR_AFTER_CXX14
450size_t
451char_traits<char16_t>::length(const char_type* __s) _NOEXCEPT
452{
453    size_t __len = 0;
454    for (; !eq(*__s, char_type(0)); ++__s)
455        ++__len;
456    return __len;
457}
458
459inline _LIBCPP_CONSTEXPR_AFTER_CXX14
460const char16_t*
461char_traits<char16_t>::find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT
462{
463    for (; __n; --__n)
464    {
465        if (eq(*__s, __a))
466            return __s;
467        ++__s;
468    }
469    return 0;
470}
471
472inline
473char16_t*
474char_traits<char16_t>::move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
475{
476    char_type* __r = __s1;
477    if (__s1 < __s2)
478    {
479        for (; __n; --__n, ++__s1, ++__s2)
480            assign(*__s1, *__s2);
481    }
482    else if (__s2 < __s1)
483    {
484        __s1 += __n;
485        __s2 += __n;
486        for (; __n; --__n)
487            assign(*--__s1, *--__s2);
488    }
489    return __r;
490}
491
492inline
493char16_t*
494char_traits<char16_t>::copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
495{
496    _LIBCPP_ASSERT(__s2 < __s1 || __s2 >= __s1+__n, "char_traits::copy overlapped range");
497    char_type* __r = __s1;
498    for (; __n; --__n, ++__s1, ++__s2)
499        assign(*__s1, *__s2);
500    return __r;
501}
502
503inline
504char16_t*
505char_traits<char16_t>::assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT
506{
507    char_type* __r = __s;
508    for (; __n; --__n, ++__s)
509        assign(*__s, __a);
510    return __r;
511}
512
513template <>
514struct _LIBCPP_TEMPLATE_VIS char_traits<char32_t>
515{
516    typedef char32_t       char_type;
517    typedef uint_least32_t int_type;
518    typedef streamoff      off_type;
519    typedef u32streampos   pos_type;
520    typedef mbstate_t      state_type;
521
522    static inline _LIBCPP_CONSTEXPR_AFTER_CXX14
523    void assign(char_type& __c1, const char_type& __c2) _NOEXCEPT {__c1 = __c2;}
524    static inline _LIBCPP_CONSTEXPR bool eq(char_type __c1, char_type __c2) _NOEXCEPT
525        {return __c1 == __c2;}
526    static inline _LIBCPP_CONSTEXPR bool lt(char_type __c1, char_type __c2) _NOEXCEPT
527        {return __c1 < __c2;}
528
529    _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14
530    int              compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
531    _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14
532    size_t           length(const char_type* __s) _NOEXCEPT;
533    _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14
534    const char_type* find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT;
535    _LIBCPP_INLINE_VISIBILITY
536    static char_type*       move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
537    _LIBCPP_INLINE_VISIBILITY
538    static char_type*       copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
539    _LIBCPP_INLINE_VISIBILITY
540    static char_type*       assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT;
541
542    static inline _LIBCPP_CONSTEXPR int_type  not_eof(int_type __c) _NOEXCEPT
543        {return eq_int_type(__c, eof()) ? ~eof() : __c;}
544    static inline _LIBCPP_CONSTEXPR char_type to_char_type(int_type __c) _NOEXCEPT
545        {return char_type(__c);}
546    static inline _LIBCPP_CONSTEXPR int_type to_int_type(char_type __c) _NOEXCEPT
547        {return int_type(__c);}
548    static inline _LIBCPP_CONSTEXPR bool eq_int_type(int_type __c1, int_type __c2) _NOEXCEPT
549        {return __c1 == __c2;}
550    static inline _LIBCPP_CONSTEXPR int_type eof() _NOEXCEPT
551        {return int_type(0xFFFFFFFF);}
552};
553
554inline _LIBCPP_CONSTEXPR_AFTER_CXX14
555int
556char_traits<char32_t>::compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
557{
558    for (; __n; --__n, ++__s1, ++__s2)
559    {
560        if (lt(*__s1, *__s2))
561            return -1;
562        if (lt(*__s2, *__s1))
563            return 1;
564    }
565    return 0;
566}
567
568inline _LIBCPP_CONSTEXPR_AFTER_CXX14
569size_t
570char_traits<char32_t>::length(const char_type* __s) _NOEXCEPT
571{
572    size_t __len = 0;
573    for (; !eq(*__s, char_type(0)); ++__s)
574        ++__len;
575    return __len;
576}
577
578inline _LIBCPP_CONSTEXPR_AFTER_CXX14
579const char32_t*
580char_traits<char32_t>::find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT
581{
582    for (; __n; --__n)
583    {
584        if (eq(*__s, __a))
585            return __s;
586        ++__s;
587    }
588    return 0;
589}
590
591inline
592char32_t*
593char_traits<char32_t>::move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
594{
595    char_type* __r = __s1;
596    if (__s1 < __s2)
597    {
598        for (; __n; --__n, ++__s1, ++__s2)
599            assign(*__s1, *__s2);
600    }
601    else if (__s2 < __s1)
602    {
603        __s1 += __n;
604        __s2 += __n;
605        for (; __n; --__n)
606            assign(*--__s1, *--__s2);
607    }
608    return __r;
609}
610
611inline
612char32_t*
613char_traits<char32_t>::copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
614{
615    _LIBCPP_ASSERT(__s2 < __s1 || __s2 >= __s1+__n, "char_traits::copy overlapped range");
616    char_type* __r = __s1;
617    for (; __n; --__n, ++__s1, ++__s2)
618        assign(*__s1, *__s2);
619    return __r;
620}
621
622inline
623char32_t*
624char_traits<char32_t>::assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT
625{
626    char_type* __r = __s;
627    for (; __n; --__n, ++__s)
628        assign(*__s, __a);
629    return __r;
630}
631
632#endif  // _LIBCPP_HAS_NO_UNICODE_CHARS
633
634// helper fns for basic_string and string_view
635
636// __str_find
637template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
638inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
639__str_find(const _CharT *__p, _SizeT __sz,
640             _CharT __c, _SizeT __pos) _NOEXCEPT
641{
642    if (__pos >= __sz)
643        return __npos;
644    const _CharT* __r = _Traits::find(__p + __pos, __sz - __pos, __c);
645    if (__r == 0)
646        return __npos;
647    return static_cast<_SizeT>(__r - __p);
648}
649
650template <class _CharT, class _Traits>
651inline _LIBCPP_CONSTEXPR_AFTER_CXX11 const _CharT *
652__search_substring(const _CharT *__first1, const _CharT *__last1,
653                   const _CharT *__first2, const _CharT *__last2) {
654  // Take advantage of knowing source and pattern lengths.
655  // Stop short when source is smaller than pattern.
656  const ptrdiff_t __len2 = __last2 - __first2;
657  if (__len2 == 0)
658    return __first1;
659
660  ptrdiff_t __len1 = __last1 - __first1;
661  if (__len1 < __len2)
662    return __last1;
663
664  // First element of __first2 is loop invariant.
665  _CharT __f2 = *__first2;
666  while (true) {
667    __len1 = __last1 - __first1;
668    // Check whether __first1 still has at least __len2 bytes.
669    if (__len1 < __len2)
670      return __last1;
671
672    // Find __f2 the first byte matching in __first1.
673    __first1 = _Traits::find(__first1, __len1 - __len2 + 1, __f2);
674    if (__first1 == 0)
675      return __last1;
676
677    // It is faster to compare from the first byte of __first1 even if we
678    // already know that it matches the first byte of __first2: this is because
679    // __first2 is most likely aligned, as it is user's "pattern" string, and
680    // __first1 + 1 is most likely not aligned, as the match is in the middle of
681    // the string.
682    if (_Traits::compare(__first1, __first2, __len2) == 0)
683      return __first1;
684
685    ++__first1;
686  }
687}
688
689template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
690inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
691__str_find(const _CharT *__p, _SizeT __sz,
692       const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT
693{
694    if (__pos > __sz)
695        return __npos;
696
697    if (__n == 0) // There is nothing to search, just return __pos.
698        return __pos;
699
700    const _CharT *__r = __search_substring<_CharT, _Traits>(
701        __p + __pos, __p + __sz, __s, __s + __n);
702
703    if (__r == __p + __sz)
704        return __npos;
705    return static_cast<_SizeT>(__r - __p);
706}
707
708
709// __str_rfind
710
711template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
712inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
713__str_rfind(const _CharT *__p, _SizeT __sz,
714              _CharT __c, _SizeT __pos) _NOEXCEPT
715{
716    if (__sz < 1)
717        return __npos;
718    if (__pos < __sz)
719        ++__pos;
720    else
721        __pos = __sz;
722    for (const _CharT* __ps = __p + __pos; __ps != __p;)
723    {
724        if (_Traits::eq(*--__ps, __c))
725            return static_cast<_SizeT>(__ps - __p);
726    }
727    return __npos;
728}
729
730template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
731inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
732__str_rfind(const _CharT *__p, _SizeT __sz,
733        const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT
734{
735    __pos = _VSTD::min(__pos, __sz);
736    if (__n < __sz - __pos)
737        __pos += __n;
738    else
739        __pos = __sz;
740    const _CharT* __r = _VSTD::__find_end(
741                  __p, __p + __pos, __s, __s + __n, _Traits::eq,
742                        random_access_iterator_tag(), random_access_iterator_tag());
743    if (__n > 0 && __r == __p + __pos)
744        return __npos;
745    return static_cast<_SizeT>(__r - __p);
746}
747
748// __str_find_first_of
749template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
750inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
751__str_find_first_of(const _CharT *__p, _SizeT __sz,
752                const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT
753{
754    if (__pos >= __sz || __n == 0)
755        return __npos;
756    const _CharT* __r = _VSTD::__find_first_of_ce
757        (__p + __pos, __p + __sz, __s, __s + __n, _Traits::eq );
758    if (__r == __p + __sz)
759        return __npos;
760    return static_cast<_SizeT>(__r - __p);
761}
762
763
764// __str_find_last_of
765template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
766inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
767__str_find_last_of(const _CharT *__p, _SizeT __sz,
768               const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT
769    {
770    if (__n != 0)
771    {
772        if (__pos < __sz)
773            ++__pos;
774        else
775            __pos = __sz;
776        for (const _CharT* __ps = __p + __pos; __ps != __p;)
777        {
778            const _CharT* __r = _Traits::find(__s, __n, *--__ps);
779            if (__r)
780                return static_cast<_SizeT>(__ps - __p);
781        }
782    }
783    return __npos;
784}
785
786
787// __str_find_first_not_of
788template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
789inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
790__str_find_first_not_of(const _CharT *__p, _SizeT __sz,
791                    const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT
792{
793    if (__pos < __sz)
794    {
795        const _CharT* __pe = __p + __sz;
796        for (const _CharT* __ps = __p + __pos; __ps != __pe; ++__ps)
797            if (_Traits::find(__s, __n, *__ps) == 0)
798                return static_cast<_SizeT>(__ps - __p);
799    }
800    return __npos;
801}
802
803
804template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
805inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
806__str_find_first_not_of(const _CharT *__p, _SizeT __sz,
807                          _CharT __c, _SizeT __pos) _NOEXCEPT
808{
809    if (__pos < __sz)
810    {
811        const _CharT* __pe = __p + __sz;
812        for (const _CharT* __ps = __p + __pos; __ps != __pe; ++__ps)
813            if (!_Traits::eq(*__ps, __c))
814                return static_cast<_SizeT>(__ps - __p);
815    }
816    return __npos;
817}
818
819
820// __str_find_last_not_of
821template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
822inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
823__str_find_last_not_of(const _CharT *__p, _SizeT __sz,
824                   const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT
825{
826    if (__pos < __sz)
827        ++__pos;
828    else
829        __pos = __sz;
830    for (const _CharT* __ps = __p + __pos; __ps != __p;)
831        if (_Traits::find(__s, __n, *--__ps) == 0)
832            return static_cast<_SizeT>(__ps - __p);
833    return __npos;
834}
835
836
837template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
838inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
839__str_find_last_not_of(const _CharT *__p, _SizeT __sz,
840                         _CharT __c, _SizeT __pos) _NOEXCEPT
841{
842    if (__pos < __sz)
843        ++__pos;
844    else
845        __pos = __sz;
846    for (const _CharT* __ps = __p + __pos; __ps != __p;)
847        if (!_Traits::eq(*--__ps, __c))
848            return static_cast<_SizeT>(__ps - __p);
849    return __npos;
850}
851
852template<class _Ptr>
853inline _LIBCPP_INLINE_VISIBILITY
854size_t __do_string_hash(_Ptr __p, _Ptr __e)
855{
856    typedef typename iterator_traits<_Ptr>::value_type value_type;
857    return __murmur2_or_cityhash<size_t>()(__p, (__e-__p)*sizeof(value_type));
858}
859
860template <class _CharT, class _Iter, class _Traits=char_traits<_CharT> >
861struct __quoted_output_proxy
862{
863    _Iter  __first;
864    _Iter  __last;
865    _CharT  __delim;
866    _CharT  __escape;
867
868    __quoted_output_proxy(_Iter __f, _Iter __l, _CharT __d, _CharT __e)
869    : __first(__f), __last(__l), __delim(__d), __escape(__e) {}
870    //  This would be a nice place for a string_ref
871};
872
873_LIBCPP_END_NAMESPACE_STD
874
875_LIBCPP_POP_MACROS
876
877#endif  // _LIBCPP___STRING
878