← 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-10-27 23:19:48 UTC
  • mto: (520.4.12 merge-innodb-plugin)
  • mto: This revision was merged to the branch mainline in revision 563.
  • Revision ID: monty@inaugust.com-20081027231948-3kl6ss04plbakqcr
Split some more things out of common_includes.h.

Show diffs side-by-side

added added

removed removed

Lines of Context:
storage/innobase/include/ut0lst.h
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