list.cc

Go to the documentation of this file.

 
_RWSTD_NAMESPACE (std) { 
 
template <class _TypeT, class _Allocator>
list<_TypeT, _Allocator>::
~list ()
{
    if (_C_node) {
        clear ();
        _C_put_node (_C_node);
        _RWSTD_NODE_LIST_FREE ();
    }
}
 
 
template <class _TypeT, class _Allocator>
typename list<_TypeT, _Allocator>::iterator 
list<_TypeT, _Allocator>::erase (iterator __first, iterator __last)
{
    _RWSTD_ASSERT_RANGE (begin (), __first);
    _RWSTD_ASSERT_RANGE (__first, __last);
 
    while (!(__first == __last)) {
        __first = erase (__first);
    }
      
    return __first;
}
 
 
#if !defined (_RWSTD_NO_LIST_NODE_BUFFER)
 
template <class _TypeT, class _Allocator>
void list<_TypeT, _Allocator>::_C_add_buffer (bool __is_list_empty)
{
    // empty list gets one node
    _RWSTD_SIZE_T __next_buffer_size = 1;
    if(!__is_list_empty) {
        if ((void*)_C_buflist) {
            __next_buffer_size = 
                _RWSTD_NEW_CAPACITY (list, this, _C_buflist->_C_bufsize);
        }
        else {
            __next_buffer_size = _RWSTD_NEW_CAPACITY (list, this, 0);
        }          
     }
    _C_buf_pointer __tmp = 
        _C_buf_alloc_type (*this).allocate (1, (void*)_C_buflist);
 
    _TRY {
        __tmp->_C_buffer = 
           _C_node_alloc_type (*this).allocate (__next_buffer_size,
                                                (void*)_C_last);
    }
    _CATCH (...) {
        _C_buf_alloc_type (*this).deallocate (__tmp, 1);
        _RETHROW;
    }
 
    __tmp->_C_next_buf = _C_buflist;
    __tmp->_C_bufsize  = __next_buffer_size;
 
    _C_buflist    = __tmp;
    _C_next_avail = _C_buflist->_C_buffer; 
    _C_last       = _C_next_avail + __next_buffer_size;
}
 
 
template <class _TypeT, class _Allocator>
void list<_TypeT, _Allocator>::_C_free_buffers ()
{
    while ((void*)_C_buflist) {
        _C_buf_pointer __tmp = _C_buflist;
        _C_buflist = _C_buflist->_C_next_buf;
        _C_node_alloc_type (*this).deallocate (__tmp->_C_buffer, 
                                               __tmp->_C_bufsize);
        _C_buf_alloc_type (*this).deallocate (__tmp, 1);
    }
    _C_free_list  = 0;
    _C_next_avail = 0;
    _C_last       = 0;
}
 
#endif // defined (_RWSTD_NO_LIST_NODE_BUFFER)
 
 
template <class _TypeT, class _Allocator>
void list<_TypeT, _Allocator>::_C_transfer (iterator __it, iterator __first, 
                                           iterator __last, list& __x)
{
    _RWSTD_ASSERT_RANGE (begin (), __it);
    _RWSTD_ASSERT_RANGE (__first, __last);
 
    if (this == &__x) {
        (*(_C_link_type ((*_ITER_NODE (__last))._C_prev)))._C_next =
            _ITER_NODE (__it);
        (*(_C_link_type ((*_ITER_NODE (__first))._C_prev)))._C_next =
            _ITER_NODE (__last);
        (*(_C_link_type ((*_ITER_NODE (__it))._C_prev)))._C_next =
            _ITER_NODE (__first);
        
        _C_link_type __tmp = _C_link_type ((*_ITER_NODE (__it))._C_prev);
        
        (*_ITER_NODE (__it))._C_prev    = (*_ITER_NODE (__last))._C_prev;
        (*_ITER_NODE (__last))._C_prev  = (*_ITER_NODE (__first))._C_prev; 
        (*_ITER_NODE (__first))._C_prev = __tmp;
    }
    else {
        insert (__it, __first, __last);
        __x.erase (__first, __last);
    }
}
 
 
template <class _TypeT, class _Allocator>
void list<_TypeT, _Allocator>::resize (size_type __size, _TypeT __val)
{
    if (__size > size ())
        insert (end (), __size - size (), __val);
    else if (__size < size ()) {
        iterator __tmp = begin ();
        advance (__tmp, __size);
        erase (__tmp, end ());
    }
}
 
 
template <class _TypeT, class _Allocator>
list<_TypeT, _Allocator>&
list<_TypeT, _Allocator>::operator= (const list<_TypeT, _Allocator>& __rhs)
{
    if (this != &__rhs) {
        iterator       __first1 = begin ();
        iterator       __last1  = end ();
        const_iterator __first2 = __rhs.begin ();
        const_iterator __last2  = __rhs.end ();
 
        for ( ; !(__first1 == __last1) && !(__first2 == __last2);
              ++__first1, ++__first2)
            *__first1 = *__first2;
 
        if (__first2 == __last2)
            erase (__first1, __last1);
        else
            insert (__last1, __first2, __last2);
    }
    return *this;
}
 
 
template <class _TypeT, class _Allocator>
void list<_TypeT, _Allocator>::splice (iterator __it, list &__x)
{
    // assert 23.2.2.4, p3
    _RWSTD_ASSERT (&__x != this);
    _RWSTD_ASSERT_RANGE (begin (), __it);
 
 
#if !defined (_RWSTD_NO_LIST_NODE_BUFFER)
    // linear complexity
    insert (__it, __x.begin (), __x.end ());
    __x.clear ();
#else
    if (get_allocator () == __x.get_allocator ()) {
 
        // constant complexity
 
        // relink `it' and the head of `x'
        (*(_C_link_type ((*_ITER_NODE (__it))._C_prev)))._C_next =
            __x._C_node->_C_next;
 
        __x._C_node->_C_next->_C_prev = (*_ITER_NODE (__it))._C_prev;
        (*_ITER_NODE (__it))._C_prev  = __x._C_node->_C_prev;
        __x._C_node->_C_prev->_C_next = _ITER_NODE (__it);
 
        // empty out `x'
        __x._C_node->_C_next =
        __x._C_node->_C_prev = __x._C_node;
 
        // adjust sizes
        _C_length     += __x._C_length;
        __x._C_length  = 0;
    }
    else {
        // linear complexity
        insert (__it, __x.begin (), __x.end ());
        __x.clear ();
    }
#endif // _RWSTD_NO_LIST_NODE_BUFFER
}
 
 
template <class _TypeT, class _Allocator>
void list<_TypeT, _Allocator>::splice (iterator __i, list &__x, iterator __j)
{
    _RWSTD_ASSERT_RANGE (begin (), __i);
    _RWSTD_ASSERT_RANGE (__x.begin (), __j);
    
    if (   !(__x.end () == __j)
        && !(__i == __j) && !(__i == ++iterator (__j))) {
 
#if !defined (_RWSTD_NO_LIST_NODE_BUFFER)
        // linear complexity
        insert (__i, *__j);
        __x.erase (__j);
#else
        if (get_allocator () == __x.get_allocator ()) {
 
            // constant complexity
 
            // relink `i' and `j'
            (*(_C_link_type ((*_ITER_NODE (__i))._C_prev)))._C_next =
                _ITER_NODE (__j);
 
            // save position before `i'
            _C_link_type __tmp = (*_ITER_NODE (__i))._C_prev;
 
            (*_ITER_NODE (__i))._C_prev = _ITER_NODE (__j);
            (*_ITER_NODE (__j))._C_prev->_C_next = (*_ITER_NODE (__j))._C_next;
            (*_ITER_NODE (__j))._C_next->_C_prev = (*_ITER_NODE (__j))._C_prev;
 
            (*_ITER_NODE (__j))._C_next = _ITER_NODE (__i);
            (*_ITER_NODE (__j))._C_prev = __tmp;
 
            // adjust sizes
            ++_C_length;
            --__x._C_length;
        }
        else {
            // linear complexity
            insert (__i, *__j);
            __x.erase (__j);
        }
#endif  //  _RWSTD_NO_LIST_NODE_BUFFER
    }
}
 
 
template <class _TypeT, class _Allocator>
void list<_TypeT, _Allocator>::
splice (iterator __i, list &__x, iterator __j, iterator __k)
{
    _RWSTD_ASSERT_RANGE (begin (), __i);
    _RWSTD_ASSERT_RANGE (__x.begin (), __j);
    _RWSTD_ASSERT_RANGE (__j, __k);
 
    // 23.2.2.4, p12 - check undefined behavior
    _RWSTD_ASSERT (&__x != this || (__i != __j && __i != __k));
 
    if (__j == __k)
        return;
 
#if !defined (_RWSTD_NO_LIST_NODE_BUFFER)
        insert (__i, __j, __k);
        __x.erase (__j, __k);
#else
    if (get_allocator () == __x.get_allocator ()) {
 
# ifdef _RWSTDDEBUG
 
        for (iterator __it = __j; __it != __k; ++__it) {
            // 23.2.2.4, p12 - check undefined behavior (linear time)
            _RWSTD_ASSERT (&__x != this || __i != __j);
 
            ++_C_length;
            --__x._C_length;
        }
 
# else   // if !defined (_RWSTDDEBUG)
 
        if (&__x != this) {
            // adjust sizes first
            for (iterator __it = __j; __it != __k; ++__it) {
                ++_C_length;
                --__x._C_length;
            }
        }
 
# endif   // _RWSTDDEBUG
 
        (*(_C_link_type ((*_ITER_NODE (__k))._C_prev)))._C_next =
            _ITER_NODE (__i);
        (*(_C_link_type ((*_ITER_NODE (__j))._C_prev)))._C_next =
            _ITER_NODE (__k);
        (*(_C_link_type ((*_ITER_NODE (__i))._C_prev)))._C_next =
            _ITER_NODE (__j);
        
        _C_link_type __tmp = _C_link_type ((*_ITER_NODE (__i))._C_prev);
        
        (*_ITER_NODE (__i))._C_prev = (*_ITER_NODE (__k))._C_prev;
        (*_ITER_NODE (__k))._C_prev = (*_ITER_NODE (__j))._C_prev; 
        (*_ITER_NODE (__j))._C_prev = __tmp;
    }
    else {
        insert (__i, __j, __k);
        __x.erase (__j, __k);
    }
#endif  //  _RWSTD_NO_LIST_NODE_BUFFER
}
 
template <class _TypeT, class _Allocator>
void list<_TypeT, _Allocator>::remove (const_reference __val)
{
    for (iterator __first = begin (), __last = end (); !(__first == __last); ) {
        iterator __next = __first;
        ++__next;
        if (*__first == __val)
            erase (__first);
        __first = __next;
    }
}
 
 
template <class _TypeT, class _Allocator>
void list<_TypeT, _Allocator>::unique ()
{
    iterator __first = begin ();
    iterator __last  = end ();
 
    if (__first == __last)
        return;
 
    iterator __next = __first;
 
    while (!(++__next == __last)) {
        if (*__first == *__next)
            erase (__next);
        else
            __first = __next;
        __next = __first;
    }
}
 
 
template <class _TypeT, class _Allocator>
void list<_TypeT, _Allocator>::merge (list<_TypeT, _Allocator>& __x)
{
    if (&__x == this)
        return;
    iterator __first1 = begin ();
    iterator __last1  = end ();
    iterator __first2 = __x.begin ();
    iterator __last2  = __x.end ();
 
    while (!(__first1 == __last1) && !(__first2 == __last2)) {
      if (*__first2 < *__first1) {
          iterator __next = __first2;
          _C_transfer (__first1, __first2, ++__next, __x);
          __first2 = __next;
      }
      else
        ++__first1;
    }
 
    if (!(__first2 == __last2))
        _C_transfer (__last1, __first2, __last2, __x);
}
 
 
template <class _TypeT, class _Allocator>
void list<_TypeT, _Allocator>::reverse ()
{
    if (size () < 2)
        return;
 
    for (iterator __first = ++begin (); !(__first == end ()); ) {
        iterator __tmp = __first;
        _C_transfer (begin (), __tmp, ++__first, *this);
    }
}
 
// sorts list by moving nodes within list; preserves iterators pointing to
// elements of the list.
template <class _TypeT, class _Allocator>
void list<_TypeT, _Allocator>::sort ()
{
    for (size_type __n = 1; __n < size (); __n *= 2) {
        iterator __i1 = begin (),
                 __i2 = begin (),
                 __i3 = begin ();
 
        _C_advance (__i2, (difference_type)__n, end ());
        _C_advance (__i3, (difference_type)(2 * __n), end ());
 
        for (size_type __m = 0;
             __m < (size () + (2 * __n)) / (__n * 2); __m++) {
 
            if (!(__i1 == end ()) && !(__i2 == end ())) {
                _C_adjacent_merge (__i1, __i2, __i3);
                __i1 = __i2 = __i3;
                _C_advance (__i2, (difference_type) __n, end ());
                _C_advance (__i3, (difference_type) 2 * __n, end ());
            }
        }
    }
}
 
 
template <class _TypeT, class _Allocator>
void list<_TypeT, _Allocator>::
_C_adjacent_merge (iterator __first1, iterator __last1, iterator __last2)
{
    difference_type __n = _DISTANCE (__first1, __last1, difference_type);
 
    for (iterator __first2 = __last1; __n >= 0 && !(__first2 == __last2); ) {
        if (*__first2 < *__first1) {
            iterator __next = __first2;
            _C_transfer (__first1, __first2, ++__next, *this);
            __first2 = __next;
        }
        else {
            ++__first1;
            --__n;
        }
    }
}
 
 
template <class _TypeT, class _Allocator>
template<class _Compare>
void list<_TypeT, _Allocator>::
_C_adjacent_merge (iterator __first1, iterator __last1, iterator __last2,
                   _Compare __cmp)
{
    difference_type __n = _DISTANCE (__first1, __last1, difference_type);
 
    for (iterator __first2 = __last1; __n >= 0 && !(__first2 == __last2); ) {
        if (__cmp (*__first2, *__first1)) {
            iterator __next = __first2;
            _C_transfer (__first1, __first2, ++__next, *this);
            __first2 = __next;
        }
        else {
            ++__first1;
            --__n;
        }
    }
}
 
 
template<class _TypeT, class _Allocator>
template<class _Predicate>
void list<_TypeT, _Allocator>::remove_if (_Predicate __pred)
{
    iterator __first = begin ();
    iterator __last = end ();
 
    while (!(__first == __last)) {
        iterator __next = __first;
        ++__next;
        if (__pred (*__first))
            erase (__first);
        __first = __next;
    }
}
 
 
template<class _TypeT, class _Allocator>
template<class _BinaryPredicate>
void list<_TypeT, _Allocator>::unique (_BinaryPredicate __pred)
{
    iterator __first = begin ();
    iterator __last = end ();
 
    if (__first == __last)
        return;
 
    iterator __next = __first;
    while (!(++__next == __last)) {
        if (__pred (*__first, *__next))
            erase (__next);
        else
            __first = __next;
        __next = __first;
    }
}
 
 
template<class _TypeT, class _Allocator>
template<class _Compare>
void list<_TypeT, _Allocator>::
merge (list<_TypeT, _Allocator>& __x, _Compare __cmp)
{
    if (&__x == this)
        return;
    iterator __first1 = begin ();
    iterator __last1  = end ();
    iterator __first2 = __x.begin ();
    iterator __last2  = __x.end ();
 
    while (!(__first1 == __last1) && !(__first2 == __last2)) {
      if (__cmp (*__first2, *__first1)) {
          iterator __next = __first2;
          _C_transfer (__first1, __first2, ++__next, __x);
          __first2 = __next;
      }
      else
          ++__first1;
    }
 
    if (!(__first2 == __last2))
        _C_transfer (__last1, __first2, __last2, __x);
}
 
 
template <class _TypeT, class _Allocator>
template<class _Compare>
void list<_TypeT, _Allocator>::sort (_Compare __cmp)
{
    for (size_type __n = 1; __n < size (); __n *= 2) {
 
        iterator __it1 = begin (), 
                 __it2 = begin (), 
                 __it3 = begin ();
 
        _C_advance (__it2, __n, end ());
        _C_advance (__it3, 2 * __n, end ());
 
        for (size_type __m = 0;
             __m != (size () + (2 * __n)) / (__n * 2); ++__m) {
            
            if (!(__it1 == end ()) && !(__it2 == end ())) {
                _C_adjacent_merge (__it1, __it2, __it3, __cmp);
                __it1 = __it3;
                __it2 = __it3;
                _C_advance (__it2, __n, end ());
                _C_advance (__it3, 2 * __n, end ());
            }
        }
    }
}
 
 
}   // namespace std