1 /*****************************************************************************
2
3 Copyright (c) 1995, 2011, Oracle and/or its affiliates. All Rights Reserved.
4
5 This program is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License, version 2.0,
7 as published by the Free Software Foundation.
8
9 This program is also distributed with certain software (including
10 but not limited to OpenSSL) that is licensed under separate terms,
11 as designated in a particular file or component or in included license
12 documentation. The authors of MySQL hereby grant you an additional
13 permission to link the program and your derivative works with the
14 separately licensed software that they have included with MySQL.
15
16 This program is distributed in the hope that it will be useful,
17 but WITHOUT ANY WARRANTY; without even the implied warranty of
18 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19 GNU General Public License, version 2.0, for more details.
20
21 You should have received a copy of the GNU General Public License along with
22 this program; if not, write to the Free Software Foundation, Inc.,
23 51 Franklin Street, Suite 500, Boston, MA 02110-1335 USA
24
25 *****************************************************************************/
26
27 /******************************************************************//**
28 @file include/ut0lst.h
29 List utilities
30
31 Created 9/10/1995 Heikki Tuuri
32 ***********************************************************************/
33
34 #ifndef ut0lst_h
35 #define ut0lst_h
36
37 #include "univ.i"
38
39 /*******************************************************************//**
40 Return offset of F in POD T.
41 @param T - POD pointer
42 @param F - Field in T */
43 #define IB_OFFSETOF(T, F) \
44 (reinterpret_cast<byte*>(&(T)->F) - reinterpret_cast<byte*>(T))
45
46 /* This module implements the two-way linear list which should be used
47 if a list is used in the database. Note that a single struct may belong
48 to two or more lists, provided that the list are given different names.
49 An example of the usage of the lists can be found in fil0fil.cc. */
50
51 /*******************************************************************//**
52 This macro expands to the unnamed type definition of a struct which acts
53 as the two-way list base node. The base node contains pointers
54 to both ends of the list and a count of nodes in the list (excluding
55 the base node from the count).
56 @param TYPE the name of the list node data type */
57 template <typename TYPE>
58 struct ut_list_base {
59 typedef TYPE elem_type;
60
61 ulint count; /*!< count of nodes in list */
62 TYPE* start; /*!< pointer to list start, NULL if empty */
63 TYPE* end; /*!< pointer to list end, NULL if empty */
64 };
65
66 #define UT_LIST_BASE_NODE_T(TYPE) ut_list_base<TYPE>
67
68 /*******************************************************************//**
69 This macro expands to the unnamed type definition of a struct which
70 should be embedded in the nodes of the list, the node type must be a struct.
71 This struct contains the pointers to next and previous nodes in the list.
72 The name of the field in the node struct should be the name given
73 to the list.
74 @param TYPE the list node type name */
75 /* Example:
76 struct LRU_node_t {
77 UT_LIST_NODE_T(LRU_node_t) LRU_list;
78 ...
79 }
80 The example implements an LRU list of name LRU_list. Its nodes are of type
81 LRU_node_t. */
82
83 template <typename TYPE>
84 struct ut_list_node {
85 TYPE* prev; /*!< pointer to the previous node,
86 NULL if start of list */
87 TYPE* next; /*!< pointer to next node, NULL if end of list */
88 };
89
90 #define UT_LIST_NODE_T(TYPE) ut_list_node<TYPE>
91
92 /*******************************************************************//**
93 Get the list node at offset.
94 @param elem - list element
95 @param offset - offset within element.
96 @return reference to list node. */
97 template <typename Type>
98 ut_list_node<Type>&
ut_elem_get_node(Type & elem,size_t offset)99 ut_elem_get_node(Type& elem, size_t offset)
100 {
101 ut_a(offset < sizeof(elem));
102
103 return(*reinterpret_cast<ut_list_node<Type>*>(
104 reinterpret_cast<byte*>(&elem) + offset));
105 }
106
107 /*******************************************************************//**
108 Initializes the base node of a two-way list.
109 @param BASE the list base node
110 */
111 #define UT_LIST_INIT(BASE)\
112 {\
113 (BASE).count = 0;\
114 (BASE).start = NULL;\
115 (BASE).end = NULL;\
116 }\
117
118 /*******************************************************************//**
119 Adds the node as the first element in a two-way linked list.
120 @param list the base node (not a pointer to it)
121 @param elem the element to add
122 @param offset offset of list node in elem. */
123 template <typename List, typename Type>
124 void
ut_list_prepend(List & list,Type & elem,size_t offset)125 ut_list_prepend(
126 List& list,
127 Type& elem,
128 size_t offset)
129 {
130 ut_list_node<Type>& elem_node = ut_elem_get_node(elem, offset);
131
132 elem_node.prev = 0;
133 elem_node.next = list.start;
134
135 if (list.start != 0) {
136 ut_list_node<Type>& base_node =
137 ut_elem_get_node(*list.start, offset);
138
139 ut_ad(list.start != &elem);
140
141 base_node.prev = &elem;
142 }
143
144 list.start = &elem;
145
146 if (list.end == 0) {
147 list.end = &elem;
148 }
149
150 ++list.count;
151 }
152
153 /*******************************************************************//**
154 Adds the node as the first element in a two-way linked list.
155 @param NAME list name
156 @param LIST the base node (not a pointer to it)
157 @param ELEM the element to add */
158 #define UT_LIST_ADD_FIRST(NAME, LIST, ELEM) \
159 ut_list_prepend(LIST, *ELEM, IB_OFFSETOF(ELEM, NAME))
160
161 /*******************************************************************//**
162 Adds the node as the last element in a two-way linked list.
163 @param list list
164 @param elem the element to add
165 @param offset offset of list node in elem */
166 template <typename List, typename Type>
167 void
ut_list_append(List & list,Type & elem,size_t offset)168 ut_list_append(
169 List& list,
170 Type& elem,
171 size_t offset)
172 {
173 ut_list_node<Type>& elem_node = ut_elem_get_node(elem, offset);
174
175 elem_node.next = 0;
176 elem_node.prev = list.end;
177
178 if (list.end != 0) {
179 ut_list_node<Type>& base_node =
180 ut_elem_get_node(*list.end, offset);
181
182 ut_ad(list.end != &elem);
183
184 base_node.next = &elem;
185 }
186
187 list.end = &elem;
188
189 if (list.start == 0) {
190 list.start = &elem;
191 }
192
193 ++list.count;
194 }
195
196 /*******************************************************************//**
197 Adds the node as the last element in a two-way linked list.
198 @param NAME list name
199 @param LIST list
200 @param ELEM the element to add */
201 #define UT_LIST_ADD_LAST(NAME, LIST, ELEM)\
202 ut_list_append(LIST, *ELEM, IB_OFFSETOF(ELEM, NAME))
203
204 /*******************************************************************//**
205 Inserts a ELEM2 after ELEM1 in a list.
206 @param list the base node
207 @param elem1 node after which ELEM2 is inserted
208 @param elem2 node being inserted after NODE1
209 @param offset offset of list node in elem1 and elem2 */
210 template <typename List, typename Type>
211 void
ut_list_insert(List & list,Type & elem1,Type & elem2,size_t offset)212 ut_list_insert(
213 List& list,
214 Type& elem1,
215 Type& elem2,
216 size_t offset)
217 {
218 ut_ad(&elem1 != &elem2);
219
220 ut_list_node<Type>& elem1_node = ut_elem_get_node(elem1, offset);
221 ut_list_node<Type>& elem2_node = ut_elem_get_node(elem2, offset);
222
223 elem2_node.prev = &elem1;
224 elem2_node.next = elem1_node.next;
225
226 if (elem1_node.next != NULL) {
227 ut_list_node<Type>& next_node =
228 ut_elem_get_node(*elem1_node.next, offset);
229
230 next_node.prev = &elem2;
231 }
232
233 elem1_node.next = &elem2;
234
235 if (list.end == &elem1) {
236 list.end = &elem2;
237 }
238
239 ++list.count;
240 }
241
242 /*******************************************************************//**
243 Inserts a ELEM2 after ELEM1 in a list.
244 @param NAME list name
245 @param LIST the base node
246 @param ELEM1 node after which ELEM2 is inserted
247 @param ELEM2 node being inserted after ELEM1 */
248 #define UT_LIST_INSERT_AFTER(NAME, LIST, ELEM1, ELEM2)\
249 ut_list_insert(LIST, *ELEM1, *ELEM2, IB_OFFSETOF(ELEM1, NAME))
250
251 #ifdef UNIV_LIST_DEBUG
252 /** Invalidate the pointers in a list node.
253 @param NAME list name
254 @param N pointer to the node that was removed */
255 # define UT_LIST_REMOVE_CLEAR(N) \
256 (N).next = (Type*) -1; \
257 (N).prev = (N).next
258 #else
259 /** Invalidate the pointers in a list node.
260 @param NAME list name
261 @param N pointer to the node that was removed */
262 # define UT_LIST_REMOVE_CLEAR(N)
263 #endif /* UNIV_LIST_DEBUG */
264
265 /*******************************************************************//**
266 Removes a node from a two-way linked list.
267 @param list the base node (not a pointer to it)
268 @param elem node to be removed from the list
269 @param offset offset of list node within elem */
270 template <typename List, typename Type>
271 void
ut_list_remove(List & list,Type & elem,size_t offset)272 ut_list_remove(
273 List& list,
274 Type& elem,
275 size_t offset)
276 {
277 ut_list_node<Type>& elem_node = ut_elem_get_node(elem, offset);
278
279 ut_a(list.count > 0);
280
281 if (elem_node.next != NULL) {
282 ut_list_node<Type>& next_node =
283 ut_elem_get_node(*elem_node.next, offset);
284
285 next_node.prev = elem_node.prev;
286 } else {
287 list.end = elem_node.prev;
288 }
289
290 if (elem_node.prev != NULL) {
291 ut_list_node<Type>& prev_node =
292 ut_elem_get_node(*elem_node.prev, offset);
293
294 prev_node.next = elem_node.next;
295 } else {
296 list.start = elem_node.next;
297 }
298
299 UT_LIST_REMOVE_CLEAR(elem_node);
300
301 --list.count;
302 }
303
304 /*******************************************************************//**
305 Removes a node from a two-way linked list.
306 aram NAME list name
307 @param LIST the base node (not a pointer to it)
308 @param ELEM node to be removed from the list */
309 #define UT_LIST_REMOVE(NAME, LIST, ELEM) \
310 ut_list_remove(LIST, *ELEM, IB_OFFSETOF(ELEM, NAME))
311
312 /********************************************************************//**
313 Gets the next node in a two-way list.
314 @param NAME list name
315 @param N pointer to a node
316 @return the successor of N in NAME, or NULL */
317 #define UT_LIST_GET_NEXT(NAME, N)\
318 (((N)->NAME).next)
319
320 /********************************************************************//**
321 Gets the previous node in a two-way list.
322 @param NAME list name
323 @param N pointer to a node
324 @return the predecessor of N in NAME, or NULL */
325 #define UT_LIST_GET_PREV(NAME, N)\
326 (((N)->NAME).prev)
327
328 /********************************************************************//**
329 Alternative macro to get the number of nodes in a two-way list, i.e.,
330 its length.
331 @param BASE the base node (not a pointer to it).
332 @return the number of nodes in the list */
333 #define UT_LIST_GET_LEN(BASE)\
334 (BASE).count
335
336 /********************************************************************//**
337 Gets the first node in a two-way list.
338 @param BASE the base node (not a pointer to it)
339 @return first node, or NULL if the list is empty */
340 #define UT_LIST_GET_FIRST(BASE)\
341 (BASE).start
342
343 /********************************************************************//**
344 Gets the last node in a two-way list.
345 @param BASE the base node (not a pointer to it)
346 @return last node, or NULL if the list is empty */
347 #define UT_LIST_GET_LAST(BASE)\
348 (BASE).end
349
operatorNullValidate350 struct NullValidate { void operator()(const void* elem) { } };
351
352 /********************************************************************//**
353 Iterate over all the elements and call the functor for each element.
354 @param list base node (not a pointer to it)
355 @param functor Functor that is called for each element in the list
356 @parm node pointer to member node within list element */
357 template <typename List, class Functor>
358 void
ut_list_map(List & list,ut_list_node<typename List::elem_type> List::elem_type::* node,Functor functor)359 ut_list_map(
360 List& list,
361 ut_list_node<typename List::elem_type>
362 List::elem_type::*node,
363 Functor functor)
364 {
365 ulint count = 0;
366
367 for (typename List::elem_type* elem = list.start;
368 elem != 0;
369 elem = (elem->*node).next, ++count) {
370
371 functor(elem);
372 }
373
374 ut_a(count == list.count);
375 }
376
377 /********************************************************************//**
378 Checks the consistency of a two-way list.
379 @param list base node (not a pointer to it)
380 @param functor Functor that is called for each element in the list
381 @parm node pointer to member node within list element */
382 template <typename List, class Functor>
383 void
384 ut_list_validate(
385 List& list,
386 ut_list_node<typename List::elem_type>
387 List::elem_type::*node,
388 Functor functor = NullValidate())
389 {
390 ut_list_map(list, node, functor);
391
392 ulint count = 0;
393
394 for (typename List::elem_type* elem = list.end;
395 elem != 0;
396 elem = (elem->*node).prev, ++count) {
397
398 functor(elem);
399 }
400
401 ut_a(count == list.count);
402 }
403
404 /********************************************************************//**
405 Checks the consistency of a two-way list.
406 @param NAME the name of the list
407 @param TYPE node type
408 @param LIST base node (not a pointer to it)
409 @param FUNCTOR called for each list element */
410 #define UT_LIST_VALIDATE(NAME, TYPE, LIST, FUNCTOR) \
411 ut_list_validate(LIST, &TYPE::NAME, FUNCTOR)
412
413 #define UT_LIST_CHECK(NAME, TYPE, LIST) \
414 ut_list_validate(LIST, &TYPE::NAME, NullValidate())
415
416 #endif /* ut0lst.h */
417