Clang Project

clang_source_code/test/Analysis/Inputs/system-header-simulator-cxx.h
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
8typedef unsigned char uint8_t;
9
10typedef __typeof__(sizeof(int)) size_t;
11typedef __typeof__((char*)0-(char*)0) ptrdiff_t;
12void *memmove(void *s1, const void *s2, size_t n);
13
14namespace std {
15  typedef size_t size_type;
16#if __cplusplus >= 201103L
17  using nullptr_t = decltype(nullptr);
18#endif
19}
20
21namespace 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
37template <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
47  __vector_iterator(const Ptr p = 0) : ptr(p) {}
48  __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  __vector_iterator<T, Ptr, Ref> operator-(difference_type n) {
64    return ptr - n;
65  }
66  __vector_iterator<T, Ptr, Ref> operator+=(difference_type n) {
67    return ptr += n;
68  }
69  __vector_iterator<T, Ptr, Ref> operator-=(difference_type n) {
70    return ptr -= n;
71  }
72
73  Ref operator*() const { return *ptr; }
74  Ptr operator->() const { return *ptr; }
75
76  bool operator==(const iterator &rhs) const { return ptr == rhs.ptr; }
77  bool operator==(const const_iterator &rhs) const { return ptr == rhs.ptr; }
78
79  bool operator!=(const iterator &rhs) const { return ptr != rhs.ptr; }
80  bool operator!=(const const_iterator &rhs) const { return ptr != rhs.ptr; }
81
82  const Ptr& base() const { return ptr; }
83
84private:
85  Ptr ptr;
86};
87
88template <typename T, typename Ptr, typename Ref> struct __deque_iterator {
89  typedef __deque_iterator<T, T *, T &> iterator;
90  typedef __deque_iterator<T, const T *, const T &> const_iterator;
91
92  typedef ptrdiff_t difference_type;
93  typedef T value_type;
94  typedef Ptr pointer;
95  typedef Ref reference;
96  typedef std::random_access_iterator_tag iterator_category;
97
98  __deque_iterator(const Ptr p = 0) : ptr(p) {}
99  __deque_iterator(const iterator &rhs): ptr(rhs.base()) {}
100  __deque_iterator<T, Ptr, Ref> operator++() { ++ ptr; return *this; }
101  __deque_iterator<T, Ptr, Ref> operator++(int) {
102    auto tmp = *this;
103    ++ ptr;
104    return tmp;
105  }
106  __deque_iterator<T, Ptr, Ref> operator--() { -- ptr; return *this; }
107  __deque_iterator<T, Ptr, Ref> operator--(int) {
108    auto tmp = *this; -- ptr;
109    return tmp;
110  }
111  __deque_iterator<T, Ptr, Ref> operator+(difference_type n) {
112    return ptr + n;
113  }
114  __deque_iterator<T, Ptr, Ref> operator-(difference_type n) {
115    return ptr - n;
116  }
117  __deque_iterator<T, Ptr, Ref> operator+=(difference_type n) {
118    return ptr += n;
119  }
120  __deque_iterator<T, Ptr, Ref> operator-=(difference_type n) {
121    return ptr -= n;
122  }
123
124  Ref operator*() const { return *ptr; }
125  Ptr operator->() const { return *ptr; }
126
127  bool operator==(const iterator &rhs) const { return ptr == rhs.ptr; }
128  bool operator==(const const_iterator &rhs) const { return ptr == rhs.ptr; }
129
130  bool operator!=(const iterator &rhs) const { return ptr != rhs.ptr; }
131  bool operator!=(const const_iterator &rhs) const { return ptr != rhs.ptr; }
132
133  const Ptr& base() const { return ptr; }
134
135private:
136  Ptr ptr;
137};
138
139template <typename T, typename Ptr, typename Ref> struct __list_iterator {
140  typedef __list_iterator<T, __typeof__(T::data) *, __typeof__(T::data) &> iterator;
141  typedef __list_iterator<T, const __typeof__(T::data) *, const __typeof__(T::data) &> const_iterator;
142
143  typedef ptrdiff_t difference_type;
144  typedef T value_type;
145  typedef Ptr pointer;
146  typedef Ref reference;
147  typedef std::bidirectional_iterator_tag iterator_category;
148
149  __list_iterator(T* it = 0) : item(it) {}
150  __list_iterator(const iterator &rhs): item(rhs.base()) {}
151  __list_iterator<T, Ptr, Ref> operator++() { item = item->next; return *this; }
152  __list_iterator<T, Ptr, Ref> operator++(int) {
153    auto tmp = *this;
154    item = item->next;
155    return tmp;
156  }
157  __list_iterator<T, Ptr, Ref> operator--() { item = item->prev; return *this; }
158  __list_iterator<T, Ptr, Ref> operator--(int) {
159    auto tmp = *this;
160    item = item->prev;
161    return tmp;
162  }
163
164  Ref operator*() const { return item->data; }
165  Ptr operator->() const { return item->data; }
166
167  bool operator==(const iterator &rhs) const { return item == rhs->item; }
168  bool operator==(const const_iterator &rhs) const { return item == rhs->item; }
169
170  bool operator!=(const iterator &rhs) const { return item != rhs->item; }
171  bool operator!=(const const_iterator &rhs) const { return item != rhs->item; }
172
173  const T* &base() const { return item; }
174
175private:
176  T* item;
177};
178
179template <typename T, typename Ptr, typename Ref> struct __fwdl_iterator {
180  typedef __fwdl_iterator<T, __typeof__(T::data) *, __typeof__(T::data) &> iterator;
181  typedef __fwdl_iterator<T, const __typeof__(T::data) *, const __typeof__(T::data) &> const_iterator;
182
183  typedef ptrdiff_t difference_type;
184  typedef T value_type;
185  typedef Ptr pointer;
186  typedef Ref reference;
187  typedef std::forward_iterator_tag iterator_category;
188
189  __fwdl_iterator(T* it = 0) : item(it) {}
190  __fwdl_iterator(const iterator &rhs): item(rhs.base()) {}
191  __fwdl_iterator<T, Ptr, Ref> operator++() { item = item->next; return *this; }
192  __fwdl_iterator<T, Ptr, Ref> operator++(int) {
193    auto tmp = *this;
194    item = item->next;
195    return tmp;
196  }
197  Ref operator*() const { return item->data; }
198  Ptr operator->() const { return item->data; }
199
200  bool operator==(const iterator &rhs) const { return item == rhs->item; }
201  bool operator==(const const_iterator &rhs) const { return item == rhs->item; }
202
203  bool operator!=(const iterator &rhs) const { return item != rhs->item; }
204  bool operator!=(const const_iterator &rhs) const { return item != rhs->item; }
205
206  const T* &base() const { return item; }
207
208private:
209  T* item;
210};
211
212namespace std {
213  template <class T1, class T2>
214  struct pair {
215    T1 first;
216    T2 second;
217    
218    pair() : first(), second() {}
219    pair(const T1 &a, const T2 &b) : first(a), second(b) {}
220    
221    template<class U1, class U2>
222    pair(const pair<U1, U2> &other) : first(other.first),
223                                      second(other.second) {}
224  };
225  
226  typedef __typeof__(sizeof(int)) size_t;
227
228  template <class T> class initializer_list;
229  
230  template< class T > struct remove_reference      {typedef T type;};
231  template< class T > struct remove_reference<T&>  {typedef T type;};
232  template< class T > struct remove_reference<T&&> {typedef T type;};
233
234  template<class T> 
235  typename remove_reference<T>::type&& move(T&& a) {
236    typedef typename remove_reference<T>::type&& RvalRef;
237    return static_cast<RvalRef>(a);
238  }
239
240  template <class T>
241  void swap(T &a, T &b) {
242    T c(std::move(a));
243    a = std::move(b);
244    b = std::move(c);
245  }
246
247  template<typename T>
248  class vector {
249    typedef T value_type;
250    typedef size_t size_type;
251    typedef __vector_iterator<T, T *, T &> iterator;
252    typedef __vector_iterator<T, const T *, const T &> const_iterator;
253
254    T *_start;
255    T *_finish;
256    T *_end_of_storage;
257  public:
258    vector() : _start(0), _finish(0), _end_of_storage(0) {}
259    template <typename InputIterator>
260    vector(InputIterator first, InputIterator last);
261    vector(const vector &other);
262    vector(vector &&other);
263    ~vector();
264    
265    size_t size() const {
266      return size_t(_finish - _start);
267    }
268
269    vector& operator=(const vector &other);
270    vector& operator=(vector &&other);
271    vector& operator=(std::initializer_list<T> ilist);
272
273    void assign(size_type count, const T &value);
274    template <typename InputIterator >
275    void assign(InputIterator first, InputIterator last);
276    void assign(std::initializer_list<T> ilist);
277
278    void clear();
279
280    void push_back(const T &value);
281    void push_back(T &&value);
282    template<class... Args>
283    void emplace_back(Args&&... args);
284    void pop_back();
285
286    iterator insert(const_iterator position, const value_type &val);
287    iterator insert(const_iterator position, size_type n,
288                    const value_type &val);
289    template <typename InputIterator>
290    iterator insert(const_iterator position, InputIterator first,
291                    InputIterator last);
292    iterator insert(const_iterator position, value_type &&val);
293    iterator insert(const_iterator position, initializer_list<value_type> il);
294
295    template <class... Args>
296    iterator emplace(const_iterator position, Args&&... args);
297
298    iterator erase(const_iterator position);
299    iterator erase(const_iterator first, const_iterator last);
300
301    T &operator[](size_t n) {
302      return _start[n];
303    }
304    
305    const T &operator[](size_t n) const {
306      return _start[n];
307    }
308    
309    iterator begin() { return iterator(_start); }
310    const_iterator begin() const { return const_iterator(_start); }
311    const_iterator cbegin() const { return const_iterator(_start); }
312    iterator end() { return iterator(_finish); }
313    const_iterator end() const { return const_iterator(_finish); }
314    const_iterator cend() const { return const_iterator(_finish); }
315    T& front() { return *begin(); }
316    const T& front() const { return *begin(); }
317    T& back() { return *(end() - 1); }
318    const T& back() const { return *(end() - 1); }
319  };
320  
321  template<typename T>
322  class list {
323    struct __item {
324      T data;
325      __item *prev, *next;
326    } *_start, *_finish;
327  public:
328    typedef T value_type;
329    typedef size_t size_type;
330    typedef __list_iterator<__item, T *, T &> iterator;
331    typedef __list_iterator<__item, const T *, const T &> const_iterator;
332
333    list() : _start(0), _finish(0) {}
334    template <typename InputIterator>
335    list(InputIterator first, InputIterator last);
336    list(const list &other);
337    list(list &&other);
338    ~list();
339    
340    list& operator=(const list &other);
341    list& operator=(list &&other);
342    list& operator=(std::initializer_list<T> ilist);
343
344    void assign(size_type count, const T &value);
345    template <typename InputIterator >
346    void assign(InputIterator first, InputIterator last);
347    void assign(std::initializer_list<T> ilist);
348
349    void clear();
350
351    void push_back(const T &value);
352    void push_back(T &&value);
353    template<class... Args>
354    void emplace_back(Args&&... args);
355    void pop_back();
356
357    void push_front(const T &value);
358    void push_front(T &&value);
359    template<class... Args>
360    void emplace_front(Args&&... args);
361    void pop_front();
362
363    iterator insert(const_iterator position, const value_type &val);
364    iterator insert(const_iterator position, size_type n,
365                    const value_type &val);
366    template <typename InputIterator>
367    iterator insert(const_iterator position, InputIterator first,
368                    InputIterator last);
369    iterator insert(const_iterator position, value_type &&val);
370    iterator insert(const_iterator position, initializer_list<value_type> il);
371
372    template <class... Args>
373    iterator emplace(const_iterator position, Args&&... args);
374
375    iterator erase(const_iterator position);
376    iterator erase(const_iterator first, const_iterator last);
377
378    iterator begin() { return iterator(_start); }
379    const_iterator begin() const { return const_iterator(_start); }
380    const_iterator cbegin() const { return const_iterator(_start); }
381    iterator end() { return iterator(_finish); }
382    const_iterator end() const { return const_iterator(_finish); }
383    const_iterator cend() const { return const_iterator(_finish); }
384
385    T& front() { return *begin(); }
386    const T& front() const { return *begin(); }
387    T& back() { return *--end(); }
388    const T& back() const { return *--end(); }
389  };
390
391  template<typename T>
392  class deque {
393    typedef T value_type;
394    typedef size_t size_type;
395    typedef __deque_iterator<T, T *, T &> iterator;
396    typedef __deque_iterator<T, const T *, const T &> const_iterator;
397
398    T *_start;
399    T *_finish;
400    T *_end_of_storage;
401  public:
402    deque() : _start(0), _finish(0), _end_of_storage(0) {}
403    template <typename InputIterator>
404    deque(InputIterator first, InputIterator last);
405    deque(const deque &other);
406    deque(deque &&other);
407    ~deque();
408    
409    size_t size() const {
410      return size_t(_finish - _start);
411    }
412    
413    deque& operator=(const deque &other);
414    deque& operator=(deque &&other);
415    deque& operator=(std::initializer_list<T> ilist);
416
417    void assign(size_type count, const T &value);
418    template <typename InputIterator >
419    void assign(InputIterator first, InputIterator last);
420    void assign(std::initializer_list<T> ilist);
421
422    void clear();
423
424    void push_back(const T &value);
425    void push_back(T &&value);
426    template<class... Args>
427    void emplace_back(Args&&... args);
428    void pop_back();
429
430    void push_front(const T &value);
431    void push_front(T &&value);
432    template<class... Args>
433    void emplace_front(Args&&... args);
434    void pop_front();
435
436    iterator insert(const_iterator position, const value_type &val);
437    iterator insert(const_iterator position, size_type n,
438                    const value_type &val);
439    template <typename InputIterator>
440    iterator insert(const_iterator position, InputIterator first,
441                    InputIterator last);
442    iterator insert(const_iterator position, value_type &&val);
443    iterator insert(const_iterator position, initializer_list<value_type> il);
444
445    template <class... Args>
446    iterator emplace(const_iterator position, Args&&... args);
447
448    iterator erase(const_iterator position);
449    iterator erase(const_iterator first, const_iterator last);
450
451    T &operator[](size_t n) {
452      return _start[n];
453    }
454
455    const T &operator[](size_t n) const {
456      return _start[n];
457    }
458
459    iterator begin() { return iterator(_start); }
460    const_iterator begin() const { return const_iterator(_start); }
461    const_iterator cbegin() const { return const_iterator(_start); }
462    iterator end() { return iterator(_finish); }
463    const_iterator end() const { return const_iterator(_finish); }
464    const_iterator cend() const { return const_iterator(_finish); }
465    T& front() { return *begin(); }
466    const T& front() const { return *begin(); }
467    T& back() { return *(end() - 1); }
468    const T& back() const { return *(end() - 1); }
469  };
470
471  template<typename T>
472  class forward_list {
473    struct __item {
474      T data;
475      __item *next;
476    } *_start;
477  public:
478    typedef T value_type;
479    typedef size_t size_type;
480    typedef __fwdl_iterator<__item, T *, T &> iterator;
481    typedef __fwdl_iterator<__item, const T *, const T &> const_iterator;
482
483    forward_list() : _start(0) {}
484    template <typename InputIterator>
485    forward_list(InputIterator first, InputIterator last);
486    forward_list(const forward_list &other);
487    forward_list(forward_list &&other);
488    ~forward_list();
489    
490    forward_list& operator=(const forward_list &other);
491    forward_list& operator=(forward_list &&other);
492    forward_list& operator=(std::initializer_list<T> ilist);
493
494    void assign(size_type count, const T &value);
495    template <typename InputIterator >
496    void assign(InputIterator first, InputIterator last);
497    void assign(std::initializer_list<T> ilist);
498
499    void clear();
500
501    void push_front(const T &value);
502    void push_front(T &&value);
503    template<class... Args>
504    void emplace_front(Args&&... args);
505    void pop_front();
506
507    iterator insert_after(const_iterator position, const value_type &val);
508    iterator insert_after(const_iterator position, value_type &&val);
509    iterator insert_after(const_iterator position, size_type n,
510                          const value_type &val);
511    template <typename InputIterator>
512    iterator insert_after(const_iterator position, InputIterator first,
513                          InputIterator last);
514    iterator insert_after(const_iterator position,
515                          initializer_list<value_type> il);
516
517    template <class... Args>
518    iterator emplace_after(const_iterator position, Args&&... args);
519
520    iterator erase_after(const_iterator position);
521    iterator erase_after(const_iterator first, const_iterator last);
522
523    iterator begin() { return iterator(_start); }
524    const_iterator begin() const { return const_iterator(_start); }
525    const_iterator cbegin() const { return const_iterator(_start); }
526    iterator end() { return iterator(); }
527    const_iterator end() const { return const_iterator(); }
528    const_iterator cend() const { return const_iterator(); }
529
530    T& front() { return *begin(); }
531    const T& front() const { return *begin(); }
532  };
533
534  template <typename CharT>
535  class basic_string {
536  public:
537    basic_string();
538    basic_string(const CharT *s);
539
540    ~basic_string();
541    void clear();
542
543    basic_string &operator=(const basic_string &str);
544    basic_string &operator+=(const basic_string &str);
545
546    const CharT *c_str() const;
547    const CharT *data() const;
548    CharT *data();
549
550    basic_string &append(size_type count, CharT ch);
551    basic_string &assign(size_type count, CharT ch);
552    basic_string &erase(size_type index, size_type count);
553    basic_string &insert(size_type index, size_type count, CharT ch);
554    basic_string &replace(size_type pos, size_type count, const basic_string &str);
555    void pop_back();
556    void push_back(CharT ch);
557    void reserve(size_type new_cap);
558    void resize(size_type count);
559    void shrink_to_fit();
560    void swap(basic_string &other);
561  };
562
563  typedef basic_string<char> string;
564  typedef basic_string<wchar_t> wstring;
565#if __cplusplus >= 201103L
566  typedef basic_string<char16_t> u16string;
567  typedef basic_string<char32_t> u32string;
568#endif
569
570  class exception {
571  public:
572    exception() throw();
573    virtual ~exception() throw();
574    virtual const char *what() const throw() {
575      return 0;
576    }
577  };
578
579  class bad_alloc : public exception {
580    public:
581    bad_alloc() throw();
582    bad_alloc(const bad_alloc&) throw();
583    bad_alloc& operator=(const bad_alloc&) throw();
584    virtual const char* what() const throw() {
585      return 0;
586    }
587  };
588
589  struct nothrow_t {};
590
591  extern const nothrow_t nothrow;
592
593  // libc++'s implementation
594  template <class _E>
595  class initializer_list
596  {
597    const _E* __begin_;
598    size_t    __size_;
599
600    initializer_list(const _E* __b, size_t __s)
601      : __begin_(__b),
602        __size_(__s)
603    {}
604
605  public:
606    typedef _E        value_type;
607    typedef const _E& reference;
608    typedef const _E& const_reference;
609    typedef size_t    size_type;
610
611    typedef const _E* iterator;
612    typedef const _E* const_iterator;
613
614    initializer_list() : __begin_(0), __size_(0) {}
615
616    size_t    size()  const {return __size_;}
617    const _E* begin() const {return __begin_;}
618    const _E* end()   const {return __begin_ + __size_;}
619  };
620
621  template <bool, class _Tp = void> struct enable_if {};
622  template <class _Tp> struct enable_if<true, _Tp> {typedef _Tp type;};
623
624  template <class _Tp, _Tp __v>
625  struct integral_constant
626  {
627      static const _Tp      value = __v;
628      typedef _Tp               value_type;
629      typedef integral_constant type;
630
631     operator value_type() const {return value;}
632
633     value_type operator ()() const {return value;}
634  };
635
636  template <class _Tp, _Tp __v>
637  const _Tp integral_constant<_Tp, __v>::value;
638
639    template <class _Tp, class _Arg>
640    struct is_trivially_assignable
641      : integral_constant<bool, __is_trivially_assignable(_Tp, _Arg)>
642    {
643    };
644
645  typedef integral_constant<bool,true>  true_type;
646  typedef integral_constant<bool,false> false_type;
647
648  template <class _Tp> struct is_const            : public false_type {};
649  template <class _Tp> struct is_const<_Tp const> : public true_type {};
650
651  template <class _Tp> struct  is_reference        : public false_type {};
652  template <class _Tp> struct  is_reference<_Tp&>  : public true_type {};
653
654  template <class _Tp, class _Up> struct  is_same           : public false_type {};
655  template <class _Tp>            struct  is_same<_Tp, _Tp> : public true_type {};
656
657  template <class _Tp, bool = is_const<_Tp>::value || is_reference<_Tp>::value    >
658  struct __add_const             {typedef _Tp type;};
659
660  template <class _Tp>
661  struct __add_const<_Tp, false> {typedef const _Tp type;};
662
663  template <class _Tp> struct add_const {typedef typename __add_const<_Tp>::type type;};
664
665  template <class _Tp> struct  remove_const            {typedef _Tp type;};
666  template <class _Tp> struct  remove_const<const _Tp> {typedef _Tp type;};
667
668  template <class _Tp> struct  add_lvalue_reference    {typedef _Tp& type;};
669
670  template <class _Tp> struct is_trivially_copy_assignable
671      : public is_trivially_assignable<typename add_lvalue_reference<_Tp>::type,
672            typename add_lvalue_reference<typename add_const<_Tp>::type>::type> {};
673
674    template<class InputIter, class OutputIter>
675    OutputIter __copy(InputIter II, InputIter IE, OutputIter OI) {
676      while (II != IE)
677        *OI++ = *II++;
678
679      return OI;
680    }
681
682  template <class _Tp, class _Up>
683  inline
684  typename enable_if
685  <
686      is_same<typename remove_const<_Tp>::type, _Up>::value &&
687      is_trivially_copy_assignable<_Up>::value,
688      _Up*
689  >::type __copy(_Tp* __first, _Tp* __last, _Up* __result) {
690      size_t __n = __last - __first;
691
692      if (__n > 0)
693        memmove(__result, __first, __n * sizeof(_Up));
694
695      return __result + __n;
696    }
697
698  template<class InputIter, class OutputIter>
699  OutputIter copy(InputIter II, InputIter IE, OutputIter OI) {
700    return __copy(II, IE, OI);
701  }
702
703  template <class _BidirectionalIterator, class _OutputIterator>
704  inline
705  _OutputIterator
706  __copy_backward(_BidirectionalIterator __first, _BidirectionalIterator __last,
707                  _OutputIterator __result)
708  {
709      while (__first != __last)
710          *--__result = *--__last;
711      return __result;
712  }
713
714  template <class _Tp, class _Up>
715  inline
716  typename enable_if
717  <
718      is_same<typename remove_const<_Tp>::type, _Up>::value &&
719      is_trivially_copy_assignable<_Up>::value,
720      _Up*
721  >::type __copy_backward(_Tp* __first, _Tp* __last, _Up* __result) {
722      size_t __n = __last - __first;
723
724    if (__n > 0)
725    {
726        __result -= __n;
727        memmove(__result, __first, __n * sizeof(_Up));
728    }
729    return __result;
730  }
731
732  template<class InputIter, class OutputIter>
733  OutputIter copy_backward(InputIter II, InputIter IE, OutputIter OI) {
734    return __copy_backward(II, IE, OI);
735  }
736}
737
738template <class BidirectionalIterator, class Distance>
739void __advance (BidirectionalIterator& it, Distance n,
740                std::bidirectional_iterator_tag) {
741  if (n >= 0) while(n-- > 0) ++it; else while (n++<0) --it;
742}
743
744template <class RandomAccessIterator, class Distance>
745void __advance (RandomAccessIterator& it, Distance n,
746                std::random_access_iterator_tag) {
747  it += n;
748}
749
750namespace std {
751  template <class InputIterator, class Distance>
752  void advance (InputIterator& it, Distance n) {
753    __advance(it, n, typename InputIterator::iterator_category());
754  }
755
756  template <class BidirectionalIterator>
757  BidirectionalIterator
758  prev (BidirectionalIterator it,
759        typename iterator_traits<BidirectionalIterator>::difference_type n =
760        1) {
761    advance(it, -n);
762    return it;
763  }
764
765  template <class InputIterator, class T>
766  InputIterator find(InputIterator first, InputIterator last, const T &val);
767
768  template <class ForwardIterator1, class ForwardIterator2>
769  ForwardIterator1 find_first_of(ForwardIterator1 first1,
770                                 ForwardIterator1 last1,
771                                 ForwardIterator2 first2,
772                                 ForwardIterator2 last2);
773
774  template <class InputIterator, class OutputIterator>
775  OutputIterator copy(InputIterator first, InputIterator last,
776                      OutputIterator result);
777
778}
779
780#if __cplusplus >= 201103L
781namespace std {
782  template <typename T> // TODO: Implement the stub for deleter.
783  class unique_ptr {
784  public:
785    unique_ptr(const unique_ptr &) = delete;
786    unique_ptr(unique_ptr &&);
787
788    T *get() const;
789
790    typename std::add_lvalue_reference<T>::type operator*() const;
791    T *operator->() const;
792  };
793}
794#endif
795
796#ifdef TEST_INLINABLE_ALLOCATORS
797namespace std {
798  void *malloc(size_t);
799  void free(void *);
800}
801void* operator new(std::size_t size, const std::nothrow_t&) throw() { return std::malloc(size); }
802void* operator new[](std::size_t size, const std::nothrow_t&) throw() { return std::malloc(size); }
803void operator delete(void* ptr, const std::nothrow_t&) throw() { std::free(ptr); }
804void operator delete[](void* ptr, const std::nothrow_t&) throw() { std::free(ptr); }
805#else
806void* operator new(std::size_t, const std::nothrow_t&) throw();
807void* operator new[](std::size_t, const std::nothrow_t&) throw();
808void operator delete(void*, const std::nothrow_t&) throw();
809void operator delete[](void*, const std::nothrow_t&) throw();
810#endif
811
812void* operator new (std::size_t size, void* ptr) throw() { return ptr; };
813void* operator new[] (std::size_t size, void* ptr) throw() { return ptr; };
814void operator delete (void* ptr, void*) throw() {};
815void operator delete[] (void* ptr, void*) throw() {};
816
817namespace __cxxabiv1 {
818extern "C" {
819extern char *__cxa_demangle(const char *mangled_name,
820                            char *output_buffer,
821                            size_t *length,
822                            int *status);
823}}
824namespace abi = __cxxabiv1;
825
826namespace std {
827  template<class ForwardIt>
828  bool is_sorted(ForwardIt first, ForwardIt last);
829
830  template <class RandomIt>
831  void nth_element(RandomIt first, RandomIt nth, RandomIt last);
832
833  template<class RandomIt>
834  void partial_sort(RandomIt first, RandomIt middle, RandomIt last);
835
836  template<class RandomIt>
837  void sort (RandomIt first, RandomIt last);
838
839  template<class RandomIt>
840  void stable_sort(RandomIt first, RandomIt last);
841
842  template<class BidirIt, class UnaryPredicate>
843  BidirIt partition(BidirIt first, BidirIt last, UnaryPredicate p);
844
845  template<class BidirIt, class UnaryPredicate>
846  BidirIt stable_partition(BidirIt first, BidirIt last, UnaryPredicate p);
847}
848
CodeThinker, Enjoy your reading code