MySQL 8.0.31
Source Code Documentation
ut0lst.h File Reference

List utilities. More...

#include <atomic>
#include "ut0dbg.h"

Go to the source code of this file.

Classes

struct  ut_list_node< Type >
 The two way list node. More...
 
struct  ut_list_base< Type, NodeGetter >
 The two-way list base node. More...
 
class  ut_list_base< Type, NodeGetter >::base_iterator< E >
 
class  ut_list_base< Type, NodeGetter >::Removable
 A helper wrapper class for the list, which exposes begin(),end() iterators which let you remove the current item or items after it during the loop, while still having O(1) space and time complexity. More...
 
class  ut_list_base< Type, NodeGetter >::Removable::iterator
 
struct  ut_list_base_explicit_getter< Type, node_ptr >
 
struct  NullValidate
 

Macros

#define UT_LIST_NODE_T(t)   ut_list_node<t>
 Macro used for legacy reasons. More...
 
#define UT_LIST_INITIALISED   0xCAFE
 
#define UT_LIST_IS_INITIALISED(b)   ((b).init == UT_LIST_INITIALISED)
 
#define UT_LIST_BASE_NODE_T(t, m)    ut_list_base<t, ut_list_base_explicit_getter<t, &t::m>>
 A type of a list storing pointers to t, chained by member m of t. More...
 
#define UT_LIST_NODE_GETTER(t, m)   t##_##m##_node_getter
 A helper for the UT_LIST_BASE_NODE_T_EXTERN which builds a name of a node getter struct from the name of elem type t, and its member name m. More...
 
#define UT_LIST_NODE_GETTER_DEFINITION(t, m)
 A helper for the UT_LIST_BASE_NODE_T_EXTERN which declares a node getter struct which extracts member m from element of type t. More...
 
#define UT_LIST_BASE_NODE_T_EXTERN(t, m)    ut_list_base<t, struct UT_LIST_NODE_GETTER(t, m)>
 A variant of UT_LIST_BASE_NODE_T to be used in rare cases where the full definition of t is not yet in scope, and thus UT_LIST_BASE_NODE_T can't be used yet as it needs to know how to access member m of t. More...
 
#define UT_LIST_INIT(b)
 Initializes the base node of a two-way list. More...
 
#define UT_LIST_ADD_FIRST(LIST, ELEM)   ut_list_prepend(LIST, ELEM)
 Adds the node as the first element in a two-way linked list. More...
 
#define UT_LIST_ADD_LAST(LIST, ELEM)   ut_list_append(LIST, ELEM)
 Adds the node as the last element in a two-way linked list. More...
 
#define UT_LIST_INSERT_AFTER(LIST, ELEM1, ELEM2)    ut_list_insert(LIST, ELEM1, ELEM2)
 Inserts a ELEM2 after ELEM1 in a list. More...
 
#define UT_LIST_REMOVE(LIST, ELEM)   ut_list_remove(LIST, ELEM)
 Removes a node from a two-way linked list. More...
 
#define UT_LIST_GET_NEXT(NAME, N)   (((N)->NAME).next)
 Gets the next node in a two-way list. More...
 
#define UT_LIST_GET_PREV(NAME, N)   (((N)->NAME).prev)
 Gets the previous node in a two-way list. More...
 
#define UT_LIST_GET_LEN(BASE)   (BASE).get_length()
 Alternative macro to get the number of nodes in a two-way list, i.e., its length. More...
 
#define UT_LIST_GET_FIRST(BASE)   (BASE).first_element
 Gets the first node in a two-way list. More...
 
#define UT_LIST_GET_LAST(BASE)   (BASE).last_element
 Gets the last node in a two-way list. More...
 
#define UT_LIST_REVERSE(LIST)   ut_list_reverse(LIST)
 
#define UT_LIST_CHECK(LIST)
 Check the consistency of a two-way list. More...
 

Functions

template<typename List >
void ut_list_prepend (List &list, typename List::elem_type *elem)
 Adds the node as the first element in a two-way linked list. More...
 
template<typename List >
void ut_list_append (List &list, typename List::elem_type *elem)
 Adds the node as the last element in a two-way linked list. More...
 
template<typename List >
void ut_list_insert (List &list, typename List::elem_type *elem1, typename List::elem_type *elem2)
 Inserts a ELEM2 after ELEM1 in a list. More...
 
template<typename List >
void ut_list_remove (List &list, typename List::elem_type *elem)
 Removes a node from a two-way linked list. More...
 
template<typename List , class Functor >
void ut_list_map (const List &list, Functor &functor)
 Iterate over all the elements and call the functor for each element. More...
 
template<typename List >
void ut_list_reverse (List &list)
 
template<typename List , class Functor >
void ut_list_validate (const List &list, Functor &functor)
 Checks the consistency of a two-way list. More...
 
template<typename List >
void ut_list_move_to_front (List &list, typename List::elem_type *elem)
 Move the given element to the beginning of the list. More...
 
template<typename List >
bool ut_list_exists (List &list, typename List::elem_type *elem)
 Check if the given element exists in the list. More...
 

Detailed Description

List utilities.

Created 9/10/1995 Heikki Tuuri Rewritten by Sunny Bains Dec 2011.

Macro Definition Documentation

◆ UT_LIST_ADD_FIRST

#define UT_LIST_ADD_FIRST (   LIST,
  ELEM 
)    ut_list_prepend(LIST, ELEM)

Adds the node as the first element in a two-way linked list.

Parameters
LISTthe base node (not a pointer to it)
ELEMthe element to add

◆ UT_LIST_ADD_LAST

#define UT_LIST_ADD_LAST (   LIST,
  ELEM 
)    ut_list_append(LIST, ELEM)

Adds the node as the last element in a two-way linked list.

Parameters
LISTlist base node (not a pointer to it)
ELEMthe element to add

◆ UT_LIST_BASE_NODE_T

#define UT_LIST_BASE_NODE_T (   t,
 
)     ut_list_base<t, ut_list_base_explicit_getter<t, &t::m>>

A type of a list storing pointers to t, chained by member m of t.

NOTE: In cases in which definition of t is not yet in scope and thus you can't refer to t::m at this point yet, use UT_LIST_BASE_NODE_T_EXTERN macro instead.

◆ UT_LIST_BASE_NODE_T_EXTERN

#define UT_LIST_BASE_NODE_T_EXTERN (   t,
 
)     ut_list_base<t, struct UT_LIST_NODE_GETTER(t, m)>

A variant of UT_LIST_BASE_NODE_T to be used in rare cases where the full definition of t is not yet in scope, and thus UT_LIST_BASE_NODE_T can't be used yet as it needs to know how to access member m of t.

The trick used here is to forward declare UT_LIST_NODE_GETTER(t,m) struct to be defined later by the UT_LIST_NODE_GETTER_DEFINITION(t,m) once t::m is defined.

◆ UT_LIST_CHECK

#define UT_LIST_CHECK (   LIST)
Value:
do { \
NullValidate nullV; \
ut_list_validate(LIST, nullV); \
} while (0)
Definition: my_list.h:35

Check the consistency of a two-way list.

Parameters
[in]LISTbase node reference

◆ UT_LIST_GET_FIRST

#define UT_LIST_GET_FIRST (   BASE)    (BASE).first_element

Gets the first node in a two-way list.

Parameters
BASEthe base node (not a pointer to it)
Returns
first node, or NULL if the list is empty

◆ UT_LIST_GET_LAST

#define UT_LIST_GET_LAST (   BASE)    (BASE).last_element

Gets the last node in a two-way list.

Parameters
BASEthe base node (not a pointer to it)
Returns
last node, or NULL if the list is empty

◆ UT_LIST_GET_LEN

#define UT_LIST_GET_LEN (   BASE)    (BASE).get_length()

Alternative macro to get the number of nodes in a two-way list, i.e., its length.

Parameters
BASEthe base node (not a pointer to it).
Returns
the number of nodes in the list

◆ UT_LIST_GET_NEXT

#define UT_LIST_GET_NEXT (   NAME,
 
)    (((N)->NAME).next)

Gets the next node in a two-way list.

Parameters
NAMElist name
Npointer to a node
Returns
the successor of N in NAME, or NULL

◆ UT_LIST_GET_PREV

#define UT_LIST_GET_PREV (   NAME,
 
)    (((N)->NAME).prev)

Gets the previous node in a two-way list.

Parameters
NAMElist name
Npointer to a node
Returns
the predecessor of N in NAME, or NULL

◆ UT_LIST_INIT

#define UT_LIST_INIT (   b)
Value:
{ \
auto &list_ref = (b); \
new (&list_ref) std::remove_reference_t<decltype(list_ref)>(); \
}

Initializes the base node of a two-way list.

Parameters
bthe list base node

◆ UT_LIST_INITIALISED

#define UT_LIST_INITIALISED   0xCAFE

◆ UT_LIST_INSERT_AFTER

#define UT_LIST_INSERT_AFTER (   LIST,
  ELEM1,
  ELEM2 
)     ut_list_insert(LIST, ELEM1, ELEM2)

Inserts a ELEM2 after ELEM1 in a list.

Parameters
LISTlist base node (not a pointer to it)
ELEM1node after which ELEM2 is inserted
ELEM2node being inserted after ELEM1

◆ UT_LIST_IS_INITIALISED

#define UT_LIST_IS_INITIALISED (   b)    ((b).init == UT_LIST_INITIALISED)

◆ UT_LIST_NODE_GETTER

#define UT_LIST_NODE_GETTER (   t,
 
)    t##_##m##_node_getter

A helper for the UT_LIST_BASE_NODE_T_EXTERN which builds a name of a node getter struct from the name of elem type t, and its member name m.

◆ UT_LIST_NODE_GETTER_DEFINITION

#define UT_LIST_NODE_GETTER_DEFINITION (   t,
 
)
Value:
struct UT_LIST_NODE_GETTER(t, m) \
: public ut_list_base_explicit_getter<t, &t::m> {};
Definition: ut0lst.h:244
#define UT_LIST_NODE_GETTER(t, m)
A helper for the UT_LIST_BASE_NODE_T_EXTERN which builds a name of a node getter struct from the name...
Definition: ut0lst.h:257

A helper for the UT_LIST_BASE_NODE_T_EXTERN which declares a node getter struct which extracts member m from element of type t.

Note that the definition of the get_node function is inline, so this declaration/definition can appear multiple times in our codebase, and the intent is that you simply put it in the header which defines member m of t for the first time, so that it is accessible. This way all the places in codebase which know how to access m from t, will be also able to use this node getter, and thus iterate over a list chained by it. This also ensures, that for(auto elem: list) loops can be fully inlined by the compiler as it can see through the get_node implementation, because each place in code which knows that get_node exists also knows its implementation.

◆ UT_LIST_NODE_T

#define UT_LIST_NODE_T (   t)    ut_list_node<t>

Macro used for legacy reasons.

◆ UT_LIST_REMOVE

#define UT_LIST_REMOVE (   LIST,
  ELEM 
)    ut_list_remove(LIST, ELEM)

Removes a node from a two-way linked list.

Parameters
LISTthe base node (not a pointer to it)
ELEMnode to be removed from the list

◆ UT_LIST_REVERSE

#define UT_LIST_REVERSE (   LIST)    ut_list_reverse(LIST)

Function Documentation

◆ ut_list_append()

template<typename List >
void ut_list_append ( List list,
typename List::elem_type *  elem 
)

Adds the node as the last element in a two-way linked list.

Parameters
listlist
elemthe element to add

◆ ut_list_exists()

template<typename List >
bool ut_list_exists ( List list,
typename List::elem_type *  elem 
)

Check if the given element exists in the list.

Parameters
[in,out]listthe list object
[in]elemthe element of the list which will be checked

◆ ut_list_insert()

template<typename List >
void ut_list_insert ( List list,
typename List::elem_type *  elem1,
typename List::elem_type *  elem2 
)

Inserts a ELEM2 after ELEM1 in a list.

Parameters
listthe base node
elem1node after which ELEM2 is inserted
elem2node being inserted after ELEM1

◆ ut_list_map()

template<typename List , class Functor >
void ut_list_map ( const List list,
Functor &  functor 
)

Iterate over all the elements and call the functor for each element.

Parameters
[in]listbase node (not a pointer to it)
[in,out]functorFunctor that is called for each element in the list

◆ ut_list_move_to_front()

template<typename List >
void ut_list_move_to_front ( List list,
typename List::elem_type *  elem 
)

Move the given element to the beginning of the list.

Parameters
[in,out]listthe list object
[in]elemthe element of the list which will be moved to the beginning of the list.

◆ ut_list_prepend()

template<typename List >
void ut_list_prepend ( List list,
typename List::elem_type *  elem 
)

Adds the node as the first element in a two-way linked list.

Parameters
listthe base node (not a pointer to it)
elemthe element to add

◆ ut_list_remove()

template<typename List >
void ut_list_remove ( List list,
typename List::elem_type *  elem 
)

Removes a node from a two-way linked list.

Parameters
listthe base node (not a pointer to it)
elempointer to the element to remove from the list

◆ ut_list_reverse()

template<typename List >
void ut_list_reverse ( List list)

◆ ut_list_validate()

template<typename List , class Functor >
void ut_list_validate ( const List list,
Functor &  functor 
)

Checks the consistency of a two-way list.

Parameters
[in]listbase node (not a pointer to it)
[in,out]functorFunctor that is called for each element in the list