1 /////////////////////////////////////////////////////////////////////////////// 2 // list.hpp 3 // A simple implementation of std::list that allows incomplete 4 // types, does no dynamic allocation in the default constructor, 5 // and has a guarnteed O(1) splice. 6 // 7 // Copyright 2009 Eric Niebler. Distributed under the Boost 8 // Software License, Version 1.0. (See accompanying file 9 // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) 10 11 #ifndef BOOST_XPRESSIVE_DETAIL_CORE_LIST_HPP_EAN_10_26_2009 12 #define BOOST_XPRESSIVE_DETAIL_CORE_LIST_HPP_EAN_10_26_2009 13 14 // MS compatible compilers support #pragma once 15 #if defined(_MSC_VER) 16 # pragma once 17 #endif 18 19 #include <cstddef> 20 #include <iterator> 21 #include <algorithm> 22 #include <boost/assert.hpp> 23 #include <boost/iterator/iterator_facade.hpp> 24 25 namespace boost { namespace xpressive { namespace detail 26 { 27 28 /////////////////////////////////////////////////////////////////////////////// 29 // list 30 // 31 template<typename T> 32 struct list 33 { 34 private: 35 struct node_base 36 { 37 node_base *_prev; 38 node_base *_next; 39 }; 40 41 struct node : node_base 42 { nodeboost::xpressive::detail::list::node43 explicit node(T const &value) 44 : _value(value) 45 {} 46 47 T _value; 48 }; 49 50 node_base _sentry; 51 52 template<typename Ref = T &> 53 struct list_iterator 54 : boost::iterator_facade<list_iterator<Ref>, T, std::bidirectional_iterator_tag, Ref> 55 { list_iteratorboost::xpressive::detail::list::list_iterator56 list_iterator(list_iterator<> const &it) : _node(it._node) {} list_iteratorboost::xpressive::detail::list::list_iterator57 explicit list_iterator(node_base *n = 0) : _node(n) {} 58 private: 59 friend struct list<T>; 60 friend class boost::iterator_core_access; dereferenceboost::xpressive::detail::list::list_iterator61 Ref dereference() const { return static_cast<node *>(_node)->_value; } incrementboost::xpressive::detail::list::list_iterator62 void increment() { _node = _node->_next; } decrementboost::xpressive::detail::list::list_iterator63 void decrement() { _node = _node->_prev; } equalboost::xpressive::detail::list::list_iterator64 bool equal(list_iterator const &it) const { return _node == it._node; } 65 node_base *_node; 66 }; 67 68 public: 69 typedef T *pointer; 70 typedef T const *const_pointer; 71 typedef T &reference; 72 typedef T const &const_reference; 73 typedef list_iterator<> iterator; 74 typedef list_iterator<T const &> const_iterator; 75 typedef std::size_t size_type; 76 listboost::xpressive::detail::list77 list() 78 { 79 _sentry._next = _sentry._prev = &_sentry; 80 } 81 listboost::xpressive::detail::list82 list(list const &that) 83 { 84 _sentry._next = _sentry._prev = &_sentry; 85 const_iterator it = that.begin(), e = that.end(); 86 for( ; it != e; ++it) 87 push_back(*it); 88 } 89 operator =boost::xpressive::detail::list90 list &operator =(list const &that) 91 { 92 list(that).swap(*this); 93 return *this; 94 } 95 ~listboost::xpressive::detail::list96 ~list() 97 { 98 clear(); 99 } 100 clearboost::xpressive::detail::list101 void clear() 102 { 103 while(!empty()) 104 pop_front(); 105 } 106 swapboost::xpressive::detail::list107 void swap(list &that) // throw() 108 { 109 list temp; 110 temp.splice(temp.begin(), that); // move that to temp 111 that.splice(that.begin(), *this); // move this to that 112 splice(begin(), temp); // move temp to this 113 } 114 push_frontboost::xpressive::detail::list115 void push_front(T const &t) 116 { 117 node *new_node = new node(t); 118 119 new_node->_next = _sentry._next; 120 new_node->_prev = &_sentry; 121 122 _sentry._next->_prev = new_node; 123 _sentry._next = new_node; 124 } 125 push_backboost::xpressive::detail::list126 void push_back(T const &t) 127 { 128 node *new_node = new node(t); 129 130 new_node->_next = &_sentry; 131 new_node->_prev = _sentry._prev; 132 133 _sentry._prev->_next = new_node; 134 _sentry._prev = new_node; 135 } 136 pop_frontboost::xpressive::detail::list137 void pop_front() 138 { 139 BOOST_ASSERT(!empty()); 140 node *old_node = static_cast<node *>(_sentry._next); 141 _sentry._next = old_node->_next; 142 _sentry._next->_prev = &_sentry; 143 delete old_node; 144 } 145 pop_backboost::xpressive::detail::list146 void pop_back() 147 { 148 BOOST_ASSERT(!empty()); 149 node *old_node = static_cast<node *>(_sentry._prev); 150 _sentry._prev = old_node->_prev; 151 _sentry._prev->_next = &_sentry; 152 delete old_node; 153 } 154 emptyboost::xpressive::detail::list155 bool empty() const 156 { 157 return _sentry._next == &_sentry; 158 } 159 spliceboost::xpressive::detail::list160 void splice(iterator it, list &x) 161 { 162 if(x.empty()) 163 return; 164 165 x._sentry._prev->_next = it._node; 166 x._sentry._next->_prev = it._node->_prev; 167 168 it._node->_prev->_next = x._sentry._next; 169 it._node->_prev = x._sentry._prev; 170 171 x._sentry._prev = x._sentry._next = &x._sentry; 172 } 173 spliceboost::xpressive::detail::list174 void splice(iterator it, list &, iterator xit) 175 { 176 xit._node->_prev->_next = xit._node->_next; 177 xit._node->_next->_prev = xit._node->_prev; 178 179 xit._node->_next = it._node; 180 xit._node->_prev = it._node->_prev; 181 182 it._node->_prev = it._node->_prev->_next = xit._node; 183 } 184 frontboost::xpressive::detail::list185 reference front() 186 { 187 BOOST_ASSERT(!empty()); 188 return static_cast<node *>(_sentry._next)->_value; 189 } 190 frontboost::xpressive::detail::list191 const_reference front() const 192 { 193 BOOST_ASSERT(!empty()); 194 return static_cast<node *>(_sentry._next)->_value; 195 } 196 backboost::xpressive::detail::list197 reference back() 198 { 199 BOOST_ASSERT(!empty()); 200 return static_cast<node *>(_sentry._prev)->_value; 201 } 202 backboost::xpressive::detail::list203 const_reference back() const 204 { 205 BOOST_ASSERT(!empty()); 206 return static_cast<node *>(_sentry._prev)->_value; 207 } 208 beginboost::xpressive::detail::list209 iterator begin() 210 { 211 return iterator(_sentry._next); 212 } 213 beginboost::xpressive::detail::list214 const_iterator begin() const 215 { 216 return const_iterator(_sentry._next); 217 } 218 endboost::xpressive::detail::list219 iterator end() 220 { 221 return iterator(&_sentry); 222 } 223 endboost::xpressive::detail::list224 const_iterator end() const 225 { 226 return const_iterator(const_cast<node_base *>(&_sentry)); 227 } 228 sizeboost::xpressive::detail::list229 size_type size() const 230 { 231 return static_cast<size_type>(std::distance(begin(), end())); 232 } 233 }; 234 235 template<typename T> swap(list<T> & lhs,list<T> & rhs)236 void swap(list<T> &lhs, list<T> &rhs) 237 { 238 lhs.swap(rhs); 239 } 240 241 }}} // namespace boost::xpressive::detail 242 243 #endif 244