blob: 75608cea71d9c8e7e7c58510380c2a2a92557652 [file] [log] [blame]
Marshall Clowdf63a6d2016-07-21 05:31:24 +00001// -*- 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
Marshall Clow951035b2017-01-12 04:37:14 +000029 static constexpr void assign(char_type& c1, const char_type& c2) noexcept;
Marshall Clowdf63a6d2016-07-21 05:31:24 +000030 static constexpr bool eq(char_type c1, char_type c2) noexcept;
31 static constexpr bool lt(char_type c1, char_type c2) noexcept;
32
Marshall Clow951035b2017-01-12 04:37:14 +000033 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);
Marshall Clowdf63a6d2016-07-21 05:31:24 +000037 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>
Eric Fiselierb5eb1bf2017-01-04 23:56:00 +000073struct _LIBCPP_TEMPLATE_VIS char_traits
Marshall Clowdf63a6d2016-07-21 05:31:24 +000074{
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
Marshall Clow951035b2017-01-12 04:37:14 +000081 static inline void _LIBCPP_CONSTEXPR_AFTER_CXX14
82 assign(char_type& __c1, const char_type& __c2) _NOEXCEPT {__c1 = __c2;}
Marshall Clowdf63a6d2016-07-21 05:31:24 +000083 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
Marshall Clow951035b2017-01-12 04:37:14 +000088 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);
Marshall Clowdf63a6d2016-07-21 05:31:24 +000094 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>
Marshall Clow951035b2017-01-12 04:37:14 +0000113_LIBCPP_CONSTEXPR_AFTER_CXX14 int
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000114char_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
Marshall Clow951035b2017-01-12 04:37:14 +0000128_LIBCPP_CONSTEXPR_AFTER_CXX14 size_t
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000129char_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
Marshall Clow951035b2017-01-12 04:37:14 +0000139_LIBCPP_CONSTEXPR_AFTER_CXX14 const _CharT*
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000140char_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 <>
Eric Fiselierb5eb1bf2017-01-04 23:56:00 +0000197struct _LIBCPP_TEMPLATE_VIS char_traits<char>
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000198{
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
Marshall Clow951035b2017-01-12 04:37:14 +0000205 static inline _LIBCPP_CONSTEXPR_AFTER_CXX14
206 void assign(char_type& __c1, const char_type& __c2) _NOEXCEPT {__c1 = __c2;}
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000207 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
Marshall Clowaa32f162017-01-12 05:40:58 +0000212 static _LIBCPP_CONSTEXPR_AFTER_CXX14
213 int compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
Marshall Clow951035b2017-01-12 04:37:14 +0000214 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;
Marshall Clow36097db2016-07-28 04:52:02 +0000218 static inline char_type* move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000219 {return __n == 0 ? __s1 : (char_type*) memmove(__s1, __s2, __n);}
Marshall Clow36097db2016-07-28 04:52:02 +0000220 static inline char_type* copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000221 {
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 }
Marshall Clow36097db2016-07-28 04:52:02 +0000225 static inline char_type* assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000226 {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
Marshall Clow951035b2017-01-12 04:37:14 +0000240inline _LIBCPP_CONSTEXPR_AFTER_CXX14
Marshall Clowaa32f162017-01-12 05:40:58 +0000241int
242char_traits<char>::compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
243{
244 if (__n == 0)
245 return 0;
Marshall Clowb344c362017-01-26 06:58:29 +0000246#if __has_feature(cxx_constexpr_string_builtins)
Marshall Clowaa32f162017-01-12 05:40:58 +0000247 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
Marshall Clow951035b2017-01-12 04:37:14 +0000263const 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;
Marshall Clowb344c362017-01-26 06:58:29 +0000268#if __has_feature(cxx_constexpr_string_builtins)
269 return __builtin_char_memchr(__s, to_int_type(__a), __n);
270#elif _LIBCPP_STD_VER <= 14
Marshall Clow951035b2017-01-12 04:37:14 +0000271 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
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000284// char_traits<wchar_t>
285
286template <>
Eric Fiselierb5eb1bf2017-01-04 23:56:00 +0000287struct _LIBCPP_TEMPLATE_VIS char_traits<wchar_t>
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000288{
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
Marshall Clow951035b2017-01-12 04:37:14 +0000295 static inline _LIBCPP_CONSTEXPR_AFTER_CXX14
296 void assign(char_type& __c1, const char_type& __c2) _NOEXCEPT {__c1 = __c2;}
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000297 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
Marshall Clow951035b2017-01-12 04:37:14 +0000302 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;
Marshall Clow36097db2016-07-28 04:52:02 +0000308 static inline char_type* move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000309 {return __n == 0 ? __s1 : (char_type*)wmemmove(__s1, __s2, __n);}
Marshall Clow36097db2016-07-28 04:52:02 +0000310 static inline char_type* copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000311 {
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 }
Marshall Clow36097db2016-07-28 04:52:02 +0000315 static inline char_type* assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000316 {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
Marshall Clow951035b2017-01-12 04:37:14 +0000330inline _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;
Marshall Clowb344c362017-01-26 06:58:29 +0000336#if __has_feature(cxx_constexpr_string_builtins)
Marshall Clow951035b2017-01-12 04:37:14 +0000337 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{
Marshall Clowb344c362017-01-26 06:58:29 +0000356#if __has_feature(cxx_constexpr_string_builtins)
Marshall Clow951035b2017-01-12 04:37:14 +0000357 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;
Marshall Clowb344c362017-01-26 06:58:29 +0000374#if __has_feature(cxx_constexpr_string_builtins)
Marshall Clow951035b2017-01-12 04:37:14 +0000375 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
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000390#ifndef _LIBCPP_HAS_NO_UNICODE_CHARS
391
392template <>
Eric Fiselierb5eb1bf2017-01-04 23:56:00 +0000393struct _LIBCPP_TEMPLATE_VIS char_traits<char16_t>
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000394{
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
Marshall Clow951035b2017-01-12 04:37:14 +0000401 static inline _LIBCPP_CONSTEXPR_AFTER_CXX14
402 void assign(char_type& __c1, const char_type& __c2) _NOEXCEPT {__c1 = __c2;}
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000403 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
Marshall Clow951035b2017-01-12 04:37:14 +0000408 _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;
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000414 _LIBCPP_INLINE_VISIBILITY
Marshall Clow36097db2016-07-28 04:52:02 +0000415 static char_type* move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000416 _LIBCPP_INLINE_VISIBILITY
Marshall Clow36097db2016-07-28 04:52:02 +0000417 static char_type* copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000418 _LIBCPP_INLINE_VISIBILITY
Marshall Clow36097db2016-07-28 04:52:02 +0000419 static char_type* assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT;
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000420
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
Marshall Clow951035b2017-01-12 04:37:14 +0000433inline _LIBCPP_CONSTEXPR_AFTER_CXX14
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000434int
Marshall Clow36097db2016-07-28 04:52:02 +0000435char_traits<char16_t>::compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000436{
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
Marshall Clow951035b2017-01-12 04:37:14 +0000447inline _LIBCPP_CONSTEXPR_AFTER_CXX14
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000448size_t
Marshall Clow36097db2016-07-28 04:52:02 +0000449char_traits<char16_t>::length(const char_type* __s) _NOEXCEPT
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000450{
451 size_t __len = 0;
452 for (; !eq(*__s, char_type(0)); ++__s)
453 ++__len;
454 return __len;
455}
456
Marshall Clow951035b2017-01-12 04:37:14 +0000457inline _LIBCPP_CONSTEXPR_AFTER_CXX14
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000458const char16_t*
Marshall Clow36097db2016-07-28 04:52:02 +0000459char_traits<char16_t>::find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000460{
461 for (; __n; --__n)
462 {
463 if (eq(*__s, __a))
464 return __s;
465 ++__s;
466 }
467 return 0;
468}
469
470inline
471char16_t*
Marshall Clow36097db2016-07-28 04:52:02 +0000472char_traits<char16_t>::move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000473{
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*
Marshall Clow36097db2016-07-28 04:52:02 +0000492char_traits<char16_t>::copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000493{
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*
Marshall Clow36097db2016-07-28 04:52:02 +0000503char_traits<char16_t>::assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000504{
505 char_type* __r = __s;
506 for (; __n; --__n, ++__s)
507 assign(*__s, __a);
508 return __r;
509}
510
511template <>
Eric Fiselierb5eb1bf2017-01-04 23:56:00 +0000512struct _LIBCPP_TEMPLATE_VIS char_traits<char32_t>
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000513{
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
Marshall Clow951035b2017-01-12 04:37:14 +0000520 static inline _LIBCPP_CONSTEXPR_AFTER_CXX14
521 void assign(char_type& __c1, const char_type& __c2) _NOEXCEPT {__c1 = __c2;}
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000522 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
Marshall Clow951035b2017-01-12 04:37:14 +0000527 _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;
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000533 _LIBCPP_INLINE_VISIBILITY
Marshall Clow36097db2016-07-28 04:52:02 +0000534 static char_type* move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000535 _LIBCPP_INLINE_VISIBILITY
Marshall Clow36097db2016-07-28 04:52:02 +0000536 static char_type* copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT;
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000537 _LIBCPP_INLINE_VISIBILITY
Marshall Clow36097db2016-07-28 04:52:02 +0000538 static char_type* assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT;
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000539
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
Marshall Clow951035b2017-01-12 04:37:14 +0000552inline _LIBCPP_CONSTEXPR_AFTER_CXX14
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000553int
Marshall Clow36097db2016-07-28 04:52:02 +0000554char_traits<char32_t>::compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000555{
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
Marshall Clow951035b2017-01-12 04:37:14 +0000566inline _LIBCPP_CONSTEXPR_AFTER_CXX14
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000567size_t
Marshall Clow36097db2016-07-28 04:52:02 +0000568char_traits<char32_t>::length(const char_type* __s) _NOEXCEPT
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000569{
570 size_t __len = 0;
571 for (; !eq(*__s, char_type(0)); ++__s)
572 ++__len;
573 return __len;
574}
575
Marshall Clow951035b2017-01-12 04:37:14 +0000576inline _LIBCPP_CONSTEXPR_AFTER_CXX14
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000577const char32_t*
Marshall Clow36097db2016-07-28 04:52:02 +0000578char_traits<char32_t>::find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000579{
580 for (; __n; --__n)
581 {
582 if (eq(*__s, __a))
583 return __s;
584 ++__s;
585 }
586 return 0;
587}
588
589inline
590char32_t*
Marshall Clow36097db2016-07-28 04:52:02 +0000591char_traits<char32_t>::move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000592{
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*
Marshall Clow36097db2016-07-28 04:52:02 +0000611char_traits<char32_t>::copy(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000612{
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*
Marshall Clow36097db2016-07-28 04:52:02 +0000622char_traits<char32_t>::assign(char_type* __s, size_t __n, char_type __a) _NOEXCEPT
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000623{
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
Sebastian Pop65115202016-12-30 18:01:36 +0000648template <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
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000687template<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{
Sebastian Pop65115202016-12-30 18:01:36 +0000692 if (__pos > __sz)
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000693 return __npos;
Sebastian Pop65115202016-12-30 18:01:36 +0000694
695 if (__n == 0) // There is nothing to search, just return __pos.
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000696 return __pos;
Sebastian Pop65115202016-12-30 18:01:36 +0000697
698 const _CharT *__r = __search_substring<_CharT, _Traits>(
699 __p + __pos, __p + __sz, __s, __s + __n);
700
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000701 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>
Eric Fiselier1b57fa82016-09-15 22:27:07 +0000851inline _LIBCPP_INLINE_VISIBILITY
852size_t __do_string_hash(_Ptr __p, _Ptr __e)
Marshall Clowdf63a6d2016-07-21 05:31:24 +0000853{
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