Subversion Repositories openrisc

//  -*- C++ -*-

// Copyright (C) 2008, 2009, 2010 Free Software Foundation, Inc.

//

// This file is part of the GNU ISO C++ Library.  This library is free

// software; you can redistribute it and/or modify it under the

// terms of the GNU General Public License as published by the

// Free Software Foundation; either version 3, or (at your option)

// any later version.

// This library is distributed in the hope that it will be useful,

// but WITHOUT ANY WARRANTY; without even the implied warranty of

// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

// GNU General Public License for more details.

// Under Section 7 of GPL version 3, you are granted additional

// permissions described in the GCC Runtime Library Exception, version

// 3.1, as published by the Free Software Foundation.

// You should have received a copy of the GNU General Public License and

// a copy of the GCC Runtime Library Exception along with this program;

// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see

// .

/** @file forward_list.tcc

 *  This is a Standard C++ Library header.

 */

#ifndef _FORWARD_LIST_TCC

#define _FORWARD_LIST_TCC 1

_GLIBCXX_BEGIN_NAMESPACE(std)

  template

    _Fwd_list_base<_Tp, _Alloc>::

    _Fwd_list_base(const _Fwd_list_base& __lst, const _Alloc& __a)

    : _M_impl(__a)

    {

      this->_M_impl._M_head._M_next = 0;

      _Fwd_list_node_base* __to = &this->_M_impl._M_head;

      _Node* __curr = static_cast<_Node*>(__lst._M_impl._M_head._M_next);

      while (__curr)

        {

          __to->_M_next = _M_create_node(__curr->_M_value);

          __to = __to->_M_next;

          __curr = static_cast<_Node*>(__curr->_M_next);

        }

    }

  template

    template

      _Fwd_list_node_base*

      _Fwd_list_base<_Tp, _Alloc>::

      _M_insert_after(const_iterator __pos, _Args&&... __args)

      {

        _Fwd_list_node_base* __to

          = const_cast<_Fwd_list_node_base*>(__pos._M_node);

        _Node* __thing = _M_create_node(std::forward<_Args>(__args)...);

        __thing->_M_next = __to->_M_next;

        __to->_M_next = __thing;

        return __to->_M_next;

      }

  template

    void

    _Fwd_list_base<_Tp, _Alloc>::

    _M_erase_after(_Fwd_list_node_base* __pos)

    {

      _Node* __curr = static_cast<_Node*>(__pos->_M_next);

      __pos->_M_next = __curr->_M_next;

      _M_get_Node_allocator().destroy(__curr);

      _M_put_node(__curr);

    }

  template

    void

    _Fwd_list_base<_Tp, _Alloc>::

    _M_erase_after(_Fwd_list_node_base* __pos,

                   _Fwd_list_node_base* __last)

    {

      _Node* __curr = static_cast<_Node*>(__pos->_M_next);

      while (__curr != __last)

        {

          _Node* __temp = __curr;

          __curr = static_cast<_Node*>(__curr->_M_next);

          _M_get_Node_allocator().destroy(__temp);

          _M_put_node(__temp);

        }

      __pos->_M_next = __last;

    }

  // Called by the range constructor to implement [23.1.1]/9

  template

    template

      void

      forward_list<_Tp, _Alloc>::

      _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,

                             __false_type)

      {

        _Node_base* __to = &this->_M_impl._M_head;

        for (; __first != __last; ++__first)

          {

            __to->_M_next = this->_M_create_node(*__first);

            __to = __to->_M_next;

          }

      }

  // Called by forward_list(n,v,a), and the range constructor

  // when it turns out to be the same thing.

  template

    void

    forward_list<_Tp, _Alloc>::

    _M_fill_initialize(size_type __n, const value_type& __value)

    {

      _Node_base* __to = &this->_M_impl._M_head;

      for (; __n > 0; --__n)

        {

          __to->_M_next = this->_M_create_node(__value);

          __to = __to->_M_next;

        }

    }

  template

    forward_list<_Tp, _Alloc>::

    forward_list(size_type __n)

    : _Base()

    {

      _Node_base* __to = &this->_M_impl._M_head;

      for (; __n > 0; --__n)

        {

          __to->_M_next = this->_M_create_node();

          __to = __to->_M_next;

        }

    }

  template

    forward_list<_Tp, _Alloc>&

    forward_list<_Tp, _Alloc>::

    operator=(const forward_list& __list)

    {

      if (&__list != this)

        {

          iterator __prev1 = before_begin();

          iterator __curr1 = begin();

          iterator __last1 = end();

          const_iterator __first2 = __list.cbegin();

          const_iterator __last2 = __list.cend();

          while (__curr1 != __last1 && __first2 != __last2)

            {

              *__curr1 = *__first2;

              ++__prev1;

              ++__curr1;

              ++__first2;

            }

          if (__first2 == __last2)

            erase_after(__prev1, __last1);

          else

            insert_after(__prev1, __first2, __last2);

        }

      return *this;

    }

  template

    void

    forward_list<_Tp, _Alloc>::

    resize(size_type __sz)

    {

      iterator __k = before_begin();

      size_type __len = 0;

      while (__k._M_next() != end() && __len < __sz)

        {

          ++__k;

          ++__len;

        }

      if (__len == __sz)

        erase_after(__k, end());

      else

        {

          forward_list __tmp(__sz - __len);

          splice_after(__k, std::move(__tmp));

        }

    }

  template

    void

    forward_list<_Tp, _Alloc>::

    resize(size_type __sz, value_type __val)

    {

      iterator __k = before_begin();

      size_type __len = 0;

      while (__k._M_next() != end() && __len < __sz)

        {

          ++__k;

          ++__len;

        }

      if (__len == __sz)

        erase_after(__k, end());

      else

        insert_after(__k, __sz - __len, __val);

    }

  template

    typename forward_list<_Tp, _Alloc>::iterator

    forward_list<_Tp, _Alloc>::

    _M_splice_after(const_iterator __pos, forward_list&& __list)

    {

      _Node_base* __tmp = const_cast<_Node_base*>(__pos._M_node);

      iterator __before = __list.before_begin();

      return iterator(__tmp->_M_transfer_after(__before._M_node));

    }

  template

    void

    forward_list<_Tp, _Alloc>::

    splice_after(const_iterator __pos, forward_list&&,

                 const_iterator __before, const_iterator __last)

    {

      _Node_base* __tmp = const_cast<_Node_base*>(__pos._M_node);

      __tmp->_M_transfer_after(const_cast<_Node_base*>(__before._M_node),

                               const_cast<_Node_base*>(__last._M_node));

    }

  template

    typename forward_list<_Tp, _Alloc>::iterator

    forward_list<_Tp, _Alloc>::

    insert_after(const_iterator __pos, size_type __n, const _Tp& __val)

    {

      if (__n)

        {

          forward_list __tmp(__n, __val, this->_M_get_Node_allocator());

          return _M_splice_after(__pos, std::move(__tmp));

        }

      else

        return iterator(const_cast<_Node_base*>(__pos._M_node));

    }

  template

    template

      typename forward_list<_Tp, _Alloc>::iterator

      forward_list<_Tp, _Alloc>::

      insert_after(const_iterator __pos,

                   _InputIterator __first, _InputIterator __last)

      {

        forward_list __tmp(__first, __last, this->_M_get_Node_allocator());

        if (!__tmp.empty())

          return _M_splice_after(__pos, std::move(__tmp));

        else

          return iterator(const_cast<_Node_base*>(__pos._M_node));

      }

  template

    typename forward_list<_Tp, _Alloc>::iterator

    forward_list<_Tp, _Alloc>::

    insert_after(const_iterator __pos, std::initializer_list<_Tp> __il)

    {

      if (__il.size())

        {

          forward_list __tmp(__il, this->_M_get_Node_allocator());

          return _M_splice_after(__pos, std::move(__tmp));

        }

      else

        return iterator(const_cast<_Node_base*>(__pos._M_node));

    }

  template

    void

    forward_list<_Tp, _Alloc>::

    remove(const _Tp& __val)

    {

      _Node* __curr = static_cast<_Node*>(&this->_M_impl._M_head);

      while (_Node* __temp = static_cast<_Node*>(__curr->_M_next))

        {

          if (__temp->_M_value == __val)

            this->_M_erase_after(__curr);

          else

            __curr = static_cast<_Node*>(__curr->_M_next);

        }

    }

  template

    template

      void

      forward_list<_Tp, _Alloc>::

      remove_if(_Pred __pred)

      {

        _Node* __curr = static_cast<_Node*>(&this->_M_impl._M_head);

        while (_Node* __temp = static_cast<_Node*>(__curr->_M_next))

          {

            if (__pred(__temp->_M_value))

              this->_M_erase_after(__curr);

            else

              __curr = static_cast<_Node*>(__curr->_M_next);

          }

      }

  template

    template

      void

      forward_list<_Tp, _Alloc>::

      unique(_BinPred __binary_pred)

      {

        iterator __first = begin();

        iterator __last = end();

        if (__first == __last)

          return;

        iterator __next = __first;

        while (++__next != __last)

        {

          if (__binary_pred(*__first, *__next))

            erase_after(__first);

          else

            __first = __next;

          __next = __first;

        }

      }

  template

    template

      void

      forward_list<_Tp, _Alloc>::

      merge(forward_list&& __list, _Comp __comp)

      {

        _Node_base* __node = &this->_M_impl._M_head;

        while (__node->_M_next && __list._M_impl._M_head._M_next)

          {

            if (__comp(static_cast<_Node*>

                       (__list._M_impl._M_head._M_next)->_M_value,

                       static_cast<_Node*>

                       (__node->_M_next)->_M_value))

              __node->_M_transfer_after(&__list._M_impl._M_head,

                                        __list._M_impl._M_head._M_next);

            __node = __node->_M_next;

          }

        if (__list._M_impl._M_head._M_next)

          {

            __node->_M_next = __list._M_impl._M_head._M_next;

            __list._M_impl._M_head._M_next = 0;

          }

      }

  template

    bool

    operator==(const forward_list<_Tp, _Alloc>& __lx,

               const forward_list<_Tp, _Alloc>& __ly)

    {

      //  We don't have size() so we need to walk through both lists

      //  making sure both iterators are valid.

      auto __ix = __lx.cbegin();

      auto __iy = __ly.cbegin();

      while (__ix != __lx.cend() && __iy != __ly.cend())

        {

          if (*__ix != *__iy)

            return false;

          ++__ix;

          ++__iy;

        }

      if (__ix == __lx.cend() && __iy == __ly.cend())

        return true;

      else

        return false;

    }

  template

    template

      void

      forward_list<_Tp, _Alloc>::

      sort(_Comp __comp)

      {

        // If `next' is 0, return immediately.

        _Node* __list = static_cast<_Node*>(this->_M_impl._M_head._M_next);

        if (!__list)

          return;

        unsigned long __insize = 1;

        while (1)

          {

            _Node* __p = __list;

            __list = 0;

            _Node* __tail = 0;

            // Count number of merges we do in this pass.

            unsigned long __nmerges = 0;

            while (__p)

              {

                ++__nmerges;

                // There exists a merge to be done.

                // Step `insize' places along from p.

                _Node* __q = __p;

                unsigned long __psize = 0;

                for (unsigned long __i = 0; __i < __insize; ++__i)

                  {

                    ++__psize;

                    __q = static_cast<_Node*>(__q->_M_next);

                    if (!__q)

                      break;

                  }

                // If q hasn't fallen off end, we have two lists to merge.

                unsigned long __qsize = __insize;

                // Now we have two lists; merge them.

                while (__psize > 0 || (__qsize > 0 && __q))

                  {

                    // Decide whether next node of merge comes from p or q.

                    _Node* __e;

                    if (__psize == 0)

                      {

                        // p is empty; e must come from q.

                        __e = __q;

                        __q = static_cast<_Node*>(__q->_M_next);

                        --__qsize;

                      }

                    else if (__qsize == 0 || !__q)

                      {

                        // q is empty; e must come from p.

                        __e = __p;

                        __p = static_cast<_Node*>(__p->_M_next);

                        --__psize;

                      }

                    else if (__comp(__p->_M_value, __q->_M_value))

                      {

                        // First node of p is lower; e must come from p.

                        __e = __p;

                        __p = static_cast<_Node*>(__p->_M_next);

                        --__psize;

                      }

                    else

                      {

                        // First node of q is lower; e must come from q.

                        __e = __q;

                        __q = static_cast<_Node*>(__q->_M_next);

                        --__qsize;

                      }

                    // Add the next node to the merged list.

                    if (__tail)

                      __tail->_M_next = __e;

                    else

                      __list = __e;

                    __tail = __e;

                  }

                // Now p has stepped `insize' places along, and q has too.

                __p = __q;

              }

            __tail->_M_next = 0;

            // If we have done only one merge, we're finished.

            // Allow for nmerges == 0, the empty list case.

            if (__nmerges <= 1)

              {

                this->_M_impl._M_head._M_next = __list;

                return;

              }

            // Otherwise repeat, merging lists twice the size.

            __insize *= 2;

          }

      }

_GLIBCXX_END_NAMESPACE // namespace std

#endif /* _FORWARD_LIST_TCC */