ut0lst.h 8.38 KB
Newer Older
1 2
/*****************************************************************************

3
Copyright (c) 1995, 2010, Innobase Oy. All Rights Reserved.
4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

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., 59 Temple
Place, Suite 330, Boston, MA 02111-1307 USA

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

19 20
/******************************************************************//**
@file include/ut0lst.h
osku's avatar
osku committed
21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
List utilities

Created 9/10/1995 Heikki Tuuri
***********************************************************************/

#ifndef ut0lst_h
#define ut0lst_h

#include "univ.i"

/* 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.c. */

36
/*******************************************************************//**
osku's avatar
osku committed
37 38 39
This macro expands to the unnamed type definition of a struct which acts
as 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
40 41
the base node from the count).
@param TYPE	the name of the list node data type */
osku's avatar
osku committed
42 43
#define UT_LIST_BASE_NODE_T(TYPE)\
struct {\
44 45 46
	ulint	count;	/*!< count of nodes in list */\
	TYPE *	start;	/*!< pointer to list start, NULL if empty */\
	TYPE *	end;	/*!< pointer to list end, NULL if empty */\
osku's avatar
osku committed
47 48
}\

49
/*******************************************************************//**
osku's avatar
osku committed
50 51 52 53
This macro expands to the unnamed type definition of a struct which
should be embedded in the nodes of the list, the node type must be a struct.
This struct contains the pointers to next and previous nodes in the list.
The name of the field in the node struct should be the name given
54 55 56
to the list.
@param TYPE	the list node type name */
/* Example:
osku's avatar
osku committed
57 58 59 60 61 62
typedef struct LRU_node_struct	LRU_node_t;
struct LRU_node_struct {
	UT_LIST_NODE_T(LRU_node_t)	LRU_list;
	...
}
The example implements an LRU list of name LRU_list. Its nodes are of type
63
LRU_node_t. */
osku's avatar
osku committed
64 65 66

#define UT_LIST_NODE_T(TYPE)\
struct {\
67
	TYPE *	prev;	/*!< pointer to the previous node,\
osku's avatar
osku committed
68
			NULL if start of list */\
69
	TYPE *	next;	/*!< pointer to next node, NULL if end of list */\
osku's avatar
osku committed
70 71
}\

72 73 74 75
/*******************************************************************//**
Initializes the base node of a two-way list.
@param BASE	the list base node
*/
osku's avatar
osku committed
76 77 78 79 80 81 82
#define UT_LIST_INIT(BASE)\
{\
	(BASE).count = 0;\
	(BASE).start = NULL;\
	(BASE).end   = NULL;\
}\

83
/*******************************************************************//**
osku's avatar
osku committed
84
Adds the node as the first element in a two-way linked list.
85 86 87 88
@param NAME	list name
@param BASE	the base node (not a pointer to it)
@param N	pointer to the node to be added to the list.
*/
osku's avatar
osku committed
89 90 91 92 93 94
#define UT_LIST_ADD_FIRST(NAME, BASE, N)\
{\
	ut_ad(N);\
	((BASE).count)++;\
	((N)->NAME).next = (BASE).start;\
	((N)->NAME).prev = NULL;\
95
	if (UNIV_LIKELY((BASE).start != NULL)) {\
96
		ut_ad((BASE).start != (N));\
osku's avatar
osku committed
97 98 99
		(((BASE).start)->NAME).prev = (N);\
	}\
	(BASE).start = (N);\
100
	if (UNIV_UNLIKELY((BASE).end == NULL)) {\
osku's avatar
osku committed
101 102 103 104
		(BASE).end = (N);\
	}\
}\

105
/*******************************************************************//**
osku's avatar
osku committed
106
Adds the node as the last element in a two-way linked list.
107 108 109 110
@param NAME	list name
@param BASE	the base node (not a pointer to it)
@param N	pointer to the node to be added to the list
*/
osku's avatar
osku committed
111 112
#define UT_LIST_ADD_LAST(NAME, BASE, N)\
{\
113
	ut_ad(N != NULL);\
osku's avatar
osku committed
114 115 116 117
	((BASE).count)++;\
	((N)->NAME).prev = (BASE).end;\
	((N)->NAME).next = NULL;\
	if ((BASE).end != NULL) {\
118
		ut_ad((BASE).end != (N));\
osku's avatar
osku committed
119 120 121 122 123 124 125 126
		(((BASE).end)->NAME).next = (N);\
	}\
	(BASE).end = (N);\
	if ((BASE).start == NULL) {\
		(BASE).start = (N);\
	}\
}\

127
/*******************************************************************//**
osku's avatar
osku committed
128
Inserts a NODE2 after NODE1 in a list.
129 130 131 132 133
@param NAME	list name
@param BASE	the base node (not a pointer to it)
@param NODE1	pointer to node after which NODE2 is inserted
@param NODE2	pointer to node being inserted after NODE1
*/
osku's avatar
osku committed
134 135 136 137
#define UT_LIST_INSERT_AFTER(NAME, BASE, NODE1, NODE2)\
{\
	ut_ad(NODE1);\
	ut_ad(NODE2);\
138
	ut_ad((NODE1) != (NODE2));\
osku's avatar
osku committed
139 140 141 142 143 144 145 146 147 148 149 150
	((BASE).count)++;\
	((NODE2)->NAME).prev = (NODE1);\
	((NODE2)->NAME).next = ((NODE1)->NAME).next;\
	if (((NODE1)->NAME).next != NULL) {\
		((((NODE1)->NAME).next)->NAME).prev = (NODE2);\
	}\
	((NODE1)->NAME).next = (NODE2);\
	if ((BASE).end == (NODE1)) {\
		(BASE).end = (NODE2);\
	}\
}\

151
#ifdef UNIV_LIST_DEBUG
152 153 154
/** Invalidate the pointers in a list node.
@param NAME	list name
@param N	pointer to the node that was removed */
155 156 157
# define UT_LIST_REMOVE_CLEAR(NAME, N)		\
((N)->NAME.prev = (N)->NAME.next = (void*) -1)
#else
158 159 160
/** Invalidate the pointers in a list node.
@param NAME	list name
@param N	pointer to the node that was removed */
161 162 163
# define UT_LIST_REMOVE_CLEAR(NAME, N) while (0)
#endif

164 165 166 167 168 169
/*******************************************************************//**
Removes a node from a two-way linked list.
@param NAME	list name
@param BASE	the base node (not a pointer to it)
@param N	pointer to the node to be removed from the list
*/
170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186
#define UT_LIST_REMOVE(NAME, BASE, N)					\
do {									\
	ut_ad(N);							\
	ut_a((BASE).count > 0);						\
	((BASE).count)--;						\
	if (((N)->NAME).next != NULL) {					\
		((((N)->NAME).next)->NAME).prev = ((N)->NAME).prev;	\
	} else {							\
		(BASE).end = ((N)->NAME).prev;				\
	}								\
	if (((N)->NAME).prev != NULL) {					\
		((((N)->NAME).prev)->NAME).next = ((N)->NAME).next;	\
	} else {							\
		(BASE).start = ((N)->NAME).next;			\
	}								\
	UT_LIST_REMOVE_CLEAR(NAME, N);					\
} while (0)
osku's avatar
osku committed
187

188 189 190 191 192
/********************************************************************//**
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 */
osku's avatar
osku committed
193 194 195
#define UT_LIST_GET_NEXT(NAME, N)\
	(((N)->NAME).next)

196 197 198 199 200
/********************************************************************//**
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 */
osku's avatar
osku committed
201 202 203
#define UT_LIST_GET_PREV(NAME, N)\
	(((N)->NAME).prev)

204
/********************************************************************//**
osku's avatar
osku committed
205
Alternative macro to get the number of nodes in a two-way list, i.e.,
206 207 208
its length.
@param BASE	the base node (not a pointer to it).
@return		the number of nodes in the list */
osku's avatar
osku committed
209 210 211
#define UT_LIST_GET_LEN(BASE)\
	(BASE).count

212 213 214 215
/********************************************************************//**
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 */
osku's avatar
osku committed
216 217 218
#define UT_LIST_GET_FIRST(BASE)\
	(BASE).start

219 220 221 222
/********************************************************************//**
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 */
osku's avatar
osku committed
223 224 225
#define UT_LIST_GET_LAST(BASE)\
	(BASE).end

226 227 228 229 230 231
/********************************************************************//**
Checks the consistency of a two-way list.
@param NAME		the name of the list
@param TYPE		node type
@param BASE		base node (not a pointer to it)
@param ASSERTION	a condition on ut_list_node_313 */
232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258
#define UT_LIST_VALIDATE(NAME, TYPE, BASE, ASSERTION)			\
do {									\
	ulint	ut_list_i_313;						\
	TYPE*	ut_list_node_313;					\
									\
	ut_list_node_313 = (BASE).start;				\
									\
	for (ut_list_i_313 = (BASE).count; ut_list_i_313--; ) {		\
		ut_a(ut_list_node_313);					\
		ASSERTION;						\
		ut_ad((ut_list_node_313->NAME).next || !ut_list_i_313);	\
		ut_list_node_313 = (ut_list_node_313->NAME).next;	\
	}								\
									\
	ut_a(ut_list_node_313 == NULL);					\
									\
	ut_list_node_313 = (BASE).end;					\
									\
	for (ut_list_i_313 = (BASE).count; ut_list_i_313--; ) {		\
		ut_a(ut_list_node_313);					\
		ASSERTION;						\
		ut_ad((ut_list_node_313->NAME).prev || !ut_list_i_313);	\
		ut_list_node_313 = (ut_list_node_313->NAME).prev;	\
	}								\
									\
	ut_a(ut_list_node_313 == NULL);					\
} while (0)
osku's avatar
osku committed
259 260 261

#endif