MySQL 8.0.29
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
29template <typename T, typename L>
32template <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
72template <typename T, typename B, typename C = I_P_List_null_counter,
73 typename I = I_P_List_no_push_back<T>>
74class I_P_List : public C, public I {
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 }
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
166template <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
196template <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
240template <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
258template <typename T>
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
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
T ** get_last() const
Definition: sql_plist.h:265
Iterator for I_P_List.
Definition: sql_plist.h:167
void rewind()
Definition: sql_plist.h:188
T * operator++()
Definition: sql_plist.h:184
I_P_List_iterator(const L &a)
Definition: sql_plist.h:172
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
T * front()
Definition: sql_plist.h:132
T * pop_front()
Definition: sql_plist.h:134
I_P_List()
Definition: sql_plist.h:83
T * m_first
Definition: sql_plist.h:75
void insert_after(T *pos, T *a)
Definition: sql_plist.h:108
void push_front(T *a)
Definition: sql_plist.h:90
const T * front() const
Definition: sql_plist.h:133
I_P_List_iterator< T, Base > Iterator
Definition: sql_plist.h:156
#define L
Definition: ctype-tis620.cc:75
char * pos
Definition: do_ctype.cc:76
Fido Client Authentication nullptr
Definition: fido_client_plugin.cc:221
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:611
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 *** prev_ptr(T *el)
Definition: sql_plist.h:200
static T ** next_ptr(T *el)
Definition: sql_plist.h:198
Definition: result.h:29
unsigned int uint
Definition: uca-dump.cc:29