- Main Page
- Namespaces
- Classes
- Files
- Related Pages

# /Users/fpy/titan-1-5-MBARI/Mers/Executives/DeductiveController/Configs/TI_DSP_BIOS/stl/stl_slist.h

    00001 /*
    00002  * Copyright (c) 1997
    00003  * Silicon Graphics Computer Systems, Inc.
    00004  *
    00005  * Permission to use, copy, modify, distribute and sell this software
    00006  * and its documentation for any purpose is hereby granted without fee,
    00007  * provided that the above copyright notice appear in all copies and
    00008  * that both that copyright notice and this permission notice appear
    00009  * in supporting documentation.  Silicon Graphics makes no
    00010  * representations about the suitability of this software for any
    00011  * purpose.  It is provided "as is" without express or implied warranty.
    00012  *
    00013  */
    00014
    00015 /* NOTE: This is an internal header file, included by other STL headers.
    00016  *   You should not attempt to use it directly.
    00017  */
    00018
    00019 #ifndef __SGI_STL_INTERNAL_SLIST_H
    00020 #define __SGI_STL_INTERNAL_SLIST_H
    00021
    00022
    00023 __STL_BEGIN_NAMESPACE
    00024
    00025 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
    00026 #pragma set woff 1174
    00027 #pragma set woff 1375
    00028 #endif
    00029
    00030 struct _Slist_node_base
    00031 {
    00032   _Slist_node_base* _M_next;
    00033 };
    00034
    00035 inline _Slist_node_base*
    00036 __slist_make_link(_Slist_node_base* __prev_node,
    00037                   _Slist_node_base* __new_node)
    00038 {
    00039   __new_node->_M_next = __prev_node->_M_next;
    00040   __prev_node->_M_next = __new_node;
    00041   return __new_node;
    00042 }
    00043
    00044 inline _Slist_node_base*
    00045 __slist_previous(_Slist_node_base* __head,
    00046                  const _Slist_node_base* __node)
    00047 {
    00048   while (__head && __head->_M_next != __node)
    00049     __head = __head->_M_next;
    00050   return __head;
    00051 }
    00052
    00053 inline const _Slist_node_base*
    00054 __slist_previous(const _Slist_node_base* __head,
    00055                  const _Slist_node_base* __node)
    00056 {
    00057   while (__head && __head->_M_next != __node)
    00058     __head = __head->_M_next;
    00059   return __head;
    00060 }
    00061
    00062 inline void __slist_splice_after(_Slist_node_base* __pos,
    00063                                  _Slist_node_base* __before_first,
    00064                                  _Slist_node_base* __before_last)
    00065 {
    00066   if (__pos != __before_first && __pos != __before_last) {
    00067     _Slist_node_base* __first = __before_first->_M_next;
    00068     _Slist_node_base* __after = __pos->_M_next;
    00069     __before_first->_M_next = __before_last->_M_next;
    00070     __pos->_M_next = __first;
    00071     __before_last->_M_next = __after;
    00072   }
    00073 }
    00074
    00075 inline _Slist_node_base* __slist_reverse(_Slist_node_base* __node)
    00076 {
    00077   _Slist_node_base* __result = __node;
    00078   __node = __node->_M_next;
    00079   __result->_M_next = 0;
    00080   while(__node) {
    00081     _Slist_node_base* __next = __node->_M_next;
    00082     __node->_M_next = __result;
    00083     __result = __node;
    00084     __node = __next;
    00085   }
    00086   return __result;
    00087 }
    00088
    00089 inline size_t __slist_size(_Slist_node_base* __node)
    00090 {
    00091   size_t __result = 0;
    00092   for ( ; __node != 0; __node = __node->_M_next)
    00093     ++__result;
    00094   return __result;
    00095 }
    00096
    00097 template <class _Tp>
    00098 struct _Slist_node : public _Slist_node_base
    00099 {
    00100   _Tp _M_data;
    00101 };
    00102
    00103 struct _Slist_iterator_base
    00104 {
    00105   typedef size_t               size_type;
    00106   typedef ptrdiff_t            difference_type;
    00107   typedef forward_iterator_tag iterator_category;
    00108
    00109   _Slist_node_base* _M_node;
    00110
    00111   _Slist_iterator_base(_Slist_node_base* __x) : _M_node(__x) {}
    00112   void _M_incr() { _M_node = _M_node->_M_next; }
    00113
    00114   bool operator==(const _Slist_iterator_base& __x) const {
    00115     return _M_node == __x._M_node;
    00116   }
    00117   bool operator!=(const _Slist_iterator_base& __x) const {
    00118     return _M_node != __x._M_node;
    00119   }
    00120 };
    00121
    00122 template <class _Tp, class _Ref, class _Ptr>
    00123 struct _Slist_iterator : public _Slist_iterator_base
    00124 {
    00125   typedef _Slist_iterator<_Tp, _Tp&, _Tp*>             iterator;
    00126   typedef _Slist_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;
    00127   typedef _Slist_iterator<_Tp, _Ref, _Ptr>             _Self;
    00128
    00129   typedef _Tp              value_type;
    00130   typedef _Ptr             pointer;
    00131   typedef _Ref             reference;
    00132   typedef _Slist_node<_Tp> _Node;
    00133
    00134   _Slist_iterator(_Node* __x) : _Slist_iterator_base(__x) {}
    00135   _Slist_iterator() : _Slist_iterator_base(0) {}
    00136   _Slist_iterator(const iterator& __x) : _Slist_iterator_base(__x._M_node) {}
    00137
    00138   reference operator*() const { return ((_Node*) _M_node)->_M_data; }
    00139 #ifndef __SGI_STL_NO_ARROW_OPERATOR
    00140   pointer operator->() const { return &(operator*()); }
    00141 #endif /* __SGI_STL_NO_ARROW_OPERATOR */
    00142
    00143   _Self& operator++()
    00144   {
    00145     _M_incr();
    00146     return *this;
    00147   }
    00148   _Self operator++(int)
    00149   {
    00150     _Self __tmp = *this;
    00151     _M_incr();
    00152     return __tmp;
    00153   }
    00154 };
    00155
    00156 #ifndef __STL_CLASS_PARTIAL_SPECIALIZATION
    00157
    00158 inline ptrdiff_t* distance_type(const _Slist_iterator_base&) {
    00159   return 0;
    00160 }
    00161
    00162 inline forward_iterator_tag iterator_category(const _Slist_iterator_base&) {
    00163   return forward_iterator_tag();
    00164 }
    00165
    00166 template <class _Tp, class _Ref, class _Ptr>
    00167 inline _Tp* value_type(const _Slist_iterator<_Tp, _Ref, _Ptr>&) {
    00168   return 0;
    00169 }
    00170
    00171 #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
    00172
    00173 // Base class that encapsulates details of allocators.  Three cases:
    00174 // an ordinary standard-conforming allocator, a standard-conforming
    00175 // allocator with no non-static data, and an SGI-style allocator.
    00176 // This complexity is necessary only because we're worrying about backward
    00177 // compatibility and because we want to avoid wasting storage on an
    00178 // allocator instance if it isn't necessary.
    00179
    00180 #ifdef __STL_USE_STD_ALLOCATORS
    00181
    00182 // Base for general standard-conforming allocators.
    00183 template <class _Tp, class _Allocator, bool _IsStatic>
    00184 class _Slist_alloc_base {
    00185 public:
    00186   typedef typename _Alloc_traits<_Tp,_Allocator>::allocator_type
    00187           allocator_type;
    00188   allocator_type get_allocator() const { return _M_node_allocator; }
    00189
    00190   _Slist_alloc_base(const allocator_type& __a) : _M_node_allocator(__a) {}
    00191
    00192 protected:
    00193   _Slist_node<_Tp>* _M_get_node()
    00194     { return _M_node_allocator.allocate(1); }
    00195   void _M_put_node(_Slist_node<_Tp>* __p)
    00196     { _M_node_allocator.deallocate(__p, 1); }
    00197
    00198 protected:
    00199   typename _Alloc_traits<_Slist_node<_Tp>,_Allocator>::allocator_type
    00200            _M_node_allocator;
    00201   _Slist_node_base _M_head;
    00202 };
    00203
    00204 // Specialization for instanceless allocators.
    00205 template <class _Tp, class _Allocator>
    00206 class _Slist_alloc_base<_Tp,_Allocator, true> {
    00207 public:
    00208   typedef typename _Alloc_traits<_Tp,_Allocator>::allocator_type
    00209           allocator_type;
    00210   allocator_type get_allocator() const { return allocator_type(); }
    00211
    00212   _Slist_alloc_base(const allocator_type&) {}
    00213
    00214 protected:
    00215   typedef typename _Alloc_traits<_Slist_node<_Tp>, _Allocator>::_Alloc_type
    00216           _Alloc_type;
    00217   _Slist_node<_Tp>* _M_get_node() { return _Alloc_type::allocate(1); }
    00218   void _M_put_node(_Slist_node<_Tp>* __p) { _Alloc_type::deallocate(__p, 1); }
    00219
    00220 protected:
    00221   _Slist_node_base _M_head;
    00222 };
    00223
    00224
    00225 template <class _Tp, class _Alloc>
    00226 struct _Slist_base
    00227   : public _Slist_alloc_base<_Tp, _Alloc,
    00228                              _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
    00229 {
    00230   typedef _Slist_alloc_base<_Tp, _Alloc,
    00231                             _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
    00232           _Base;
    00233   typedef typename _Base::allocator_type allocator_type;
    00234
    00235   _Slist_base(const allocator_type& __a) : _Base(__a) { _M_head._M_next = 0; }
    00236   ~_Slist_base() { _M_erase_after(&_M_head, 0); }
    00237
    00238 protected:
    00239
    00240   _Slist_node_base* _M_erase_after(_Slist_node_base* __pos)
    00241   {
    00242     _Slist_node<_Tp>* __next = (_Slist_node<_Tp>*) (__pos->_M_next);
    00243     _Slist_node_base* __next_next = __next->_M_next;
    00244     __pos->_M_next = __next_next;
    00245     destroy(&__next->_M_data);
    00246     _M_put_node(__next);
    00247     return __next_next;
    00248   }
    00249   _Slist_node_base* _M_erase_after(_Slist_node_base*, _Slist_node_base*);
    00250 };
    00251
    00252 #else /* __STL_USE_STD_ALLOCATORS */
    00253
    00254 template <class _Tp, class _Alloc>
    00255 struct _Slist_base {
    00256   typedef _Alloc allocator_type;
    00257   allocator_type get_allocator() const { return allocator_type(); }
    00258
    00259   _Slist_base(const allocator_type&) { _M_head._M_next = 0; }
    00260   ~_Slist_base() { _M_erase_after(&_M_head, 0); }
    00261
    00262 protected:
    00263   typedef simple_alloc<_Slist_node<_Tp>, _Alloc> _Alloc_type;
    00264   _Slist_node<_Tp>* _M_get_node() { return _Alloc_type::allocate(1); }
    00265   void _M_put_node(_Slist_node<_Tp>* __p) { _Alloc_type::deallocate(__p, 1); }
    00266
    00267   _Slist_node_base* _M_erase_after(_Slist_node_base* __pos)
    00268   {
    00269     _Slist_node<_Tp>* __next = (_Slist_node<_Tp>*) (__pos->_M_next);
    00270     _Slist_node_base* __next_next = __next->_M_next;
    00271     __pos->_M_next = __next_next;
    00272     destroy(&__next->_M_data);
    00273     _M_put_node(__next);
    00274     return __next_next;
    00275   }
    00276   _Slist_node_base* _M_erase_after(_Slist_node_base*, _Slist_node_base*);
    00277
    00278 protected:
    00279   _Slist_node_base _M_head;
    00280 };
    00281
    00282 #endif /* __STL_USE_STD_ALLOCATORS */
    00283
    00284 template <class _Tp, class _Alloc>
    00285 _Slist_node_base*
    00286 _Slist_base<_Tp,_Alloc>::_M_erase_after(_Slist_node_base* __before_first,
    00287                                         _Slist_node_base* __last_node) {
    00288   _Slist_node<_Tp>* __cur = (_Slist_node<_Tp>*) (__before_first->_M_next);
    00289   while (__cur != __last_node) {
    00290     _Slist_node<_Tp>* __tmp = __cur;
    00291     __cur = (_Slist_node<_Tp>*) __cur->_M_next;
    00292     destroy(&__tmp->_M_data);
    00293     _M_put_node(__tmp);
    00294   }
    00295   __before_first->_M_next = __last_node;
    00296   return __last_node;
    00297 }
    00298
    00299 template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
    00300 class slist : private _Slist_base<_Tp,_Alloc>
    00301 {
    00302 private:
    00303   typedef _Slist_base<_Tp,_Alloc> _Base;
    00304 public:
    00305   typedef _Tp                value_type;
    00306   typedef value_type*       pointer;
    00307   typedef const value_type* const_pointer;
    00308   typedef value_type&       reference;
    00309   typedef const value_type& const_reference;
    00310   typedef size_t            size_type;
    00311   typedef ptrdiff_t         difference_type;
    00312
    00313   typedef _Slist_iterator<_Tp, _Tp&, _Tp*>             iterator;
    00314   typedef _Slist_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;
    00315
    00316   typedef typename _Base::allocator_type allocator_type;
    00317   allocator_type get_allocator() const { return _Base::get_allocator(); }
    00318
    00319 private:
    00320   typedef _Slist_node<_Tp>      _Node;
    00321   typedef _Slist_node_base      _Node_base;
    00322   typedef _Slist_iterator_base  _Iterator_base;
    00323
    00324   _Node* _M_create_node(const value_type& __x) {
    00325     _Node* __node = _M_get_node();
    00326     __STL_TRY {
    00327       construct(&__node->_M_data, __x);
    00328       __node->_M_next = 0;
    00329     }
    00330     __STL_UNWIND(_M_put_node(__node));
    00331     return __node;
    00332   }
    00333
    00334   _Node* _M_create_node() {
    00335     _Node* __node = _M_get_node();
    00336     __STL_TRY {
    00337       construct(&__node->_M_data);
    00338       __node->_M_next = 0;
    00339     }
    00340     __STL_UNWIND(_M_put_node(__node));
    00341     return __node;
    00342   }
    00343
    00344 private:
    00345 #ifdef __STL_USE_NAMESPACES
    00346   using _Base::_M_get_node;
    00347   using _Base::_M_put_node;
    00348   using _Base::_M_erase_after;
    00349   using _Base::_M_head;
    00350 #endif /* __STL_USE_NAMESPACES */
    00351
    00352 public:
    00353   explicit slist(const allocator_type& __a = allocator_type()) : _Base(__a) {}
    00354
    00355   slist(size_type __n, const value_type& __x,
    00356         const allocator_type& __a =  allocator_type()) : _Base(__a)
    00357     { _M_insert_after_fill(&_M_head, __n, __x); }
    00358
    00359   explicit slist(size_type __n) : _Base(allocator_type())
    00360     { _M_insert_after_fill(&_M_head, __n, value_type()); }
    00361
    00362 #ifdef __STL_MEMBER_TEMPLATES
    00363   // We don't need any dispatching tricks here, because _M_insert_after_range
    00364   // already does them.
    00365   template <class _InputIterator>
    00366   slist(_InputIterator __first, _InputIterator __last,
    00367         const allocator_type& __a =  allocator_type()) : _Base(__a)
    00368     { _M_insert_after_range(&_M_head, __first, __last); }
    00369
    00370 #else /* __STL_MEMBER_TEMPLATES */
    00371   slist(const_iterator __first, const_iterator __last,
    00372         const allocator_type& __a =  allocator_type()) : _Base(__a)
    00373     { _M_insert_after_range(&_M_head, __first, __last); }
    00374   slist(const value_type* __first, const value_type* __last,
    00375         const allocator_type& __a =  allocator_type()) : _Base(__a)
    00376     { _M_insert_after_range(&_M_head, __first, __last); }
    00377 #endif /* __STL_MEMBER_TEMPLATES */
    00378
    00379   slist(const slist& __x) : _Base(__x.get_allocator())
    00380     { _M_insert_after_range(&_M_head, __x.begin(), __x.end()); }
    00381
    00382   slist& operator= (const slist& __x);
    00383
    00384   ~slist() {}
    00385
    00386 public:
    00387   // assign(), a generalized assignment member function.  Two
    00388   // versions: one that takes a count, and one that takes a range.
    00389   // The range version is a member template, so we dispatch on whether
    00390   // or not the type is an integer.
    00391
    00392   void assign(size_type __n, const _Tp& __val);
    00393
    00394 #ifdef __STL_MEMBER_TEMPLATES
    00395
    00396   template <class _InputIterator>
    00397   void assign(_InputIterator __first, _InputIterator __last) {
    00398     typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
    00399     _M_assign_dispatch(__first, __last, _Integral());
    00400   }
    00401
    00402   template <class _Integer>
    00403   void _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
    00404     { assign((size_type) __n, (_Tp) __val); }
    00405
    00406   template <class _InputIterator>
    00407   void _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
    00408                           __false_type);
    00409
    00410 #endif /* __STL_MEMBER_TEMPLATES */
    00411
    00412 public:
    00413
    00414   iterator begin() { return iterator((_Node*)_M_head._M_next); }
    00415   const_iterator begin() const
    00416     { return const_iterator((_Node*)_M_head._M_next);}
    00417
    00418   iterator end() { return iterator(0); }
    00419   const_iterator end() const { return const_iterator(0); }
    00420
    00421   size_type size() const { return __slist_size(_M_head._M_next); }
    00422
    00423   size_type max_size() const { return size_type(-1); }
    00424
    00425   bool empty() const { return _M_head._M_next == 0; }
    00426
    00427   void swap(slist& __x) { __STD::swap(_M_head._M_next, __x._M_head._M_next); }
    00428
    00429 public:
    00430   friend bool operator== __STL_NULL_TMPL_ARGS (const slist<_Tp,_Alloc>& _SL1,
    00431                                                const slist<_Tp,_Alloc>& _SL2);
    00432
    00433 public:
    00434
    00435   reference front() { return ((_Node*) _M_head._M_next)->_M_data; }
    00436   const_reference front() const
    00437     { return ((_Node*) _M_head._M_next)->_M_data; }
    00438   void push_front(const value_type& __x)   {
    00439     __slist_make_link(&_M_head, _M_create_node(__x));
    00440   }
    00441   void push_front() { __slist_make_link(&_M_head, _M_create_node());}
    00442   void pop_front() {
    00443     _Node* __node = (_Node*) _M_head._M_next;
    00444     _M_head._M_next = __node->_M_next;
    00445     destroy(&__node->_M_data);
    00446     _M_put_node(__node);
    00447   }
    00448
    00449   iterator previous(const_iterator __pos) {
    00450     return iterator((_Node*) __slist_previous(&_M_head, __pos._M_node));
    00451   }
    00452   const_iterator previous(const_iterator __pos) const {
    00453     return const_iterator((_Node*) __slist_previous(&_M_head, __pos._M_node));
    00454   }
    00455
    00456 private:
    00457   _Node* _M_insert_after(_Node_base* __pos, const value_type& __x) {
    00458     return (_Node*) (__slist_make_link(__pos, _M_create_node(__x)));
    00459   }
    00460
    00461   _Node* _M_insert_after(_Node_base* __pos) {
    00462     return (_Node*) (__slist_make_link(__pos, _M_create_node()));
    00463   }
    00464
    00465   void _M_insert_after_fill(_Node_base* __pos,
    00466                             size_type __n, const value_type& __x) {
    00467     for (size_type __i = 0; __i < __n; ++__i)
    00468       __pos = __slist_make_link(__pos, _M_create_node(__x));
    00469   }
    00470
    00471 #ifdef __STL_MEMBER_TEMPLATES
    00472
    00473   // Check whether it's an integral type.  If so, it's not an iterator.
    00474   template <class _InIter>
    00475   void _M_insert_after_range(_Node_base* __pos,
    00476                              _InIter __first, _InIter __last) {
    00477     typedef typename _Is_integer<_InIter>::_Integral _Integral;
    00478     _M_insert_after_range(__pos, __first, __last, _Integral());
    00479   }
    00480
    00481   template <class _Integer>
    00482   void _M_insert_after_range(_Node_base* __pos, _Integer __n, _Integer __x,
    00483                              __true_type) {
    00484     _M_insert_after_fill(__pos, __n, __x);
    00485   }
    00486
    00487   template <class _InIter>
    00488   void _M_insert_after_range(_Node_base* __pos,
    00489                              _InIter __first, _InIter __last,
    00490                              __false_type) {
    00491     while (__first != __last) {
    00492       __pos = __slist_make_link(__pos, _M_create_node(*__first));
    00493       ++__first;
    00494     }
    00495   }
    00496
    00497 #else /* __STL_MEMBER_TEMPLATES */
    00498
    00499   void _M_insert_after_range(_Node_base* __pos,
    00500                              const_iterator __first, const_iterator __last) {
    00501     while (__first != __last) {
    00502       __pos = __slist_make_link(__pos, _M_create_node(*__first));
    00503       ++__first;
    00504     }
    00505   }
    00506   void _M_insert_after_range(_Node_base* __pos,
    00507                              const value_type* __first,
    00508                              const value_type* __last) {
    00509     while (__first != __last) {
    00510       __pos = __slist_make_link(__pos, _M_create_node(*__first));
    00511       ++__first;
    00512     }
    00513   }
    00514
    00515 #endif /* __STL_MEMBER_TEMPLATES */
    00516
    00517 public:
    00518
    00519   iterator insert_after(iterator __pos, const value_type& __x) {
    00520     return iterator(_M_insert_after(__pos._M_node, __x));
    00521   }
    00522
    00523   iterator insert_after(iterator __pos) {
    00524     return insert_after(__pos, value_type());
    00525   }
    00526
    00527   void insert_after(iterator __pos, size_type __n, const value_type& __x) {
    00528     _M_insert_after_fill(__pos._M_node, __n, __x);
    00529   }
    00530
    00531 #ifdef __STL_MEMBER_TEMPLATES
    00532
    00533   // We don't need any dispatching tricks here, because _M_insert_after_range
    00534   // already does them.
    00535   template <class _InIter>
    00536   void insert_after(iterator __pos, _InIter __first, _InIter __last) {
    00537     _M_insert_after_range(__pos._M_node, __first, __last);
    00538   }
    00539
    00540 #else /* __STL_MEMBER_TEMPLATES */
    00541
    00542   void insert_after(iterator __pos,
    00543                     const_iterator __first, const_iterator __last) {
    00544     _M_insert_after_range(__pos._M_node, __first, __last);
    00545   }
    00546   void insert_after(iterator __pos,
    00547                     const value_type* __first, const value_type* __last) {
    00548     _M_insert_after_range(__pos._M_node, __first, __last);
    00549   }
    00550
    00551 #endif /* __STL_MEMBER_TEMPLATES */
    00552
    00553   iterator insert(iterator __pos, const value_type& __x) {
    00554     return iterator(_M_insert_after(__slist_previous(&_M_head, __pos._M_node),
    00555                     __x));
    00556   }
    00557
    00558   iterator insert(iterator __pos) {
    00559     return iterator(_M_insert_after(__slist_previous(&_M_head, __pos._M_node),
    00560                                     value_type()));
    00561   }
    00562
    00563   void insert(iterator __pos, size_type __n, const value_type& __x) {
    00564     _M_insert_after_fill(__slist_previous(&_M_head, __pos._M_node), __n, __x);
    00565   }
    00566
    00567 #ifdef __STL_MEMBER_TEMPLATES
    00568
    00569   // We don't need any dispatching tricks here, because _M_insert_after_range
    00570   // already does them.
    00571   template <class _InIter>
    00572   void insert(iterator __pos, _InIter __first, _InIter __last) {
    00573     _M_insert_after_range(__slist_previous(&_M_head, __pos._M_node),
    00574                           __first, __last);
    00575   }
    00576
    00577 #else /* __STL_MEMBER_TEMPLATES */
    00578
    00579   void insert(iterator __pos, const_iterator __first, const_iterator __last) {
    00580     _M_insert_after_range(__slist_previous(&_M_head, __pos._M_node),
    00581                           __first, __last);
    00582   }
    00583   void insert(iterator __pos, const value_type* __first,
    00584                               const value_type* __last) {
    00585     _M_insert_after_range(__slist_previous(&_M_head, __pos._M_node),
    00586                           __first, __last);
    00587   }
    00588
    00589 #endif /* __STL_MEMBER_TEMPLATES */
    00590
    00591
    00592 public:
    00593   iterator erase_after(iterator __pos) {
    00594     return iterator((_Node*) _M_erase_after(__pos._M_node));
    00595   }
    00596   iterator erase_after(iterator __before_first, iterator __last) {
    00597     return iterator((_Node*) _M_erase_after(__before_first._M_node,
    00598                                             __last._M_node));
    00599   }
    00600
    00601   iterator erase(iterator __pos) {
    00602     return (_Node*) _M_erase_after(__slist_previous(&_M_head,
    00603                                                     __pos._M_node));
    00604   }
    00605   iterator erase(iterator __first, iterator __last) {
    00606     return (_Node*) _M_erase_after(
    00607       __slist_previous(&_M_head, __first._M_node), __last._M_node);
    00608   }
    00609
    00610   void resize(size_type new_size, const _Tp& __x);
    00611   void resize(size_type new_size) { resize(new_size, _Tp()); }
    00612   void clear() { _M_erase_after(&_M_head, 0); }
    00613
    00614 public:
    00615   // Moves the range [__before_first + 1, __before_last + 1) to *this,
    00616   //  inserting it immediately after __pos.  This is constant time.
    00617   void splice_after(iterator __pos,
    00618                     iterator __before_first, iterator __before_last)
    00619   {
    00620     if (__before_first != __before_last)
    00621       __slist_splice_after(__pos._M_node, __before_first._M_node,
    00622                            __before_last._M_node);
    00623   }
    00624
    00625   // Moves the element that follows __prev to *this, inserting it immediately
    00626   //  after __pos.  This is constant time.
    00627   void splice_after(iterator __pos, iterator __prev)
    00628   {
    00629     __slist_splice_after(__pos._M_node,
    00630                          __prev._M_node, __prev._M_node->_M_next);
    00631   }
    00632
    00633
    00634   // Linear in distance(begin(), __pos), and linear in __x.size().
    00635   void splice(iterator __pos, slist& __x) {
    00636     if (__x._M_head._M_next)
    00637       __slist_splice_after(__slist_previous(&_M_head, __pos._M_node),
    00638                            &__x._M_head, __slist_previous(&__x._M_head, 0));
    00639   }
    00640
    00641   // Linear in distance(begin(), __pos), and in distance(__x.begin(), __i).
    00642   void splice(iterator __pos, slist& __x, iterator __i) {
    00643     __slist_splice_after(__slist_previous(&_M_head, __pos._M_node),
    00644                          __slist_previous(&__x._M_head, __i._M_node),
    00645                          __i._M_node);
    00646   }
    00647
    00648   // Linear in distance(begin(), __pos), in distance(__x.begin(), __first),
    00649   // and in distance(__first, __last).
    00650   void splice(iterator __pos, slist& __x, iterator __first, iterator __last)
    00651   {
    00652     if (__first != __last)
    00653       __slist_splice_after(__slist_previous(&_M_head, __pos._M_node),
    00654                            __slist_previous(&__x._M_head, __first._M_node),
    00655                            __slist_previous(__first._M_node, __last._M_node));
    00656   }
    00657
    00658 public:
    00659   void reverse() {
    00660     if (_M_head._M_next)
    00661       _M_head._M_next = __slist_reverse(_M_head._M_next);
    00662   }
    00663
    00664   void remove(const _Tp& __val);
    00665   void unique();
    00666   void merge(slist& __x);
    00667   void sort();
    00668
    00669 #ifdef __STL_MEMBER_TEMPLATES
    00670   template <class _Predicate>
    00671   void remove_if(_Predicate __pred);
    00672
    00673   template <class _BinaryPredicate>
    00674   void unique(_BinaryPredicate __pred);
    00675
    00676   template <class _StrictWeakOrdering>
    00677   void merge(slist&, _StrictWeakOrdering);
    00678
    00679   template <class _StrictWeakOrdering>
    00680   void sort(_StrictWeakOrdering __comp);
    00681 #endif /* __STL_MEMBER_TEMPLATES */
    00682 };
    00683
    00684 template <class _Tp, class _Alloc>
    00685 slist<_Tp,_Alloc>& slist<_Tp,_Alloc>::operator=(const slist<_Tp,_Alloc>& __x)
    00686 {
    00687   if (&__x != this) {
    00688     _Node_base* __p1 = &_M_head;
    00689     _Node* __n1 = (_Node*) _M_head._M_next;
    00690     const _Node* __n2 = (const _Node*) __x._M_head._M_next;
    00691     while (__n1 && __n2) {
    00692       __n1->_M_data = __n2->_M_data;
    00693       __p1 = __n1;
    00694       __n1 = (_Node*) __n1->_M_next;
    00695       __n2 = (const _Node*) __n2->_M_next;
    00696     }
    00697     if (__n2 == 0)
    00698       _M_erase_after(__p1, 0);
    00699     else
    00700       _M_insert_after_range(__p1, const_iterator((_Node*)__n2),
    00701                                   const_iterator(0));
    00702   }
    00703   return *this;
    00704 }
    00705
    00706 template <class _Tp, class _Alloc>
    00707 void slist<_Tp, _Alloc>::assign(size_type __n, const _Tp& __val) {
    00708   _Node_base* __prev = &_M_head;
    00709   _Node* __node = (_Node*) _M_head._M_next;
    00710   for ( ; __node != 0 && __n > 0 ; --__n) {
    00711     __node->_M_data = __val;
    00712     __prev = __node;
    00713     __node = (_Node*) __node->_M_next;
    00714   }
    00715   if (__n > 0)
    00716     _M_insert_after_fill(__prev, __n, __val);
    00717   else
    00718     _M_erase_after(__prev, 0);
    00719 }
    00720
    00721 #ifdef __STL_MEMBER_TEMPLATES
    00722
    00723 template <class _Tp, class _Alloc> template <class _InputIter>
    00724 void
    00725 slist<_Tp, _Alloc>::_M_assign_dispatch(_InputIter __first, _InputIter __last,
    00726                                        __false_type)
    00727 {
    00728   _Node_base* __prev = &_M_head;
    00729   _Node* __node = (_Node*) _M_head._M_next;
    00730   while (__node != 0 && __first != __last) {
    00731     __node->_M_data = *__first;
    00732     __prev = __node;
    00733     __node = (_Node*) __node->_M_next;
    00734     ++__first;
    00735   }
    00736   if (__first != __last)
    00737     _M_insert_after_range(__prev, __first, __last);
    00738   else
    00739     _M_erase_after(__prev, 0);
    00740 }
    00741
    00742 #endif /* __STL_MEMBER_TEMPLATES */
    00743
    00744 template <class _Tp, class _Alloc>
    00745 inline bool
    00746 operator==(const slist<_Tp,_Alloc>& _SL1, const slist<_Tp,_Alloc>& _SL2)
    00747 {
    00748   typedef typename slist<_Tp,_Alloc>::_Node _Node;
    00749   _Node* __n1 = (_Node*) _SL1._M_head._M_next;
    00750   _Node* __n2 = (_Node*) _SL2._M_head._M_next;
    00751   while (__n1 && __n2 && __n1->_M_data == __n2->_M_data) {
    00752     __n1 = (_Node*) __n1->_M_next;
    00753     __n2 = (_Node*) __n2->_M_next;
    00754   }
    00755   return __n1 == 0 && __n2 == 0;
    00756 }
    00757
    00758 template <class _Tp, class _Alloc>
    00759 inline bool operator<(const slist<_Tp,_Alloc>& _SL1,
    00760                       const slist<_Tp,_Alloc>& _SL2)
    00761 {
    00762   return lexicographical_compare(_SL1.begin(), _SL1.end(),
    00763                                  _SL2.begin(), _SL2.end());
    00764 }
    00765
    00766 #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
    00767
    00768 template <class _Tp, class _Alloc>
    00769 inline void swap(slist<_Tp,_Alloc>& __x, slist<_Tp,_Alloc>& __y) {
    00770   __x.swap(__y);
    00771 }
    00772
    00773 #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
    00774
    00775
    00776 template <class _Tp, class _Alloc>
    00777 void slist<_Tp,_Alloc>::resize(size_type __len, const _Tp& __x)
    00778 {
    00779   _Node_base* __cur = &_M_head;
    00780   while (__cur->_M_next != 0 && __len > 0) {
    00781     --__len;
    00782     __cur = __cur->_M_next;
    00783   }
    00784   if (__cur->_M_next)
    00785     _M_erase_after(__cur, 0);
    00786   else
    00787     _M_insert_after_fill(__cur, __len, __x);
    00788 }
    00789
    00790 template <class _Tp, class _Alloc>
    00791 void slist<_Tp,_Alloc>::remove(const _Tp& __val)
    00792 {
    00793   _Node_base* __cur = &_M_head;
    00794   while (__cur && __cur->_M_next) {
    00795     if (((_Node*) __cur->_M_next)->_M_data == __val)
    00796       _M_erase_after(__cur);
    00797     else
    00798       __cur = __cur->_M_next;
    00799   }
    00800 }
    00801
    00802 template <class _Tp, class _Alloc>
    00803 void slist<_Tp,_Alloc>::unique()
    00804 {
    00805   _Node_base* __cur = _M_head._M_next;
    00806   if (__cur) {
    00807     while (__cur->_M_next) {
    00808       if (((_Node*)__cur)->_M_data ==
    00809           ((_Node*)(__cur->_M_next))->_M_data)
    00810         _M_erase_after(__cur);
    00811       else
    00812         __cur = __cur->_M_next;
    00813     }
    00814   }
    00815 }
    00816
    00817 template <class _Tp, class _Alloc>
    00818 void slist<_Tp,_Alloc>::merge(slist<_Tp,_Alloc>& __x)
    00819 {
    00820   _Node_base* __n1 = &_M_head;
    00821   while (__n1->_M_next && __x._M_head._M_next) {
    00822     if (((_Node*) __x._M_head._M_next)->_M_data <
    00823         ((_Node*)       __n1->_M_next)->_M_data)
    00824       __slist_splice_after(__n1, &__x._M_head, __x._M_head._M_next);
    00825     __n1 = __n1->_M_next;
    00826   }
    00827   if (__x._M_head._M_next) {
    00828     __n1->_M_next = __x._M_head._M_next;
    00829     __x._M_head._M_next = 0;
    00830   }
    00831 }
    00832
    00833 template <class _Tp, class _Alloc>
    00834 void slist<_Tp,_Alloc>::sort()
    00835 {
    00836   if (_M_head._M_next && _M_head._M_next->_M_next) {
    00837     slist __carry;
    00838     slist __counter[64];
    00839     int __fill = 0;
    00840     while (!empty()) {
    00841       __slist_splice_after(&__carry._M_head, &_M_head, _M_head._M_next);
    00842       int __i = 0;
    00843       while (__i < __fill && !__counter[__i].empty()) {
    00844         __counter[__i].merge(__carry);
    00845         __carry.swap(__counter[__i]);
    00846         ++__i;
    00847       }
    00848       __carry.swap(__counter[__i]);
    00849       if (__i == __fill)
    00850         ++__fill;
    00851     }
    00852
    00853     for (int __i = 1; __i < __fill; ++__i)
    00854       __counter[__i].merge(__counter[__i-1]);
    00855     this->swap(__counter[__fill-1]);
    00856   }
    00857 }
    00858
    00859 #ifdef __STL_MEMBER_TEMPLATES
    00860
    00861 template <class _Tp, class _Alloc>
    00862 template <class _Predicate>
    00863 void slist<_Tp,_Alloc>::remove_if(_Predicate __pred)
    00864 {
    00865   _Node_base* __cur = &_M_head;
    00866   while (__cur->_M_next) {
    00867     if (__pred(((_Node*) __cur->_M_next)->_M_data))
    00868       _M_erase_after(__cur);
    00869     else
    00870       __cur = __cur->_M_next;
    00871   }
    00872 }
    00873
    00874 template <class _Tp, class _Alloc> template <class _BinaryPredicate>
    00875 void slist<_Tp,_Alloc>::unique(_BinaryPredicate __pred)
    00876 {
    00877   _Node* __cur = (_Node*) _M_head._M_next;
    00878   if (__cur) {
    00879     while (__cur->_M_next) {
    00880       if (__pred(((_Node*)__cur)->_M_data,
    00881                  ((_Node*)(__cur->_M_next))->_M_data))
    00882         _M_erase_after(__cur);
    00883       else
    00884         __cur = (_Node*) __cur->_M_next;
    00885     }
    00886   }
    00887 }
    00888
    00889 template <class _Tp, class _Alloc> template <class _StrictWeakOrdering>
    00890 void slist<_Tp,_Alloc>::merge(slist<_Tp,_Alloc>& __x,
    00891                               _StrictWeakOrdering __comp)
    00892 {
    00893   _Node_base* __n1 = &_M_head;
    00894   while (__n1->_M_next && __x._M_head._M_next) {
    00895     if (__comp(((_Node*) __x._M_head._M_next)->_M_data,
    00896                ((_Node*)       __n1->_M_next)->_M_data))
    00897       __slist_splice_after(__n1, &__x._M_head, __x._M_head._M_next);
    00898     __n1 = __n1->_M_next;
    00899   }
    00900   if (__x._M_head._M_next) {
    00901     __n1->_M_next = __x._M_head._M_next;
    00902     __x._M_head._M_next = 0;
    00903   }
    00904 }
    00905
    00906 template <class _Tp, class _Alloc> template <class _StrictWeakOrdering>
    00907 void slist<_Tp,_Alloc>::sort(_StrictWeakOrdering __comp)
    00908 {
    00909   if (_M_head._M_next && _M_head._M_next->_M_next) {
    00910     slist __carry;
    00911     slist __counter[64];
    00912     int __fill = 0;
    00913     while (!empty()) {
    00914       __slist_splice_after(&__carry._M_head, &_M_head, _M_head._M_next);
    00915       int __i = 0;
    00916       while (__i < __fill && !__counter[__i].empty()) {
    00917         __counter[__i].merge(__carry, __comp);
    00918         __carry.swap(__counter[__i]);
    00919         ++__i;
    00920       }
    00921       __carry.swap(__counter[__i]);
    00922       if (__i == __fill)
    00923         ++__fill;
    00924     }
    00925
    00926     for (int __i = 1; __i < __fill; ++__i)
    00927       __counter[__i].merge(__counter[__i-1], __comp);
    00928     this->swap(__counter[__fill-1]);
    00929   }
    00930 }
    00931
    00932 #endif /* __STL_MEMBER_TEMPLATES */
    00933
    00934 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
    00935 #pragma reset woff 1174
    00936 #pragma reset woff 1375
    00937 #endif
    00938
    00939 __STL_END_NAMESPACE
    00940
    00941 #endif /* __SGI_STL_INTERNAL_SLIST_H */
    00942
    00943 // Local Variables:
    00944 // mode:C++
    00945 // End: