MySQL 8.3.0
Source Code Documentation
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_typeget_node (const elem_type &e)
 
static node_typeget_node (elem_type &e)
 
static const elem_typenext (const elem_type &e)
 
static elem_typenext (elem_type &e)
 
static const elem_typeprev (const elem_type &e)
 
static elem_typeprev (elem_type &e)
 

Public Attributes

elem_typefirst_element {nullptr}
 Pointer to list start, NULL if empty. More...
 
elem_typelast_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
Typethe type of the list element
NodeGettera 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
diffthe 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: