1 //======================================================================= 2 // Copyright 2002 Indiana University. 3 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek 4 // 5 // Distributed under the Boost Software License, Version 1.0. (See 6 // accompanying file LICENSE_1_0.txt or copy at 7 // http://www.boost.org/LICENSE_1_0.txt) 8 //======================================================================= 9 10 #ifndef BOOST_LIST_BASE_HPP 11 #define BOOST_LIST_BASE_HPP 12 13 #include <boost/iterator_adaptors.hpp> 14 15 // Perhaps this should go through formal review, and move to <boost/>. 16 17 /* 18 An alternate interface idea: 19 Extend the std::list functionality by creating remove/insert 20 functions that do not require the container object! 21 */ 22 23 namespace boost { 24 namespace detail { 25 26 //========================================================================= 27 // Linked-List Generic Implementation Functions 28 29 template <class Node, class Next> 30 inline Node slist_insert_after(Node pos,Node x,Next next)31 slist_insert_after(Node pos, Node x, 32 Next next) 33 { 34 next(x) = next(pos); 35 next(pos) = x; 36 return x; 37 } 38 39 // return next(pos) or next(next(pos)) ? 40 template <class Node, class Next> 41 inline Node slist_remove_after(Node pos,Next next)42 slist_remove_after(Node pos, 43 Next next) 44 { 45 Node n = next(pos); 46 next(pos) = next(n); 47 return n; 48 } 49 50 template <class Node, class Next> 51 inline Node slist_remove_range(Node before_first,Node last,Next next)52 slist_remove_range(Node before_first, Node last, 53 Next next) 54 { 55 next(before_first) = last; 56 return last; 57 } 58 59 template <class Node, class Next> 60 inline Node slist_previous(Node head,Node x,Node nil,Next next)61 slist_previous(Node head, Node x, Node nil, 62 Next next) 63 { 64 while (head != nil && next(head) != x) 65 head = next(head); 66 return head; 67 } 68 69 template<class Node, class Next> 70 inline void slist_splice_after(Node pos,Node before_first,Node before_last,Next next)71 slist_splice_after(Node pos, Node before_first, Node before_last, 72 Next next) 73 { 74 if (pos != before_first && pos != before_last) { 75 Node first = next(before_first); 76 Node after = next(pos); 77 next(before_first) = next(before_last); 78 next(pos) = first; 79 next(before_last) = after; 80 } 81 } 82 83 template <class Node, class Next> 84 inline Node slist_reverse(Node node,Node nil,Next next)85 slist_reverse(Node node, Node nil, 86 Next next) 87 { 88 Node result = node; 89 node = next(node); 90 next(result) = nil; 91 while(node) { 92 Node next = next(node); 93 next(node) = result; 94 result = node; 95 node = next; 96 } 97 return result; 98 } 99 100 template <class Node, class Next> 101 inline std::size_t slist_size(Node head,Node nil,Next next)102 slist_size(Node head, Node nil, 103 Next next) 104 { 105 std::size_t s = 0; 106 for ( ; head != nil; head = next(head)) 107 ++s; 108 return s; 109 } 110 111 template <class Next, class Data> 112 class slist_iterator_policies 113 { 114 public: slist_iterator_policies(const Next & n,const Data & d)115 explicit slist_iterator_policies(const Next& n, const Data& d) 116 : m_next(n), m_data(d) { } 117 118 template <class Reference, class Node> 119 Reference dereference(type<Reference>, const Node& x) const 120 { return m_data(x); } 121 122 template <class Node> increment(Node & x) const123 void increment(Node& x) const 124 { x = m_next(x); } 125 126 template <class Node> equal(Node & x,Node & y) const127 bool equal(Node& x, Node& y) const 128 { return x == y; } 129 130 protected: 131 Next m_next; 132 Data m_data; 133 }; 134 135 //=========================================================================== 136 // Doubly-Linked List Generic Implementation Functions 137 138 template <class Node, class Next, class Prev> 139 inline void dlist_insert_before(Node pos,Node x,Next next,Prev prev)140 dlist_insert_before(Node pos, Node x, 141 Next next, Prev prev) 142 { 143 next(x) = pos; 144 prev(x) = prev(pos); 145 next(prev(pos)) = x; 146 prev(pos) = x; 147 } 148 149 template <class Node, class Next, class Prev> 150 void dlist_remove(Node pos,Next next,Prev prev)151 dlist_remove(Node pos, 152 Next next, Prev prev) 153 { 154 Node next_node = next(pos); 155 Node prev_node = prev(pos); 156 next(prev_node) = next_node; 157 prev(next_node) = prev_node; 158 } 159 160 // This deletes every node in the list except the 161 // sentinel node. 162 template <class Node, class Delete> 163 inline void dlist_clear(Node sentinel,Delete del)164 dlist_clear(Node sentinel, Delete del) 165 { 166 Node i, tmp; 167 i = next(sentinel); 168 while (i != sentinel) { 169 tmp = i; 170 i = next(i); 171 del(tmp); 172 } 173 } 174 175 template <class Node> 176 inline bool dlist_empty(Node dummy)177 dlist_empty(Node dummy) 178 { 179 return next(dummy) == dummy; 180 } 181 182 template <class Node, class Next, class Prev> 183 void dlist_transfer(Node pos,Node first,Node last,Next next,Prev prev)184 dlist_transfer(Node pos, Node first, Node last, 185 Next next, Prev prev) 186 { 187 if (pos != last) { 188 // Remove [first,last) from its old position 189 next(prev(last)) = pos; 190 next(prev(first)) = last; 191 next(prev(pos)) = first; 192 193 // Splice [first,last) into its new position 194 Node tmp = prev(pos); 195 prev(pos) = prev(last); 196 prev(last) = prev(first); 197 prev(first) = tmp; 198 } 199 } 200 201 template <class Next, class Prev, class Data> 202 class dlist_iterator_policies 203 : public slist_iterator_policies<Next, Data> 204 { 205 typedef slist_iterator_policies<Next, Data> Base; 206 public: 207 template <class Node> decrement(Node & x) const208 void decrement(Node& x) const 209 { x = m_prev(x); } 210 dlist_iterator_policies(Next n,Prev p,Data d)211 dlist_iterator_policies(Next n, Prev p, Data d) 212 : Base(n,d), m_prev(p) { } 213 protected: 214 Prev m_prev; 215 }; 216 217 } // namespace detail 218 } // namespace boost 219 220 #endif // BOOST_LIST_BASE_HPP 221