Quelle  ut0lst.h   Sprache: C

/*****************************************************************************

Copyright (c) 1995, 2015, Oracle and/or its affiliates. All Rights Reserved.
Copyright (c) 2019, 2022, MariaDB Corporation.

This program is free software; you can redistribute it and/or modify it under
the terms of the GNU General Public License as published by the Free Software
Foundation; version 2 of the License.

This program is distributed in the hope that it will be useful, but WITHOUT
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with
this program; if not, write to the Free Software Foundation, Inc.,
51 Franklin Street, Fifth Floor, Boston, MA 02110-1335 USA

*****************************************************************************/

/******************************************************************//**
@file include/ut0lst.h
List utilities

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

#pragma once

/* Do not include univ.i because univ.i includes this. */

#include "ut0dbg.h"

/* This module implements the two-way linear list. Note that a single
list node may belong to two or more lists, but is only on one list
at a time. */

/*******************************************************************//**
The two way list node.
@param TYPE the list node type name */
template <typename Type>
struct ut_list_node {
 Type*  prev;   /*!< pointer to the previous
node, NULL if start of list */
 Type*  next;   /*!< pointer to next node,
NULL if end of list */

 void reverse()
 {
  Type* tmp = prev;
  prev = next;
  next = tmp;
 }
};

/** Macro used for legacy reasons */
#define UT_LIST_NODE_T(t)  ut_list_node<t>

/*******************************************************************//**
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.
@param Type the type of the list element
@param NodePtr field member pointer that points to the list node */
template <typename Type, typename NodePtr>
struct ut_list_base {
 typedef Type elem_type;
 typedef NodePtr node_ptr;
 typedef ut_list_node<Type> node_type;

 ulint  count;   /*!< count of nodes in list */
 elem_type* start;   /*!< pointer to list start,
NULL if empty */
 elem_type* end;   /*!< pointer to list end,
NULL if empty */
 node_ptr node;   /*!< Pointer to member field
that is used as a link node */
#ifdef UNIV_DEBUG
 ulint  init;   /*!< UT_LIST_INITIALISED if
      the list was initialised with
UT_LIST_INIT() */
#endif /* UNIV_DEBUG */

 void reverse()
 {
  Type* tmp = start;
  start = end;
  end = tmp;
 }
};

#define UT_LIST_BASE_NODE_T(t) ut_list_base<t, ut_list_node<t> t::*>

#ifdef UNIV_DEBUG
# define UT_LIST_INITIALISED  0xCAFE
# define UT_LIST_INITIALISE(b)  (b).init = UT_LIST_INITIALISED
# define UT_LIST_IS_INITIALISED(b) ut_a(((b).init == UT_LIST_INITIALISED))
#else
# define UT_LIST_INITIALISE(b)
# define UT_LIST_IS_INITIALISED(b)
#endif /* UNIV_DEBUG */

/*******************************************************************//**
Note: This is really the list constructor. We should be able to use
placement new here.
Initializes the base node of a two-way list.
@param b the list base node
@param pmf point to member field that will be used as the link node */
#define UT_LIST_INIT(b, pmf)      \
{         \
 (b).count = 0;       \
 (b).start = 0;       \
 (b).end   = 0;       \
 (b).node  = pmf;      \
 UT_LIST_INITIALISE(b);      \
}

/** Functor for accessing the embedded node within a list element. This is
required because some lists can have the node embedded inside a nested
struct/union. See lock0priv.h (table locks) for an example. It provides a
specialised functor to grant access to the list node. */
template <typename Type>
struct GenericGetNode {

 typedef ut_list_node<Type> node_type;

 GenericGetNode(node_type Type::* node) : m_node(node) {}

 node_type& operator() (Type& elem)
 {
  return(elem.*m_node);
 }

 node_type Type::*m_node;
};

/*******************************************************************//**
Adds the node as the first element in a two-way linked list.
@param list the base node (not a pointer to it)
@param elem the element to add */
template <typename List>
void
ut_list_prepend(
 List&    list,
 typename List::elem_type* elem)
{
 typename List::node_type& elem_node = elem->*list.node;

 UT_LIST_IS_INITIALISED(list);

 elem_node.prev = 0;
 elem_node.next = list.start;

 if (list.start != 0) {
  typename List::node_type& base_node =
   list.start->*list.node;

  ut_ad(list.start != elem);

  base_node.prev = elem;
 }

 list.start = elem;

 if (list.end == 0) {
  list.end = elem;
 }

 ++list.count;
}

/*******************************************************************//**
Adds the node as the first element in a two-way linked list.
@param LIST the base node (not a pointer to it)
@param ELEM the element to add */
#define UT_LIST_ADD_FIRST(LIST, ELEM) ut_list_prepend(LIST, ELEM)

/*******************************************************************//**
Adds the node as the last element in a two-way linked list.
@param list list
@param elem the element to add
@param get_node to get the list node for that element */
template <typename List, typename Functor>
void
ut_list_append(
 List&    list,
 typename List::elem_type* elem,
 Functor    get_node)
{
 typename List::node_type& node = get_node(*elem);

 UT_LIST_IS_INITIALISED(list);

 node.next = 0;
 node.prev = list.end;

 if (list.end != 0) {
  typename List::node_type& base_node = get_node(*list.end);

  ut_ad(list.end != elem);

  base_node.next = elem;
 }

 list.end = elem;

 if (list.start == 0) {
  list.start = elem;
 }

 ++list.count;
}

/*******************************************************************//**
Adds the node as the last element in a two-way linked list.
@param list list
@param elem the element to add */
template <typename List>
void
ut_list_append(
 List&    list,
 typename List::elem_type* elem)
{
 ut_list_append(
  list, elem,
  GenericGetNode<typename List::elem_type>(list.node));
}

/*******************************************************************//**
Adds the node as the last element in a two-way linked list.
@param LIST list base node (not a pointer to it)
@param ELEM the element to add */
#define UT_LIST_ADD_LAST(LIST, ELEM) ut_list_append(LIST, ELEM)

/*******************************************************************//**
Inserts a ELEM2 after ELEM1 in a list.
@param list the base node
@param elem1 node after which ELEM2 is inserted
@param elem2 node being inserted after ELEM1 */
template <typename List>
void
ut_list_insert(
 List&    list,
 typename List::elem_type* elem1,
 typename List::elem_type* elem2)
{
 ut_ad(elem1 != elem2);
 UT_LIST_IS_INITIALISED(list);

 typename List::node_type& elem1_node = elem1->*list.node;
 typename List::node_type& elem2_node = elem2->*list.node;

 elem2_node.prev = elem1;
 elem2_node.next = elem1_node.next;

 if (elem1_node.next != NULL) {
  typename List::node_type& next_node =
   elem1_node.next->*list.node;

  next_node.prev = elem2;
 }

 elem1_node.next = elem2;

 if (list.end == elem1) {
  list.end = elem2;
 }

 ++list.count;
}

/*******************************************************************//**
Inserts a ELEM2 after ELEM1 in a list.
@param LIST list base node (not a pointer to it)
@param ELEM1 node after which ELEM2 is inserted
@param ELEM2 node being inserted after ELEM1 */
#define UT_LIST_INSERT_AFTER(LIST, ELEM1, ELEM2)   \
 ut_list_insert(LIST, ELEM1, ELEM2)

/*******************************************************************//**
Inserts a ELEM2 after ELEM1 in a list.
@param list the base node
@param elem1 node after which ELEM2 is inserted
@param elem2 node being inserted after ELEM1
@param get_node to get the list node for that element */

template <typename List, typename Functor>
void
ut_list_insert(
 List&    list,
 typename List::elem_type* elem1,
        typename List::elem_type* elem2,
 Functor    get_node)
{
 ut_ad(elem1 != elem2);
 UT_LIST_IS_INITIALISED(list);

 typename List::node_type& elem1_node = get_node(*elem1);
 typename List::node_type& elem2_node = get_node(*elem2);

 elem2_node.prev = elem1;
 elem2_node.next = elem1_node.next;

 if (elem1_node.next != NULL) {
  typename List::node_type& next_node =
   get_node(*elem1_node.next);

  next_node.prev = elem2;
 }

 elem1_node.next = elem2;

 if (list.end == elem1) {
  list.end = elem2;
 }

 ++list.count;

}
/*******************************************************************//**
Removes a node from a two-way linked list.
@param list the base node (not a pointer to it)
@param node member node within list element that is to be removed
@param get_node functor to get the list node from elem */
template <typename List, typename Functor>
void
ut_list_remove(
 List&    list,
 typename List::node_type& node,
 Functor    get_node)
{
 ut_a(list.count > 0);
 UT_LIST_IS_INITIALISED(list);

 if (node.next != NULL) {
  typename List::node_type& next_node =
   get_node(*node.next);

  next_node.prev = node.prev;
 } else {
  list.end = node.prev;
 }

 if (node.prev != NULL) {
  typename List::node_type& prev_node =
   get_node(*node.prev);

  prev_node.next = node.next;
 } else {
  list.start = node.next;
 }

 node.next = 0;
 node.prev = 0;

 --list.count;
}

/*******************************************************************//**
Removes a node from a two-way linked list.
@param list the base node (not a pointer to it)
@param elem element to be removed from the list
@param get_node functor to get the list node from elem */
template <typename List, typename Functor>
void
ut_list_remove(
 List&    list,
 typename List::elem_type* elem,
 Functor    get_node)
{
 ut_list_remove(list, get_node(*elem), get_node);
}

/*******************************************************************//**
Removes a node from a two-way linked list.
@param list the base node (not a pointer to it)
@param elem element to be removed from the list */
template <typename List>
void
ut_list_remove(
 List&    list,
 typename List::elem_type* elem)
{
 ut_list_remove(
  list, elem->*list.node,
  GenericGetNode<typename List::elem_type>(list.node));
}

/*******************************************************************//**
Removes a node from a two-way linked list.
@param LIST the base node (not a pointer to it)
@param ELEM node to be removed from the list */
#define UT_LIST_REMOVE(LIST, ELEM) ut_list_remove(LIST, ELEM)

/********************************************************************//**
Gets the next node in a two-way list.
@param NAME list name
@param N pointer to a node
@return the successor of N in NAME, or NULL */
#define UT_LIST_GET_NEXT(NAME, N) (((N)->NAME).next)

/********************************************************************//**
Gets the previous node in a two-way list.
@param NAME list name
@param N pointer to a node
@return the predecessor of N in NAME, or NULL */
#define UT_LIST_GET_PREV(NAME, N) (((N)->NAME).prev)

/********************************************************************//**
Alternative macro to get the number of nodes in a two-way list, i.e.,
its length.
@param BASE the base node (not a pointer to it).
@return the number of nodes in the list */
#define UT_LIST_GET_LEN(BASE)  (BASE).count

/********************************************************************//**
Gets the first node in a two-way list.
@param BASE the base node (not a pointer to it)
@return first node, or NULL if the list is empty */
#define UT_LIST_GET_FIRST(BASE)  (BASE).start

/********************************************************************//**
Gets the last node in a two-way list.
@param BASE the base node (not a pointer to it)
@return last node, or NULL if the list is empty */
#define UT_LIST_GET_LAST(BASE)  (BASE).end

struct NullValidate { void operator()(const void*) const {} };

/** Iterate over all the elements and call the functor for each element.
@param[in] list base node (not a pointer to it)
@param[in,out] functor Functor that is called for each element in the list */
template <typename List, class Functor>
inline void ut_list_map(const List& list, Functor& functor)
{
 ulint count = 0;

 UT_LIST_IS_INITIALISED(list);

 for (typename List::elem_type* elem = list.start; elem;
      elem = (elem->*list.node).next, ++count) {

  functor(elem);
 }

 ut_a(count == list.count);
}

/** Iterate over all the elements and call the functor for each element.
@param[in] list base node (not a pointer to it)
@param[in] functor Functor that is called for each element in the list */
template <typename List, class Functor>
inline void ut_list_map(const List& list, const Functor& functor)
{
 ulint count = 0;

 UT_LIST_IS_INITIALISED(list);

 for (typename List::elem_type* elem = list.start; elem;
      elem = (elem->*list.node).next, ++count) {

  functor(elem);
 }

 ut_a(count == list.count);
}

/** Check the consistency of a doubly linked list.
@param[in] list  base node (not a pointer to it)
@param[in,out] functor Functor that is called for each element in the list */
template <typename List, class Functor>
void ut_list_validate(const List& list, Functor& functor)
{
 ut_list_map(list, functor);
#ifdef UNIV_DEBUG
 /* Validate the list backwards. */
 ulint count = list.count;

 for (typename List::elem_type* elem = list.end;
      elem != 0;
      elem = (elem->*list.node).prev) {
  --count;
 }
 ut_ad(!count);
#endif
}

/** Check the consistency of a doubly linked list.
@param[in] list  base node (not a pointer to it)
@param[in] functor Functor that is called for each element in the list */
template <typename List, class Functor>
inline void ut_list_validate(const List& list, const Functor& functor)
{
 ut_list_map(list, functor);
#ifdef UNIV_DEBUG
 /* Validate the list backwards. */
 ulint count = list.count;

 for (typename List::elem_type* elem = list.end;
      elem != 0;
      elem = (elem->*list.node).prev) {
  --count;
 }

 ut_ad(!count);
#endif
}

template <typename List>
inline void ut_list_validate(const List& list)
{
  ut_d(ut_list_validate(list, NullValidate()));
}

#ifdef UNIV_DEBUG
template <typename List>
inline void ut_list_reverse(List& list)
{
 UT_LIST_IS_INITIALISED(list);

 for (typename List::elem_type* elem = list.start;
      elem != 0;
      elem = (elem->*list.node).prev) {
  (elem->*list.node).reverse();
 }

 list.reverse();
}

/** Check if the given element exists in the list.
@param[in,out] list the list object
@param[in] elem the element of the list which will be checked */
template <typename List>
inline bool ut_list_exists(const List& list, typename List::elem_type* elem)
{
 for (typename List::elem_type* e1 = UT_LIST_GET_FIRST(list); e1;
      e1 = (e1->*list.node).next) {
  if (elem == e1) {
   return true;
  }
 }
 return false;
}
#endif

/** Move the given element to the beginning of the list.
@param[in,out] list the list object
@param[in] elem the element of the list which will be moved
to the beginning of the list. */
template <typename List>
void
ut_list_move_to_front(
 List&    list,
 typename List::elem_type* elem)
{
 ut_ad(ut_list_exists(list, elem));

 if (UT_LIST_GET_FIRST(list) != elem) {
  ut_list_remove(list, elem);
  ut_list_prepend(list, elem);
 }
}