1 /*****************************************************************************
2
3 Copyright (c) 1995, 2019, Oracle and/or its affiliates. All Rights Reserved.
4
5 This program is free software; you can redistribute it and/or modify it under
6 the terms of the GNU General Public License, version 2.0, as published by the
7 Free Software Foundation.
8
9 This program is also distributed with certain software (including but not
10 limited to OpenSSL) that is licensed under separate terms, as designated in a
11 particular file or component or in included license documentation. The authors
12 of MySQL hereby grant you an additional permission to link the program and
13 your derivative works with the separately licensed software that they have
14 included with MySQL.
15
16 This program is distributed in the hope that it will be useful, but WITHOUT
17 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
18 FOR A PARTICULAR PURPOSE. See the GNU General Public License, version 2.0,
19 for more details.
20
21 You should have received a copy of the GNU General Public License along with
22 this program; if not, write to the Free Software Foundation, Inc.,
23 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
24
25 *****************************************************************************/
26
27 /** @file include/ut0lst.h
28 List utilities
29
30 Created 9/10/1995 Heikki Tuuri
31 Rewritten by Sunny Bains Dec 2011.
32 ***********************************************************************/
33
34 #ifndef ut0lst_h
35 #define ut0lst_h
36
37 /* Do not include univ.i because univ.i includes this. */
38
39 #include "ut0dbg.h"
40
41 /* This module implements the two-way linear list. Note that a single
42 list node may belong to two or more lists, but is only on one list
43 at a time. */
44
45 /** The two way list node.
46 @tparam Type the list node type name */
47 template <typename Type>
48 struct ut_list_node {
49 Type *prev; /*!< pointer to the previous
50 node, NULL if start of list */
51 Type *next; /*!< pointer to next node,
52 NULL if end of list */
53
reverseut_list_node54 void reverse() {
55 Type *tmp = prev;
56 prev = next;
57 next = tmp;
58 }
59 };
60
61 /** Macro used for legacy reasons */
62 #define UT_LIST_NODE_T(t) ut_list_node<t>
63
64 /** The two-way list base node. The base node contains pointers to both ends
65 of the list and a count of nodes in the list (excluding the base node
66 from the count). We also store a pointer to the member field so that it
67 doesn't have to be specified when doing list operations.
68 @tparam Type the type of the list element
69 @tparam NodePtr field member pointer that points to the list node */
70 template <typename Type, typename NodePtr>
71 struct ut_list_base {
72 typedef Type elem_type;
73 typedef NodePtr node_ptr;
74 typedef ut_list_node<Type> node_type;
75
76 ulint count{0}; /*!< count of nodes in list */
77 elem_type *start{nullptr}; /*!< pointer to list start,
78 NULL if empty */
79 elem_type *end{nullptr}; /*!< pointer to list end,
80 NULL if empty */
81 node_ptr node{nullptr}; /*!< Pointer to member field
82 that is used as a link node */
83 #ifdef UNIV_DEBUG
84 ulint init{0}; /*!< UT_LIST_INITIALISED if
85 the list was initialised with
86 UT_LIST_INIT() */
87 #endif /* UNIV_DEBUG */
88
reverseut_list_base89 void reverse() {
90 Type *tmp = start;
91 start = end;
92 end = tmp;
93 }
94 };
95
96 #define UT_LIST_BASE_NODE_T(t) ut_list_base<t, ut_list_node<t> t::*>
97
98 #ifdef UNIV_DEBUG
99 #define UT_LIST_INITIALISED 0xCAFE
100 #define UT_LIST_INITIALISE(b) (b).init = UT_LIST_INITIALISED
101 #define UT_LIST_IS_INITIALISED(b) ut_a(((b).init == UT_LIST_INITIALISED))
102 #else
103 #define UT_LIST_INITIALISE(b)
104 #define UT_LIST_IS_INITIALISED(b)
105 #endif /* UNIV_DEBUG */
106
107 /** Note: This is really the list constructor. We should be able to use
108 placement new here.
109 Initializes the base node of a two-way list.
110 @param b the list base node
111 @param pmf point to member field that will be used as the link node */
112 #define UT_LIST_INIT(b, pmf) \
113 { \
114 (b).count = 0; \
115 (b).start = 0; \
116 (b).end = 0; \
117 (b).node = pmf; \
118 UT_LIST_INITIALISE(b); \
119 }
120
121 /** Functor for accessing the embedded node within a list element. This is
122 required because some lists can have the node emebedded inside a nested
123 struct/union. See lock0priv.h (table locks) for an example. It provides a
124 specialised functor to grant access to the list node. */
125 template <typename Type>
126 struct GenericGetNode {
127 typedef ut_list_node<Type> node_type;
128
GenericGetNodeGenericGetNode129 GenericGetNode(node_type Type::*node) : m_node(node) {}
130
operatorGenericGetNode131 node_type &operator()(Type &elem) { return (elem.*m_node); }
132
133 node_type Type::*m_node;
134 };
135
136 /** Adds the node as the first element in a two-way linked list.
137 @param list the base node (not a pointer to it)
138 @param elem the element to add */
139 template <typename List>
ut_list_prepend(List & list,typename List::elem_type * elem)140 void ut_list_prepend(List &list, typename List::elem_type *elem) {
141 typename List::node_type &elem_node = elem->*list.node;
142
143 UT_LIST_IS_INITIALISED(list);
144
145 elem_node.prev = nullptr;
146 elem_node.next = list.start;
147
148 if (list.start != nullptr) {
149 typename List::node_type &base_node = list.start->*list.node;
150
151 ut_ad(list.start != elem);
152
153 base_node.prev = elem;
154 }
155
156 list.start = elem;
157
158 if (list.end == nullptr) {
159 list.end = elem;
160 }
161
162 ++list.count;
163 }
164
165 /** Adds the node as the first element in a two-way linked list.
166 @param LIST the base node (not a pointer to it)
167 @param ELEM the element to add */
168 #define UT_LIST_ADD_FIRST(LIST, ELEM) ut_list_prepend(LIST, ELEM)
169
170 /** Adds the node as the last element in a two-way linked list.
171 @param list list
172 @param elem the element to add
173 @param get_node to get the list node for that element */
174 template <typename List, typename Functor>
ut_list_append(List & list,typename List::elem_type * elem,Functor get_node)175 void ut_list_append(List &list, typename List::elem_type *elem,
176 Functor get_node) {
177 typename List::node_type &node = get_node(*elem);
178
179 UT_LIST_IS_INITIALISED(list);
180
181 node.next = nullptr;
182 node.prev = list.end;
183
184 if (list.end != nullptr) {
185 typename List::node_type &base_node = get_node(*list.end);
186
187 ut_ad(list.end != elem);
188
189 base_node.next = elem;
190 }
191
192 list.end = elem;
193
194 if (list.start == nullptr) {
195 list.start = elem;
196 }
197
198 ++list.count;
199 }
200
201 /** Adds the node as the last element in a two-way linked list.
202 @param list list
203 @param elem the element to add */
204 template <typename List>
ut_list_append(List & list,typename List::elem_type * elem)205 void ut_list_append(List &list, typename List::elem_type *elem) {
206 ut_list_append(list, elem,
207 GenericGetNode<typename List::elem_type>(list.node));
208 }
209
210 /** Adds the node as the last element in a two-way linked list.
211 @param LIST list base node (not a pointer to it)
212 @param ELEM the element to add */
213 #define UT_LIST_ADD_LAST(LIST, ELEM) ut_list_append(LIST, ELEM)
214
215 /** Inserts a ELEM2 after ELEM1 in a list.
216 @param list the base node
217 @param elem1 node after which ELEM2 is inserted
218 @param elem2 node being inserted after ELEM1 */
219 template <typename List>
ut_list_insert(List & list,typename List::elem_type * elem1,typename List::elem_type * elem2)220 void ut_list_insert(List &list, typename List::elem_type *elem1,
221 typename List::elem_type *elem2) {
222 ut_ad(elem1 != elem2);
223 UT_LIST_IS_INITIALISED(list);
224
225 typename List::node_type &elem1_node = elem1->*list.node;
226 typename List::node_type &elem2_node = elem2->*list.node;
227
228 elem2_node.prev = elem1;
229 elem2_node.next = elem1_node.next;
230
231 if (elem1_node.next != nullptr) {
232 typename List::node_type &next_node = elem1_node.next->*list.node;
233
234 next_node.prev = elem2;
235 }
236
237 elem1_node.next = elem2;
238
239 if (list.end == elem1) {
240 list.end = elem2;
241 }
242
243 ++list.count;
244 }
245
246 /** Inserts a ELEM2 after ELEM1 in a list.
247 @param LIST list base node (not a pointer to it)
248 @param ELEM1 node after which ELEM2 is inserted
249 @param ELEM2 node being inserted after ELEM1 */
250 #define UT_LIST_INSERT_AFTER(LIST, ELEM1, ELEM2) \
251 ut_list_insert(LIST, ELEM1, ELEM2)
252
253 /** Removes a node from a two-way linked list.
254 @param list the base node (not a pointer to it)
255 @param node member node within list element that is to be removed
256 @param get_node functor to get the list node from elem */
257 template <typename List, typename Functor>
ut_list_remove(List & list,typename List::node_type & node,Functor get_node)258 void ut_list_remove(List &list, typename List::node_type &node,
259 Functor get_node) {
260 ut_a(list.count > 0);
261 UT_LIST_IS_INITIALISED(list);
262
263 if (node.next != nullptr) {
264 typename List::node_type &next_node = get_node(*node.next);
265
266 next_node.prev = node.prev;
267 } else {
268 list.end = node.prev;
269 }
270
271 if (node.prev != nullptr) {
272 typename List::node_type &prev_node = get_node(*node.prev);
273
274 prev_node.next = node.next;
275 } else {
276 list.start = node.next;
277 }
278
279 node.next = nullptr;
280 node.prev = nullptr;
281
282 --list.count;
283 }
284
285 /** Removes a node from a two-way linked list.
286 @param list the base node (not a pointer to it)
287 @param elem element to be removed from the list
288 @param get_node functor to get the list node from elem */
289 template <typename List, typename Functor>
ut_list_remove(List & list,typename List::elem_type * elem,Functor get_node)290 void ut_list_remove(List &list, typename List::elem_type *elem,
291 Functor get_node) {
292 ut_list_remove(list, get_node(*elem), get_node);
293 }
294
295 /** Removes a node from a two-way linked list.
296 @param list the base node (not a pointer to it)
297 @param elem element to be removed from the list */
298 template <typename List>
ut_list_remove(List & list,typename List::elem_type * elem)299 void ut_list_remove(List &list, typename List::elem_type *elem) {
300 ut_list_remove(list, elem->*list.node,
301 GenericGetNode<typename List::elem_type>(list.node));
302 }
303
304 /** Removes a node from a two-way linked list.
305 @param LIST the base node (not a pointer to it)
306 @param ELEM node to be removed from the list */
307 #define UT_LIST_REMOVE(LIST, ELEM) ut_list_remove(LIST, ELEM)
308
309 /** Gets the next node in a two-way list.
310 @param NAME list name
311 @param N pointer to a node
312 @return the successor of N in NAME, or NULL */
313 #define UT_LIST_GET_NEXT(NAME, N) (((N)->NAME).next)
314
315 /** Gets the previous node in a two-way list.
316 @param NAME list name
317 @param N pointer to a node
318 @return the predecessor of N in NAME, or NULL */
319 #define UT_LIST_GET_PREV(NAME, N) (((N)->NAME).prev)
320
321 /** Alternative macro to get the number of nodes in a two-way list, i.e.,
322 its length.
323 @param BASE the base node (not a pointer to it).
324 @return the number of nodes in the list */
325 #define UT_LIST_GET_LEN(BASE) (BASE).count
326
327 /** Gets the first node in a two-way list.
328 @param BASE the base node (not a pointer to it)
329 @return first node, or NULL if the list is empty */
330 #define UT_LIST_GET_FIRST(BASE) (BASE).start
331
332 /** Gets the last node in a two-way list.
333 @param BASE the base node (not a pointer to it)
334 @return last node, or NULL if the list is empty */
335 #define UT_LIST_GET_LAST(BASE) (BASE).end
336
337 struct NullValidate {
operatorNullValidate338 void operator()(const void *elem) {}
339 };
340
341 /** Iterate over all the elements and call the functor for each element.
342 @param[in] list base node (not a pointer to it)
343 @param[in,out] functor Functor that is called for each element in the list */
344 template <typename List, class Functor>
ut_list_map(const List & list,Functor & functor)345 void ut_list_map(const List &list, Functor &functor) {
346 ulint count = 0;
347
348 UT_LIST_IS_INITIALISED(list);
349
350 for (typename List::elem_type *elem = list.start; elem != nullptr;
351 elem = (elem->*list.node).next, ++count) {
352 functor(elem);
353 }
354
355 ut_a(count == list.count);
356 }
357
358 template <typename List>
ut_list_reverse(List & list)359 void ut_list_reverse(List &list) {
360 UT_LIST_IS_INITIALISED(list);
361
362 for (typename List::elem_type *elem = list.start; elem != nullptr;
363 elem = (elem->*list.node).prev) {
364 (elem->*list.node).reverse();
365 }
366
367 list.reverse();
368 }
369
370 #define UT_LIST_REVERSE(LIST) ut_list_reverse(LIST)
371
372 /** Checks the consistency of a two-way list.
373 @param[in] list base node (not a pointer to it)
374 @param[in,out] functor Functor that is called for each element in
375 the list */
376 template <typename List, class Functor>
ut_list_validate(const List & list,Functor & functor)377 void ut_list_validate(const List &list, Functor &functor) {
378 ut_list_map(list, functor);
379
380 /* Validate the list backwards. */
381 ulint count = 0;
382
383 for (typename List::elem_type *elem = list.end; elem != nullptr;
384 elem = (elem->*list.node).prev) {
385 ++count;
386 }
387
388 ut_a(count == list.count);
389 }
390
391 /** Check the consistency of a two-way list.
392 @param[in] LIST base node reference */
393 #define UT_LIST_CHECK(LIST) \
394 do { \
395 NullValidate nullV; \
396 ut_list_validate(LIST, nullV); \
397 } while (0)
398
399 /** Move the given element to the beginning of the list.
400 @param[in,out] list the list object
401 @param[in] elem the element of the list which will be moved
402 to the beginning of the list. */
403 template <typename List>
ut_list_move_to_front(List & list,typename List::elem_type * elem)404 void ut_list_move_to_front(List &list, typename List::elem_type *elem) {
405 ut_ad(ut_list_exists(list, elem));
406
407 if (UT_LIST_GET_FIRST(list) != elem) {
408 ut_list_remove(list, elem);
409 ut_list_prepend(list, elem);
410 }
411 }
412
413 #ifdef UNIV_DEBUG
414 /** Check if the given element exists in the list.
415 @param[in,out] list the list object
416 @param[in] elem the element of the list which will be checked */
417 template <typename List>
ut_list_exists(List & list,typename List::elem_type * elem)418 bool ut_list_exists(List &list, typename List::elem_type *elem) {
419 typename List::elem_type *e1;
420
421 for (e1 = UT_LIST_GET_FIRST(list); e1 != nullptr;
422 e1 = (e1->*list.node).next) {
423 if (elem == e1) {
424 return (true);
425 }
426 }
427 return (false);
428 }
429 #endif
430
431 #define UT_LIST_MOVE_TO_FRONT(LIST, ELEM) ut_list_move_to_front(LIST, ELEM)
432
433 #endif /* ut0lst.h */
434