release/src/router/mysql/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.,
  15 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 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