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