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