OpenCores
URL https://opencores.org/ocsvn/altor32/altor32/trunk

Subversion Repositories altor32

[/] [altor32/] [trunk/] [gcc-x64/] [or1knd-elf/] [or1knd-elf/] [include/] [c++/] [4.8.0/] [bits/] [forward_list.tcc] - Blame information for rev 35

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 35 ultra_embe
//  -*- C++ -*-
2
 
3
// Copyright (C) 2008, 2009, 2010, 2011, 2012 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
// .
24
 
25
/** @file bits/forward_list.tcc
26
 *  This is an internal header file, included by other library headers.
27
 *  Do not attempt to use it directly. @headername{forward_list}
28
 */
29
 
30
#ifndef _FORWARD_LIST_TCC
31
#define _FORWARD_LIST_TCC 1
32
 
33
namespace std _GLIBCXX_VISIBILITY(default)
34
{
35
_GLIBCXX_BEGIN_NAMESPACE_CONTAINER
36
 
37
  template
38
    _Fwd_list_base<_Tp, _Alloc>::
39
    _Fwd_list_base(_Fwd_list_base&& __lst, const _Node_alloc_type& __a)
40
    : _M_impl(__a)
41
    {
42
      if (__lst._M_get_Node_allocator() == __a)
43
        {
44
          this->_M_impl._M_head._M_next = __lst._M_impl._M_head._M_next;
45
          __lst._M_impl._M_head._M_next = 0;
46
        }
47
      else
48
        {
49
          this->_M_impl._M_head._M_next = 0;
50
          _Fwd_list_node_base* __to = &this->_M_impl._M_head;
51
          _Node* __curr = static_cast<_Node*>(__lst._M_impl._M_head._M_next);
52
 
53
          while (__curr)
54
            {
55
              __to->_M_next =
56
                _M_create_node(std::move_if_noexcept(*__curr->_M_valptr()));
57
              __to = __to->_M_next;
58
              __curr = static_cast<_Node*>(__curr->_M_next);
59
            }
60
        }
61
    }
62
 
63
  template
64
    template
65
      _Fwd_list_node_base*
66
      _Fwd_list_base<_Tp, _Alloc>::
67
      _M_insert_after(const_iterator __pos, _Args&&... __args)
68
      {
69
        _Fwd_list_node_base* __to
70
          = const_cast<_Fwd_list_node_base*>(__pos._M_node);
71
        _Node* __thing = _M_create_node(std::forward<_Args>(__args)...);
72
        __thing->_M_next = __to->_M_next;
73
        __to->_M_next = __thing;
74
        return __to->_M_next;
75
      }
76
 
77
  template
78
    _Fwd_list_node_base*
79
    _Fwd_list_base<_Tp, _Alloc>::
80
    _M_erase_after(_Fwd_list_node_base* __pos)
81
    {
82
      _Node* __curr = static_cast<_Node*>(__pos->_M_next);
83
      __pos->_M_next = __curr->_M_next;
84
      _Tp_alloc_type __a(_M_get_Node_allocator());
85
      allocator_traits<_Tp_alloc_type>::destroy(__a, __curr->_M_valptr());
86
      __curr->~_Node();
87
      _M_put_node(__curr);
88
      return __pos->_M_next;
89
    }
90
 
91
  template
92
    _Fwd_list_node_base*
93
    _Fwd_list_base<_Tp, _Alloc>::
94
    _M_erase_after(_Fwd_list_node_base* __pos,
95
                   _Fwd_list_node_base* __last)
96
    {
97
      _Node* __curr = static_cast<_Node*>(__pos->_M_next);
98
      while (__curr != __last)
99
        {
100
          _Node* __temp = __curr;
101
          __curr = static_cast<_Node*>(__curr->_M_next);
102
          _Tp_alloc_type __a(_M_get_Node_allocator());
103
          allocator_traits<_Tp_alloc_type>::destroy(__a, __temp->_M_valptr());
104
          __temp->~_Node();
105
          _M_put_node(__temp);
106
        }
107
      __pos->_M_next = __last;
108
      return __last;
109
    }
110
 
111
  // Called by the range constructor to implement [23.3.4.2]/9
112
  template
113
    template
114
      void
115
      forward_list<_Tp, _Alloc>::
116
      _M_range_initialize(_InputIterator __first, _InputIterator __last)
117
      {
118
        _Node_base* __to = &this->_M_impl._M_head;
119
        for (; __first != __last; ++__first)
120
          {
121
            __to->_M_next = this->_M_create_node(*__first);
122
            __to = __to->_M_next;
123
          }
124
      }
125
 
126
  // Called by forward_list(n,v,a).
127
  template
128
    void
129
    forward_list<_Tp, _Alloc>::
130
    _M_fill_initialize(size_type __n, const value_type& __value)
131
    {
132
      _Node_base* __to = &this->_M_impl._M_head;
133
      for (; __n; --__n)
134
        {
135
          __to->_M_next = this->_M_create_node(__value);
136
          __to = __to->_M_next;
137
        }
138
    }
139
 
140
  template
141
    void
142
    forward_list<_Tp, _Alloc>::
143
    _M_default_initialize(size_type __n)
144
    {
145
      _Node_base* __to = &this->_M_impl._M_head;
146
      for (; __n; --__n)
147
        {
148
          __to->_M_next = this->_M_create_node();
149
          __to = __to->_M_next;
150
        }
151
    }
152
 
153
  template
154
    forward_list<_Tp, _Alloc>&
155
    forward_list<_Tp, _Alloc>::
156
    operator=(const forward_list& __list)
157
    {
158
      if (&__list != this)
159
        {
160
          if (_Node_alloc_traits::_S_propagate_on_copy_assign())
161
            {
162
              auto& __this_alloc = this->_M_get_Node_allocator();
163
              auto& __that_alloc = __list._M_get_Node_allocator();
164
              if (!_Node_alloc_traits::_S_always_equal()
165
                  && __this_alloc != __that_alloc)
166
                {
167
                  // replacement allocator cannot free existing storage
168
                  clear();
169
                }
170
              std::__alloc_on_copy(__this_alloc, __that_alloc);
171
            }
172
          assign(__list.cbegin(), __list.cend());
173
        }
174
      return *this;
175
    }
176
 
177
  template
178
    void
179
    forward_list<_Tp, _Alloc>::
180
    _M_default_insert_after(const_iterator __pos, size_type __n)
181
    {
182
      const_iterator __saved_pos = __pos;
183
      __try
184
        {
185
          for (; __n; --__n)
186
            __pos = emplace_after(__pos);
187
        }
188
      __catch(...)
189
        {
190
          erase_after(__saved_pos, ++__pos);
191
          __throw_exception_again;
192
        }
193
    }
194
 
195
  template
196
    void
197
    forward_list<_Tp, _Alloc>::
198
    resize(size_type __sz)
199
    {
200
      iterator __k = before_begin();
201
 
202
      size_type __len = 0;
203
      while (__k._M_next() != end() && __len < __sz)
204
        {
205
          ++__k;
206
          ++__len;
207
        }
208
      if (__len == __sz)
209
        erase_after(__k, end());
210
      else
211
        _M_default_insert_after(__k, __sz - __len);
212
    }
213
 
214
  template
215
    void
216
    forward_list<_Tp, _Alloc>::
217
    resize(size_type __sz, const value_type& __val)
218
    {
219
      iterator __k = before_begin();
220
 
221
      size_type __len = 0;
222
      while (__k._M_next() != end() && __len < __sz)
223
        {
224
          ++__k;
225
          ++__len;
226
        }
227
      if (__len == __sz)
228
        erase_after(__k, end());
229
      else
230
        insert_after(__k, __sz - __len, __val);
231
    }
232
 
233
  template
234
    typename forward_list<_Tp, _Alloc>::iterator
235
    forward_list<_Tp, _Alloc>::
236
    _M_splice_after(const_iterator __pos,
237
                    const_iterator __before, const_iterator __last)
238
    {
239
      _Node_base* __tmp = const_cast<_Node_base*>(__pos._M_node);
240
      _Node_base* __b = const_cast<_Node_base*>(__before._M_node);
241
      _Node_base* __end = __b;
242
 
243
      while (__end && __end->_M_next != __last._M_node)
244
        __end = __end->_M_next;
245
 
246
      if (__b != __end)
247
        return iterator(__tmp->_M_transfer_after(__b, __end));
248
      else
249
        return iterator(__tmp);
250
    }
251
 
252
  template
253
    void
254
    forward_list<_Tp, _Alloc>::
255
    splice_after(const_iterator __pos, forward_list&&,
256
                 const_iterator __i)
257
    {
258
      const_iterator __j = __i;
259
      ++__j;
260
 
261
      if (__pos == __i || __pos == __j)
262
        return;
263
 
264
      _Node_base* __tmp = const_cast<_Node_base*>(__pos._M_node);
265
      __tmp->_M_transfer_after(const_cast<_Node_base*>(__i._M_node),
266
                               const_cast<_Node_base*>(__j._M_node));
267
    }
268
 
269
  template
270
    typename forward_list<_Tp, _Alloc>::iterator
271
    forward_list<_Tp, _Alloc>::
272
    insert_after(const_iterator __pos, size_type __n, const _Tp& __val)
273
    {
274
      if (__n)
275
        {
276
          forward_list __tmp(__n, __val, get_allocator());
277
          return _M_splice_after(__pos, __tmp.before_begin(), __tmp.end());
278
        }
279
      else
280
        return iterator(const_cast<_Node_base*>(__pos._M_node));
281
    }
282
 
283
  template
284
    template
285
      typename forward_list<_Tp, _Alloc>::iterator
286
      forward_list<_Tp, _Alloc>::
287
      insert_after(const_iterator __pos,
288
                   _InputIterator __first, _InputIterator __last)
289
      {
290
        forward_list __tmp(__first, __last, get_allocator());
291
        if (!__tmp.empty())
292
          return _M_splice_after(__pos, __tmp.before_begin(), __tmp.end());
293
        else
294
          return iterator(const_cast<_Node_base*>(__pos._M_node));
295
      }
296
 
297
  template
298
    void
299
    forward_list<_Tp, _Alloc>::
300
    remove(const _Tp& __val)
301
    {
302
      _Node* __curr = static_cast<_Node*>(&this->_M_impl._M_head);
303
      _Node* __extra = 0;
304
 
305
      while (_Node* __tmp = static_cast<_Node*>(__curr->_M_next))
306
        {
307
          if (*__tmp->_M_valptr() == __val)
308
            {
309
              if (__tmp->_M_valptr() != std::__addressof(__val))
310
                {
311
                  this->_M_erase_after(__curr);
312
                  continue;
313
                }
314
              else
315
                __extra = __curr;
316
            }
317
          __curr = static_cast<_Node*>(__curr->_M_next);
318
        }
319
 
320
      if (__extra)
321
        this->_M_erase_after(__extra);
322
    }
323
 
324
  template
325
    template
326
      void
327
      forward_list<_Tp, _Alloc>::
328
      remove_if(_Pred __pred)
329
      {
330
        _Node* __curr = static_cast<_Node*>(&this->_M_impl._M_head);
331
        while (_Node* __tmp = static_cast<_Node*>(__curr->_M_next))
332
          {
333
            if (__pred(*__tmp->_M_valptr()))
334
              this->_M_erase_after(__curr);
335
            else
336
              __curr = static_cast<_Node*>(__curr->_M_next);
337
          }
338
      }
339
 
340
  template
341
    template
342
      void
343
      forward_list<_Tp, _Alloc>::
344
      unique(_BinPred __binary_pred)
345
      {
346
        iterator __first = begin();
347
        iterator __last = end();
348
        if (__first == __last)
349
          return;
350
        iterator __next = __first;
351
        while (++__next != __last)
352
        {
353
          if (__binary_pred(*__first, *__next))
354
            erase_after(__first);
355
          else
356
            __first = __next;
357
          __next = __first;
358
        }
359
      }
360
 
361
  template
362
    template
363
      void
364
      forward_list<_Tp, _Alloc>::
365
      merge(forward_list&& __list, _Comp __comp)
366
      {
367
        _Node_base* __node = &this->_M_impl._M_head;
368
        while (__node->_M_next && __list._M_impl._M_head._M_next)
369
          {
370
            if (__comp(*static_cast<_Node*>
371
                       (__list._M_impl._M_head._M_next)->_M_valptr(),
372
                       *static_cast<_Node*>
373
                       (__node->_M_next)->_M_valptr()))
374
              __node->_M_transfer_after(&__list._M_impl._M_head,
375
                                        __list._M_impl._M_head._M_next);
376
            __node = __node->_M_next;
377
          }
378
        if (__list._M_impl._M_head._M_next)
379
          {
380
            __node->_M_next = __list._M_impl._M_head._M_next;
381
            __list._M_impl._M_head._M_next = 0;
382
          }
383
      }
384
 
385
  template
386
    bool
387
    operator==(const forward_list<_Tp, _Alloc>& __lx,
388
               const forward_list<_Tp, _Alloc>& __ly)
389
    {
390
      //  We don't have size() so we need to walk through both lists
391
      //  making sure both iterators are valid.
392
      auto __ix = __lx.cbegin();
393
      auto __iy = __ly.cbegin();
394
      while (__ix != __lx.cend() && __iy != __ly.cend())
395
        {
396
          if (*__ix != *__iy)
397
            return false;
398
          ++__ix;
399
          ++__iy;
400
        }
401
      if (__ix == __lx.cend() && __iy == __ly.cend())
402
        return true;
403
      else
404
        return false;
405
    }
406
 
407
  template
408
    template
409
      void
410
      forward_list<_Tp, _Alloc>::
411
      sort(_Comp __comp)
412
      {
413
        // If `next' is 0, return immediately.
414
        _Node* __list = static_cast<_Node*>(this->_M_impl._M_head._M_next);
415
        if (!__list)
416
          return;
417
 
418
        unsigned long __insize = 1;
419
 
420
        while (1)
421
          {
422
            _Node* __p = __list;
423
            __list = 0;
424
            _Node* __tail = 0;
425
 
426
            // Count number of merges we do in this pass.
427
            unsigned long __nmerges = 0;
428
 
429
            while (__p)
430
              {
431
                ++__nmerges;
432
                // There exists a merge to be done.
433
                // Step `insize' places along from p.
434
                _Node* __q = __p;
435
                unsigned long __psize = 0;
436
                for (unsigned long __i = 0; __i < __insize; ++__i)
437
                  {
438
                    ++__psize;
439
                    __q = static_cast<_Node*>(__q->_M_next);
440
                    if (!__q)
441
                      break;
442
                  }
443
 
444
                // If q hasn't fallen off end, we have two lists to merge.
445
                unsigned long __qsize = __insize;
446
 
447
                // Now we have two lists; merge them.
448
                while (__psize > 0 || (__qsize > 0 && __q))
449
                  {
450
                    // Decide whether next node of merge comes from p or q.
451
                    _Node* __e;
452
                    if (__psize == 0)
453
                      {
454
                        // p is empty; e must come from q.
455
                        __e = __q;
456
                        __q = static_cast<_Node*>(__q->_M_next);
457
                        --__qsize;
458
                      }
459
                    else if (__qsize == 0 || !__q)
460
                      {
461
                        // q is empty; e must come from p.
462
                        __e = __p;
463
                        __p = static_cast<_Node*>(__p->_M_next);
464
                        --__psize;
465
                      }
466
                    else if (__comp(*__p->_M_valptr(), *__q->_M_valptr()))
467
                      {
468
                        // First node of p is lower; e must come from p.
469
                        __e = __p;
470
                        __p = static_cast<_Node*>(__p->_M_next);
471
                        --__psize;
472
                      }
473
                    else
474
                      {
475
                        // First node of q is lower; e must come from q.
476
                        __e = __q;
477
                        __q = static_cast<_Node*>(__q->_M_next);
478
                        --__qsize;
479
                      }
480
 
481
                    // Add the next node to the merged list.
482
                    if (__tail)
483
                      __tail->_M_next = __e;
484
                    else
485
                      __list = __e;
486
                    __tail = __e;
487
                  }
488
 
489
                // Now p has stepped `insize' places along, and q has too.
490
                __p = __q;
491
              }
492
            __tail->_M_next = 0;
493
 
494
            // If we have done only one merge, we're finished.
495
            // Allow for nmerges == 0, the empty list case.
496
            if (__nmerges <= 1)
497
              {
498
                this->_M_impl._M_head._M_next = __list;
499
                return;
500
              }
501
 
502
            // Otherwise repeat, merging lists twice the size.
503
            __insize *= 2;
504
          }
505
      }
506
 
507
_GLIBCXX_END_NAMESPACE_CONTAINER
508
} // namespace std
509
 
510
#endif /* _FORWARD_LIST_TCC */
511
 

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.