MySQL 8.4.3
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, 2024, 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 designed to work 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 either included with
15 the program or referenced in the documentation.
16
17 This program is distributed in the hope that it will be useful,
18 but WITHOUT ANY WARRANTY; without even the implied warranty of
19 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20 GNU General Public License, version 2.0, for more details.
21
22 You should have received a copy of the GNU General Public License
23 along with this program; if not, write to the Free Software
24 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
25
26#include <algorithm>
27
28#include "my_inttypes.h"
29
30template <typename T, typename L>
33template <typename T>
35
36/**
37 Intrusive parameterized list.
38
39 Unlike I_List does not require its elements to be descendant of ilink
40 class and therefore allows them to participate in several such lists
41 simultaneously.
42
43 Unlike List is doubly-linked list and thus supports efficient deletion
44 of element without iterator.
45
46 @tparam T Type of elements which will belong to list.
47 @tparam B Class which via its methods specifies which members
48 of T should be used for participating in this list.
49 Here is typical layout of such class:
50
51 struct B
52 {
53 static inline T **next_ptr(T *el)
54 {
55 return &el->next;
56 }
57 static inline T ***prev_ptr(T *el)
58 {
59 return &el->prev;
60 }
61 };
62 @tparam C Policy class specifying how counting of elements in the list
63 should be done. Instance of this class is also used as a place
64 where information about number of list elements is stored.
65 @sa I_P_List_null_counter, I_P_List_counter
66 @tparam I Policy class specifying whether I_P_List should support
67 efficient push_back() operation. Instance of this class
68 is used as place where we store information to support
69 this operation.
70 @sa I_P_List_no_push_back, I_P_List_fast_push_back.
71*/
72
73template <typename T, typename B, typename C = I_P_List_null_counter,
74 typename I = I_P_List_no_push_back<T>>
75class I_P_List : public C, public I {
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:
85 inline void clear() {
86 m_first = nullptr;
87 C::reset();
88 I::set_last(&m_first);
89 }
90 inline bool is_empty() const { return (m_first == nullptr); }
91 inline void push_front(T *a) {
92 *B::next_ptr(a) = m_first;
93 if (m_first)
94 *B::prev_ptr(m_first) = B::next_ptr(a);
95 else
96 I::set_last(B::next_ptr(a));
97 m_first = a;
98 *B::prev_ptr(a) = &m_first;
99 C::inc();
100 }
101 inline void push_back(T *a) {
102 T **last = I::get_last();
103 *B::next_ptr(a) = *last;
104 *last = a;
105 *B::prev_ptr(a) = last;
106 I::set_last(B::next_ptr(a));
107 C::inc();
108 }
109 inline void insert_after(T *pos, T *a) {
110 if (pos == nullptr)
111 push_front(a);
112 else {
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 T *old_next = *B::next_ptr(a);
118 *B::prev_ptr(old_next) = B::next_ptr(a);
119 } else
120 I::set_last(B::next_ptr(a));
121 C::inc();
122 }
123 }
124 inline void remove(T *a) {
125 T *next = *B::next_ptr(a);
126 if (next)
127 *B::prev_ptr(next) = *B::prev_ptr(a);
128 else
129 I::set_last(*B::prev_ptr(a));
130 **B::prev_ptr(a) = next;
131 C::dec();
132 }
133 inline T *front() { return m_first; }
134 inline const T *front() const { return m_first; }
135 inline T *pop_front() {
136 T *result = front();
137
138 if (result) remove(result);
139
140 return result;
141 }
144 I::swap(rhs);
145 if (m_first)
146 *B::prev_ptr(m_first) = &m_first;
147 else
148 I::set_last(&m_first);
149 if (rhs.m_first)
150 *B::prev_ptr(rhs.m_first) = &rhs.m_first;
151 else
152 I::set_last(&rhs.m_first);
153 C::swap(rhs);
154 }
155 typedef B Adapter;
159 friend class I_P_List_iterator<T, Base>;
160 friend class I_P_List_iterator<const T, Base>;
161};
162
163/**
164 Iterator for I_P_List.
165*/
166
167template <typename T, typename L>
169 const L *list;
171
172 public:
173 I_P_List_iterator(const L &a) : list(&a), current(a.m_first) {}
174 I_P_List_iterator(const L &a, T *current_arg)
175 : list(&a), current(current_arg) {}
176 inline void init(const L &a) {
177 list = &a;
178 current = a.m_first;
179 }
180 inline T *operator++(int) {
181 T *result = current;
182 if (result) current = *L::Adapter::next_ptr(current);
183 return result;
184 }
185 inline T *operator++() {
186 current = *L::Adapter::next_ptr(current);
187 return current;
188 }
189 inline void rewind() { current = list->m_first; }
190};
191
192/**
193 Hook class which via its methods specifies which members
194 of T should be used for participating in a intrusive list.
195*/
196
197template <typename T, T *T::*next, T **T::*prev>
199 static inline T **next_ptr(T *el) { return &(el->*next); }
200 static inline const T *const *next_ptr(const T *el) { return &(el->*next); }
201 static inline T ***prev_ptr(T *el) { return &(el->*prev); }
202};
203
204/**
205 Element counting policy class for I_P_List to be used in
206 cases when no element counting should be done.
207*/
208
210 protected:
211 void reset() {}
212 void inc() {}
213 void dec() {}
215};
216
217/**
218 Element counting policy class for I_P_List which provides
219 basic element counting.
220*/
221
224
225 protected:
227 void reset() { m_counter = 0; }
228 void inc() { m_counter++; }
229 void dec() { m_counter--; }
231
232 public:
233 uint elements() const { return m_counter; }
234};
235
236/**
237 A null insertion policy class for I_P_List to be used
238 in cases when push_back() operation is not necessary.
239*/
240
241template <typename T>
243 protected:
245 void set_last(T **) {}
246 /*
247 T** get_last() const method is intentionally left unimplemented
248 in order to prohibit usage of push_back() method in lists which
249 use this policy.
250 */
252};
253
254/**
255 An insertion policy class for I_P_List which can
256 be used when fast push_back() operation is required.
257*/
258
259template <typename T>
262
263 protected:
265 void set_last(T **a) { m_last = a; }
266 T **get_last() const { return m_last; }
268};
269
270#endif
Kerberos Client Authentication nullptr
Definition: auth_kerberos_client_plugin.cc:251
Element counting policy class for I_P_List which provides basic element counting.
Definition: sql_plist.h:222
uint elements() const
Definition: sql_plist.h:233
uint m_counter
Definition: sql_plist.h:223
void reset()
Definition: sql_plist.h:227
void inc()
Definition: sql_plist.h:228
void swap(I_P_List_counter &rhs)
Definition: sql_plist.h:230
void dec()
Definition: sql_plist.h:229
I_P_List_counter()
Definition: sql_plist.h:226
An insertion policy class for I_P_List which can be used when fast push_back() operation is required.
Definition: sql_plist.h:260
void swap(I_P_List_fast_push_back< T > &rhs)
Definition: sql_plist.h:267
void set_last(T **a)
Definition: sql_plist.h:265
T ** m_last
Definition: sql_plist.h:261
I_P_List_fast_push_back(T **a)
Definition: sql_plist.h:264
T ** get_last() const
Definition: sql_plist.h:266
Iterator for I_P_List.
Definition: sql_plist.h:168
void rewind()
Definition: sql_plist.h:189
T * operator++()
Definition: sql_plist.h:185
I_P_List_iterator(const L &a)
Definition: sql_plist.h:173
void init(const L &a)
Definition: sql_plist.h:176
const L * list
Definition: sql_plist.h:169
I_P_List_iterator(const L &a, T *current_arg)
Definition: sql_plist.h:174
T * current
Definition: sql_plist.h:170
T * operator++(int)
Definition: sql_plist.h:180
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:242
I_P_List_no_push_back(T **)
Definition: sql_plist.h:244
void swap(I_P_List_no_push_back< T > &)
Definition: sql_plist.h:251
void set_last(T **)
Definition: sql_plist.h:245
Element counting policy class for I_P_List to be used in cases when no element counting should be don...
Definition: sql_plist.h:209
void dec()
Definition: sql_plist.h:213
void swap(I_P_List_null_counter &)
Definition: sql_plist.h:214
void reset()
Definition: sql_plist.h:211
void inc()
Definition: sql_plist.h:212
Intrusive parameterized list.
Definition: sql_plist.h:75
void remove(T *a)
Definition: sql_plist.h:124
void clear()
Definition: sql_plist.h:85
bool is_empty() const
Definition: sql_plist.h:90
void push_back(T *a)
Definition: sql_plist.h:101
I_P_List< T, B, C, I > Base
Definition: sql_plist.h:156
void swap(I_P_List< T, B, C > &rhs)
Definition: sql_plist.h:142
B Adapter
Definition: sql_plist.h:155
I_P_List_iterator< const T, Base > Const_Iterator
Definition: sql_plist.h:158
T * front()
Definition: sql_plist.h:133
T * pop_front()
Definition: sql_plist.h:135
I_P_List()
Definition: sql_plist.h:84
T * m_first
Definition: sql_plist.h:76
void insert_after(T *pos, T *a)
Definition: sql_plist.h:109
void push_front(T *a)
Definition: sql_plist.h:91
const T * front() const
Definition: sql_plist.h:134
I_P_List_iterator< T, Base > Iterator
Definition: sql_plist.h:157
#define L
Definition: ctype-tis620.cc:75
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:293
std::string HARNESS_EXPORT reset()
get 'reset attributes' ESC sequence.
Definition: vt100.cc:37
struct result result
Definition: result.h:34
static void swap(String &a, String &b) noexcept
Definition: sql_string.h:663
Hook class which via its methods specifies which members of T should be used for participating in a i...
Definition: sql_plist.h:198
static const T *const * next_ptr(const T *el)
Definition: sql_plist.h:200
static T *** prev_ptr(T *el)
Definition: sql_plist.h:201
static T ** next_ptr(T *el)
Definition: sql_plist.h:199
Definition: result.h:30