The world's most popular open source database
mysql/src/5.1-dbg/storage/innobase/include/ut0lst.h
Go to the documentation of this file.00001 /********************************************************************** 00002 List utilities 00003 00004 (c) 1995 Innobase Oy 00005 00006 Created 9/10/1995 Heikki Tuuri 00007 ***********************************************************************/ 00008 00009 #ifndef ut0lst_h 00010 #define ut0lst_h 00011 00012 #include "univ.i" 00013 00014 /* This module implements the two-way linear list which should be used 00015 if a list is used in the database. Note that a single struct may belong 00016 to two or more lists, provided that the list are given different names. 00017 An example of the usage of the lists can be found in fil0fil.c. */ 00018 00019 /*********************************************************************** 00020 This macro expands to the unnamed type definition of a struct which acts 00021 as the two-way list base node. The base node contains pointers 00022 to both ends of the list and a count of nodes in the list (excluding 00023 the base node from the count). TYPE should be the list node type name. */ 00024 00025 #define UT_LIST_BASE_NODE_T(TYPE)\ 00026 struct {\ 00027 ulint count; /* count of nodes in list */\ 00028 TYPE * start; /* pointer to list start, NULL if empty */\ 00029 TYPE * end; /* pointer to list end, NULL if empty */\ 00030 }\ 00031 00032 /*********************************************************************** 00033 This macro expands to the unnamed type definition of a struct which 00034 should be embedded in the nodes of the list, the node type must be a struct. 00035 This struct contains the pointers to next and previous nodes in the list. 00036 The name of the field in the node struct should be the name given 00037 to the list. TYPE should be the list node type name. Example of usage: 00038 00039 typedef struct LRU_node_struct LRU_node_t; 00040 struct LRU_node_struct { 00041 UT_LIST_NODE_T(LRU_node_t) LRU_list; 00042 ... 00043 } 00044 The example implements an LRU list of name LRU_list. Its nodes are of type 00045 LRU_node_t. 00046 */ 00047 00048 #define UT_LIST_NODE_T(TYPE)\ 00049 struct {\ 00050 TYPE * prev; /* pointer to the previous node,\ 00051 NULL if start of list */\ 00052 TYPE * next; /* pointer to next node, NULL if end of list */\ 00053 }\ 00054 00055 /*********************************************************************** 00056 Initializes the base node of a two-way list. */ 00057 00058 #define UT_LIST_INIT(BASE)\ 00059 {\ 00060 (BASE).count = 0;\ 00061 (BASE).start = NULL;\ 00062 (BASE).end = NULL;\ 00063 }\ 00064 00065 /*********************************************************************** 00066 Adds the node as the first element in a two-way linked list. 00067 BASE has to be the base node (not a pointer to it). N has to be 00068 the pointer to the node to be added to the list. NAME is the list name. */ 00069 00070 #define UT_LIST_ADD_FIRST(NAME, BASE, N)\ 00071 {\ 00072 ut_ad(N);\ 00073 ((BASE).count)++;\ 00074 ((N)->NAME).next = (BASE).start;\ 00075 ((N)->NAME).prev = NULL;\ 00076 if ((BASE).start != NULL) {\ 00077 (((BASE).start)->NAME).prev = (N);\ 00078 }\ 00079 (BASE).start = (N);\ 00080 if ((BASE).end == NULL) {\ 00081 (BASE).end = (N);\ 00082 }\ 00083 }\ 00084 00085 /*********************************************************************** 00086 Adds the node as the last element in a two-way linked list. 00087 BASE has to be the base node (not a pointer to it). N has to be 00088 the pointer to the node to be added to the list. NAME is the list name. */ 00089 00090 #define UT_LIST_ADD_LAST(NAME, BASE, N)\ 00091 {\ 00092 ut_ad(N);\ 00093 ((BASE).count)++;\ 00094 ((N)->NAME).prev = (BASE).end;\ 00095 ((N)->NAME).next = NULL;\ 00096 if ((BASE).end != NULL) {\ 00097 (((BASE).end)->NAME).next = (N);\ 00098 }\ 00099 (BASE).end = (N);\ 00100 if ((BASE).start == NULL) {\ 00101 (BASE).start = (N);\ 00102 }\ 00103 }\ 00104 00105 /*********************************************************************** 00106 Inserts a NODE2 after NODE1 in a list. 00107 BASE has to be the base node (not a pointer to it). NAME is the list 00108 name, NODE1 and NODE2 are pointers to nodes. */ 00109 00110 #define UT_LIST_INSERT_AFTER(NAME, BASE, NODE1, NODE2)\ 00111 {\ 00112 ut_ad(NODE1);\ 00113 ut_ad(NODE2);\ 00114 ((BASE).count)++;\ 00115 ((NODE2)->NAME).prev = (NODE1);\ 00116 ((NODE2)->NAME).next = ((NODE1)->NAME).next;\ 00117 if (((NODE1)->NAME).next != NULL) {\ 00118 ((((NODE1)->NAME).next)->NAME).prev = (NODE2);\ 00119 }\ 00120 ((NODE1)->NAME).next = (NODE2);\ 00121 if ((BASE).end == (NODE1)) {\ 00122 (BASE).end = (NODE2);\ 00123 }\ 00124 }\ 00125 00126 /*********************************************************************** 00127 Removes a node from a two-way linked list. BASE has to be the base node 00128 (not a pointer to it). N has to be the pointer to the node to be removed 00129 from the list. NAME is the list name. */ 00130 00131 #define UT_LIST_REMOVE(NAME, BASE, N)\ 00132 {\ 00133 ut_ad(N);\ 00134 ut_a((BASE).count > 0);\ 00135 ((BASE).count)--;\ 00136 if (((N)->NAME).next != NULL) {\ 00137 ((((N)->NAME).next)->NAME).prev = ((N)->NAME).prev;\ 00138 } else {\ 00139 (BASE).end = ((N)->NAME).prev;\ 00140 }\ 00141 if (((N)->NAME).prev != NULL) {\ 00142 ((((N)->NAME).prev)->NAME).next = ((N)->NAME).next;\ 00143 } else {\ 00144 (BASE).start = ((N)->NAME).next;\ 00145 }\ 00146 }\ 00147 00148 /************************************************************************ 00149 Gets the next node in a two-way list. NAME is the name of the list 00150 and N is pointer to a node. */ 00151 00152 #define UT_LIST_GET_NEXT(NAME, N)\ 00153 (((N)->NAME).next) 00154 00155 /************************************************************************ 00156 Gets the previous node in a two-way list. NAME is the name of the list 00157 and N is pointer to a node. */ 00158 00159 #define UT_LIST_GET_PREV(NAME, N)\ 00160 (((N)->NAME).prev) 00161 00162 /************************************************************************ 00163 Alternative macro to get the number of nodes in a two-way list, i.e., 00164 its length. BASE is the base node (not a pointer to it). */ 00165 00166 #define UT_LIST_GET_LEN(BASE)\ 00167 (BASE).count 00168 00169 /************************************************************************ 00170 Gets the first node in a two-way list, or returns NULL, 00171 if the list is empty. BASE is the base node (not a pointer to it). */ 00172 00173 #define UT_LIST_GET_FIRST(BASE)\ 00174 (BASE).start 00175 00176 /************************************************************************ 00177 Gets the last node in a two-way list, or returns NULL, 00178 if the list is empty. BASE is the base node (not a pointer to it). */ 00179 00180 #define UT_LIST_GET_LAST(BASE)\ 00181 (BASE).end 00182 00183 /************************************************************************ 00184 Checks the consistency of a two-way list. NAME is the name of the list, 00185 TYPE is the node type, and BASE is the base node (not a pointer to it). */ 00186 00187 #define UT_LIST_VALIDATE(NAME, TYPE, BASE)\ 00188 {\ 00189 ulint ut_list_i_313;\ 00190 TYPE * ut_list_node_313;\ 00191 \ 00192 ut_list_node_313 = (BASE).start;\ 00193 \ 00194 for (ut_list_i_313 = 0; ut_list_i_313 < (BASE).count;\ 00195 ut_list_i_313++) {\ 00196 ut_a(ut_list_node_313);\ 00197 ut_list_node_313 = (ut_list_node_313->NAME).next;\ 00198 }\ 00199 \ 00200 ut_a(ut_list_node_313 == NULL);\ 00201 \ 00202 ut_list_node_313 = (BASE).end;\ 00203 \ 00204 for (ut_list_i_313 = 0; ut_list_i_313 < (BASE).count;\ 00205 ut_list_i_313++) {\ 00206 ut_a(ut_list_node_313);\ 00207 ut_list_node_313 = (ut_list_node_313->NAME).prev;\ 00208 }\ 00209 \ 00210 ut_a(ut_list_node_313 == NULL);\ 00211 }\ 00212 00213 00214 #endif 00215
Generated on Sat Sep 9 00:50:27 2006 for MySQL 5.1 by
1.4.7
© 1995-2008 MySQL AB, 2008- Sun Microsystems, Inc.