ut0lst.h File Reference

#include "univ.i"

Include dependency graph for ut0lst.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures
struct	ut_list_base< TYPE >
struct	ut_list_node< TYPE >
struct	NullValidate

Macros
#define	IB_OFFSETOF(T, F)   (reinterpret_cast<byte*>(&(T)->F) - reinterpret_cast<byte*>(T))
#define	UT_LIST_BASE_NODE_T(TYPE)   ut_list_base<TYPE>
#define	UT_LIST_NODE_T(TYPE)   ut_list_node<TYPE>
#define	UT_LIST_INIT(BASE)
#define	UT_LIST_ADD_FIRST(NAME, LIST, ELEM)   ut_list_prepend(LIST, *ELEM, IB_OFFSETOF(ELEM, NAME))
#define	UT_LIST_ADD_LAST(NAME, LIST, ELEM)   ut_list_append(LIST, *ELEM, IB_OFFSETOF(ELEM, NAME))
#define	UT_LIST_INSERT_AFTER(NAME, LIST, ELEM1, ELEM2)   ut_list_insert(LIST, *ELEM1, *ELEM2, IB_OFFSETOF(ELEM1, NAME))
#define	UT_LIST_REMOVE_CLEAR(N)
#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
#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())

Functions
template<typename Type >
ut_list_node< Type > &	ut_elem_get_node (Type &elem, size_t offset)
template<typename List , typename Type >
void	ut_list_prepend (List &list, Type &elem, size_t offset)
template<typename List , typename Type >
void	ut_list_append (List &list, Type &elem, size_t offset)
template<typename List , typename Type >
void	ut_list_insert (List &list, Type &elem1, Type &elem2, size_t offset)
template<typename List , typename Type >
void	ut_list_remove (List &list, Type &elem, size_t offset)
template<typename List , class Functor >
void	ut_list_map (List &list, ut_list_node< typename List::elem_type > List::elem_type::*node, Functor functor)
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())

Detailed Description

List utilities

Created 9/10/1995 Heikki Tuuri

Macro Definition Documentation

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

Return offset of F in POD T.

Parameters

T	- POD pointer
F	- Field in T

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

Adds the node as the first element in a two-way linked list.

Parameters

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

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

Adds the node as the last element in a two-way linked list.

Parameters

NAME	list name
LIST	list
ELEM	the element to add

#define UT_LIST_GET_FIRST

(

BASE

)

(BASE).start

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

#define UT_LIST_GET_LAST

(

BASE

)

(BASE).end

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

#define UT_LIST_GET_LEN

(

BASE

)

(BASE).count

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

#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

#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

#define UT_LIST_INIT

(

BASE

)

Value:

{\
        (BASE).count = 0;\
        (BASE).start = NULL;\
        (BASE).end   = NULL;\
}\

Initializes the base node of a two-way list.

Parameters

BASE	the list base node

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

Inserts a ELEM2 after ELEM1 in a list.

Parameters

NAME	list name
LIST	the base node
ELEM1	node after which ELEM2 is inserted
ELEM2	node being inserted after ELEM1

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

Removes a node from a two-way linked list. aram NAME list name

Parameters

LIST	the base node (not a pointer to it)
ELEM	node to be removed from the list

#define UT_LIST_REMOVE_CLEAR

(

N

)

Invalidate the pointers in a list node.

Parameters

NAME	list name
N	pointer to the node that was removed

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

Checks the consistency of a two-way list.

Parameters

NAME	the name of the list
TYPE	node type
LIST	base node (not a pointer to it)
FUNCTOR	called for each list element

Function Documentation

template<typename Type >

ut_list_node<Type>& ut_elem_get_node	(	Type &	elem,
		size_t	offset
	)

Get the list node at offset.

Parameters

elem	- list element
offset	- offset within element.

Returns

reference to list node.

template<typename List , typename Type >

void ut_list_append	(	List &	list,
		Type &	elem,
		size_t	offset
	)

Adds the node as the last element in a two-way linked list.

Parameters

list	list
elem	the element to add
offset	offset of list node in elem

template<typename List , typename Type >

void ut_list_insert	(	List &	list,
		Type &	elem1,
		Type &	elem2,
		size_t	offset
	)

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 NODE1
offset	offset of list node in elem1 and elem2

template<typename List , class Functor >

void ut_list_map	(	List &	list,
		ut_list_node< typename List::elem_type > List::elem_type::*	node,
		Functor	functor
	)

Iterate over all the elements and call the functor for each element.

Parameters

list	base node (not a pointer to it)
functor	Functor that is called for each element in the list node pointer to member node within list element

template<typename List , typename Type >

void ut_list_prepend	(	List &	list,
		Type &	elem,
		size_t	offset
	)

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
offset	offset of list node in elem.

template<typename List , typename Type >

void ut_list_remove	(	List &	list,
		Type &	elem,
		size_t	offset
	)

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
offset	offset of list node within elem

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()
	)

Checks the consistency of a two-way list.

Parameters

list	base node (not a pointer to it)
functor	Functor that is called for each element in the list node pointer to member node within list element