ut0lst.h

Go to the documentation of this file.

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

Copyright (c) 1995, 2011, Oracle and/or its affiliates. All Rights Reserved.

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, Suite 500, Boston, MA 02110-1335 USA

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

/******************************************************************/
#ifndef ut0lst_h
#define ut0lst_h

#include "univ.i"

/*******************************************************************/
#define IB_OFFSETOF(T, F)                                               \
        (reinterpret_cast<byte*>(&(T)->F) - reinterpret_cast<byte*>(T))

/* This module implements the two-way linear list which should be used
if a list is used in the database. Note that a single struct may belong
to two or more lists, provided that the list are given different names.
An example of the usage of the lists can be found in fil0fil.cc. */

/*******************************************************************/
template <typename TYPE>
struct ut_list_base {
        typedef TYPE elem_type;

        ulint   count;  
        TYPE*   start;  
        TYPE*   end;    
};

#define UT_LIST_BASE_NODE_T(TYPE)       ut_list_base<TYPE>

/*******************************************************************/
/* Example:
struct LRU_node_t {
        UT_LIST_NODE_T(LRU_node_t)      LRU_list;
        ...
}
The example implements an LRU list of name LRU_list. Its nodes are of type
LRU_node_t. */

template <typename TYPE>
struct ut_list_node {
        TYPE*   prev;   
        TYPE*   next;   
};

#define UT_LIST_NODE_T(TYPE)    ut_list_node<TYPE>

/*******************************************************************/
template <typename Type>
ut_list_node<Type>&
ut_elem_get_node(Type&  elem, size_t offset)
{
        ut_a(offset < sizeof(elem));

        return(*reinterpret_cast<ut_list_node<Type>*>(
                reinterpret_cast<byte*>(&elem) + offset));
}

/*******************************************************************/
#define UT_LIST_INIT(BASE)\
{\
        (BASE).count = 0;\
        (BASE).start = NULL;\
        (BASE).end   = NULL;\
}\

/*******************************************************************/
template <typename List, typename Type>
void
ut_list_prepend(
        List&           list,
        Type&           elem,
        size_t          offset)
{
        ut_list_node<Type>&     elem_node = ut_elem_get_node(elem, offset);

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

        if (list.start != 0) {
                ut_list_node<Type>&     base_node =
                        ut_elem_get_node(*list.start, offset);

                ut_ad(list.start != &elem);

                base_node.prev = &elem;
        }

        list.start = &elem;

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

        ++list.count;
}

/*******************************************************************/
#define UT_LIST_ADD_FIRST(NAME, LIST, ELEM)     \
        ut_list_prepend(LIST, *ELEM, IB_OFFSETOF(ELEM, NAME))

/*******************************************************************/
template <typename List, typename Type>
void
ut_list_append(
        List&           list,
        Type&           elem,
        size_t          offset)
{
        ut_list_node<Type>&     elem_node = ut_elem_get_node(elem, offset);

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

        if (list.end != 0) {
                ut_list_node<Type>&     base_node =
                        ut_elem_get_node(*list.end, offset);

                ut_ad(list.end != &elem);

                base_node.next = &elem;
        }

        list.end = &elem;

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

        ++list.count;
}

/*******************************************************************/
#define UT_LIST_ADD_LAST(NAME, LIST, ELEM)\
        ut_list_append(LIST, *ELEM, IB_OFFSETOF(ELEM, NAME))

/*******************************************************************/
template <typename List, typename Type>
void
ut_list_insert(
        List&           list,
        Type&           elem1,
        Type&           elem2,
        size_t          offset)
{
        ut_ad(&elem1 != &elem2);

        ut_list_node<Type>&     elem1_node = ut_elem_get_node(elem1, offset);
        ut_list_node<Type>&     elem2_node = ut_elem_get_node(elem2, offset);

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

        if (elem1_node.next != NULL) {
                ut_list_node<Type>&     next_node =
                        ut_elem_get_node(*elem1_node.next, offset);

                next_node.prev = &elem2;
        }

        elem1_node.next = &elem2;

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

        ++list.count;
}

/*******************************************************************/
#define UT_LIST_INSERT_AFTER(NAME, LIST, ELEM1, ELEM2)\
        ut_list_insert(LIST, *ELEM1, *ELEM2, IB_OFFSETOF(ELEM1, NAME))

#ifdef UNIV_LIST_DEBUG

# define UT_LIST_REMOVE_CLEAR(N)                                        \
        (N).next = (Type*) -1;                                          \
        (N).prev = (N).next
#else

# define UT_LIST_REMOVE_CLEAR(N)
#endif /* UNIV_LIST_DEBUG */

/*******************************************************************/
template <typename List, typename Type>
void
ut_list_remove(
        List&           list,
        Type&           elem,
        size_t          offset)
{
        ut_list_node<Type>&     elem_node = ut_elem_get_node(elem, offset);

        ut_a(list.count > 0);

        if (elem_node.next != NULL) {
                ut_list_node<Type>&     next_node =
                        ut_elem_get_node(*elem_node.next, offset);

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

        if (elem_node.prev != NULL) {
                ut_list_node<Type>&     prev_node =
                        ut_elem_get_node(*elem_node.prev, offset);

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

        UT_LIST_REMOVE_CLEAR(elem_node);

        --list.count;
}

/*******************************************************************/
#define UT_LIST_REMOVE(NAME, LIST, ELEM)                                \
        ut_list_remove(LIST, *ELEM, IB_OFFSETOF(ELEM, NAME))

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

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

/********************************************************************/
#define UT_LIST_GET_LEN(BASE)\
        (BASE).count

/********************************************************************/
#define UT_LIST_GET_FIRST(BASE)\
        (BASE).start

/********************************************************************/
#define UT_LIST_GET_LAST(BASE)\
        (BASE).end

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

/********************************************************************/
template <typename List, class Functor>
void
ut_list_map(
        List&           list,
        ut_list_node<typename List::elem_type>
                        List::elem_type::*node,
        Functor         functor)
{
        ulint           count = 0;

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

                functor(elem);
        }

        ut_a(count == list.count);
}

/********************************************************************/
template <typename List, class Functor>
void
ut_list_validate(
        List&           list,
        ut_list_node<typename List::elem_type>
                        List::elem_type::*node,
        Functor         functor = NullValidate())
{
        ut_list_map(list, node, functor);

        ulint           count = 0;

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

                functor(elem);
        }

        ut_a(count == list.count);
}

/********************************************************************/
#define UT_LIST_VALIDATE(NAME, TYPE, LIST, FUNCTOR)                     \
        ut_list_validate(LIST, &TYPE::NAME, FUNCTOR)

#define UT_LIST_CHECK(NAME, TYPE, LIST)                                 \
        ut_list_validate(LIST, &TYPE::NAME, NullValidate())

#endif /* ut0lst.h */