1// -*- C++ -*-
2//===-------------------------- __string ----------------------------------===//
3//
4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5// See https://llvm.org/LICENSE.txt for license information.
6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7//
8//===----------------------------------------------------------------------===//
9
10#ifndef _LIBCPP___STRING
11#define _LIBCPP___STRING
12
13/*
14 string synopsis
15
16namespace std
17{
18
19template <class charT>
20struct char_traits
21{
22 typedef charT char_type;
23 typedef ... int_type;
24 typedef streamoff off_type;
25 typedef streampos pos_type;
26 typedef mbstate_t state_type;
27
28 static constexpr void assign(char_type& c1, const char_type& c2) noexcept;
29 static constexpr bool eq(char_type c1, char_type c2) noexcept;
30 static constexpr bool lt(char_type c1, char_type c2) noexcept;
31
32 static constexpr int compare(const char_type* s1, const char_type* s2, size_t n);
33 static constexpr size_t length(const char_type* s);
34 static constexpr const char_type*
35 find(const char_type* s, size_t n, const char_type& a);
36 static char_type* move(char_type* s1, const char_type* s2, size_t n);
37 static char_type* copy(char_type* s1, const char_type* s2, size_t n);
38 static char_type* assign(char_type* s, size_t n, char_type a);
39
40 static constexpr int_type not_eof(int_type c) noexcept;
41 static constexpr char_type to_char_type(int_type c) noexcept;
42 static constexpr int_type to_int_type(char_type c) noexcept;
43 static constexpr bool eq_int_type(int_type c1, int_type c2) noexcept;
44 static constexpr int_type eof() noexcept;
45};
46
47template <> struct char_traits<char>;
48template <> struct char_traits<wchar_t>;
49template <> struct char_traits<char8_t>; // c++20
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_NO_HAS_CHAR8_T
393
394template <>
395struct _LIBCPP_TEMPLATE_VIS char_traits<char8_t>
396{
397 typedef char8_t char_type;
398 typedef unsigned int int_type;
399 typedef streamoff off_type;
400 typedef u8streampos pos_type;
401 typedef mbstate_t state_type;
402
403 static inline constexpr void assign(char_type& __c1, const char_type& __c2) noexcept
404 {__c1 = __c2;}
405 static inline constexpr bool eq(char_type __c1, char_type __c2) noexcept
406 {return __c1 == __c2;}
407 static inline constexpr bool lt(char_type __c1, char_type __c2) noexcept
408 {return __c1 < __c2;}
409
410 static constexpr
411 int compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
412
413 static constexpr
414 size_t length(const char_type* __s) _NOEXCEPT;
415
416 _LIBCPP_INLINE_VISIBILITY static constexpr
417 const char_type* find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT;
418
419 static char_type* move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
420 {return __n == 0 ? __s1 : (char_type*) memmove(__s1, __s2, __n);}
421
422 static char_type* copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
423 {
424 _LIBCPP_ASSERT(__s2 < __s1 || __s2 >= __s1+__n, "char_traits::copy overlapped range");
425 return __n == 0 ? __s1 : (char_type*)memcpy(__s1, __s2, __n);
426 }
427
428 static char_type* assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT
429 {return __n == 0 ? __s : (char_type*)memset(__s, to_int_type(__a), __n);}
430
431 static inline constexpr int_type not_eof(int_type __c) noexcept
432 {return eq_int_type(__c, eof()) ? ~eof() : __c;}
433 static inline constexpr char_type to_char_type(int_type __c) noexcept
434 {return char_type(__c);}
435 static inline constexpr int_type to_int_type(char_type __c) noexcept
436 {return int_type(__c);}
437 static inline constexpr bool eq_int_type(int_type __c1, int_type __c2) noexcept
438 {return __c1 == __c2;}
439 static inline constexpr int_type eof() noexcept
440 {return int_type(EOF);}
441};
442
443// TODO use '__builtin_strlen' if it ever supports char8_t ??
444inline constexpr
445size_t
446char_traits<char8_t>::length(const char_type* __s) _NOEXCEPT
447{
448 size_t __len = 0;
449 for (; !eq(*__s, char_type(0)); ++__s)
450 ++__len;
451 return __len;
452}
453
454inline constexpr
455int
456char_traits<char8_t>::compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
457{
458#if __has_feature(cxx_constexpr_string_builtins)
459 return __builtin_memcmp(__s1, __s2, __n);
460#else
461 for (; __n; --__n, ++__s1, ++__s2)
462 {
463 if (lt(*__s1, *__s2))
464 return -1;
465 if (lt(*__s2, *__s1))
466 return 1;
467 }
468 return 0;
469#endif
470}
471
472// TODO use '__builtin_char_memchr' if it ever supports char8_t ??
473inline constexpr
474const char8_t*
475char_traits<char8_t>::find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT
476{
477 for (; __n; --__n)
478 {
479 if (eq(*__s, __a))
480 return __s;
481 ++__s;
482 }
483 return 0;
484}
485
486#endif // #_LIBCPP_NO_HAS_CHAR8_T
487
488#ifndef _LIBCPP_HAS_NO_UNICODE_CHARS
489
490template <>
491struct _LIBCPP_TEMPLATE_VIS char_traits<char16_t>
492{
493 typedef char16_t char_type;
494 typedef uint_least16_t int_type;
495 typedef streamoff off_type;
496 typedef u16streampos pos_type;
497 typedef mbstate_t state_type;
498
499 static inline _LIBCPP_CONSTEXPR_AFTER_CXX14
500 void assign(char_type& __c1, const char_type& __c2) _NOEXCEPT {__c1 = __c2;}
501 static inline _LIBCPP_CONSTEXPR bool eq(char_type __c1, char_type __c2) _NOEXCEPT
502 {return __c1 == __c2;}
503 static inline _LIBCPP_CONSTEXPR bool lt(char_type __c1, char_type __c2) _NOEXCEPT
504 {return __c1 < __c2;}
505
506 _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14
507 int compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
508 _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14
509 size_t length(const char_type* __s) _NOEXCEPT;
510 _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14
511 const char_type* find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT;
512 _LIBCPP_INLINE_VISIBILITY
513 static char_type* move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
514 _LIBCPP_INLINE_VISIBILITY
515 static char_type* copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
516 _LIBCPP_INLINE_VISIBILITY
517 static char_type* assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT;
518
519 static inline _LIBCPP_CONSTEXPR int_type not_eof(int_type __c) _NOEXCEPT
520 {return eq_int_type(__c, eof()) ? ~eof() : __c;}
521 static inline _LIBCPP_CONSTEXPR char_type to_char_type(int_type __c) _NOEXCEPT
522 {return char_type(__c);}
523 static inline _LIBCPP_CONSTEXPR int_type to_int_type(char_type __c) _NOEXCEPT
524 {return int_type(__c);}
525 static inline _LIBCPP_CONSTEXPR bool eq_int_type(int_type __c1, int_type __c2) _NOEXCEPT
526 {return __c1 == __c2;}
527 static inline _LIBCPP_CONSTEXPR int_type eof() _NOEXCEPT
528 {return int_type(0xFFFF);}
529};
530
531inline _LIBCPP_CONSTEXPR_AFTER_CXX14
532int
533char_traits<char16_t>::compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
534{
535 for (; __n; --__n, ++__s1, ++__s2)
536 {
537 if (lt(*__s1, *__s2))
538 return -1;
539 if (lt(*__s2, *__s1))
540 return 1;
541 }
542 return 0;
543}
544
545inline _LIBCPP_CONSTEXPR_AFTER_CXX14
546size_t
547char_traits<char16_t>::length(const char_type* __s) _NOEXCEPT
548{
549 size_t __len = 0;
550 for (; !eq(*__s, char_type(0)); ++__s)
551 ++__len;
552 return __len;
553}
554
555inline _LIBCPP_CONSTEXPR_AFTER_CXX14
556const char16_t*
557char_traits<char16_t>::find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT
558{
559 for (; __n; --__n)
560 {
561 if (eq(*__s, __a))
562 return __s;
563 ++__s;
564 }
565 return 0;
566}
567
568inline
569char16_t*
570char_traits<char16_t>::move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
571{
572 char_type* __r = __s1;
573 if (__s1 < __s2)
574 {
575 for (; __n; --__n, ++__s1, ++__s2)
576 assign(*__s1, *__s2);
577 }
578 else if (__s2 < __s1)
579 {
580 __s1 += __n;
581 __s2 += __n;
582 for (; __n; --__n)
583 assign(*--__s1, *--__s2);
584 }
585 return __r;
586}
587
588inline
589char16_t*
590char_traits<char16_t>::copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
591{
592 _LIBCPP_ASSERT(__s2 < __s1 || __s2 >= __s1+__n, "char_traits::copy overlapped range");
593 char_type* __r = __s1;
594 for (; __n; --__n, ++__s1, ++__s2)
595 assign(*__s1, *__s2);
596 return __r;
597}
598
599inline
600char16_t*
601char_traits<char16_t>::assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT
602{
603 char_type* __r = __s;
604 for (; __n; --__n, ++__s)
605 assign(*__s, __a);
606 return __r;
607}
608
609template <>
610struct _LIBCPP_TEMPLATE_VIS char_traits<char32_t>
611{
612 typedef char32_t char_type;
613 typedef uint_least32_t int_type;
614 typedef streamoff off_type;
615 typedef u32streampos pos_type;
616 typedef mbstate_t state_type;
617
618 static inline _LIBCPP_CONSTEXPR_AFTER_CXX14
619 void assign(char_type& __c1, const char_type& __c2) _NOEXCEPT {__c1 = __c2;}
620 static inline _LIBCPP_CONSTEXPR bool eq(char_type __c1, char_type __c2) _NOEXCEPT
621 {return __c1 == __c2;}
622 static inline _LIBCPP_CONSTEXPR bool lt(char_type __c1, char_type __c2) _NOEXCEPT
623 {return __c1 < __c2;}
624
625 _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14
626 int compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
627 _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14
628 size_t length(const char_type* __s) _NOEXCEPT;
629 _LIBCPP_INLINE_VISIBILITY static _LIBCPP_CONSTEXPR_AFTER_CXX14
630 const char_type* find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT;
631 _LIBCPP_INLINE_VISIBILITY
632 static char_type* move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
633 _LIBCPP_INLINE_VISIBILITY
634 static char_type* copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
635 _LIBCPP_INLINE_VISIBILITY
636 static char_type* assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT;
637
638 static inline _LIBCPP_CONSTEXPR int_type not_eof(int_type __c) _NOEXCEPT
639 {return eq_int_type(__c, eof()) ? ~eof() : __c;}
640 static inline _LIBCPP_CONSTEXPR char_type to_char_type(int_type __c) _NOEXCEPT
641 {return char_type(__c);}
642 static inline _LIBCPP_CONSTEXPR int_type to_int_type(char_type __c) _NOEXCEPT
643 {return int_type(__c);}
644 static inline _LIBCPP_CONSTEXPR bool eq_int_type(int_type __c1, int_type __c2) _NOEXCEPT
645 {return __c1 == __c2;}
646 static inline _LIBCPP_CONSTEXPR int_type eof() _NOEXCEPT
647 {return int_type(0xFFFFFFFF);}
648};
649
650inline _LIBCPP_CONSTEXPR_AFTER_CXX14
651int
652char_traits<char32_t>::compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
653{
654 for (; __n; --__n, ++__s1, ++__s2)
655 {
656 if (lt(*__s1, *__s2))
657 return -1;
658 if (lt(*__s2, *__s1))
659 return 1;
660 }
661 return 0;
662}
663
664inline _LIBCPP_CONSTEXPR_AFTER_CXX14
665size_t
666char_traits<char32_t>::length(const char_type* __s) _NOEXCEPT
667{
668 size_t __len = 0;
669 for (; !eq(*__s, char_type(0)); ++__s)
670 ++__len;
671 return __len;
672}
673
674inline _LIBCPP_CONSTEXPR_AFTER_CXX14
675const char32_t*
676char_traits<char32_t>::find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT
677{
678 for (; __n; --__n)
679 {
680 if (eq(*__s, __a))
681 return __s;
682 ++__s;
683 }
684 return 0;
685}
686
687inline
688char32_t*
689char_traits<char32_t>::move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
690{
691 char_type* __r = __s1;
692 if (__s1 < __s2)
693 {
694 for (; __n; --__n, ++__s1, ++__s2)
695 assign(*__s1, *__s2);
696 }
697 else if (__s2 < __s1)
698 {
699 __s1 += __n;
700 __s2 += __n;
701 for (; __n; --__n)
702 assign(*--__s1, *--__s2);
703 }
704 return __r;
705}
706
707inline
708char32_t*
709char_traits<char32_t>::copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
710{
711 _LIBCPP_ASSERT(__s2 < __s1 || __s2 >= __s1+__n, "char_traits::copy overlapped range");
712 char_type* __r = __s1;
713 for (; __n; --__n, ++__s1, ++__s2)
714 assign(*__s1, *__s2);
715 return __r;
716}
717
718inline
719char32_t*
720char_traits<char32_t>::assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT
721{
722 char_type* __r = __s;
723 for (; __n; --__n, ++__s)
724 assign(*__s, __a);
725 return __r;
726}
727
728#endif // _LIBCPP_HAS_NO_UNICODE_CHARS
729
730// helper fns for basic_string and string_view
731
732// __str_find
733template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
734inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
735__str_find(const _CharT *__p, _SizeT __sz,
736 _CharT __c, _SizeT __pos) _NOEXCEPT
737{
738 if (__pos >= __sz)
739 return __npos;
740 const _CharT* __r = _Traits::find(__p + __pos, __sz - __pos, __c);
741 if (__r == 0)
742 return __npos;
743 return static_cast<_SizeT>(__r - __p);
744}
745
746template <class _CharT, class _Traits>
747inline _LIBCPP_CONSTEXPR_AFTER_CXX11 const _CharT *
748__search_substring(const _CharT *__first1, const _CharT *__last1,
749 const _CharT *__first2, const _CharT *__last2) {
750 // Take advantage of knowing source and pattern lengths.
751 // Stop short when source is smaller than pattern.
752 const ptrdiff_t __len2 = __last2 - __first2;
753 if (__len2 == 0)
754 return __first1;
755
756 ptrdiff_t __len1 = __last1 - __first1;
757 if (__len1 < __len2)
758 return __last1;
759
760 // First element of __first2 is loop invariant.
761 _CharT __f2 = *__first2;
762 while (true) {
763 __len1 = __last1 - __first1;
764 // Check whether __first1 still has at least __len2 bytes.
765 if (__len1 < __len2)
766 return __last1;
767
768 // Find __f2 the first byte matching in __first1.
769 __first1 = _Traits::find(__first1, __len1 - __len2 + 1, __f2);
770 if (__first1 == 0)
771 return __last1;
772
773 // It is faster to compare from the first byte of __first1 even if we
774 // already know that it matches the first byte of __first2: this is because
775 // __first2 is most likely aligned, as it is user's "pattern" string, and
776 // __first1 + 1 is most likely not aligned, as the match is in the middle of
777 // the string.
778 if (_Traits::compare(__first1, __first2, __len2) == 0)
779 return __first1;
780
781 ++__first1;
782 }
783}
784
785template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
786inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
787__str_find(const _CharT *__p, _SizeT __sz,
788 const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT
789{
790 if (__pos > __sz)
791 return __npos;
792
793 if (__n == 0) // There is nothing to search, just return __pos.
794 return __pos;
795
796 const _CharT *__r = __search_substring<_CharT, _Traits>(
797 __p + __pos, __p + __sz, __s, __s + __n);
798
799 if (__r == __p + __sz)
800 return __npos;
801 return static_cast<_SizeT>(__r - __p);
802}
803
804
805// __str_rfind
806
807template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
808inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
809__str_rfind(const _CharT *__p, _SizeT __sz,
810 _CharT __c, _SizeT __pos) _NOEXCEPT
811{
812 if (__sz < 1)
813 return __npos;
814 if (__pos < __sz)
815 ++__pos;
816 else
817 __pos = __sz;
818 for (const _CharT* __ps = __p + __pos; __ps != __p;)
819 {
820 if (_Traits::eq(*--__ps, __c))
821 return static_cast<_SizeT>(__ps - __p);
822 }
823 return __npos;
824}
825
826template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
827inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
828__str_rfind(const _CharT *__p, _SizeT __sz,
829 const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT
830{
831 __pos = _VSTD::min(__pos, __sz);
832 if (__n < __sz - __pos)
833 __pos += __n;
834 else
835 __pos = __sz;
836 const _CharT* __r = _VSTD::__find_end(
837 __p, __p + __pos, __s, __s + __n, _Traits::eq,
838 random_access_iterator_tag(), random_access_iterator_tag());
839 if (__n > 0 && __r == __p + __pos)
840 return __npos;
841 return static_cast<_SizeT>(__r - __p);
842}
843
844// __str_find_first_of
845template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
846inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
847__str_find_first_of(const _CharT *__p, _SizeT __sz,
848 const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT
849{
850 if (__pos >= __sz || __n == 0)
851 return __npos;
852 const _CharT* __r = _VSTD::__find_first_of_ce
853 (__p + __pos, __p + __sz, __s, __s + __n, _Traits::eq );
854 if (__r == __p + __sz)
855 return __npos;
856 return static_cast<_SizeT>(__r - __p);
857}
858
859
860// __str_find_last_of
861template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
862inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
863__str_find_last_of(const _CharT *__p, _SizeT __sz,
864 const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT
865 {
866 if (__n != 0)
867 {
868 if (__pos < __sz)
869 ++__pos;
870 else
871 __pos = __sz;
872 for (const _CharT* __ps = __p + __pos; __ps != __p;)
873 {
874 const _CharT* __r = _Traits::find(__s, __n, *--__ps);
875 if (__r)
876 return static_cast<_SizeT>(__ps - __p);
877 }
878 }
879 return __npos;
880}
881
882
883// __str_find_first_not_of
884template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
885inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
886__str_find_first_not_of(const _CharT *__p, _SizeT __sz,
887 const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT
888{
889 if (__pos < __sz)
890 {
891 const _CharT* __pe = __p + __sz;
892 for (const _CharT* __ps = __p + __pos; __ps != __pe; ++__ps)
893 if (_Traits::find(__s, __n, *__ps) == 0)
894 return static_cast<_SizeT>(__ps - __p);
895 }
896 return __npos;
897}
898
899
900template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
901inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
902__str_find_first_not_of(const _CharT *__p, _SizeT __sz,
903 _CharT __c, _SizeT __pos) _NOEXCEPT
904{
905 if (__pos < __sz)
906 {
907 const _CharT* __pe = __p + __sz;
908 for (const _CharT* __ps = __p + __pos; __ps != __pe; ++__ps)
909 if (!_Traits::eq(*__ps, __c))
910 return static_cast<_SizeT>(__ps - __p);
911 }
912 return __npos;
913}
914
915
916// __str_find_last_not_of
917template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
918inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
919__str_find_last_not_of(const _CharT *__p, _SizeT __sz,
920 const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT
921{
922 if (__pos < __sz)
923 ++__pos;
924 else
925 __pos = __sz;
926 for (const _CharT* __ps = __p + __pos; __ps != __p;)
927 if (_Traits::find(__s, __n, *--__ps) == 0)
928 return static_cast<_SizeT>(__ps - __p);
929 return __npos;
930}
931
932
933template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
934inline _SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
935__str_find_last_not_of(const _CharT *__p, _SizeT __sz,
936 _CharT __c, _SizeT __pos) _NOEXCEPT
937{
938 if (__pos < __sz)
939 ++__pos;
940 else
941 __pos = __sz;
942 for (const _CharT* __ps = __p + __pos; __ps != __p;)
943 if (!_Traits::eq(*--__ps, __c))
944 return static_cast<_SizeT>(__ps - __p);
945 return __npos;
946}
947
948template<class _Ptr>
949inline _LIBCPP_INLINE_VISIBILITY
950size_t __do_string_hash(_Ptr __p, _Ptr __e)
951{
952 typedef typename iterator_traits<_Ptr>::value_type value_type;
953 return __murmur2_or_cityhash<size_t>()(__p, (__e-__p)*sizeof(value_type));
954}
955
956template <class _CharT, class _Iter, class _Traits=char_traits<_CharT> >
957struct __quoted_output_proxy
958{
959 _Iter __first;
960 _Iter __last;
961 _CharT __delim;
962 _CharT __escape;
963
964 __quoted_output_proxy(_Iter __f, _Iter __l, _CharT __d, _CharT __e)
965 : __first(__f), __last(__l), __delim(__d), __escape(__e) {}
966 // This would be a nice place for a string_ref
967};
968
969_LIBCPP_END_NAMESPACE_STD
970
971_LIBCPP_POP_MACROS
972
973#endif // _LIBCPP___STRING
974