~drizzle-trunk/drizzle/development : contents of storage/innobase/include/ut0lst.h at revision 665.1.3

~drizzle-trunk/drizzle/development : (revision 665.1.3)

/**********************************************************************
List utilities

(c) 1995 Innobase Oy

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

/***********************************************************************
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
the base node from the count). TYPE should be the list node type name. */

#define UT_LIST_BASE_NODE_T(TYPE)\
struct {\
	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 */\
}\

/***********************************************************************
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
to the list. TYPE should be the list node type name. Example of usage:

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

#define UT_LIST_NODE_T(TYPE)\
struct {\
	TYPE *	prev;	/* pointer to the previous node,\
			NULL if start of list */\
	TYPE *	next;	/* pointer to next node, NULL if end of list */\
}\

/***********************************************************************
Initializes the base node of a two-way list. */

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

/***********************************************************************
Adds the node as the first element in a two-way linked list.
BASE has to be the base node (not a pointer to it). N has to be
the pointer to the node to be added to the list. NAME is the list name. */

#define UT_LIST_ADD_FIRST(NAME, BASE, N)\
{\
	ut_ad(N);\
	((BASE).count)++;\
	((N)->NAME).next = (BASE).start;\
	((N)->NAME).prev = NULL;\
	if (UNIV_LIKELY((BASE).start != NULL)) {\
		ut_ad((BASE).start != (N));\
		(((BASE).start)->NAME).prev = (N);\
	}\
	(BASE).start = (N);\
	if (UNIV_UNLIKELY((BASE).end == NULL)) {\
		(BASE).end = (N);\
	}\
}\

/***********************************************************************
Adds the node as the last element in a two-way linked list.
BASE has to be the base node (not a pointer to it). N has to be
the pointer to the node to be added to the list. NAME is the list name. */

#define UT_LIST_ADD_LAST(NAME, BASE, N)\
{\
	ut_ad(N);\
	((BASE).count)++;\
	((N)->NAME).prev = (BASE).end;\
	((N)->NAME).next = NULL;\
	if ((BASE).end != NULL) {\
		ut_ad((BASE).end != (N));\
		(((BASE).end)->NAME).next = (N);\
	}\
	(BASE).end = (N);\
	if ((BASE).start == NULL) {\
		(BASE).start = (N);\
	}\
}\

/***********************************************************************
Inserts a NODE2 after NODE1 in a list.
BASE has to be the base node (not a pointer to it). NAME is the list
name, NODE1 and NODE2 are pointers to nodes. */

#define UT_LIST_INSERT_AFTER(NAME, BASE, NODE1, NODE2)\
{\
	ut_ad(NODE1);\
	ut_ad(NODE2);\
	ut_ad((NODE1) != (NODE2));\
	((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);\
	}\
}\

/* Invalidate the pointers in a list node. */
#ifdef UNIV_LIST_DEBUG
# define UT_LIST_REMOVE_CLEAR(NAME, N)		\
((N)->NAME.prev = (N)->NAME.next = (void*) -1)
#else
# define UT_LIST_REMOVE_CLEAR(NAME, N) while (0)
#endif

/***********************************************************************
Removes a node from a two-way linked list. BASE has to be the base node
(not a pointer to it). N has to be the pointer to the node to be removed
from the list. NAME is the list name. */

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

/************************************************************************
Gets the next node in a two-way list. NAME is the name of the list
and N is pointer to a node. */

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

/************************************************************************
Gets the previous node in a two-way list. NAME is the name of the list
and N is pointer to a node. */

#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. BASE is the base node (not a pointer to it). */

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

/************************************************************************
Gets the first node in a two-way list, or returns NULL,
if the list is empty. BASE is the base node (not a pointer to it). */

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

/************************************************************************
Gets the last node in a two-way list, or returns NULL,
if the list is empty. BASE is the base node (not a pointer to it). */

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

/************************************************************************
Checks the consistency of a two-way list. NAME is the name of the list,
TYPE is the node type, and BASE is the base node (not a pointer to it). */

#define UT_LIST_VALIDATE(NAME, TYPE, BASE)\
{\
	ulint	ut_list_i_313;\
	TYPE *	ut_list_node_313;\
\
	ut_list_node_313 = (BASE).start;\
\
	for (ut_list_i_313 = 0; ut_list_i_313 < (BASE).count;\
						ut_list_i_313++) {\
		ut_a(ut_list_node_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 = 0; ut_list_i_313 < (BASE).count;\
						ut_list_i_313++) {\
		ut_a(ut_list_node_313);\
		ut_list_node_313 = (ut_list_node_313->NAME).prev;\
	}\
\
	ut_a(ut_list_node_313 == NULL);\
}\


#endif


641.1.2 by Monty Taylor Imported 1.0.1 with clean - with no changes.	1	/**********************************************************************
	2	List utilities
	3
	4	(c) 1995 Innobase Oy
	5
	6	Created 9/10/1995 Heikki Tuuri
	7	***********************************************************************/
	8
	9	#ifndef ut0lst_h
	10	#define ut0lst_h
	11
	12	#include "univ.i"
	13
	14	/* This module implements the two-way linear list which should be used
	15	if a list is used in the database. Note that a single struct may belong
	16	to two or more lists, provided that the list are given different names.
	17	An example of the usage of the lists can be found in fil0fil.c. */
	18
	19	/***********************************************************************
	20	This macro expands to the unnamed type definition of a struct which acts
	21	as the two-way list base node. The base node contains pointers
	22	to both ends of the list and a count of nodes in the list (excluding
	23	the base node from the count). TYPE should be the list node type name. */
	24
	25	#define UT_LIST_BASE_NODE_T(TYPE)\
	26	struct {\
	27	ulint count; /* count of nodes in list */\
	28	TYPE * start; /* pointer to list start, NULL if empty */\
	29	TYPE * end; /* pointer to list end, NULL if empty */\
	30	}\
	31
	32	/***********************************************************************
	33	This macro expands to the unnamed type definition of a struct which
	34	should be embedded in the nodes of the list, the node type must be a struct.
	35	This struct contains the pointers to next and previous nodes in the list.
	36	The name of the field in the node struct should be the name given
	37	to the list. TYPE should be the list node type name. Example of usage:
	38
	39	typedef struct LRU_node_struct LRU_node_t;
	40	struct LRU_node_struct {
	41	UT_LIST_NODE_T(LRU_node_t) LRU_list;
	42	...
	43	}
	44	The example implements an LRU list of name LRU_list. Its nodes are of type
	45	LRU_node_t.
	46	*/
	47
	48	#define UT_LIST_NODE_T(TYPE)\
	49	struct {\
	50	TYPE * prev; /* pointer to the previous node,\
	51	NULL if start of list */\
	52	TYPE * next; /* pointer to next node, NULL if end of list */\
	53	}\
	54
	55	/***********************************************************************
	56	Initializes the base node of a two-way list. */
	57
	58	#define UT_LIST_INIT(BASE)\
	59	{\
	60	(BASE).count = 0;\
	61	(BASE).start = NULL;\
	62	(BASE).end = NULL;\
	63	}\
	64
65	/***********************************************************************
66	Adds the node as the first element in a two-way linked list.
67	BASE has to be the base node (not a pointer to it). N has to be
68	the pointer to the node to be added to the list. NAME is the list name. */
69
70	#define UT_LIST_ADD_FIRST(NAME, BASE, N)\
71	{\
72	ut_ad(N);\
73	((BASE).count)++;\
74	((N)->NAME).next = (BASE).start;\
75	((N)->NAME).prev = NULL;\
76	if (UNIV_LIKELY((BASE).start != NULL)) {\
77	ut_ad((BASE).start != (N));\
78	(((BASE).start)->NAME).prev = (N);\
79	}\
80	(BASE).start = (N);\
81	if (UNIV_UNLIKELY((BASE).end == NULL)) {\
82	(BASE).end = (N);\
83	}\
84	}\
85
86	/***********************************************************************
87	Adds the node as the last element in a two-way linked list.
88	BASE has to be the base node (not a pointer to it). N has to be
89	the pointer to the node to be added to the list. NAME is the list name. */
90
91	#define UT_LIST_ADD_LAST(NAME, BASE, N)\
92	{\
93	ut_ad(N);\
94	((BASE).count)++;\
95	((N)->NAME).prev = (BASE).end;\
96	((N)->NAME).next = NULL;\
97	if ((BASE).end != NULL) {\
98	ut_ad((BASE).end != (N));\
99	(((BASE).end)->NAME).next = (N);\
100	}\
101	(BASE).end = (N);\
102	if ((BASE).start == NULL) {\
103	(BASE).start = (N);\
104	}\
105	}\
106
107	/***********************************************************************
108	Inserts a NODE2 after NODE1 in a list.
109	BASE has to be the base node (not a pointer to it). NAME is the list
110	name, NODE1 and NODE2 are pointers to nodes. */
111
112	#define UT_LIST_INSERT_AFTER(NAME, BASE, NODE1, NODE2)\
113	{\
114	ut_ad(NODE1);\
115	ut_ad(NODE2);\
116	ut_ad((NODE1) != (NODE2));\
117	((BASE).count)++;\
118	((NODE2)->NAME).prev = (NODE1);\
119	((NODE2)->NAME).next = ((NODE1)->NAME).next;\
120	if (((NODE1)->NAME).next != NULL) {\
121	((((NODE1)->NAME).next)->NAME).prev = (NODE2);\
122	}\
123	((NODE1)->NAME).next = (NODE2);\
124	if ((BASE).end == (NODE1)) {\
125	(BASE).end = (NODE2);\
126	}\
127	}\
128
129	/* Invalidate the pointers in a list node. */
130	#ifdef UNIV_LIST_DEBUG
131	# define UT_LIST_REMOVE_CLEAR(NAME, N) \
132	((N)->NAME.prev = (N)->NAME.next = (void*) -1)
133	#else
134	# define UT_LIST_REMOVE_CLEAR(NAME, N) while (0)
135	#endif
136
137	/***********************************************************************
138	Removes a node from a two-way linked list. BASE has to be the base node
139	(not a pointer to it). N has to be the pointer to the node to be removed
140	from the list. NAME is the list name. */
141
142	#define UT_LIST_REMOVE(NAME, BASE, N) \
143	do { \
144	ut_ad(N); \
145	ut_a((BASE).count > 0); \
146	((BASE).count)--; \
147	if (((N)->NAME).next != NULL) { \
148	((((N)->NAME).next)->NAME).prev = ((N)->NAME).prev; \
149	} else { \
150	(BASE).end = ((N)->NAME).prev; \
151	} \
152	if (((N)->NAME).prev != NULL) { \
153	((((N)->NAME).prev)->NAME).next = ((N)->NAME).next; \
154	} else { \
155	(BASE).start = ((N)->NAME).next; \
156	} \
157	UT_LIST_REMOVE_CLEAR(NAME, N); \
158	} while (0)
159
160	/************************************************************************
161	Gets the next node in a two-way list. NAME is the name of the list
162	and N is pointer to a node. */
163
164	#define UT_LIST_GET_NEXT(NAME, N)\
165	(((N)->NAME).next)
166
167	/************************************************************************
168	Gets the previous node in a two-way list. NAME is the name of the list
169	and N is pointer to a node. */
170
171	#define UT_LIST_GET_PREV(NAME, N)\
172	(((N)->NAME).prev)
173
174	/************************************************************************
175	Alternative macro to get the number of nodes in a two-way list, i.e.,
176	its length. BASE is the base node (not a pointer to it). */
177
178	#define UT_LIST_GET_LEN(BASE)\
179	(BASE).count
180
181	/************************************************************************
182	Gets the first node in a two-way list, or returns NULL,
183	if the list is empty. BASE is the base node (not a pointer to it). */
184
185	#define UT_LIST_GET_FIRST(BASE)\
186	(BASE).start
187
188	/************************************************************************
189	Gets the last node in a two-way list, or returns NULL,
190	if the list is empty. BASE is the base node (not a pointer to it). */
191
192	#define UT_LIST_GET_LAST(BASE)\
193	(BASE).end
194
195	/************************************************************************
196	Checks the consistency of a two-way list. NAME is the name of the list,
197	TYPE is the node type, and BASE is the base node (not a pointer to it). */
198
199	#define UT_LIST_VALIDATE(NAME, TYPE, BASE)\
200	{\
201	ulint ut_list_i_313;\
202	TYPE * ut_list_node_313;\
203	\
204	ut_list_node_313 = (BASE).start;\
205	\
206	for (ut_list_i_313 = 0; ut_list_i_313 < (BASE).count;\
207	ut_list_i_313++) {\
208	ut_a(ut_list_node_313);\
209	ut_list_node_313 = (ut_list_node_313->NAME).next;\
210	}\
211	\
212	ut_a(ut_list_node_313 == NULL);\
213	\
214	ut_list_node_313 = (BASE).end;\
215	\
216	for (ut_list_i_313 = 0; ut_list_i_313 < (BASE).count;\
217	ut_list_i_313++) {\
218	ut_a(ut_list_node_313);\
219	ut_list_node_313 = (ut_list_node_313->NAME).prev;\
220	}\
221	\
222	ut_a(ut_list_node_313 == NULL);\
223	}\
224
225
226	#endif
227