1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
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
|
/*****************************************************************************
Copyright (c) 1995, 2010, Innobase Oy. 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 St, Fifth Floor, Boston, MA 02110-1301 USA
*****************************************************************************/
/******************************************************************//**
@file include/ut0lst.h
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. */
/*******************************************************************//**
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).
@param TYPE the name of the list node data type */
#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.
@param TYPE the list node type name */
/* Example:
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.
@param BASE the list base node
*/
#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.
@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.
*/
#define UT_LIST_ADD_FIRST(NAME, BASE, 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.
@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
*/
#define UT_LIST_ADD_LAST(NAME, BASE, N)\
{\
ut_ad(N != NULL);\
((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.
@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
*/
#define UT_LIST_INSERT_AFTER(NAME, BASE, NODE1, NODE2)\
{\
ut_ad(NODE1);\
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);\
}\
}\
#ifdef UNIV_LIST_DEBUG
/** Invalidate the pointers in a list node.
@param NAME list name
@param N pointer to the node that was removed */
# define UT_LIST_REMOVE_CLEAR(NAME, N) \
((N)->NAME.prev = (N)->NAME.next = (void*) -1)
#else
/** Invalidate the pointers in a list node.
@param NAME list name
@param N pointer to the node that was removed */
# define UT_LIST_REMOVE_CLEAR(NAME, N) do {} while (0)
#endif
/*******************************************************************//**
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
*/
#define UT_LIST_REMOVE(NAME, BASE, N) \
do { \
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.
@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
/********************************************************************//**
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 */
#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)
#endif
|
