OSDN Git Service

5a8b27e3d6401e4e5d8707064796fe5ffd64620b
[pf3gnuchains/gcc-fork.git] / libstdc++-v3 / include / bits / forward_list.tcc
1 // <forward_list.tcc> -*- C++ -*-
2
3 // Copyright (C) 2008, 2009, 2010 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 /** @file forward_list.tcc
26  *  This is a Standard C++ Library header.
27  */
28
29 #ifndef _FORWARD_LIST_TCC
30 #define _FORWARD_LIST_TCC 1
31
32 _GLIBCXX_BEGIN_NAMESPACE(std)
33
34   template<typename _Tp, typename _Alloc>
35     _Fwd_list_base<_Tp, _Alloc>::
36     _Fwd_list_base(const _Fwd_list_base& __lst, const _Alloc& __a)
37     : _M_impl(__a)
38     {
39       this->_M_impl._M_head._M_next = 0;
40       _Fwd_list_node_base* __to = &this->_M_impl._M_head;
41       _Node* __curr = static_cast<_Node*>(__lst._M_impl._M_head._M_next);
42
43       while (__curr)
44         {
45           __to->_M_next = _M_create_node(__curr->_M_value);
46           __to = __to->_M_next;
47           __curr = static_cast<_Node*>(__curr->_M_next);
48         }
49     }
50
51   template<typename _Tp, typename _Alloc>
52     template<typename... _Args>
53       _Fwd_list_node_base*
54       _Fwd_list_base<_Tp, _Alloc>::
55       _M_insert_after(const_iterator __pos, _Args&&... __args)
56       {
57         _Fwd_list_node_base* __to
58           = const_cast<_Fwd_list_node_base*>(__pos._M_node);
59         _Node* __thing = _M_create_node(std::forward<_Args>(__args)...);
60         __thing->_M_next = __to->_M_next;
61         __to->_M_next = __thing;
62         return __to->_M_next;
63       }
64
65   template<typename _Tp, typename _Alloc>
66     void
67     _Fwd_list_base<_Tp, _Alloc>::
68     _M_erase_after(_Fwd_list_node_base* __pos)
69     {
70       _Node* __curr = static_cast<_Node*>(__pos->_M_next);
71       __pos->_M_next = __curr->_M_next;
72       _M_get_Node_allocator().destroy(__curr);
73       _M_put_node(__curr);
74     }
75
76   template<typename _Tp, typename _Alloc>
77     void
78     _Fwd_list_base<_Tp, _Alloc>::
79     _M_erase_after(_Fwd_list_node_base* __pos, 
80                    _Fwd_list_node_base* __last)
81     {
82       _Node* __curr = static_cast<_Node*>(__pos->_M_next);
83       while (__curr != __last)
84         {
85           _Node* __temp = __curr;
86           __curr = static_cast<_Node*>(__curr->_M_next);
87           _M_get_Node_allocator().destroy(__temp);
88           _M_put_node(__temp);
89         }
90       __pos->_M_next = __last;
91     }
92   
93   // Called by the range constructor to implement [23.1.1]/9
94   template<typename _Tp, typename _Alloc>
95     template<typename _InputIterator>
96       void
97       forward_list<_Tp, _Alloc>::
98       _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
99                              __false_type)
100       {
101         _Node_base* __to = &this->_M_impl._M_head;
102         for (; __first != __last; ++__first)
103           {
104             __to->_M_next = this->_M_create_node(*__first);
105             __to = __to->_M_next;
106           }
107       }
108
109   // Called by forward_list(n,v,a), and the range constructor
110   // when it turns out to be the same thing.
111   template<typename _Tp, typename _Alloc>
112     void
113     forward_list<_Tp, _Alloc>::
114     _M_fill_initialize(size_type __n, const value_type& __value)
115     {
116       _Node_base* __to = &this->_M_impl._M_head;
117       for (; __n > 0; --__n)
118         {
119           __to->_M_next = this->_M_create_node(__value);
120           __to = __to->_M_next;
121         }
122     }
123
124   template<typename _Tp, typename _Alloc>
125     forward_list<_Tp, _Alloc>::
126     forward_list(size_type __n)
127     : _Base()
128     {
129       _Node_base* __to = &this->_M_impl._M_head;
130       for (; __n > 0; --__n)
131         {
132           __to->_M_next = this->_M_create_node();
133           __to = __to->_M_next;
134         }
135     }
136
137   template<typename _Tp, typename _Alloc>
138     forward_list<_Tp, _Alloc>&
139     forward_list<_Tp, _Alloc>::
140     operator=(const forward_list& __list)
141     {
142       if (&__list != this)
143         {
144           iterator __prev1 = before_begin();
145           iterator __curr1 = begin();
146           iterator __last1 = end();
147           const_iterator __first2 = __list.cbegin();
148           const_iterator __last2 = __list.cend();
149           while (__curr1 != __last1 && __first2 != __last2)
150             {
151               *__curr1 = *__first2;
152               ++__prev1;
153               ++__curr1;
154               ++__first2;
155             }
156           if (__first2 == __last2)
157             erase_after(__prev1, __last1);
158           else
159             insert_after(__prev1, __first2, __last2);
160         }
161       return *this;
162     }
163
164   template<typename _Tp, typename _Alloc>
165     void
166     forward_list<_Tp, _Alloc>::
167     resize(size_type __sz)
168     {
169       iterator __k = before_begin();
170
171       size_type __len = 0;
172       while (__k._M_next() != end() && __len < __sz)
173         {
174           ++__k;
175           ++__len;
176         }
177       if (__len == __sz)
178         erase_after(__k, end());
179       else
180         {
181           forward_list __tmp(__sz - __len);
182           splice_after(__k, std::move(__tmp));
183         }
184     }
185
186   template<typename _Tp, typename _Alloc>
187     void
188     forward_list<_Tp, _Alloc>::
189     resize(size_type __sz, value_type __val)
190     {
191       iterator __k = before_begin();
192
193       size_type __len = 0;
194       while (__k._M_next() != end() && __len < __sz)
195         {
196           ++__k;
197           ++__len;
198         }
199       if (__len == __sz)
200         erase_after(__k, end());
201       else
202         insert_after(__k, __sz - __len, __val);
203     }
204
205   template<typename _Tp, typename _Alloc>
206     typename forward_list<_Tp, _Alloc>::iterator
207     forward_list<_Tp, _Alloc>::
208     _M_splice_after(const_iterator __pos, forward_list&& __list)
209     {
210       if (!__list.empty() && &__list != this)
211         {
212           _Node_base* __tmp = const_cast<_Node_base*>(__pos._M_node);
213           const_iterator __before = __list.cbefore_begin();
214           __tmp->_M_transfer_after(const_cast<_Node_base*>(__before._M_node));
215         }
216     }
217
218   template<typename _Tp, typename _Alloc>
219     void
220     forward_list<_Tp, _Alloc>::
221     splice_after(const_iterator __pos, forward_list&&,
222                  const_iterator __before, const_iterator __last)
223     {
224       _Node_base* __tmp = const_cast<_Node_base*>(__pos._M_node);
225       __tmp->_M_transfer_after(const_cast<_Node_base*>(__before._M_node),
226                                const_cast<_Node_base*>(__last._M_node));
227     }
228
229   template<typename _Tp, typename _Alloc>
230     void
231     forward_list<_Tp, _Alloc>::
232     remove(const _Tp& __val)
233     {
234       _Node* __curr = static_cast<_Node*>(&this->_M_impl._M_head);
235       while (_Node* __temp = static_cast<_Node*>(__curr->_M_next))
236         {
237           if (__temp->_M_value == __val)
238             this->_M_erase_after(__curr);
239           else
240             __curr = static_cast<_Node*>(__curr->_M_next);
241         }
242     }
243
244   template<typename _Tp, typename _Alloc>
245     template<typename _Pred>
246       void
247       forward_list<_Tp, _Alloc>::
248       remove_if(_Pred __pred)
249       {
250         _Node* __curr = static_cast<_Node*>(&this->_M_impl._M_head);
251         while (_Node* __temp = static_cast<_Node*>(__curr->_M_next))
252           {
253             if (__pred(__temp->_M_value))
254               this->_M_erase_after(__curr);
255             else
256               __curr = static_cast<_Node*>(__curr->_M_next);
257           }
258       }
259
260   template<typename _Tp, typename _Alloc>
261     template<typename _BinPred>
262       void
263       forward_list<_Tp, _Alloc>::
264       unique(_BinPred __binary_pred)
265       {
266         iterator __first = begin();
267         iterator __last = end();
268         if (__first == __last)
269           return;
270         iterator __next = __first;
271         while (++__next != __last)
272         {
273           if (__binary_pred(*__first, *__next))
274             erase_after(__first);
275           else
276             __first = __next;
277           __next = __first;
278         }
279       }
280
281   template<typename _Tp, typename _Alloc>
282     template<typename _Comp>
283       void
284       forward_list<_Tp, _Alloc>::
285       merge(forward_list&& __list, _Comp __comp)
286       {
287         _Node_base* __node = &this->_M_impl._M_head;
288         while (__node->_M_next && __list._M_impl._M_head._M_next)
289           {
290             if (__comp(static_cast<_Node*>
291                        (__list._M_impl._M_head._M_next)->_M_value,
292                        static_cast<_Node*>
293                        (__node->_M_next)->_M_value))
294               __node->_M_transfer_after(&__list._M_impl._M_head,
295                                         __list._M_impl._M_head._M_next);
296             __node = __node->_M_next;
297           }
298         if (__list._M_impl._M_head._M_next)
299           {
300             __node->_M_next = __list._M_impl._M_head._M_next;
301             __list._M_impl._M_head._M_next = 0;
302           }
303       }
304
305   template<typename _Tp, typename _Alloc>
306     bool
307     operator==(const forward_list<_Tp, _Alloc>& __lx,
308                const forward_list<_Tp, _Alloc>& __ly)
309     {
310       //  We don't have size() so we need to walk through both lists
311       //  making sure both iterators are valid.
312       auto __ix = __lx.cbegin();
313       auto __iy = __ly.cbegin();
314       while (__ix != __lx.cend() && __iy != __ly.cend())
315         {
316           if (*__ix != *__iy)
317             return false;
318           ++__ix;
319           ++__iy;
320         }
321       if (__ix == __lx.cend() && __iy == __ly.cend())
322         return true;
323       else
324         return false;
325     }
326
327   template<typename _Tp, class _Alloc>
328     template<typename _Comp>
329       void
330       forward_list<_Tp, _Alloc>::
331       sort(_Comp __comp)
332       {
333         // If `next' is 0, return immediately.
334         _Node* __list = static_cast<_Node*>(this->_M_impl._M_head._M_next);
335         if (!__list)
336           return;
337
338         unsigned long __insize = 1;
339
340         while (1)
341           {
342             _Node* __p = __list;
343             __list = 0;
344             _Node* __tail = 0;
345
346             // Count number of merges we do in this pass.
347             unsigned long __nmerges = 0;
348
349             while (__p)
350               {
351                 ++__nmerges;
352                 // There exists a merge to be done.
353                 // Step `insize' places along from p.
354                 _Node* __q = __p;
355                 unsigned long __psize = 0;
356                 for (unsigned long __i = 0; __i < __insize; ++__i)
357                   {
358                     ++__psize;
359                     __q = static_cast<_Node*>(__q->_M_next);
360                     if (!__q)
361                       break;
362                   }
363
364                 // If q hasn't fallen off end, we have two lists to merge.
365                 unsigned long __qsize = __insize;
366
367                 // Now we have two lists; merge them.
368                 while (__psize > 0 || (__qsize > 0 && __q))
369                   {
370                     // Decide whether next node of merge comes from p or q.
371                     _Node* __e;
372                     if (__psize == 0)
373                       {
374                         // p is empty; e must come from q.
375                         __e = __q;
376                         __q = static_cast<_Node*>(__q->_M_next);
377                         --__qsize;
378                       }
379                     else if (__qsize == 0 || !__q)
380                       {
381                         // q is empty; e must come from p.
382                         __e = __p;
383                         __p = static_cast<_Node*>(__p->_M_next);
384                         --__psize;
385                       }
386                     else if (__comp(__p->_M_value, __q->_M_value))
387                       {
388                         // First node of p is lower; e must come from p.
389                         __e = __p;
390                         __p = static_cast<_Node*>(__p->_M_next);
391                         --__psize;
392                       }
393                     else
394                       {
395                         // First node of q is lower; e must come from q.
396                         __e = __q;
397                         __q = static_cast<_Node*>(__q->_M_next);
398                         --__qsize;
399                       }
400
401                     // Add the next node to the merged list.
402                     if (__tail)
403                       __tail->_M_next = __e;
404                     else
405                       __list = __e;
406                     __tail = __e;
407                   }
408
409                 // Now p has stepped `insize' places along, and q has too.
410                 __p = __q;
411               }
412             __tail->_M_next = 0;
413
414             // If we have done only one merge, we're finished.
415             // Allow for nmerges == 0, the empty list case.
416             if (__nmerges <= 1)
417               {
418                 this->_M_impl._M_head._M_next = __list;
419                 return;
420               }
421
422             // Otherwise repeat, merging lists twice the size.
423             __insize *= 2;
424           }
425       }
426  
427 _GLIBCXX_END_NAMESPACE // namespace std
428
429 #endif /* _FORWARD_LIST_TCC */
430