MySQL  8.0.21
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, 2019, 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
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>
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:
83  I_P_List() : I(&m_first), m_first(nullptr) {}
84  inline void empty() {
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>
167 class I_P_List_iterator {
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:
225  I_P_List_counter() : m_counter(0) {}
226  void reset() { m_counter = 0; }
227  void inc() { m_counter++; }
228  void dec() { m_counter--; }
229  void swap(I_P_List_counter &rhs) { std::swap(m_counter, rhs.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>
241 class I_P_List_no_push_back {
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:
263  I_P_List_fast_push_back(T **a) : m_last(a) {}
264  void set_last(T **a) { m_last = a; }
265  T **get_last() const { return m_last; }
266  void swap(I_P_List_fast_push_back<T> &rhs) { std::swap(m_last, rhs.m_last); }
267 };
268 
269 #endif
Definition: result.h:29
static const T *const * next_ptr(const T *el)
Definition: sql_plist.h:199
bool is_empty() const
Definition: sql_plist.h:89
struct result result
Definition: result.h:33
void reset()
Definition: sql_plist.h:226
Iterator for I_P_List.
Definition: sql_plist.h:30
void swap(I_P_List< T, B, C > &rhs)
Definition: sql_plist.h:141
Some integer typedefs for easier portability.
void push_back(T *a)
Definition: sql_plist.h:100
void empty()
Definition: sql_plist.h:84
Type dec(Shards< COUNT > &shards, size_t id)
Decrement the counter of a shard by 1.
Definition: ut0counter.h:301
void swap(I_P_List_null_counter &)
Definition: sql_plist.h:213
I_P_List< T, B, C, I > Base
Definition: sql_plist.h:155
void insert_after(T *pos, T *a)
Definition: sql_plist.h:108
T * current
Definition: sql_plist.h:169
I_P_List_iterator< const T, Base > Const_Iterator
Definition: sql_plist.h:157
void dec()
Definition: sql_plist.h:228
I_P_List_iterator(const L &a, T *current_arg)
Definition: sql_plist.h:173
void inc()
Definition: sql_plist.h:227
void init(const L &a)
Definition: sql_plist.h:175
I_P_List_iterator< T, Base > Iterator
Definition: sql_plist.h:156
T * operator++(int)
Definition: sql_plist.h:179
void rewind()
Definition: sql_plist.h:188
void dec()
Definition: sql_plist.h:212
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
B Adapter
Definition: sql_plist.h:154
I_P_List_no_push_back(T **)
Definition: sql_plist.h:243
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
Hook class which via its methods specifies which members of T should be used for participating in a i...
Definition: sql_plist.h:197
char * pos
Definition: do_ctype.cc:76
T ** get_last() const
Definition: sql_plist.h:265
I_P_List_iterator(const L &a)
Definition: sql_plist.h:172
T ** m_last
Definition: sql_plist.h:260
I_P_List_fast_push_back(T **a)
Definition: sql_plist.h:263
uint elements() const
Definition: sql_plist.h:232
unsigned int uint
Definition: uca-dump.cc:29
Intrusive parameterized list.
Definition: sql_plist.h:74
std::string HARNESS_EXPORT reset()
get &#39;reset attributes&#39; ESC sequence.
Definition: vt100.cc:36
void reset()
Definition: sql_plist.h:210
void push_front(T *a)
Definition: sql_plist.h:90
T * m_first
Definition: sql_plist.h:75
void inc()
Definition: sql_plist.h:211
static T *** prev_ptr(T *el)
Definition: sql_plist.h:200
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:33
void swap(I_P_List_fast_push_back< T > &rhs)
Definition: sql_plist.h:266
static T ** next_ptr(T *el)
Definition: sql_plist.h:198
#define L
Definition: ctype-tis620.cc:75
Element counting policy class for I_P_List which provides basic element counting. ...
Definition: sql_plist.h:221
static void swap(String &a, String &b) noexcept
Definition: sql_string.h:606
T * operator++()
Definition: sql_plist.h:184
const L * list
Definition: sql_plist.h:168
Type inc(Shards< COUNT > &shards, size_t id)
Increment the counter of a shard by 1.
Definition: ut0counter.h:292
T * front()
Definition: sql_plist.h:132
I_P_List()
Definition: sql_plist.h:83
void set_last(T **a)
Definition: sql_plist.h:264
uint m_counter
Definition: sql_plist.h:222
T * pop_front()
Definition: sql_plist.h:134
void swap(I_P_List_no_push_back< T > &)
Definition: sql_plist.h:250
void set_last(T **)
Definition: sql_plist.h:244
void swap(I_P_List_counter &rhs)
Definition: sql_plist.h:229
const T * front() const
Definition: sql_plist.h:133
Dialog Client Authentication nullptr
Definition: dialog.cc:353