← Back to branch summary

~ubuntu-branches/ubuntu/precise/mysql-5.1/precise

« back to all changes in this revision

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

  • Committer: Bazaar Package Importer
  • Author(s): Norbert Tretkowski
  • Date: 2010-03-17 14:56:02 UTC
  • Revision ID: james.westby@ubuntu.com-20100317145602-x7e30l1b2sb5s6w6
Tags: upstream-5.1.45
Import upstream version 5.1.45

Show diffs side-by-side

added added

removed removed

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