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