1#ifndef SQL_PLIST_H
2#define SQL_PLIST_H
3/* Copyright (c) 2008, 2011, Oracle and/or its affiliates. All rights reserved.
4
5 This program is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published by
7 the Free Software Foundation; version 2 of the License.
8
9 This program is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 GNU General Public License for more details.
13
14 You should have received a copy of the GNU General Public License
15 along with this program; if not, write to the Free Software
16 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
17
18
19template <typename T, typename L>
20class I_P_List_iterator;
21class I_P_List_null_counter;
22template <typename T> class I_P_List_no_push_back;
23
24
25/**
26 Intrusive parameterized list.
27
28 Unlike I_List does not require its elements to be descendant of ilink
29 class and therefore allows them to participate in several such lists
30 simultaneously.
31
32 Unlike List is doubly-linked list and thus supports efficient deletion
33 of element without iterator.
34
35 @param T Type of elements which will belong to list.
36 @param B Class which via its methods specifies which members
37 of T should be used for participating in this list.
38 Here is typical layout of such class:
39
40 struct B
41 {
42 static inline T **next_ptr(T *el)
43 {
44 return &el->next;
45 }
46 static inline T ***prev_ptr(T *el)
47 {
48 return &el->prev;
49 }
50 };
51 @param C Policy class specifying how counting of elements in the list
52 should be done. Instance of this class is also used as a place
53 where information about number of list elements is stored.
54 @sa I_P_List_null_counter, I_P_List_counter
55 @param I Policy class specifying whether I_P_List should support
56 efficient push_back() operation. Instance of this class
57 is used as place where we store information to support
58 this operation.
59 @sa I_P_List_no_push_back, I_P_List_fast_push_back.
60*/
61
62template <typename T, typename B,
63 typename C = I_P_List_null_counter,
64 typename I = I_P_List_no_push_back<T> >
65class I_P_List : public C, public I
66{
67 T *m_first;
68
69 /*
70 Do not prohibit copying of I_P_List object to simplify their usage in
71 backup/restore scenarios. Note that performing any operations on such
72 is a bad idea.
73 */
74public:
75 I_P_List() : I(&m_first), m_first(NULL) {};
76 /*
77 empty() is used in many places in the code instead of a constructor, to
78 initialize a bzero-ed I_P_List instance.
79 */
80
81 inline void empty() { m_first= NULL; C::reset(); I::set_last(&m_first); }
82 inline bool is_empty() const { return (m_first == NULL); }
83 inline void push_front(T* a)
84 {
85 *B::next_ptr(a)= m_first;
86 if (m_first)
87 *B::prev_ptr(m_first)= B::next_ptr(a);
88 else
89 I::set_last(B::next_ptr(a));
90 m_first= a;
91 *B::prev_ptr(a)= &m_first;
92 C::inc();
93 }
94 inline void push_back(T *a)
95 {
96 T **last= I::get_last();
97 *B::next_ptr(a)= *last;
98 *last= a;
99 *B::prev_ptr(a)= last;
100 I::set_last(B::next_ptr(a));
101 C::inc();
102 }
103 inline void insert_after(T *pos, T *a)
104 {
105 if (pos == NULL)
106 push_front(a);
107 else
108 {
109 *B::next_ptr(a)= *B::next_ptr(pos);
110 *B::prev_ptr(a)= B::next_ptr(pos);
111 *B::next_ptr(pos)= a;
112 if (*B::next_ptr(a))
113 {
114 T *old_next= *B::next_ptr(a);
115 *B::prev_ptr(old_next)= B::next_ptr(a);
116 }
117 else
118 I::set_last(B::next_ptr(a));
119 C::inc();
120 }
121 }
122 inline void remove(T *a)
123 {
124 T *next= *B::next_ptr(a);
125 if (next)
126 *B::prev_ptr(next)= *B::prev_ptr(a);
127 else
128 I::set_last(*B::prev_ptr(a));
129 **B::prev_ptr(a)= next;
130 C::dec();
131 }
132 inline T* front() { return m_first; }
133 inline const T *front() const { return m_first; }
134 inline T* pop_front()
135 {
136 T *result= front();
137
138 if (result)
139 remove(result);
140
141 return result;
142 }
143 void swap(I_P_List<T, B, C> &rhs)
144 {
145 swap_variables(T *, m_first, rhs.m_first);
146 I::swap(rhs);
147 if (m_first)
148 *B::prev_ptr(m_first)= &m_first;
149 else
150 I::set_last(&m_first);
151 if (rhs.m_first)
152 *B::prev_ptr(rhs.m_first)= &rhs.m_first;
153 else
154 I::set_last(&rhs.m_first);
155 C::swap(rhs);
156 }
157 typedef B Adapter;
158 typedef I_P_List<T, B, C, I> Base;
159 typedef I_P_List_iterator<T, Base> Iterator;
160 typedef I_P_List_iterator<const T, Base> Const_Iterator;
161#ifndef _lint
162 friend class I_P_List_iterator<T, Base>;
163 friend class I_P_List_iterator<const T, Base>;
164#endif
165};
166
167
168/**
169 Iterator for I_P_List.
170*/
171
172template <typename T, typename L>
173class I_P_List_iterator
174{
175 const L *list;
176 T *current;
177public:
178 I_P_List_iterator(const L &a)
179 : list(&a), current(a.m_first) {}
180 I_P_List_iterator(const L &a, T* current_arg)
181 : list(&a), current(current_arg) {}
182 inline void init(const L &a)
183 {
184 list= &a;
185 current= a.m_first;
186 }
187 /* Operator for it++ */
188 inline T* operator++(int)
189 {
190 T *result= current;
191 if (result)
192 current= *L::Adapter::next_ptr(current);
193 return result;
194 }
195 /* Operator for ++it */
196 inline T* operator++()
197 {
198 current= *L::Adapter::next_ptr(current);
199 return current;
200 }
201 inline void rewind()
202 {
203 current= list->m_first;
204 }
205};
206
207
208/**
209 Hook class which via its methods specifies which members
210 of T should be used for participating in a intrusive list.
211*/
212
213template <typename T, T* T::*next, T** T::*prev>
214struct I_P_List_adapter
215{
216 static inline T **next_ptr(T *el) { return &(el->*next); }
217 static inline const T* const* next_ptr(const T *el) { return &(el->*next); }
218 static inline T ***prev_ptr(T *el) { return &(el->*prev); }
219};
220
221
222/**
223 Element counting policy class for I_P_List to be used in
224 cases when no element counting should be done.
225*/
226
227class I_P_List_null_counter
228{
229protected:
230 void reset() {}
231 void inc() {}
232 void dec() {}
233 void swap(I_P_List_null_counter &) {}
234};
235
236
237/**
238 Element counting policy class for I_P_List which provides
239 basic element counting.
240*/
241
242class I_P_List_counter
243{
244 uint m_counter;
245protected:
246 I_P_List_counter() : m_counter (0) {}
247 void reset() {m_counter= 0;}
248 void inc() {m_counter++;}
249 void dec() {m_counter--;}
250 void swap(I_P_List_counter &rhs)
251 { swap_variables(uint, m_counter, rhs.m_counter); }
252public:
253 uint elements() const { return m_counter; }
254};
255
256
257/**
258 A null insertion policy class for I_P_List to be used
259 in cases when push_back() operation is not necessary.
260*/
261
262template <typename T> class I_P_List_no_push_back
263{
264protected:
265 I_P_List_no_push_back(T **) {}
266 void set_last(T **) {}
267 /*
268 T** get_last() const method is intentionally left unimplemented
269 in order to prohibit usage of push_back() method in lists which
270 use this policy.
271 */
272 void swap(I_P_List_no_push_back<T> &) {}
273};
274
275
276/**
277 An insertion policy class for I_P_List which can
278 be used when fast push_back() operation is required.
279*/
280
281template <typename T> class I_P_List_fast_push_back
282{
283 T **m_last;
284protected:
285 I_P_List_fast_push_back(T **a) : m_last(a) { };
286 void set_last(T **a) { m_last= a; }
287 T** get_last() const { return m_last; }
288 void swap(I_P_List_fast_push_back<T> &rhs)
289 { swap_variables(T**, m_last, rhs.m_last); }
290};
291
292#endif
293