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-1335 USA */ 17 18 19 template <typename T, typename L> 20 class I_P_List_iterator; 21 class I_P_List_null_counter; 22 template <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 62 template <typename T, typename B, 63 typename C = I_P_List_null_counter, 64 typename I = I_P_List_no_push_back<T> > 65 class 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 */ 74 public: 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 172 template <typename T, typename L> 173 class I_P_List_iterator 174 { 175 const L *list; 176 T *current; 177 public: 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 /** 188 Operator for it++ 189 190 @note since we save next element pointer, caller may remove current element. 191 Such modification doesn't invalidate iterator. 192 */ 193 inline T* operator++(int) 194 { 195 T *result= current; 196 if (result) 197 current= *L::Adapter::next_ptr(current); 198 return result; 199 } 200 /* Operator for ++it */ 201 inline T* operator++() 202 { 203 current= *L::Adapter::next_ptr(current); 204 return current; 205 } 206 inline void rewind() 207 { 208 current= list->m_first; 209 } 210 }; 211 212 213 /** 214 Hook class which via its methods specifies which members 215 of T should be used for participating in a intrusive list. 216 */ 217 218 template <typename T, T* T::*next, T** T::*prev> 219 struct I_P_List_adapter 220 { 221 static inline T **next_ptr(T *el) { return &(el->*next); } 222 static inline const T* const* next_ptr(const T *el) { return &(el->*next); } 223 static inline T ***prev_ptr(T *el) { return &(el->*prev); } 224 }; 225 226 227 /** 228 Element counting policy class for I_P_List to be used in 229 cases when no element counting should be done. 230 */ 231 232 class I_P_List_null_counter 233 { 234 protected: 235 void reset() {} 236 void inc() {} 237 void dec() {} 238 void swap(I_P_List_null_counter &) {} 239 }; 240 241 242 /** 243 Element counting policy class for I_P_List which provides 244 basic element counting. 245 */ 246 247 class I_P_List_counter 248 { 249 uint m_counter; 250 protected: 251 I_P_List_counter() : m_counter (0) {} 252 void reset() {m_counter= 0;} 253 void inc() {m_counter++;} 254 void dec() {m_counter--;} 255 void swap(I_P_List_counter &rhs) 256 { swap_variables(uint, m_counter, rhs.m_counter); } 257 public: 258 uint elements() const { return m_counter; } 259 }; 260 261 262 /** 263 A null insertion policy class for I_P_List to be used 264 in cases when push_back() operation is not necessary. 265 */ 266 267 template <typename T> class I_P_List_no_push_back 268 { 269 protected: 270 I_P_List_no_push_back(T **) {} 271 void set_last(T **) {} 272 /* 273 T** get_last() const method is intentionally left unimplemented 274 in order to prohibit usage of push_back() method in lists which 275 use this policy. 276 */ 277 void swap(I_P_List_no_push_back<T> &) {} 278 }; 279 280 281 /** 282 An insertion policy class for I_P_List which can 283 be used when fast push_back() operation is required. 284 */ 285 286 template <typename T> class I_P_List_fast_push_back 287 { 288 T **m_last; 289 protected: 290 I_P_List_fast_push_back(T **a) : m_last(a) { }; 291 void set_last(T **a) { m_last= a; } 292 T** get_last() const { return m_last; } 293 void swap(I_P_List_fast_push_back<T> &rhs) 294 { swap_variables(T**, m_last, rhs.m_last); } 295 }; 296 297 #endif 298