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