1
/**********************************************************************
6
Created 9/10/1995 Heikki Tuuri
7
***********************************************************************/
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. */
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. */
25
#define UT_LIST_BASE_NODE_T(TYPE)\
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 */\
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:
39
typedef struct LRU_node_struct LRU_node_t;
40
struct LRU_node_struct {
41
UT_LIST_NODE_T(LRU_node_t) LRU_list;
44
The example implements an LRU list of name LRU_list. Its nodes are of type
48
#define UT_LIST_NODE_T(TYPE)\
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 */\
55
/***********************************************************************
56
Initializes the base node of a two-way list. */
58
#define UT_LIST_INIT(BASE)\
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. */
70
#define UT_LIST_ADD_FIRST(NAME, BASE, N)\
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);\
81
if (UNIV_UNLIKELY((BASE).end == NULL)) {\
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. */
91
#define UT_LIST_ADD_LAST(NAME, BASE, N)\
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);\
102
if ((BASE).start == NULL) {\
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. */
112
#define UT_LIST_INSERT_AFTER(NAME, BASE, NODE1, NODE2)\
116
ut_ad((NODE1) != (NODE2));\
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);\
123
((NODE1)->NAME).next = (NODE2);\
124
if ((BASE).end == (NODE1)) {\
125
(BASE).end = (NODE2);\
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)
134
# define UT_LIST_REMOVE_CLEAR(NAME, N) while (0)
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. */
142
#define UT_LIST_REMOVE(NAME, BASE, N) \
145
ut_a((BASE).count > 0); \
147
if (((N)->NAME).next != NULL) { \
148
((((N)->NAME).next)->NAME).prev = ((N)->NAME).prev; \
150
(BASE).end = ((N)->NAME).prev; \
152
if (((N)->NAME).prev != NULL) { \
153
((((N)->NAME).prev)->NAME).next = ((N)->NAME).next; \
155
(BASE).start = ((N)->NAME).next; \
157
UT_LIST_REMOVE_CLEAR(NAME, N); \
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. */
164
#define UT_LIST_GET_NEXT(NAME, N)\
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. */
171
#define UT_LIST_GET_PREV(NAME, N)\
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). */
178
#define UT_LIST_GET_LEN(BASE)\
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). */
185
#define UT_LIST_GET_FIRST(BASE)\
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). */
192
#define UT_LIST_GET_LAST(BASE)\
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). */
199
#define UT_LIST_VALIDATE(NAME, TYPE, BASE)\
201
ulint ut_list_i_313;\
202
TYPE * ut_list_node_313;\
204
ut_list_node_313 = (BASE).start;\
206
for (ut_list_i_313 = 0; ut_list_i_313 < (BASE).count;\
208
ut_a(ut_list_node_313);\
209
ut_list_node_313 = (ut_list_node_313->NAME).next;\
212
ut_a(ut_list_node_313 == NULL);\
214
ut_list_node_313 = (BASE).end;\
216
for (ut_list_i_313 = 0; ut_list_i_313 < (BASE).count;\
218
ut_a(ut_list_node_313);\
219
ut_list_node_313 = (ut_list_node_313->NAME).prev;\
222
ut_a(ut_list_node_313 == NULL);\
added
removed
include/ut0lst.h
