1 /***************************************************************************** 2 3 Copyright (c) 2006, 2009, 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/ut0list.h 29 A double-linked list 30 31 Created 4/26/2006 Osku Salerma 32 ************************************************************************/ 33 34 /*******************************************************************//** 35 A double-linked list. This differs from the one in ut0lst.h in that in this 36 one, each list node contains a pointer to the data, whereas the one in 37 ut0lst.h uses a strategy where the list pointers are embedded in the data 38 items themselves. 39 40 Use this one when you need to store arbitrary data in the list where you 41 can't embed the list pointers in the data, if a data item needs to be 42 stored in multiple lists, etc. 43 44 Note about the memory management: ib_list_t is a fixed-size struct whose 45 allocation/deallocation is done through ib_list_create/ib_list_free, but the 46 memory for the list nodes is allocated through a user-given memory heap, 47 which can either be the same for all nodes or vary per node. Most users will 48 probably want to create a memory heap to store the item-specific data, and 49 pass in this same heap to the list node creation functions, thus 50 automatically freeing the list node when the item's heap is freed. 51 52 ************************************************************************/ 53 54 #ifndef IB_LIST_H 55 #define IB_LIST_H 56 57 #include "mem0mem.h" 58 59 struct ib_list_t; 60 struct ib_list_node_t; 61 62 /****************************************************************//** 63 Create a new list using mem_alloc. Lists created with this function must be 64 freed with ib_list_free. 65 @return list */ 66 UNIV_INTERN 67 ib_list_t* 68 ib_list_create(void); 69 /*=================*/ 70 71 72 /****************************************************************//** 73 Create a new list using the given heap. ib_list_free MUST NOT BE CALLED for 74 lists created with this function. 75 @return list */ 76 UNIV_INTERN 77 ib_list_t* 78 ib_list_create_heap( 79 /*================*/ 80 mem_heap_t* heap); /*!< in: memory heap to use */ 81 82 /****************************************************************//** 83 Free a list. */ 84 UNIV_INTERN 85 void 86 ib_list_free( 87 /*=========*/ 88 ib_list_t* list); /*!< in: list */ 89 90 /****************************************************************//** 91 Add the data to the start of the list. 92 @return new list node */ 93 UNIV_INTERN 94 ib_list_node_t* 95 ib_list_add_first( 96 /*==============*/ 97 ib_list_t* list, /*!< in: list */ 98 void* data, /*!< in: data */ 99 mem_heap_t* heap); /*!< in: memory heap to use */ 100 101 /****************************************************************//** 102 Add the data to the end of the list. 103 @return new list node */ 104 UNIV_INTERN 105 ib_list_node_t* 106 ib_list_add_last( 107 /*=============*/ 108 ib_list_t* list, /*!< in: list */ 109 void* data, /*!< in: data */ 110 mem_heap_t* heap); /*!< in: memory heap to use */ 111 112 /****************************************************************//** 113 Add the data after the indicated node. 114 @return new list node */ 115 UNIV_INTERN 116 ib_list_node_t* 117 ib_list_add_after( 118 /*==============*/ 119 ib_list_t* list, /*!< in: list */ 120 ib_list_node_t* prev_node, /*!< in: node preceding new node (can 121 be NULL) */ 122 void* data, /*!< in: data */ 123 mem_heap_t* heap); /*!< in: memory heap to use */ 124 125 /****************************************************************//** 126 Remove the node from the list. */ 127 UNIV_INTERN 128 void 129 ib_list_remove( 130 /*===========*/ 131 ib_list_t* list, /*!< in: list */ 132 ib_list_node_t* node); /*!< in: node to remove */ 133 134 /****************************************************************//** 135 Get the first node in the list. 136 @return first node, or NULL */ 137 UNIV_INLINE 138 ib_list_node_t* 139 ib_list_get_first( 140 /*==============*/ 141 ib_list_t* list); /*!< in: list */ 142 143 /****************************************************************//** 144 Get the last node in the list. 145 @return last node, or NULL */ 146 UNIV_INLINE 147 ib_list_node_t* 148 ib_list_get_last( 149 /*=============*/ 150 ib_list_t* list); /*!< in: list */ 151 152 /******************************************************************** 153 Check if list is empty. */ 154 UNIV_INLINE 155 ibool 156 ib_list_is_empty( 157 /*=============*/ 158 /* out: TRUE if empty else */ 159 const ib_list_t* list); /* in: list */ 160 161 /* List. */ 162 struct ib_list_t { 163 ib_list_node_t* first; /*!< first node */ 164 ib_list_node_t* last; /*!< last node */ 165 ibool is_heap_list; /*!< TRUE if this list was 166 allocated through a heap */ 167 }; 168 169 /* A list node. */ 170 struct ib_list_node_t { 171 ib_list_node_t* prev; /*!< previous node */ 172 ib_list_node_t* next; /*!< next node */ 173 void* data; /*!< user data */ 174 }; 175 176 /* Quite often, the only additional piece of data you need is the per-item 177 memory heap, so we have this generic struct available to use in those 178 cases. */ 179 struct ib_list_helper_t { 180 mem_heap_t* heap; /*!< memory heap */ 181 void* data; /*!< user data */ 182 }; 183 184 #ifndef UNIV_NONINL 185 #include "ut0list.ic" 186 #endif 187 188 #endif 189