← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to storage/innobase/include/ut0lst.h

  • Committer: Monty Taylor
  • Date: 2008-12-06 22:41:03 UTC
  • mto: (656.1.7 devel)
  • mto: This revision was merged to the branch mainline in revision 665.
  • Revision ID: monty@inaugust.com-20081206224103-jdouqwt9hb0f01y1
Moved non-working tests into broken suite for easier running of working tests.

Show diffs side-by-side

added added

removed removed

Lines of Context:
storage/innobase/include/ut0lst.h
1
 
/*****************************************************************************
2
 
 
3
 
Copyright (C) 1995, 2010, Innobase Oy. All Rights Reserved.
4
 
 
5
 
This program is free software; you can redistribute it and/or modify it under
6
 
the terms of the GNU General Public License as published by the Free Software
7
 
Foundation; version 2 of the License.
8
 
 
9
 
This program is distributed in the hope that it will be useful, but WITHOUT
10
 
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
11
 
FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
12
 
 
13
 
You should have received a copy of the GNU General Public License along with
14
 
this program; if not, write to the Free Software Foundation, Inc., 51 Franklin
15
 
St, Fifth Floor, Boston, MA 02110-1301 USA
16
 
 
17
 
*****************************************************************************/
18
 
 
19
 
/******************************************************************//**
20
 
@file include/ut0lst.h
 
1
/**********************************************************************
21
2
List utilities
22
3
 
 
4
(c) 1995 Innobase Oy
 
5
 
23
6
Created 9/10/1995 Heikki Tuuri
24
7
***********************************************************************/
25
8
 
33
16
to two or more lists, provided that the list are given different names.
34
17
An example of the usage of the lists can be found in fil0fil.c. */
35
18
 
36
 
/*******************************************************************//**
 
19
/***********************************************************************
37
20
This macro expands to the unnamed type definition of a struct which acts
38
21
as the two-way list base node. The base node contains pointers
39
22
to both ends of the list and a count of nodes in the list (excluding
40
 
the base node from the count).
41
 
@param TYPE     the name of the list node data type */
42
 
#ifdef __cplusplus
43
 
template<class T>
44
 
class ut_list_base_node
45
 
{
46
 
public:
47
 
  size_t count; /*!< count of nodes in list */\
48
 
  T *   start;  /*!< pointer to list start, NULL if empty */\
49
 
  T *   end;    /*!< pointer to list end, NULL if empty */\
50
 
};
51
 
#define UT_LIST_BASE_NODE_T(TYPE) ut_list_base_node<TYPE>
52
 
#else
53
 
#define UT_LIST_BASE_NODE_T(TYPE) int
54
 
#endif
55
 
 
56
 
/*******************************************************************//**
 
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
/***********************************************************************
57
33
This macro expands to the unnamed type definition of a struct which
58
34
should be embedded in the nodes of the list, the node type must be a struct.
59
35
This struct contains the pointers to next and previous nodes in the list.
60
36
The name of the field in the node struct should be the name given
61
 
to the list.
62
 
@param TYPE     the list node type name */
63
 
/* Example:
 
37
to the list. TYPE should be the list node type name. Example of usage:
 
38
 
64
39
typedef struct LRU_node_struct  LRU_node_t;
65
40
struct LRU_node_struct {
66
41
        UT_LIST_NODE_T(LRU_node_t)      LRU_list;
67
42
        ...
68
43
}
69
44
The example implements an LRU list of name LRU_list. Its nodes are of type
70
 
LRU_node_t. */
 
45
LRU_node_t.
 
46
*/
71
47
 
72
48
#define UT_LIST_NODE_T(TYPE)\
73
49
struct {\
74
 
        TYPE *  prev;   /*!< pointer to the previous node,\
 
50
        TYPE *  prev;   /* pointer to the previous node,\
75
51
                        NULL if start of list */\
76
 
        TYPE *  next;   /*!< pointer to next node, NULL if end of list */\
 
52
        TYPE *  next;   /* pointer to next node, NULL if end of list */\
77
53
}\
78
54
 
79
 
/*******************************************************************//**
80
 
Initializes the base node of a two-way list.
81
 
@param BASE     the list base node
82
 
*/
 
55
/***********************************************************************
 
56
Initializes the base node of a two-way list. */
 
57
 
83
58
#define UT_LIST_INIT(BASE)\
84
59
{\
85
60
        (BASE).count = 0;\
87
62
        (BASE).end   = NULL;\
88
63
}\
89
64
 
90
 
/*******************************************************************//**
 
65
/***********************************************************************
91
66
Adds the node as the first element in a two-way linked list.
92
 
@param NAME     list name
93
 
@param BASE     the base node (not a pointer to it)
94
 
@param N        pointer to the node to be added to the list.
95
 
*/
 
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
 
96
70
#define UT_LIST_ADD_FIRST(NAME, BASE, N)\
97
71
{\
98
72
        ut_ad(N);\
109
83
        }\
110
84
}\
111
85
 
112
 
/*******************************************************************//**
 
86
/***********************************************************************
113
87
Adds the node as the last element in a two-way linked list.
114
 
@param NAME     list name
115
 
@param BASE     the base node (not a pointer to it)
116
 
@param N        pointer to the node to be added to the list
117
 
*/
 
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
 
118
91
#define UT_LIST_ADD_LAST(NAME, BASE, N)\
119
92
{\
120
 
        ut_ad(N != NULL);\
 
93
        ut_ad(N);\
121
94
        ((BASE).count)++;\
122
95
        ((N)->NAME).prev = (BASE).end;\
123
96
        ((N)->NAME).next = NULL;\
131
104
        }\
132
105
}\
133
106
 
134
 
/*******************************************************************//**
 
107
/***********************************************************************
135
108
Inserts a NODE2 after NODE1 in a list.
136
 
@param NAME     list name
137
 
@param BASE     the base node (not a pointer to it)
138
 
@param NODE1    pointer to node after which NODE2 is inserted
139
 
@param NODE2    pointer to node being inserted after NODE1
140
 
*/
 
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
 
141
112
#define UT_LIST_INSERT_AFTER(NAME, BASE, NODE1, NODE2)\
142
113
{\
143
114
        ut_ad(NODE1);\
155
126
        }\
156
127
}\
157
128
 
 
129
/* Invalidate the pointers in a list node. */
158
130
#ifdef UNIV_LIST_DEBUG
159
 
/** Invalidate the pointers in a list node.
160
 
@param NAME     list name
161
 
@param N        pointer to the node that was removed */
162
131
# define UT_LIST_REMOVE_CLEAR(NAME, N)          \
163
132
((N)->NAME.prev = (N)->NAME.next = (void*) -1)
164
133
#else
165
 
/** Invalidate the pointers in a list node.
166
 
@param NAME     list name
167
 
@param N        pointer to the node that was removed */
168
 
# define UT_LIST_REMOVE_CLEAR(NAME, N)
 
134
# define UT_LIST_REMOVE_CLEAR(NAME, N) while (0)
169
135
#endif
170
136
 
171
 
/*******************************************************************//**
172
 
Removes a node from a two-way linked list.
173
 
@param NAME     list name
174
 
@param BASE     the base node (not a pointer to it)
175
 
@param N        pointer to the node to be removed from the list
176
 
*/
 
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
 
177
142
#define UT_LIST_REMOVE(NAME, BASE, N)                                   \
178
143
do {                                                                    \
179
144
        ut_ad(N);                                                       \
192
157
        UT_LIST_REMOVE_CLEAR(NAME, N);                                  \
193
158
} while (0)
194
159
 
195
 
/********************************************************************//**
196
 
Gets the next node in a two-way list.
197
 
@param NAME     list name
198
 
@param N        pointer to a node
199
 
@return         the successor of N in NAME, or NULL */
 
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
 
200
164
#define UT_LIST_GET_NEXT(NAME, N)\
201
165
        (((N)->NAME).next)
202
166
 
203
 
/********************************************************************//**
204
 
Gets the previous node in a two-way list.
205
 
@param NAME     list name
206
 
@param N        pointer to a node
207
 
@return         the predecessor of N in NAME, or NULL */
 
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
 
208
171
#define UT_LIST_GET_PREV(NAME, N)\
209
172
        (((N)->NAME).prev)
210
173
 
211
 
/********************************************************************//**
 
174
/************************************************************************
212
175
Alternative macro to get the number of nodes in a two-way list, i.e.,
213
 
its length.
214
 
@param BASE     the base node (not a pointer to it).
215
 
@return         the number of nodes in the list */
 
176
its length. BASE is the base node (not a pointer to it). */
 
177
 
216
178
#define UT_LIST_GET_LEN(BASE)\
217
179
        (BASE).count
218
180
 
219
 
/********************************************************************//**
220
 
Gets the first node in a two-way list.
221
 
@param BASE     the base node (not a pointer to it)
222
 
@return         first node, or NULL if the list is empty */
 
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
 
223
185
#define UT_LIST_GET_FIRST(BASE)\
224
186
        (BASE).start
225
187
 
226
 
/********************************************************************//**
227
 
Gets the last node in a two-way list.
228
 
@param BASE     the base node (not a pointer to it)
229
 
@return         last node, or NULL if the list is empty */
230
 
#ifdef __cplusplus
 
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
 
231
192
#define UT_LIST_GET_LAST(BASE)\
232
193
        (BASE).end
233
 
#else
234
 
#define UT_LIST_GET_LAST(BASE) (BASE= NULL)
235
 
#endif
236
 
 
237
 
/********************************************************************//**
238
 
Checks the consistency of a two-way list.
239
 
@param NAME             the name of the list
240
 
@param TYPE             node type
241
 
@param BASE             base node (not a pointer to it)
242
 
@param ASSERTION        a condition on ut_list_node_313 */
243
 
#define UT_LIST_VALIDATE(NAME, TYPE, BASE, ASSERTION)                   \
244
 
do {                                                                    \
245
 
        ulint   ut_list_i_313;                                          \
246
 
        TYPE*   ut_list_node_313;                                       \
247
 
                                                                        \
248
 
        ut_list_node_313 = (BASE).start;                                \
249
 
                                                                        \
250
 
        for (ut_list_i_313 = (BASE).count; ut_list_i_313--; ) {         \
251
 
                ut_a(ut_list_node_313);                                 \
252
 
                ASSERTION;                                              \
253
 
                ut_ad((ut_list_node_313->NAME).next || !ut_list_i_313); \
254
 
                ut_list_node_313 = (ut_list_node_313->NAME).next;       \
255
 
        }                                                               \
256
 
                                                                        \
257
 
        ut_a(ut_list_node_313 == NULL);                                 \
258
 
                                                                        \
259
 
        ut_list_node_313 = (BASE).end;                                  \
260
 
                                                                        \
261
 
        for (ut_list_i_313 = (BASE).count; ut_list_i_313--; ) {         \
262
 
                ut_a(ut_list_node_313);                                 \
263
 
                ASSERTION;                                              \
264
 
                ut_ad((ut_list_node_313->NAME).prev || !ut_list_i_313); \
265
 
                ut_list_node_313 = (ut_list_node_313->NAME).prev;       \
266
 
        }                                                               \
267
 
                                                                        \
268
 
        ut_a(ut_list_node_313 == NULL);                                 \
269
 
} while (0)
 
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
 
270
225
 
271
226
#endif
272
227