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

LIST	the base node (not a pointer to it)
ELEM	the 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

LIST	list base node (not a pointer to it)
ELEM	the element to add

UT_LIST_BASE_NODE_T

#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.

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,
			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.

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)

Check the consistency of a two-way list.

Parameters

[in]

LIST

base 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

BASE	the 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

BASE	the 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

BASE	the 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
	)		(((N)->NAME).next)

Gets the next node in a two-way list.

Parameters

NAME	list name
N	pointer to a node

Returns

the successor of N in NAME, or NULL

UT_LIST_GET_PREV

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

Gets the previous node in a two-way list.

Parameters

NAME	list name
N	pointer 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

b	the 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

LIST	list base node (not a pointer to it)
ELEM1	node after which ELEM2 is inserted
ELEM2	node 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,
			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.

UT_LIST_NODE_GETTER_DEFINITION

#define UT_LIST_NODE_GETTER_DEFINITION	(		t,
			m
	)

Value:

  struct UT_LIST_NODE_GETTER(t, m)           \
      : public ut_list_base_explicit_getter<t, &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.

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

LIST	the base node (not a pointer to it)
ELEM	node 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

list	list
elem	the 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]	list	the list object
[in]	elem	the 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

list	the base node
elem1	node after which ELEM2 is inserted
elem2	node 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]	list	base node (not a pointer to it)
[in,out]	functor	Functor 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]	list	the list object
[in]	elem	the 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

list	the base node (not a pointer to it)
elem	the 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

list	the base node (not a pointer to it)
elem	pointer 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]	list	base node (not a pointer to it)
[in,out]	functor	Functor that is called for each element in the list