1 // Like the compiler, the static analyzer treats some functions differently if 2 // they come from a system header -- for example, it is assumed that system 3 // functions do not arbitrarily free() their parameters, and that some bugs 4 // found in system headers cannot be fixed by the user and should be 5 // suppressed. 6 #pragma clang system_header 7 8 typedef unsigned char uint8_t; 9 10 typedef __typeof__(sizeof(int)) size_t; 11 typedef __typeof__((char*)0-(char*)0) ptrdiff_t; 12 void *memmove(void *s1, const void *s2, size_t n); 13 14 namespace std { 15 typedef size_t size_type; 16 #if __cplusplus >= 201103L 17 using nullptr_t = decltype(nullptr); 18 #endif 19 } 20 21 namespace std { 22 struct input_iterator_tag { }; 23 struct output_iterator_tag { }; 24 struct forward_iterator_tag : public input_iterator_tag { }; 25 struct bidirectional_iterator_tag : public forward_iterator_tag { }; 26 struct random_access_iterator_tag : public bidirectional_iterator_tag { }; 27 28 template <typename Iterator> struct iterator_traits { 29 typedef typename Iterator::difference_type difference_type; 30 typedef typename Iterator::value_type value_type; 31 typedef typename Iterator::pointer pointer; 32 typedef typename Iterator::reference reference; 33 typedef typename Iterator::iterator_category iterator_category; 34 }; 35 } 36 37 template <typename T, typename Ptr, typename Ref> struct __vector_iterator { 38 typedef __vector_iterator<T, T *, T &> iterator; 39 typedef __vector_iterator<T, const T *, const T &> const_iterator; 40 41 typedef ptrdiff_t difference_type; 42 typedef T value_type; 43 typedef Ptr pointer; 44 typedef Ref reference; 45 typedef std::random_access_iterator_tag iterator_category; 46 ptr__vector_iterator47 __vector_iterator(const Ptr p = 0) : ptr(p) {} __vector_iterator__vector_iterator48 __vector_iterator(const iterator &rhs): ptr(rhs.base()) {} 49 __vector_iterator<T, Ptr, Ref>& operator++() { ++ ptr; return *this; } 50 __vector_iterator<T, Ptr, Ref> operator++(int) { 51 auto tmp = *this; 52 ++ ptr; 53 return tmp; 54 } 55 __vector_iterator<T, Ptr, Ref> operator--() { -- ptr; return *this; } 56 __vector_iterator<T, Ptr, Ref> operator--(int) { 57 auto tmp = *this; -- ptr; 58 return tmp; 59 } 60 __vector_iterator<T, Ptr, Ref> operator+(difference_type n) { 61 return ptr + n; 62 } 63 friend __vector_iterator<T, Ptr, Ref> operator+( 64 difference_type n, 65 const __vector_iterator<T, Ptr, Ref> &iter) { 66 return n + iter.ptr; 67 } 68 __vector_iterator<T, Ptr, Ref> operator-(difference_type n) { 69 return ptr - n; 70 } 71 __vector_iterator<T, Ptr, Ref> operator+=(difference_type n) { 72 return ptr += n; 73 } 74 __vector_iterator<T, Ptr, Ref> operator-=(difference_type n) { 75 return ptr -= n; 76 } 77 78 template<typename U, typename Ptr2, typename Ref2> 79 difference_type operator-(const __vector_iterator<U, Ptr2, Ref2> &rhs); 80 81 Ref operator*() const { return *ptr; } 82 Ptr operator->() const { return ptr; } 83 84 Ref operator[](difference_type n) { 85 return *(ptr+n); 86 } 87 88 bool operator==(const iterator &rhs) const { return ptr == rhs.ptr; } 89 bool operator==(const const_iterator &rhs) const { return ptr == rhs.ptr; } 90 91 bool operator!=(const iterator &rhs) const { return ptr != rhs.ptr; } 92 bool operator!=(const const_iterator &rhs) const { return ptr != rhs.ptr; } 93 base__vector_iterator94 const Ptr& base() const { return ptr; } 95 96 private: 97 Ptr ptr; 98 }; 99 100 template <typename T, typename Ptr, typename Ref> struct __deque_iterator { 101 typedef __deque_iterator<T, T *, T &> iterator; 102 typedef __deque_iterator<T, const T *, const T &> const_iterator; 103 104 typedef ptrdiff_t difference_type; 105 typedef T value_type; 106 typedef Ptr pointer; 107 typedef Ref reference; 108 typedef std::random_access_iterator_tag iterator_category; 109 ptr__deque_iterator110 __deque_iterator(const Ptr p = 0) : ptr(p) {} __deque_iterator__deque_iterator111 __deque_iterator(const iterator &rhs): ptr(rhs.base()) {} 112 __deque_iterator<T, Ptr, Ref>& operator++() { ++ ptr; return *this; } 113 __deque_iterator<T, Ptr, Ref> operator++(int) { 114 auto tmp = *this; 115 ++ ptr; 116 return tmp; 117 } 118 __deque_iterator<T, Ptr, Ref> operator--() { -- ptr; return *this; } 119 __deque_iterator<T, Ptr, Ref> operator--(int) { 120 auto tmp = *this; -- ptr; 121 return tmp; 122 } 123 __deque_iterator<T, Ptr, Ref> operator+(difference_type n) { 124 return ptr + n; 125 } 126 friend __deque_iterator<T, Ptr, Ref> operator+( 127 difference_type n, 128 const __deque_iterator<T, Ptr, Ref> &iter) { 129 return n + iter.ptr; 130 } 131 __deque_iterator<T, Ptr, Ref> operator-(difference_type n) { 132 return ptr - n; 133 } 134 __deque_iterator<T, Ptr, Ref> operator+=(difference_type n) { 135 return ptr += n; 136 } 137 __deque_iterator<T, Ptr, Ref> operator-=(difference_type n) { 138 return ptr -= n; 139 } 140 141 Ref operator*() const { return *ptr; } 142 Ptr operator->() const { return ptr; } 143 144 Ref operator[](difference_type n) { 145 return *(ptr+n); 146 } 147 148 bool operator==(const iterator &rhs) const { return ptr == rhs.ptr; } 149 bool operator==(const const_iterator &rhs) const { return ptr == rhs.ptr; } 150 151 bool operator!=(const iterator &rhs) const { return ptr != rhs.ptr; } 152 bool operator!=(const const_iterator &rhs) const { return ptr != rhs.ptr; } 153 base__deque_iterator154 const Ptr& base() const { return ptr; } 155 156 private: 157 Ptr ptr; 158 }; 159 160 template <typename T, typename Ptr, typename Ref> struct __list_iterator { 161 typedef __list_iterator<T, __typeof__(T::data) *, __typeof__(T::data) &> iterator; 162 typedef __list_iterator<T, const __typeof__(T::data) *, const __typeof__(T::data) &> const_iterator; 163 164 typedef ptrdiff_t difference_type; 165 typedef T value_type; 166 typedef Ptr pointer; 167 typedef Ref reference; 168 typedef std::bidirectional_iterator_tag iterator_category; 169 item__list_iterator170 __list_iterator(T* it = 0) : item(it) {} __list_iterator__list_iterator171 __list_iterator(const iterator &rhs): item(rhs.item) {} 172 __list_iterator<T, Ptr, Ref>& operator++() { item = item->next; return *this; } 173 __list_iterator<T, Ptr, Ref> operator++(int) { 174 auto tmp = *this; 175 item = item->next; 176 return tmp; 177 } 178 __list_iterator<T, Ptr, Ref> operator--() { item = item->prev; return *this; } 179 __list_iterator<T, Ptr, Ref> operator--(int) { 180 auto tmp = *this; 181 item = item->prev; 182 return tmp; 183 } 184 185 Ref operator*() const { return item->data; } 186 Ptr operator->() const { return &item->data; } 187 188 bool operator==(const iterator &rhs) const { return item == rhs->item; } 189 bool operator==(const const_iterator &rhs) const { return item == rhs->item; } 190 191 bool operator!=(const iterator &rhs) const { return item != rhs->item; } 192 bool operator!=(const const_iterator &rhs) const { return item != rhs->item; } 193 base__list_iterator194 const T* &base() const { return item; } 195 196 template <typename UT, typename UPtr, typename URef> 197 friend struct __list_iterator; 198 199 private: 200 T* item; 201 }; 202 203 template <typename T, typename Ptr, typename Ref> struct __fwdl_iterator { 204 typedef __fwdl_iterator<T, __typeof__(T::data) *, __typeof__(T::data) &> iterator; 205 typedef __fwdl_iterator<T, const __typeof__(T::data) *, const __typeof__(T::data) &> const_iterator; 206 207 typedef ptrdiff_t difference_type; 208 typedef T value_type; 209 typedef Ptr pointer; 210 typedef Ref reference; 211 typedef std::forward_iterator_tag iterator_category; 212 item__fwdl_iterator213 __fwdl_iterator(T* it = 0) : item(it) {} __fwdl_iterator__fwdl_iterator214 __fwdl_iterator(const iterator &rhs): item(rhs.item) {} 215 __fwdl_iterator<T, Ptr, Ref>& operator++() { item = item->next; return *this; } 216 __fwdl_iterator<T, Ptr, Ref> operator++(int) { 217 auto tmp = *this; 218 item = item->next; 219 return tmp; 220 } 221 Ref operator*() const { return item->data; } 222 Ptr operator->() const { return &item->data; } 223 224 bool operator==(const iterator &rhs) const { return item == rhs->item; } 225 bool operator==(const const_iterator &rhs) const { return item == rhs->item; } 226 227 bool operator!=(const iterator &rhs) const { return item != rhs->item; } 228 bool operator!=(const const_iterator &rhs) const { return item != rhs->item; } 229 base__fwdl_iterator230 const T* &base() const { return item; } 231 232 template <typename UT, typename UPtr, typename URef> 233 friend struct __fwdl_iterator; 234 235 private: 236 T* item; 237 }; 238 239 namespace std { 240 template <class T1, class T2> 241 struct pair { 242 T1 first; 243 T2 second; 244 pairpair245 pair() : first(), second() {} pairpair246 pair(const T1 &a, const T2 &b) : first(a), second(b) {} 247 248 template<class U1, class U2> pairpair249 pair(const pair<U1, U2> &other) : first(other.first), 250 second(other.second) {} 251 }; 252 253 typedef __typeof__(sizeof(int)) size_t; 254 255 template <class T> class initializer_list; 256 257 template< class T > struct remove_reference {typedef T type;}; 258 template< class T > struct remove_reference<T&> {typedef T type;}; 259 template< class T > struct remove_reference<T&&> {typedef T type;}; 260 261 template<class T> 262 typename remove_reference<T>::type&& move(T&& a) { 263 typedef typename remove_reference<T>::type&& RvalRef; 264 return static_cast<RvalRef>(a); 265 } 266 267 template <class T> 268 void swap(T &a, T &b) { 269 T c(std::move(a)); 270 a = std::move(b); 271 b = std::move(c); 272 } 273 274 template<typename T> 275 class vector { 276 T *_start; 277 T *_finish; 278 T *_end_of_storage; 279 280 public: 281 typedef T value_type; 282 typedef size_t size_type; 283 typedef __vector_iterator<T, T *, T &> iterator; 284 typedef __vector_iterator<T, const T *, const T &> const_iterator; 285 286 vector() : _start(0), _finish(0), _end_of_storage(0) {} 287 template <typename InputIterator> 288 vector(InputIterator first, InputIterator last); 289 vector(const vector &other); 290 vector(vector &&other); 291 ~vector(); 292 293 size_t size() const { 294 return size_t(_finish - _start); 295 } 296 297 vector& operator=(const vector &other); 298 vector& operator=(vector &&other); 299 vector& operator=(std::initializer_list<T> ilist); 300 301 void assign(size_type count, const T &value); 302 template <typename InputIterator > 303 void assign(InputIterator first, InputIterator last); 304 void assign(std::initializer_list<T> ilist); 305 306 void clear(); 307 308 void push_back(const T &value); 309 void push_back(T &&value); 310 template<class... Args> 311 void emplace_back(Args&&... args); 312 void pop_back(); 313 314 iterator insert(const_iterator position, const value_type &val); 315 iterator insert(const_iterator position, size_type n, 316 const value_type &val); 317 template <typename InputIterator> 318 iterator insert(const_iterator position, InputIterator first, 319 InputIterator last); 320 iterator insert(const_iterator position, value_type &&val); 321 iterator insert(const_iterator position, initializer_list<value_type> il); 322 323 template <class... Args> 324 iterator emplace(const_iterator position, Args&&... args); 325 326 iterator erase(const_iterator position); 327 iterator erase(const_iterator first, const_iterator last); 328 329 T &operator[](size_t n) { 330 return _start[n]; 331 } 332 333 const T &operator[](size_t n) const { 334 return _start[n]; 335 } 336 337 iterator begin() { return iterator(_start); } 338 const_iterator begin() const { return const_iterator(_start); } 339 const_iterator cbegin() const { return const_iterator(_start); } 340 iterator end() { return iterator(_finish); } 341 const_iterator end() const { return const_iterator(_finish); } 342 const_iterator cend() const { return const_iterator(_finish); } 343 T& front() { return *begin(); } 344 const T& front() const { return *begin(); } 345 T& back() { return *(end() - 1); } 346 const T& back() const { return *(end() - 1); } 347 }; 348 349 template<typename T> 350 class list { 351 struct __item { 352 T data; 353 __item *prev, *next; 354 } *_start, *_finish; 355 356 public: 357 typedef T value_type; 358 typedef size_t size_type; 359 typedef __list_iterator<__item, T *, T &> iterator; 360 typedef __list_iterator<__item, const T *, const T &> const_iterator; 361 362 list() : _start(0), _finish(0) {} 363 template <typename InputIterator> 364 list(InputIterator first, InputIterator last); 365 list(const list &other); 366 list(list &&other); 367 ~list(); 368 369 list& operator=(const list &other); 370 list& operator=(list &&other); 371 list& operator=(std::initializer_list<T> ilist); 372 373 void assign(size_type count, const T &value); 374 template <typename InputIterator > 375 void assign(InputIterator first, InputIterator last); 376 void assign(std::initializer_list<T> ilist); 377 378 void clear(); 379 380 void push_back(const T &value); 381 void push_back(T &&value); 382 template<class... Args> 383 void emplace_back(Args&&... args); 384 void pop_back(); 385 386 void push_front(const T &value); 387 void push_front(T &&value); 388 template<class... Args> 389 void emplace_front(Args&&... args); 390 void pop_front(); 391 392 iterator insert(const_iterator position, const value_type &val); 393 iterator insert(const_iterator position, size_type n, 394 const value_type &val); 395 template <typename InputIterator> 396 iterator insert(const_iterator position, InputIterator first, 397 InputIterator last); 398 iterator insert(const_iterator position, value_type &&val); 399 iterator insert(const_iterator position, initializer_list<value_type> il); 400 401 template <class... Args> 402 iterator emplace(const_iterator position, Args&&... args); 403 404 iterator erase(const_iterator position); 405 iterator erase(const_iterator first, const_iterator last); 406 407 iterator begin() { return iterator(_start); } 408 const_iterator begin() const { return const_iterator(_start); } 409 const_iterator cbegin() const { return const_iterator(_start); } 410 iterator end() { return iterator(_finish); } 411 const_iterator end() const { return const_iterator(_finish); } 412 const_iterator cend() const { return const_iterator(_finish); } 413 414 T& front() { return *begin(); } 415 const T& front() const { return *begin(); } 416 T& back() { return *--end(); } 417 const T& back() const { return *--end(); } 418 }; 419 420 template<typename T> 421 class deque { 422 T *_start; 423 T *_finish; 424 T *_end_of_storage; 425 426 public: 427 typedef T value_type; 428 typedef size_t size_type; 429 typedef __deque_iterator<T, T *, T &> iterator; 430 typedef __deque_iterator<T, const T *, const T &> const_iterator; 431 432 deque() : _start(0), _finish(0), _end_of_storage(0) {} 433 template <typename InputIterator> 434 deque(InputIterator first, InputIterator last); 435 deque(const deque &other); 436 deque(deque &&other); 437 ~deque(); 438 439 size_t size() const { 440 return size_t(_finish - _start); 441 } 442 443 deque& operator=(const deque &other); 444 deque& operator=(deque &&other); 445 deque& operator=(std::initializer_list<T> ilist); 446 447 void assign(size_type count, const T &value); 448 template <typename InputIterator > 449 void assign(InputIterator first, InputIterator last); 450 void assign(std::initializer_list<T> ilist); 451 452 void clear(); 453 454 void push_back(const T &value); 455 void push_back(T &&value); 456 template<class... Args> 457 void emplace_back(Args&&... args); 458 void pop_back(); 459 460 void push_front(const T &value); 461 void push_front(T &&value); 462 template<class... Args> 463 void emplace_front(Args&&... args); 464 void pop_front(); 465 466 iterator insert(const_iterator position, const value_type &val); 467 iterator insert(const_iterator position, size_type n, 468 const value_type &val); 469 template <typename InputIterator> 470 iterator insert(const_iterator position, InputIterator first, 471 InputIterator last); 472 iterator insert(const_iterator position, value_type &&val); 473 iterator insert(const_iterator position, initializer_list<value_type> il); 474 475 template <class... Args> 476 iterator emplace(const_iterator position, Args&&... args); 477 478 iterator erase(const_iterator position); 479 iterator erase(const_iterator first, const_iterator last); 480 481 T &operator[](size_t n) { 482 return _start[n]; 483 } 484 485 const T &operator[](size_t n) const { 486 return _start[n]; 487 } 488 489 iterator begin() { return iterator(_start); } 490 const_iterator begin() const { return const_iterator(_start); } 491 const_iterator cbegin() const { return const_iterator(_start); } 492 iterator end() { return iterator(_finish); } 493 const_iterator end() const { return const_iterator(_finish); } 494 const_iterator cend() const { return const_iterator(_finish); } 495 T& front() { return *begin(); } 496 const T& front() const { return *begin(); } 497 T& back() { return *(end() - 1); } 498 const T& back() const { return *(end() - 1); } 499 }; 500 501 template<typename T> 502 class forward_list { 503 struct __item { 504 T data; 505 __item *next; 506 } *_start; 507 508 public: 509 typedef T value_type; 510 typedef size_t size_type; 511 typedef __fwdl_iterator<__item, T *, T &> iterator; 512 typedef __fwdl_iterator<__item, const T *, const T &> const_iterator; 513 514 forward_list() : _start(0) {} 515 template <typename InputIterator> 516 forward_list(InputIterator first, InputIterator last); 517 forward_list(const forward_list &other); 518 forward_list(forward_list &&other); 519 ~forward_list(); 520 521 forward_list& operator=(const forward_list &other); 522 forward_list& operator=(forward_list &&other); 523 forward_list& operator=(std::initializer_list<T> ilist); 524 525 void assign(size_type count, const T &value); 526 template <typename InputIterator > 527 void assign(InputIterator first, InputIterator last); 528 void assign(std::initializer_list<T> ilist); 529 530 void clear(); 531 532 void push_front(const T &value); 533 void push_front(T &&value); 534 template<class... Args> 535 void emplace_front(Args&&... args); 536 void pop_front(); 537 538 iterator insert_after(const_iterator position, const value_type &val); 539 iterator insert_after(const_iterator position, value_type &&val); 540 iterator insert_after(const_iterator position, size_type n, 541 const value_type &val); 542 template <typename InputIterator> 543 iterator insert_after(const_iterator position, InputIterator first, 544 InputIterator last); 545 iterator insert_after(const_iterator position, 546 initializer_list<value_type> il); 547 548 template <class... Args> 549 iterator emplace_after(const_iterator position, Args&&... args); 550 551 iterator erase_after(const_iterator position); 552 iterator erase_after(const_iterator first, const_iterator last); 553 554 iterator begin() { return iterator(_start); } 555 const_iterator begin() const { return const_iterator(_start); } 556 const_iterator cbegin() const { return const_iterator(_start); } 557 iterator end() { return iterator(); } 558 const_iterator end() const { return const_iterator(); } 559 const_iterator cend() const { return const_iterator(); } 560 561 T& front() { return *begin(); } 562 const T& front() const { return *begin(); } 563 }; 564 565 template <typename CharT> 566 class basic_string { 567 class Allocator {}; 568 569 public: 570 basic_string() : basic_string(Allocator()) {} 571 explicit basic_string(const Allocator &alloc); 572 basic_string(size_type count, CharT ch, 573 const Allocator &alloc = Allocator()); 574 basic_string(const basic_string &other, 575 size_type pos, 576 const Allocator &alloc = Allocator()); 577 basic_string(const basic_string &other, 578 size_type pos, size_type count, 579 const Allocator &alloc = Allocator()); 580 basic_string(const CharT *s, size_type count, 581 const Allocator &alloc = Allocator()); 582 basic_string(const CharT *s, 583 const Allocator &alloc = Allocator()); 584 template <class InputIt> 585 basic_string(InputIt first, InputIt last, 586 const Allocator &alloc = Allocator()); 587 basic_string(const basic_string &other); 588 basic_string(const basic_string &other, 589 const Allocator &alloc); 590 basic_string(basic_string &&other); 591 basic_string(basic_string &&other, 592 const Allocator &alloc); 593 basic_string(std::initializer_list<CharT> ilist, 594 const Allocator &alloc = Allocator()); 595 template <class T> 596 basic_string(const T &t, size_type pos, size_type n, 597 const Allocator &alloc = Allocator()); 598 // basic_string(std::nullptr_t) = delete; 599 600 ~basic_string(); 601 void clear(); 602 603 basic_string &operator=(const basic_string &str); 604 basic_string &operator+=(const basic_string &str); 605 606 const CharT *c_str() const; 607 const CharT *data() const; 608 CharT *data(); 609 610 const char *begin() const; 611 const char *end() const; 612 613 basic_string &append(size_type count, CharT ch); 614 basic_string &assign(size_type count, CharT ch); 615 basic_string &erase(size_type index, size_type count); 616 basic_string &insert(size_type index, size_type count, CharT ch); 617 basic_string &replace(size_type pos, size_type count, const basic_string &str); 618 void pop_back(); 619 void push_back(CharT ch); 620 void reserve(size_type new_cap); 621 void resize(size_type count); 622 void shrink_to_fit(); 623 void swap(basic_string &other); 624 }; 625 626 typedef basic_string<char> string; 627 typedef basic_string<wchar_t> wstring; 628 #if __cplusplus >= 201103L 629 typedef basic_string<char16_t> u16string; 630 typedef basic_string<char32_t> u32string; 631 #endif 632 633 class exception { 634 public: 635 exception() throw(); 636 virtual ~exception() throw(); 637 virtual const char *what() const throw() { 638 return 0; 639 } 640 }; 641 642 class bad_alloc : public exception { 643 public: 644 bad_alloc() throw(); 645 bad_alloc(const bad_alloc&) throw(); 646 bad_alloc& operator=(const bad_alloc&) throw(); 647 virtual const char* what() const throw() { 648 return 0; 649 } 650 }; 651 652 struct nothrow_t {}; 653 extern const nothrow_t nothrow; 654 655 enum class align_val_t : size_t {}; 656 657 // libc++'s implementation 658 template <class _E> 659 class initializer_list 660 { 661 const _E* __begin_; 662 size_t __size_; 663 664 initializer_list(const _E* __b, size_t __s) 665 : __begin_(__b), 666 __size_(__s) 667 {} 668 669 public: 670 typedef _E value_type; 671 typedef const _E& reference; 672 typedef const _E& const_reference; 673 typedef size_t size_type; 674 675 typedef const _E* iterator; 676 typedef const _E* const_iterator; 677 678 initializer_list() : __begin_(0), __size_(0) {} 679 680 size_t size() const {return __size_;} 681 const _E* begin() const {return __begin_;} 682 const _E* end() const {return __begin_ + __size_;} 683 }; 684 685 template <bool, class _Tp = void> struct enable_if {}; 686 template <class _Tp> struct enable_if<true, _Tp> {typedef _Tp type;}; 687 688 template <class _Tp, _Tp __v> 689 struct integral_constant 690 { 691 static const _Tp value = __v; 692 typedef _Tp value_type; 693 typedef integral_constant type; 694 695 operator value_type() const {return value;} 696 697 value_type operator ()() const {return value;} 698 }; 699 700 template <class _Tp, _Tp __v> 701 const _Tp integral_constant<_Tp, __v>::value; 702 703 template <class _Tp, class _Arg> 704 struct is_trivially_assignable 705 : integral_constant<bool, __is_trivially_assignable(_Tp, _Arg)> 706 { 707 }; 708 709 typedef integral_constant<bool,true> true_type; 710 typedef integral_constant<bool,false> false_type; 711 712 template <class _Tp> struct is_const : public false_type {}; 713 template <class _Tp> struct is_const<_Tp const> : public true_type {}; 714 715 template <class _Tp> struct is_reference : public false_type {}; 716 template <class _Tp> struct is_reference<_Tp&> : public true_type {}; 717 718 template <class _Tp, class _Up> struct is_same : public false_type {}; 719 template <class _Tp> struct is_same<_Tp, _Tp> : public true_type {}; 720 721 template <class _Tp, bool = is_const<_Tp>::value || is_reference<_Tp>::value > 722 struct __add_const {typedef _Tp type;}; 723 724 template <class _Tp> 725 struct __add_const<_Tp, false> {typedef const _Tp type;}; 726 727 template <class _Tp> struct add_const {typedef typename __add_const<_Tp>::type type;}; 728 729 template <class _Tp> struct remove_const {typedef _Tp type;}; 730 template <class _Tp> struct remove_const<const _Tp> {typedef _Tp type;}; 731 732 template <class _Tp> struct add_lvalue_reference {typedef _Tp& type;}; 733 734 template <class _Tp> struct is_trivially_copy_assignable 735 : public is_trivially_assignable<typename add_lvalue_reference<_Tp>::type, 736 typename add_lvalue_reference<typename add_const<_Tp>::type>::type> {}; 737 738 template<class InputIter, class OutputIter> 739 OutputIter __copy(InputIter II, InputIter IE, OutputIter OI) { 740 while (II != IE) 741 *OI++ = *II++; 742 743 return OI; 744 } 745 746 template <class _Tp, class _Up> 747 inline 748 typename enable_if 749 < 750 is_same<typename remove_const<_Tp>::type, _Up>::value && 751 is_trivially_copy_assignable<_Up>::value, 752 _Up* 753 >::type __copy(_Tp* __first, _Tp* __last, _Up* __result) { 754 size_t __n = __last - __first; 755 756 if (__n > 0) 757 memmove(__result, __first, __n * sizeof(_Up)); 758 759 return __result + __n; 760 } 761 762 template<class InputIter, class OutputIter> 763 OutputIter copy(InputIter II, InputIter IE, OutputIter OI) { 764 return __copy(II, IE, OI); 765 } 766 767 template <class _BidirectionalIterator, class _OutputIterator> 768 inline 769 _OutputIterator 770 __copy_backward(_BidirectionalIterator __first, _BidirectionalIterator __last, 771 _OutputIterator __result) 772 { 773 while (__first != __last) 774 *--__result = *--__last; 775 return __result; 776 } 777 778 template <class _Tp, class _Up> 779 inline 780 typename enable_if 781 < 782 is_same<typename remove_const<_Tp>::type, _Up>::value && 783 is_trivially_copy_assignable<_Up>::value, 784 _Up* 785 >::type __copy_backward(_Tp* __first, _Tp* __last, _Up* __result) { 786 size_t __n = __last - __first; 787 788 if (__n > 0) 789 { 790 __result -= __n; 791 memmove(__result, __first, __n * sizeof(_Up)); 792 } 793 return __result; 794 } 795 796 template<class InputIter, class OutputIter> 797 OutputIter copy_backward(InputIter II, InputIter IE, OutputIter OI) { 798 return __copy_backward(II, IE, OI); 799 } 800 } 801 802 template <class BidirectionalIterator, class Distance> 803 void __advance(BidirectionalIterator& it, Distance n, 804 std::bidirectional_iterator_tag) 805 #if !defined(STD_ADVANCE_INLINE_LEVEL) || STD_ADVANCE_INLINE_LEVEL > 2 806 { 807 if (n >= 0) while(n-- > 0) ++it; else while (n++<0) --it; 808 } 809 #else 810 ; 811 #endif 812 813 template <class RandomAccessIterator, class Distance> 814 void __advance(RandomAccessIterator& it, Distance n, 815 std::random_access_iterator_tag) 816 #if !defined(STD_ADVANCE_INLINE_LEVEL) || STD_ADVANCE_INLINE_LEVEL > 2 817 { 818 it += n; 819 } 820 #else 821 ; 822 #endif 823 824 namespace std { 825 826 template <class InputIterator, class Distance> 827 void advance(InputIterator& it, Distance n) 828 #if !defined(STD_ADVANCE_INLINE_LEVEL) || STD_ADVANCE_INLINE_LEVEL > 1 829 { 830 __advance(it, n, typename InputIterator::iterator_category()); 831 } 832 #else 833 ; 834 #endif 835 836 template <class BidirectionalIterator> 837 BidirectionalIterator 838 prev(BidirectionalIterator it, 839 typename iterator_traits<BidirectionalIterator>::difference_type n = 840 1) 841 #if !defined(STD_ADVANCE_INLINE_LEVEL) || STD_ADVANCE_INLINE_LEVEL > 0 842 { 843 advance(it, -n); 844 return it; 845 } 846 #else 847 ; 848 #endif 849 850 template <class ForwardIterator> 851 ForwardIterator 852 next(ForwardIterator it, 853 typename iterator_traits<ForwardIterator>::difference_type n = 854 1) 855 #if !defined(STD_ADVANCE_INLINE_LEVEL) || STD_ADVANCE_INLINE_LEVEL > 0 856 { 857 advance(it, n); 858 return it; 859 } 860 #else 861 ; 862 #endif 863 864 template <class InputIt, class T> 865 InputIt find(InputIt first, InputIt last, const T& value); 866 867 template <class ExecutionPolicy, class ForwardIt, class T> 868 ForwardIt find(ExecutionPolicy&& policy, ForwardIt first, ForwardIt last, 869 const T& value); 870 871 template <class InputIt, class UnaryPredicate> 872 InputIt find_if (InputIt first, InputIt last, UnaryPredicate p); 873 874 template <class ExecutionPolicy, class ForwardIt, class UnaryPredicate> 875 ForwardIt find_if (ExecutionPolicy&& policy, ForwardIt first, ForwardIt last, 876 UnaryPredicate p); 877 878 template <class InputIt, class UnaryPredicate> 879 InputIt find_if_not (InputIt first, InputIt last, UnaryPredicate q); 880 881 template <class ExecutionPolicy, class ForwardIt, class UnaryPredicate> 882 ForwardIt find_if_not (ExecutionPolicy&& policy, ForwardIt first, 883 ForwardIt last, UnaryPredicate q); 884 885 template <class InputIt, class ForwardIt> 886 InputIt find_first_of(InputIt first, InputIt last, 887 ForwardIt s_first, ForwardIt s_last); 888 889 template <class ExecutionPolicy, class ForwardIt1, class ForwardIt2> 890 ForwardIt1 find_first_of (ExecutionPolicy&& policy, 891 ForwardIt1 first, ForwardIt1 last, 892 ForwardIt2 s_first, ForwardIt2 s_last); 893 894 template <class InputIt, class ForwardIt, class BinaryPredicate> 895 InputIt find_first_of (InputIt first, InputIt last, 896 ForwardIt s_first, ForwardIt s_last, 897 BinaryPredicate p ); 898 899 template <class ExecutionPolicy, class ForwardIt1, class ForwardIt2, 900 class BinaryPredicate> 901 ForwardIt1 find_first_of (ExecutionPolicy&& policy, 902 ForwardIt1 first, ForwardIt1 last, 903 ForwardIt2 s_first, ForwardIt2 s_last, 904 BinaryPredicate p ); 905 906 template <class InputIt, class ForwardIt> 907 InputIt find_end(InputIt first, InputIt last, 908 ForwardIt s_first, ForwardIt s_last); 909 910 template <class ExecutionPolicy, class ForwardIt1, class ForwardIt2> 911 ForwardIt1 find_end (ExecutionPolicy&& policy, 912 ForwardIt1 first, ForwardIt1 last, 913 ForwardIt2 s_first, ForwardIt2 s_last); 914 915 template <class InputIt, class ForwardIt, class BinaryPredicate> 916 InputIt find_end (InputIt first, InputIt last, 917 ForwardIt s_first, ForwardIt s_last, 918 BinaryPredicate p ); 919 920 template <class ExecutionPolicy, class ForwardIt1, class ForwardIt2, 921 class BinaryPredicate> 922 ForwardIt1 find_end (ExecutionPolicy&& policy, 923 ForwardIt1 first, ForwardIt1 last, 924 ForwardIt2 s_first, ForwardIt2 s_last, 925 BinaryPredicate p ); 926 927 template <class ForwardIt, class T> 928 ForwardIt lower_bound (ForwardIt first, ForwardIt last, const T& value); 929 930 template <class ForwardIt, class T, class Compare> 931 ForwardIt lower_bound (ForwardIt first, ForwardIt last, const T& value, 932 Compare comp); 933 934 template <class ForwardIt, class T> 935 ForwardIt upper_bound (ForwardIt first, ForwardIt last, const T& value); 936 937 template <class ForwardIt, class T, class Compare> 938 ForwardIt upper_bound (ForwardIt first, ForwardIt last, const T& value, 939 Compare comp); 940 941 template <class ForwardIt1, class ForwardIt2> 942 ForwardIt1 search (ForwardIt1 first, ForwardIt1 last, 943 ForwardIt2 s_first, ForwardIt2 s_last); 944 945 template <class ExecutionPolicy, class ForwardIt1, class ForwardIt2> 946 ForwardIt1 search (ExecutionPolicy&& policy, 947 ForwardIt1 first, ForwardIt1 last, 948 ForwardIt2 s_first, ForwardIt2 s_last); 949 950 template <class ForwardIt1, class ForwardIt2, class BinaryPredicate> 951 ForwardIt1 search (ForwardIt1 first, ForwardIt1 last, 952 ForwardIt2 s_first, ForwardIt2 s_last, BinaryPredicate p); 953 954 template <class ExecutionPolicy, class ForwardIt1, class ForwardIt2, 955 class BinaryPredicate > 956 ForwardIt1 search (ExecutionPolicy&& policy, 957 ForwardIt1 first, ForwardIt1 last, 958 ForwardIt2 s_first, ForwardIt2 s_last, BinaryPredicate p); 959 960 template <class ForwardIt, class Searcher> 961 ForwardIt search (ForwardIt first, ForwardIt last, const Searcher& searcher); 962 963 template <class ForwardIt, class Size, class T> 964 ForwardIt search_n (ForwardIt first, ForwardIt last, Size count, 965 const T& value); 966 967 template <class ExecutionPolicy, class ForwardIt, class Size, class T> 968 ForwardIt search_n (ExecutionPolicy&& policy, ForwardIt first, ForwardIt last, 969 Size count, const T& value); 970 971 template <class ForwardIt, class Size, class T, class BinaryPredicate> 972 ForwardIt search_n (ForwardIt first, ForwardIt last, Size count, 973 const T& value, BinaryPredicate p); 974 975 template <class ExecutionPolicy, class ForwardIt, class Size, class T, 976 class BinaryPredicate> 977 ForwardIt search_n (ExecutionPolicy&& policy, ForwardIt first, ForwardIt last, 978 Size count, const T& value, BinaryPredicate p); 979 980 template <class InputIterator, class OutputIterator> 981 OutputIterator copy(InputIterator first, InputIterator last, 982 OutputIterator result); 983 984 } 985 986 #if __cplusplus >= 201103L 987 namespace std { 988 template <typename T> // TODO: Implement the stub for deleter. 989 class unique_ptr { 990 public: 991 unique_ptr() noexcept {} 992 unique_ptr(T *) noexcept {} 993 unique_ptr(const unique_ptr &) noexcept = delete; 994 unique_ptr(unique_ptr &&) noexcept; 995 996 T *get() const noexcept; 997 T *release() noexcept; 998 void reset(T *p = nullptr) noexcept; 999 void swap(unique_ptr<T> &p) noexcept; 1000 1001 typename std::add_lvalue_reference<T>::type operator*() const; 1002 T *operator->() const noexcept; 1003 operator bool() const noexcept; 1004 unique_ptr<T> &operator=(unique_ptr<T> &&p) noexcept; 1005 unique_ptr<T> &operator=(nullptr_t) noexcept; 1006 }; 1007 1008 // TODO :: Once the deleter parameter is added update with additional template parameter. 1009 template <typename T> 1010 void swap(unique_ptr<T> &x, unique_ptr<T> &y) noexcept { 1011 x.swap(y); 1012 } 1013 1014 template <typename T1, typename T2> 1015 bool operator==(const unique_ptr<T1> &x, const unique_ptr<T2> &y); 1016 1017 template <typename T1, typename T2> 1018 bool operator!=(const unique_ptr<T1> &x, const unique_ptr<T2> &y); 1019 1020 template <typename T1, typename T2> 1021 bool operator<(const unique_ptr<T1> &x, const unique_ptr<T2> &y); 1022 1023 template <typename T1, typename T2> 1024 bool operator>(const unique_ptr<T1> &x, const unique_ptr<T2> &y); 1025 1026 template <typename T1, typename T2> 1027 bool operator<=(const unique_ptr<T1> &x, const unique_ptr<T2> &y); 1028 1029 template <typename T1, typename T2> 1030 bool operator>=(const unique_ptr<T1> &x, const unique_ptr<T2> &y); 1031 1032 template <typename T> 1033 bool operator==(const unique_ptr<T> &x, nullptr_t y); 1034 1035 template <typename T> 1036 bool operator!=(const unique_ptr<T> &x, nullptr_t y); 1037 1038 template <typename T> 1039 bool operator<(const unique_ptr<T> &x, nullptr_t y); 1040 1041 template <typename T> 1042 bool operator>(const unique_ptr<T> &x, nullptr_t y); 1043 1044 template <typename T> 1045 bool operator<=(const unique_ptr<T> &x, nullptr_t y); 1046 1047 template <typename T> 1048 bool operator>=(const unique_ptr<T> &x, nullptr_t y); 1049 1050 template <typename T> 1051 bool operator==(nullptr_t x, const unique_ptr<T> &y); 1052 1053 template <typename T> 1054 bool operator!=(nullptr_t x, const unique_ptr<T> &y); 1055 1056 template <typename T> 1057 bool operator>(nullptr_t x, const unique_ptr<T> &y); 1058 1059 template <typename T> 1060 bool operator<(nullptr_t x, const unique_ptr<T> &y); 1061 1062 template <typename T> 1063 bool operator>=(nullptr_t x, const unique_ptr<T> &y); 1064 1065 template <typename T> 1066 bool operator<=(nullptr_t x, const unique_ptr<T> &y); 1067 1068 template <class T, class... Args> 1069 unique_ptr<T> make_unique(Args &&...args); 1070 1071 #if __cplusplus >= 202002L 1072 1073 template <class T> 1074 unique_ptr<T> make_unique_for_overwrite(); 1075 1076 #endif 1077 1078 } // namespace std 1079 #endif 1080 1081 namespace std { 1082 template <class CharT> 1083 class basic_ostream; 1084 1085 using ostream = basic_ostream<char>; 1086 1087 extern std::ostream cout; 1088 1089 ostream &operator<<(ostream &, const string &); 1090 1091 #if __cplusplus >= 202002L 1092 template <class T> 1093 ostream &operator<<(ostream &, const std::unique_ptr<T> &); 1094 #endif 1095 } // namespace std 1096 1097 #ifdef TEST_INLINABLE_ALLOCATORS 1098 namespace std { 1099 void *malloc(size_t); 1100 void free(void *); 1101 } 1102 void* operator new(std::size_t size, const std::nothrow_t&) throw() { return std::malloc(size); } 1103 void* operator new[](std::size_t size, const std::nothrow_t&) throw() { return std::malloc(size); } 1104 void operator delete(void* ptr, const std::nothrow_t&) throw() { std::free(ptr); } 1105 void operator delete[](void* ptr, const std::nothrow_t&) throw() { std::free(ptr); } 1106 #else 1107 // C++20 standard draft 17.6.1, from "Header <new> synopsis", but with throw() 1108 // instead of noexcept: 1109 1110 void *operator new(std::size_t size); 1111 void *operator new(std::size_t size, std::align_val_t alignment); 1112 void *operator new(std::size_t size, const std::nothrow_t &) throw(); 1113 void *operator new(std::size_t size, std::align_val_t alignment, 1114 const std::nothrow_t &) throw(); 1115 void operator delete(void *ptr) throw(); 1116 void operator delete(void *ptr, std::size_t size) throw(); 1117 void operator delete(void *ptr, std::align_val_t alignment) throw(); 1118 void operator delete(void *ptr, std::size_t size, std::align_val_t alignment) throw(); 1119 void operator delete(void *ptr, const std::nothrow_t &)throw(); 1120 void operator delete(void *ptr, std::align_val_t alignment, 1121 const std::nothrow_t &)throw(); 1122 void *operator new[](std::size_t size); 1123 void *operator new[](std::size_t size, std::align_val_t alignment); 1124 void *operator new[](std::size_t size, const std::nothrow_t &) throw(); 1125 void *operator new[](std::size_t size, std::align_val_t alignment, 1126 const std::nothrow_t &) throw(); 1127 void operator delete[](void *ptr) throw(); 1128 void operator delete[](void *ptr, std::size_t size) throw(); 1129 void operator delete[](void *ptr, std::align_val_t alignment) throw(); 1130 void operator delete[](void *ptr, std::size_t size, std::align_val_t alignment) throw(); 1131 void operator delete[](void *ptr, const std::nothrow_t &) throw(); 1132 void operator delete[](void *ptr, std::align_val_t alignment, 1133 const std::nothrow_t &) throw(); 1134 #endif 1135 1136 void* operator new (std::size_t size, void* ptr) throw() { return ptr; }; 1137 void* operator new[] (std::size_t size, void* ptr) throw() { return ptr; }; 1138 void operator delete (void* ptr, void*) throw() {}; 1139 void operator delete[] (void* ptr, void*) throw() {}; 1140 1141 namespace __cxxabiv1 { 1142 extern "C" { 1143 extern char *__cxa_demangle(const char *mangled_name, 1144 char *output_buffer, 1145 size_t *length, 1146 int *status); 1147 }} 1148 namespace abi = __cxxabiv1; 1149 1150 namespace std { 1151 template<class ForwardIt> 1152 bool is_sorted(ForwardIt first, ForwardIt last); 1153 1154 template <class RandomIt> 1155 void nth_element(RandomIt first, RandomIt nth, RandomIt last); 1156 1157 template<class RandomIt> 1158 void partial_sort(RandomIt first, RandomIt middle, RandomIt last); 1159 1160 template<class RandomIt> 1161 void sort (RandomIt first, RandomIt last); 1162 1163 template<class RandomIt> 1164 void stable_sort(RandomIt first, RandomIt last); 1165 1166 template<class BidirIt, class UnaryPredicate> 1167 BidirIt partition(BidirIt first, BidirIt last, UnaryPredicate p); 1168 1169 template<class BidirIt, class UnaryPredicate> 1170 BidirIt stable_partition(BidirIt first, BidirIt last, UnaryPredicate p); 1171 } 1172 1173 namespace std { 1174 1175 template< class T = void > 1176 struct less; 1177 1178 template< class T > 1179 struct allocator; 1180 1181 template< class Key > 1182 struct hash; 1183 1184 template< 1185 class Key, 1186 class Compare = std::less<Key>, 1187 class Alloc = std::allocator<Key> 1188 > class set { 1189 public: 1190 set(initializer_list<Key> __list) {} 1191 1192 class iterator { 1193 public: 1194 iterator(Key *key): ptr(key) {} 1195 iterator& operator++() { ++ptr; return *this; } 1196 bool operator!=(const iterator &other) const { return ptr != other.ptr; } 1197 const Key &operator*() const { return *ptr; } 1198 private: 1199 Key *ptr; 1200 }; 1201 1202 public: 1203 Key *val; 1204 iterator begin() const { return iterator(val); } 1205 iterator end() const { return iterator(val + 1); } 1206 }; 1207 1208 template< 1209 class Key, 1210 class Hash = std::hash<Key>, 1211 class Compare = std::less<Key>, 1212 class Alloc = std::allocator<Key> 1213 > class unordered_set { 1214 public: 1215 unordered_set(initializer_list<Key> __list) {} 1216 1217 class iterator { 1218 public: 1219 iterator(Key *key): ptr(key) {} 1220 iterator& operator++() { ++ptr; return *this; } 1221 bool operator!=(const iterator &other) const { return ptr != other.ptr; } 1222 const Key &operator*() const { return *ptr; } 1223 private: 1224 Key *ptr; 1225 }; 1226 1227 public: 1228 Key *val; 1229 iterator begin() const { return iterator(val); } 1230 iterator end() const { return iterator(val + 1); } 1231 }; 1232 1233 namespace execution { 1234 class sequenced_policy {}; 1235 } 1236 1237 template <class T = void> struct equal_to {}; 1238 1239 template <class ForwardIt, class BinaryPredicate = std::equal_to<> > 1240 class default_searcher { 1241 public: 1242 default_searcher (ForwardIt pat_first, 1243 ForwardIt pat_last, 1244 BinaryPredicate pred = BinaryPredicate()); 1245 template <class ForwardIt2> 1246 std::pair <ForwardIt2, ForwardIt2> 1247 operator()( ForwardIt2 first, ForwardIt2 last ) const; 1248 }; 1249 1250 template <typename> class packaged_task; 1251 template <typename Ret, typename... Args> class packaged_task<Ret(Args...)> { 1252 // TODO: Add some actual implementation. 1253 }; 1254 1255 } // namespace std 1256