ut_list_base< Type, NodeGetter > Struct Template Reference

The two-way list base node. More...

#include <ut0lst.h>

Classes
class	base_iterator
class	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...

Public Types
using	elem_type = Type
using	node_type = ut_list_node< elem_type >
using	iterator = base_iterator< elem_type >
using	const_iterator = base_iterator< const elem_type >

Public Member Functions
size_t	get_length () const
	Returns number of nodes currently present in the list. More...
void	update_length (int diff)
	Updates the length of the list by the amount specified. More...
void	clear ()
void	reverse ()
iterator	begin ()
iterator	end ()
const_iterator	begin () const
const_iterator	end () const
Removable	removable ()
	Returns a wrapper which lets you remove current item or items after it. More...

Static Public Member Functions
static const node_type &	get_node (const elem_type &e)
static node_type &	get_node (elem_type &e)
static const elem_type *	next (const elem_type &e)
static elem_type *	next (elem_type &e)
static const elem_type *	prev (const elem_type &e)
static elem_type *	prev (elem_type &e)

Public Attributes
elem_type *	first_element {nullptr}
	Pointer to list start, NULL if empty. More...
elem_type *	last_element {nullptr}
	Pointer to list end, NULL if empty. More...
ulint	init {UT_LIST_INITIALISED}
	UT_LIST_INITIALISED if the list was initialised with the constructor. More...

Private Attributes
std::atomic< size_t >	count {0}
	Number of nodes in list. More...

Detailed Description

template<typename Type, typename NodeGetter>
struct ut_list_base< Type, NodeGetter >

The two-way list base node.

The base node contains pointers to both ends of the list and a count of nodes in the list (excluding the base node from the count). We also store a pointer to the member field so that it doesn't have to be specified when doing list operations.

Template Parameters

Type	the type of the list element
NodeGetter	a class which has a static member ut_list_node<Type> get_node(const Type & e) which knows how to extract a node from an element

Member Typedef Documentation

const_iterator

template<typename Type , typename NodeGetter >

using ut_list_base< Type, NodeGetter >::const_iterator = base_iterator<const elem_type>

elem_type

template<typename Type , typename NodeGetter >

using ut_list_base< Type, NodeGetter >::elem_type = Type

iterator

template<typename Type , typename NodeGetter >

using ut_list_base< Type, NodeGetter >::iterator = base_iterator<elem_type>

node_type

template<typename Type , typename NodeGetter >

using ut_list_base< Type, NodeGetter >::node_type = ut_list_node<elem_type>

Member Function Documentation

begin() [1/2]

template<typename Type , typename NodeGetter >

iterator ut_list_base< Type, NodeGetter >::begin ( void  )

inline

begin() [2/2]

template<typename Type , typename NodeGetter >

const_iterator ut_list_base< Type, NodeGetter >::begin ( void  ) const

inline

clear()

template<typename Type , typename NodeGetter >

void ut_list_base< Type, NodeGetter >::clear ( )

inline

end() [1/2]

template<typename Type , typename NodeGetter >

iterator ut_list_base< Type, NodeGetter >::end ( void  )

inline

end() [2/2]

template<typename Type , typename NodeGetter >

const_iterator ut_list_base< Type, NodeGetter >::end ( void  ) const

inline

get_length()

template<typename Type , typename NodeGetter >

size_t ut_list_base< Type, NodeGetter >::get_length ( ) const

inline

Returns number of nodes currently present in the list.

get_node() [1/2]

template<typename Type , typename NodeGetter >

static const node_type & ut_list_base< Type, NodeGetter >::get_node ( const elem_type &  e )

inlinestatic

get_node() [2/2]

template<typename Type , typename NodeGetter >

static node_type & ut_list_base< Type, NodeGetter >::get_node ( elem_type &  e )

inlinestatic

next() [1/2]

template<typename Type , typename NodeGetter >

static const elem_type * ut_list_base< Type, NodeGetter >::next ( const elem_type &  e )

inlinestatic

next() [2/2]

template<typename Type , typename NodeGetter >

static elem_type * ut_list_base< Type, NodeGetter >::next ( elem_type &  e )

inlinestatic

prev() [1/2]

template<typename Type , typename NodeGetter >

static const elem_type * ut_list_base< Type, NodeGetter >::prev ( const elem_type &  e )

inlinestatic

prev() [2/2]

template<typename Type , typename NodeGetter >

static elem_type * ut_list_base< Type, NodeGetter >::prev ( elem_type &  e )

inlinestatic

removable()

template<typename Type , typename NodeGetter >

Removable ut_list_base< Type, NodeGetter >::removable ( )

inline

Returns a wrapper which lets you remove current item or items after it.

It can be used like in this example: for (auto lock : table->locks.removable()) { lock_remove_all_on_table_for_trx(table, lock->trx,..); } Or in general: for (auto item : list.removable()) { remove_items_which_are_similar_to(item); } Basically you can remove any item, except for prev(item).

You can also insert to the list during iteration, keeping in mind that the position you insert the element at has following impact:

• after the current item: the new item WILL be processed eventually,
• before the previous item: the new item WILL NOT be processed,
• right before the current item: DON'T DO IT, as you risk an endless loop! A safe subcase of this is reinserting the current item, in which case it won't be processed again. This lets you implement "move to front" easily.

  See also

  Removable

reverse()

template<typename Type , typename NodeGetter >

void ut_list_base< Type, NodeGetter >::reverse ( )

inline

update_length()

template<typename Type , typename NodeGetter >

void ut_list_base< Type, NodeGetter >::update_length ( int  diff )

inline

Updates the length of the list by the amount specified.

Parameters

diff	the value by which to increase the length. Can be negative.

Member Data Documentation

count

template<typename Type , typename NodeGetter >

std::atomic<size_t> ut_list_base< Type, NodeGetter >::count {0}

private

Number of nodes in list.

It is atomic to allow unprotected reads. Writes must be protected by some external latch.

first_element

template<typename Type , typename NodeGetter >

elem_type* ut_list_base< Type, NodeGetter >::first_element {nullptr}

Pointer to list start, NULL if empty.

init

template<typename Type , typename NodeGetter >

ulint ut_list_base< Type, NodeGetter >::init {UT_LIST_INITIALISED}

UT_LIST_INITIALISED if the list was initialised with the constructor.

It is used to detect if the ut_list_base object is used directly after allocating memory from malloc-like calls that do not run constructor.

last_element

template<typename Type , typename NodeGetter >

elem_type* ut_list_base< Type, NodeGetter >::last_element {nullptr}

Pointer to list end, NULL if empty.

---

The documentation for this struct was generated from the following file:

• storage/innobase/include/ut0lst.h