MySQL  8.0.27
Source Code Documentation
sql_plist.h
Go to the documentation of this file.
1 #ifndef SQL_PLIST_H
2 #define SQL_PLIST_H
3 /* Copyright (c) 2009, 2021, Oracle and/or its affiliates.
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
23  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
24 
25 #include <algorithm>
26 
27 #include "my_inttypes.h"
28 
29 template <typename T, typename L>
30 class I_P_List_iterator;
32 template <typename T>
34 
35 /**
36  Intrusive parameterized list.
37 
38  Unlike I_List does not require its elements to be descendant of ilink
39  class and therefore allows them to participate in several such lists
40  simultaneously.
41 
42  Unlike List is doubly-linked list and thus supports efficient deletion
43  of element without iterator.
44 
45  @tparam T Type of elements which will belong to list.
46  @tparam B Class which via its methods specifies which members
47  of T should be used for participating in this list.
48  Here is typical layout of such class:
49 
50  struct B
51  {
52  static inline T **next_ptr(T *el)
53  {
54  return &el->next;
55  }
56  static inline T ***prev_ptr(T *el)
57  {
58  return &el->prev;
59  }
60  };
61  @tparam C Policy class specifying how counting of elements in the list
62  should be done. Instance of this class is also used as a place
63  where information about number of list elements is stored.
64  @sa I_P_List_null_counter, I_P_List_counter
65  @tparam I Policy class specifying whether I_P_List should support
66  efficient push_back() operation. Instance of this class
67  is used as place where we store information to support
68  this operation.
69  @sa I_P_List_no_push_back, I_P_List_fast_push_back.
70 */
71 
72 template <typename T, typename B, 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  T *m_first;
76 
77  /*
78  Do not prohibit copying of I_P_List object to simplify their usage in
79  backup/restore scenarios. Note that performing any operations on such
80  is a bad idea.
81  */
82  public:
84  inline void clear() {
85  m_first = nullptr;
86  C::reset();
87  I::set_last(&m_first);
88  }
89  inline bool is_empty() const { return (m_first == nullptr); }
90  inline void push_front(T *a) {
91  *B::next_ptr(a) = m_first;
92  if (m_first)
93  *B::prev_ptr(m_first) = B::next_ptr(a);
94  else
95  I::set_last(B::next_ptr(a));
96  m_first = a;
97  *B::prev_ptr(a) = &m_first;
98  C::inc();
99  }
100  inline void push_back(T *a) {
101  T **last = I::get_last();
102  *B::next_ptr(a) = *last;
103  *last = a;
104  *B::prev_ptr(a) = last;
105  I::set_last(B::next_ptr(a));
106  C::inc();
107  }
108  inline void insert_after(T *pos, T *a) {
109  if (pos == nullptr)
110  push_front(a);
111  else {
112  *B::next_ptr(a) = *B::next_ptr(pos);
113  *B::prev_ptr(a) = B::next_ptr(pos);
114  *B::next_ptr(pos) = a;
115  if (*B::next_ptr(a)) {
116  T *old_next = *B::next_ptr(a);
117  *B::prev_ptr(old_next) = B::next_ptr(a);
118  } else
119  I::set_last(B::next_ptr(a));
120  C::inc();
121  }
122  }
123  inline void remove(T *a) {
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  T *result = front();
136 
137  if (result) remove(result);
138 
139  return result;
140  }
141  void swap(I_P_List<T, B, C> &rhs) {
142  std::swap(m_first, rhs.m_first);
143  I::swap(rhs);
144  if (m_first)
145  *B::prev_ptr(m_first) = &m_first;
146  else
147  I::set_last(&m_first);
148  if (rhs.m_first)
149  *B::prev_ptr(rhs.m_first) = &rhs.m_first;
150  else
151  I::set_last(&rhs.m_first);
152  C::swap(rhs);
153  }
154  typedef B Adapter;
158  friend class I_P_List_iterator<T, Base>;
159  friend class I_P_List_iterator<const T, Base>;
160 };
161 
162 /**
163  Iterator for I_P_List.
164 */
165 
166 template <typename T, typename L>
168  const L *list;
170 
171  public:
172  I_P_List_iterator(const L &a) : list(&a), current(a.m_first) {}
173  I_P_List_iterator(const L &a, T *current_arg)
174  : list(&a), current(current_arg) {}
175  inline void init(const L &a) {
176  list = &a;
177  current = a.m_first;
178  }
179  inline T *operator++(int) {
180  T *result = current;
181  if (result) current = *L::Adapter::next_ptr(current);
182  return result;
183  }
184  inline T *operator++() {
185  current = *L::Adapter::next_ptr(current);
186  return current;
187  }
188  inline void rewind() { current = list->m_first; }
189 };
190 
191 /**
192  Hook class which via its methods specifies which members
193  of T should be used for participating in a intrusive list.
194 */
195 
196 template <typename T, T *T::*next, T **T::*prev>
198  static inline T **next_ptr(T *el) { return &(el->*next); }
199  static inline const T *const *next_ptr(const T *el) { return &(el->*next); }
200  static inline T ***prev_ptr(T *el) { return &(el->*prev); }
201 };
202 
203 /**
204  Element counting policy class for I_P_List to be used in
205  cases when no element counting should be done.
206 */
207 
209  protected:
210  void reset() {}
211  void inc() {}
212  void dec() {}
214 };
215 
216 /**
217  Element counting policy class for I_P_List which provides
218  basic element counting.
219 */
220 
223 
224  protected:
226  void reset() { m_counter = 0; }
227  void inc() { m_counter++; }
228  void dec() { m_counter--; }
230 
231  public:
232  uint elements() const { return m_counter; }
233 };
234 
235 /**
236  A null insertion policy class for I_P_List to be used
237  in cases when push_back() operation is not necessary.
238 */
239 
240 template <typename T>
242  protected:
244  void set_last(T **) {}
245  /*
246  T** get_last() const method is intentionally left unimplemented
247  in order to prohibit usage of push_back() method in lists which
248  use this policy.
249  */
251 };
252 
253 /**
254  An insertion policy class for I_P_List which can
255  be used when fast push_back() operation is required.
256 */
257 
258 template <typename T>
260  T **m_last;
261 
262  protected:
264  void set_last(T **a) { m_last = a; }
265  T **get_last() const { return m_last; }
267 };
268 
269 #endif
Element counting policy class for I_P_List which provides basic element counting.
Definition: sql_plist.h:221
uint elements() const
Definition: sql_plist.h:232
uint m_counter
Definition: sql_plist.h:222
void reset()
Definition: sql_plist.h:226
void inc()
Definition: sql_plist.h:227
void swap(I_P_List_counter &rhs)
Definition: sql_plist.h:229
void dec()
Definition: sql_plist.h:228
I_P_List_counter()
Definition: sql_plist.h:225
An insertion policy class for I_P_List which can be used when fast push_back() operation is required.
Definition: sql_plist.h:259
void swap(I_P_List_fast_push_back< T > &rhs)
Definition: sql_plist.h:266
T ** get_last() const
Definition: sql_plist.h:265
void set_last(T **a)
Definition: sql_plist.h:264
T ** m_last
Definition: sql_plist.h:260
I_P_List_fast_push_back(T **a)
Definition: sql_plist.h:263
Iterator for I_P_List.
Definition: sql_plist.h:167
void rewind()
Definition: sql_plist.h:188
I_P_List_iterator(const L &a)
Definition: sql_plist.h:172
T * operator++()
Definition: sql_plist.h:184
void init(const L &a)
Definition: sql_plist.h:175
const L * list
Definition: sql_plist.h:168
I_P_List_iterator(const L &a, T *current_arg)
Definition: sql_plist.h:173
T * current
Definition: sql_plist.h:169
T * operator++(int)
Definition: sql_plist.h:179
A null insertion policy class for I_P_List to be used in cases when push_back() operation is not nece...
Definition: sql_plist.h:241
I_P_List_no_push_back(T **)
Definition: sql_plist.h:243
void swap(I_P_List_no_push_back< T > &)
Definition: sql_plist.h:250
void set_last(T **)
Definition: sql_plist.h:244
Element counting policy class for I_P_List to be used in cases when no element counting should be don...
Definition: sql_plist.h:208
void dec()
Definition: sql_plist.h:212
void swap(I_P_List_null_counter &)
Definition: sql_plist.h:213
void reset()
Definition: sql_plist.h:210
void inc()
Definition: sql_plist.h:211
Intrusive parameterized list.
Definition: sql_plist.h:74
void remove(T *a)
Definition: sql_plist.h:123
void clear()
Definition: sql_plist.h:84
bool is_empty() const
Definition: sql_plist.h:89
void push_back(T *a)
Definition: sql_plist.h:100
I_P_List< T, B, C, I > Base
Definition: sql_plist.h:155
void swap(I_P_List< T, B, C > &rhs)
Definition: sql_plist.h:141
B Adapter
Definition: sql_plist.h:154
I_P_List_iterator< const T, Base > Const_Iterator
Definition: sql_plist.h:157
const T * front() const
Definition: sql_plist.h:133
I_P_List()
Definition: sql_plist.h:83
T * m_first
Definition: sql_plist.h:75
T * pop_front()
Definition: sql_plist.h:134
void insert_after(T *pos, T *a)
Definition: sql_plist.h:108
void push_front(T *a)
Definition: sql_plist.h:90
T * front()
Definition: sql_plist.h:132
I_P_List_iterator< T, Base > Iterator
Definition: sql_plist.h:156
#define L
Definition: ctype-tis620.cc:75
Dialog Client Authentication nullptr
Definition: dialog.cc:352
char * pos
Definition: do_ctype.cc:76
static const std::string dec("DECRYPTION")
Some integer typedefs for easier portability.
Type inc(Shards< COUNT > &shards, size_t id)
Increment the counter of a shard by 1.
Definition: ut0counter.h:292
std::string HARNESS_EXPORT reset()
get 'reset attributes' ESC sequence.
Definition: vt100.cc:36
struct result result
Definition: result.h:33
static void swap(String &a, String &b) noexcept
Definition: sql_string.h:610
Hook class which via its methods specifies which members of T should be used for participating in a i...
Definition: sql_plist.h:197
static const T *const * next_ptr(const T *el)
Definition: sql_plist.h:199
static T ** next_ptr(T *el)
Definition: sql_plist.h:198
static T *** prev_ptr(T *el)
Definition: sql_plist.h:200
Definition: result.h:29
unsigned int uint
Definition: uca-dump.cc:29