Clang Project

include/c++/7/bits/list.tcc
1// List implementation (out of line) -*- C++ -*-
2
3// Copyright (C) 2001-2017 Free Software Foundation, Inc.
4//
5// This file is part of the GNU ISO C++ Library.  This library is free
6// software; you can redistribute it and/or modify it under the
7// terms of the GNU General Public License as published by the
8// Free Software Foundation; either version 3, or (at your option)
9// any later version.
10
11// This library is distributed in the hope that it will be useful,
12// but WITHOUT ANY WARRANTY; without even the implied warranty of
13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14// GNU General Public License for more details.
15
16// Under Section 7 of GPL version 3, you are granted additional
17// permissions described in the GCC Runtime Library Exception, version
18// 3.1, as published by the Free Software Foundation.
19
20// You should have received a copy of the GNU General Public License and
21// a copy of the GCC Runtime Library Exception along with this program;
22// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
23// <http://www.gnu.org/licenses/>.
24
25/*
26 *
27 * Copyright (c) 1994
28 * Hewlett-Packard Company
29 *
30 * Permission to use, copy, modify, distribute and sell this software
31 * and its documentation for any purpose is hereby granted without fee,
32 * provided that the above copyright notice appear in all copies and
33 * that both that copyright notice and this permission notice appear
34 * in supporting documentation.  Hewlett-Packard Company makes no
35 * representations about the suitability of this software for any
36 * purpose.  It is provided "as is" without express or implied warranty.
37 *
38 *
39 * Copyright (c) 1996,1997
40 * Silicon Graphics Computer Systems, Inc.
41 *
42 * Permission to use, copy, modify, distribute and sell this software
43 * and its documentation for any purpose is hereby granted without fee,
44 * provided that the above copyright notice appear in all copies and
45 * that both that copyright notice and this permission notice appear
46 * in supporting documentation.  Silicon Graphics makes no
47 * representations about the suitability of this software for any
48 * purpose.  It is provided "as is" without express or implied warranty.
49 */
50
51/** @file bits/list.tcc
52 *  This is an internal header file, included by other library headers.
53 *  Do not attempt to use it directly. @headername{list}
54 */
55
56#ifndef _LIST_TCC
57#define _LIST_TCC 1
58
59namespace std _GLIBCXX_VISIBILITY(default)
60{
61_GLIBCXX_BEGIN_NAMESPACE_CONTAINER
62
63  template<typename _Tp, typename _Alloc>
64    void
65    _List_base<_Tp, _Alloc>::
66    _M_clear() _GLIBCXX_NOEXCEPT
67    {
68      typedef _List_node<_Tp>  _Node;
69      __detail::_List_node_base* __cur = _M_impl._M_node._M_next;
70      while (__cur != &_M_impl._M_node)
71 {
72   _Node* __tmp = static_cast<_Node*>(__cur);
73   __cur = __tmp->_M_next;
74   _Tp* __val = __tmp->_M_valptr();
75#if __cplusplus >= 201103L
76   _Node_alloc_traits::destroy(_M_get_Node_allocator(), __val);
77#else
78   _Tp_alloc_type(_M_get_Node_allocator()).destroy(__val);
79#endif
80   _M_put_node(__tmp);
81 }
82    }
83
84#if __cplusplus >= 201103L
85  template<typename _Tp, typename _Alloc>
86    template<typename... _Args>
87      typename list<_Tp, _Alloc>::iterator
88      list<_Tp, _Alloc>::
89      emplace(const_iterator __position, _Args&&... __args)
90      {
91 _Node* __tmp = _M_create_node(std::forward<_Args>(__args)...);
92 __tmp->_M_hook(__position._M_const_cast()._M_node);
93 this->_M_inc_size(1);
94 return iterator(__tmp);
95      }
96#endif
97
98  template<typename _Tp, typename _Alloc>
99    typename list<_Tp, _Alloc>::iterator
100    list<_Tp, _Alloc>::
101#if __cplusplus >= 201103L
102    insert(const_iterator __position, const value_type& __x)
103#else
104    insert(iterator __position, const value_type& __x)
105#endif
106    {
107      _Node* __tmp = _M_create_node(__x);
108      __tmp->_M_hook(__position._M_const_cast()._M_node);
109      this->_M_inc_size(1);
110      return iterator(__tmp);
111    }
112
113#if __cplusplus >= 201103L
114  template<typename _Tp, typename _Alloc>
115    typename list<_Tp, _Alloc>::iterator
116    list<_Tp, _Alloc>::
117    insert(const_iterator __position, size_type __n, const value_type& __x)
118    {
119      if (__n)
120 {
121   list __tmp(__n, __x, get_allocator());
122   iterator __it = __tmp.begin();
123   splice(__position, __tmp);
124   return __it;
125 }
126      return __position._M_const_cast();
127    }
128
129  template<typename _Tp, typename _Alloc>
130    template<typename _InputIterator, typename>
131      typename list<_Tp, _Alloc>::iterator
132      list<_Tp, _Alloc>::
133      insert(const_iterator __position, _InputIterator __first,
134      _InputIterator __last)
135      {
136 list __tmp(__first, __last, get_allocator());
137 if (!__tmp.empty())
138   {
139     iterator __it = __tmp.begin();
140     splice(__position, __tmp);
141     return __it;
142   }
143 return __position._M_const_cast();
144      }
145#endif
146
147  template<typename _Tp, typename _Alloc>
148    typename list<_Tp, _Alloc>::iterator
149    list<_Tp, _Alloc>::
150#if __cplusplus >= 201103L
151    erase(const_iterator __position) noexcept
152#else
153    erase(iterator __position)
154#endif
155    {
156      iterator __ret = iterator(__position._M_node->_M_next);
157      _M_erase(__position._M_const_cast());
158      return __ret;
159    }
160
161  // Return a const_iterator indicating the position to start inserting or
162  // erasing elements (depending whether the list is growing or shrinking),
163  // and set __new_size to the number of new elements that must be appended.
164  // Equivalent to the following, but performed optimally:
165  // if (__new_size < size()) {
166  //   __new_size = 0;
167  //   return std::next(begin(), __new_size);
168  // } else {
169  //   __newsize -= size();
170  //   return end();
171  // }
172  template<typename _Tp, typename _Alloc>
173    typename list<_Tp, _Alloc>::const_iterator
174    list<_Tp, _Alloc>::
175    _M_resize_pos(size_type& __new_size) const
176    {
177      const_iterator __i;
178#if _GLIBCXX_USE_CXX11_ABI
179      const size_type __len = size();
180      if (__new_size < __len)
181 {
182   if (__new_size <= __len / 2)
183     {
184       __i = begin();
185       std::advance(__i, __new_size);
186     }
187   else
188     {
189       __i = end();
190       ptrdiff_t __num_erase = __len - __new_size;
191       std::advance(__i, -__num_erase);
192     }
193   __new_size = 0;
194   return __i;
195 }
196      else
197 __i = end();
198#else
199      size_type __len = 0;
200      for (__i = begin(); __i != end() && __len < __new_size; ++__i, ++__len)
201        ;
202#endif
203      __new_size -= __len;
204      return __i;
205    }
206
207#if __cplusplus >= 201103L
208  template<typename _Tp, typename _Alloc>
209    void
210    list<_Tp, _Alloc>::
211    _M_default_append(size_type __n)
212    {
213      size_type __i = 0;
214      __try
215 {
216   for (; __i < __n; ++__i)
217     emplace_back();
218 }
219      __catch(...)
220 {
221   for (; __i; --__i)
222     pop_back();
223   __throw_exception_again;
224 }
225    }
226
227  template<typename _Tp, typename _Alloc>
228    void
229    list<_Tp, _Alloc>::
230    resize(size_type __new_size)
231    {
232      const_iterator __i = _M_resize_pos(__new_size);
233      if (__new_size)
234 _M_default_append(__new_size);
235      else
236        erase(__i, end());
237    }
238
239  template<typename _Tp, typename _Alloc>
240    void
241    list<_Tp, _Alloc>::
242    resize(size_type __new_size, const value_type& __x)
243    {
244      const_iterator __i = _M_resize_pos(__new_size);
245      if (__new_size)
246        insert(end(), __new_size, __x);
247      else
248        erase(__i, end());
249    }
250#else
251  template<typename _Tp, typename _Alloc>
252    void
253    list<_Tp, _Alloc>::
254    resize(size_type __new_size, value_type __x)
255    {
256      const_iterator __i = _M_resize_pos(__new_size);
257      if (__new_size)
258        insert(end(), __new_size, __x);
259      else
260        erase(__i._M_const_cast(), end());
261    }
262#endif
263
264  template<typename _Tp, typename _Alloc>
265    list<_Tp, _Alloc>&
266    list<_Tp, _Alloc>::
267    operator=(const list& __x)
268    {
269      if (this != std::__addressof(__x))
270 {
271#if __cplusplus >= 201103L
272   if (_Node_alloc_traits::_S_propagate_on_copy_assign())
273     {
274              auto& __this_alloc = this->_M_get_Node_allocator();
275              auto& __that_alloc = __x._M_get_Node_allocator();
276              if (!_Node_alloc_traits::_S_always_equal()
277           && __this_alloc != __that_alloc)
278         {
279   // replacement allocator cannot free existing storage
280   clear();
281 }
282       std::__alloc_on_copy(__this_alloc, __that_alloc);
283            }
284#endif
285   _M_assign_dispatch(__x.begin(), __x.end(), __false_type());
286 }
287      return *this;
288    }
289
290  template<typename _Tp, typename _Alloc>
291    void
292    list<_Tp, _Alloc>::
293    _M_fill_assign(size_type __n, const value_type& __val)
294    {
295      iterator __i = begin();
296      for (; __i != end() && __n > 0; ++__i, --__n)
297        *__i = __val;
298      if (__n > 0)
299        insert(end(), __n, __val);
300      else
301        erase(__i, end());
302    }
303
304  template<typename _Tp, typename _Alloc>
305    template <typename _InputIterator>
306      void
307      list<_Tp, _Alloc>::
308      _M_assign_dispatch(_InputIterator __first2, _InputIterator __last2,
309  __false_type)
310      {
311        iterator __first1 = begin();
312        iterator __last1 = end();
313        for (; __first1 != __last1 && __first2 != __last2;
314      ++__first1, ++__first2)
315          *__first1 = *__first2;
316        if (__first2 == __last2)
317          erase(__first1, __last1);
318        else
319          insert(__last1, __first2, __last2);
320      }
321
322  template<typename _Tp, typename _Alloc>
323    void
324    list<_Tp, _Alloc>::
325    remove(const value_type& __value)
326    {
327      iterator __first = begin();
328      iterator __last = end();
329      iterator __extra = __last;
330      while (__first != __last)
331 {
332   iterator __next = __first;
333   ++__next;
334   if (*__first == __value)
335     {
336       // _GLIBCXX_RESOLVE_LIB_DEFECTS
337       // 526. Is it undefined if a function in the standard changes
338       // in parameters?
339       if (std::__addressof(*__first) != std::__addressof(__value))
340 _M_erase(__first);
341       else
342 __extra = __first;
343     }
344   __first = __next;
345 }
346      if (__extra != __last)
347 _M_erase(__extra);
348    }
349
350  template<typename _Tp, typename _Alloc>
351    void
352    list<_Tp, _Alloc>::
353    unique()
354    {
355      iterator __first = begin();
356      iterator __last = end();
357      if (__first == __last)
358 return;
359      iterator __next = __first;
360      while (++__next != __last)
361 {
362   if (*__first == *__next)
363     _M_erase(__next);
364   else
365     __first = __next;
366   __next = __first;
367 }
368    }
369
370  template<typename _Tp, typename _Alloc>
371    void
372    list<_Tp, _Alloc>::
373#if __cplusplus >= 201103L
374    merge(list&& __x)
375#else
376    merge(list& __x)
377#endif
378    {
379      // _GLIBCXX_RESOLVE_LIB_DEFECTS
380      // 300. list::merge() specification incomplete
381      if (this != std::__addressof(__x))
382 {
383   _M_check_equal_allocators(__x);
384
385   iterator __first1 = begin();
386   iterator __last1 = end();
387   iterator __first2 = __x.begin();
388   iterator __last2 = __x.end();
389   const size_t __orig_size = __x.size();
390   __try {
391     while (__first1 != __last1 && __first2 != __last2)
392       if (*__first2 < *__first1)
393 {
394   iterator __next = __first2;
395   _M_transfer(__first1, __first2, ++__next);
396   __first2 = __next;
397 }
398       else
399 ++__first1;
400     if (__first2 != __last2)
401       _M_transfer(__last1, __first2, __last2);
402
403     this->_M_inc_size(__x._M_get_size());
404     __x._M_set_size(0);
405   }
406   __catch(...)
407     {
408       const size_t __dist = std::distance(__first2, __last2);
409       this->_M_inc_size(__orig_size - __dist);
410       __x._M_set_size(__dist);
411       __throw_exception_again;
412     }
413 }
414    }
415
416  template<typename _Tp, typename _Alloc>
417    template <typename _StrictWeakOrdering>
418      void
419      list<_Tp, _Alloc>::
420#if __cplusplus >= 201103L
421      merge(list&& __x, _StrictWeakOrdering __comp)
422#else
423      merge(list& __x, _StrictWeakOrdering __comp)
424#endif
425      {
426 // _GLIBCXX_RESOLVE_LIB_DEFECTS
427 // 300. list::merge() specification incomplete
428 if (this != std::__addressof(__x))
429   {
430     _M_check_equal_allocators(__x);
431
432     iterator __first1 = begin();
433     iterator __last1 = end();
434     iterator __first2 = __x.begin();
435     iterator __last2 = __x.end();
436     const size_t __orig_size = __x.size();
437     __try
438       {
439 while (__first1 != __last1 && __first2 != __last2)
440   if (__comp(*__first2, *__first1))
441     {
442       iterator __next = __first2;
443       _M_transfer(__first1, __first2, ++__next);
444       __first2 = __next;
445     }
446   else
447     ++__first1;
448 if (__first2 != __last2)
449   _M_transfer(__last1, __first2, __last2);
450
451 this->_M_inc_size(__x._M_get_size());
452 __x._M_set_size(0);
453       }
454     __catch(...)
455       {
456 const size_t __dist = std::distance(__first2, __last2);
457 this->_M_inc_size(__orig_size - __dist);
458 __x._M_set_size(__dist);
459 __throw_exception_again;
460       }
461   }
462      }
463
464  template<typename _Tp, typename _Alloc>
465    void
466    list<_Tp, _Alloc>::
467    sort()
468    {
469      // Do nothing if the list has length 0 or 1.
470      if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
471   && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
472      {
473        list __carry;
474        list __tmp[64];
475        list * __fill = __tmp;
476        list * __counter;
477 __try
478   {
479     do
480       {
481 __carry.splice(__carry.begin(), *this, begin());
482
483 for(__counter = __tmp;
484     __counter != __fill && !__counter->empty();
485     ++__counter)
486   {
487     __counter->merge(__carry);
488     __carry.swap(*__counter);
489   }
490 __carry.swap(*__counter);
491 if (__counter == __fill)
492   ++__fill;
493       }
494     while ( !empty() );
495
496     for (__counter = __tmp + 1; __counter != __fill; ++__counter)
497       __counter->merge(*(__counter - 1));
498     swap( *(__fill - 1) );
499   }
500 __catch(...)
501   {
502     this->splice(this->end(), __carry);
503     for (int __i = 0; __i < sizeof(__tmp)/sizeof(__tmp[0]); ++__i)
504       this->splice(this->end(), __tmp[__i]);
505     __throw_exception_again;
506   }
507      }
508    }
509
510  template<typename _Tp, typename _Alloc>
511    template <typename _Predicate>
512      void
513      list<_Tp, _Alloc>::
514      remove_if(_Predicate __pred)
515      {
516        iterator __first = begin();
517        iterator __last = end();
518        while (__first != __last)
519   {
520     iterator __next = __first;
521     ++__next;
522     if (__pred(*__first))
523       _M_erase(__first);
524     __first = __next;
525   }
526      }
527
528  template<typename _Tp, typename _Alloc>
529    template <typename _BinaryPredicate>
530      void
531      list<_Tp, _Alloc>::
532      unique(_BinaryPredicate __binary_pred)
533      {
534        iterator __first = begin();
535        iterator __last = end();
536        if (__first == __last)
537   return;
538        iterator __next = __first;
539        while (++__next != __last)
540   {
541     if (__binary_pred(*__first, *__next))
542       _M_erase(__next);
543     else
544       __first = __next;
545     __next = __first;
546   }
547      }
548
549  template<typename _Tp, typename _Alloc>
550    template <typename _StrictWeakOrdering>
551      void
552      list<_Tp, _Alloc>::
553      sort(_StrictWeakOrdering __comp)
554      {
555 // Do nothing if the list has length 0 or 1.
556 if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
557     && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
558   {
559     list __carry;
560     list __tmp[64];
561     list * __fill = __tmp;
562     list * __counter;
563     __try
564       {
565 do
566   {
567     __carry.splice(__carry.begin(), *this, begin());
568
569     for(__counter = __tmp;
570 __counter != __fill && !__counter->empty();
571 ++__counter)
572       {
573 __counter->merge(__carry, __comp);
574 __carry.swap(*__counter);
575       }
576     __carry.swap(*__counter);
577     if (__counter == __fill)
578       ++__fill;
579   }
580 while ( !empty() );
581
582 for (__counter = __tmp + 1; __counter != __fill; ++__counter)
583   __counter->merge(*(__counter - 1), __comp);
584 swap(*(__fill - 1));
585       }
586     __catch(...)
587       {
588 this->splice(this->end(), __carry);
589 for (int __i = 0; __i < sizeof(__tmp)/sizeof(__tmp[0]); ++__i)
590   this->splice(this->end(), __tmp[__i]);
591 __throw_exception_again;
592       }
593   }
594      }
595
596_GLIBCXX_END_NAMESPACE_CONTAINER
597} // namespace std
598
599#endif /* _LIST_TCC */
600
601
std::_List_base::_M_clear
std::list::emplace
std::list::insert
std::list::insert
std::list::insert
std::list::erase
std::list::_M_resize_pos
std::list::_M_default_append
std::list::resize
std::list::resize
std::list::_M_fill_assign
std::list::_M_assign_dispatch
std::list::remove
std::list::unique
std::list::merge
std::list::merge
std::list::sort
std::list::remove_if
std::list::unique
std::list::sort
CodeThinker, Enjoy your reading code