00001 /* 00002 * Asterisk -- An open source telephony toolkit. 00003 * 00004 * Copyright (C) 1999 - 2006, Digium, Inc. 00005 * 00006 * Mark Spencer <markster@digium.com> 00007 * Kevin P. Fleming <kpfleming@digium.com> 00008 * 00009 * See http://www.asterisk.org for more information about 00010 * the Asterisk project. Please do not directly contact 00011 * any of the maintainers of this project for assistance; 00012 * the project provides a web site, mailing lists and IRC 00013 * channels for your use. 00014 * 00015 * This program is free software, distributed under the terms of 00016 * the GNU General Public License Version 2. See the LICENSE file 00017 * at the top of the source tree. 00018 */ 00019 00020 #ifndef ASTERISK_LINKEDLISTS_H 00021 #define ASTERISK_LINKEDLISTS_H 00022 00023 #include "asterisk/lock.h" 00024 00025 /*! 00026 \file linkedlists.h 00027 \brief A set of macros to manage forward-linked lists. 00028 */ 00029 00030 /*! 00031 \brief Attempts to lock a list. 00032 \param head This is a pointer to the list head structure 00033 00034 This macro attempts to place an exclusive lock in the 00035 list head structure pointed to by head. 00036 Returns non-zero on success, 0 on failure 00037 */ 00038 #define AST_LIST_LOCK(head) \ 00039 ast_mutex_lock(&(head)->lock) 00040 00041 /*! 00042 \brief Attempts to unlock a list. 00043 \param head This is a pointer to the list head structure 00044 00045 This macro attempts to remove an exclusive lock from the 00046 list head structure pointed to by head. If the list 00047 was not locked by this thread, this macro has no effect. 00048 */ 00049 #define AST_LIST_UNLOCK(head) \ 00050 ast_mutex_unlock(&(head)->lock) 00051 00052 /*! 00053 \brief Defines a structure to be used to hold a list of specified type. 00054 \param name This will be the name of the defined structure. 00055 \param type This is the type of each list entry. 00056 00057 This macro creates a structure definition that can be used 00058 to hold a list of the entries of type \a type. It does not actually 00059 declare (allocate) a structure; to do that, either follow this 00060 macro with the desired name of the instance you wish to declare, 00061 or use the specified \a name to declare instances elsewhere. 00062 00063 Example usage: 00064 \code 00065 static AST_LIST_HEAD(entry_list, entry) entries; 00066 \endcode 00067 00068 This would define \c struct \c entry_list, and declare an instance of it named 00069 \a entries, all intended to hold a list of type \c struct \c entry. 00070 */ 00071 #define AST_LIST_HEAD(name, type) \ 00072 struct name { \ 00073 struct type *first; \ 00074 struct type *last; \ 00075 ast_mutex_t lock; \ 00076 } 00077 00078 /*! 00079 \brief Defines a structure to be used to hold a list of specified type (with no lock). 00080 \param name This will be the name of the defined structure. 00081 \param type This is the type of each list entry. 00082 00083 This macro creates a structure definition that can be used 00084 to hold a list of the entries of type \a type. It does not actually 00085 declare (allocate) a structure; to do that, either follow this 00086 macro with the desired name of the instance you wish to declare, 00087 or use the specified \a name to declare instances elsewhere. 00088 00089 Example usage: 00090 \code 00091 static AST_LIST_HEAD_NOLOCK(entry_list, entry) entries; 00092 \endcode 00093 00094 This would define \c struct \c entry_list, and declare an instance of it named 00095 \a entries, all intended to hold a list of type \c struct \c entry. 00096 */ 00097 #define AST_LIST_HEAD_NOLOCK(name, type) \ 00098 struct name { \ 00099 struct type *first; \ 00100 struct type *last; \ 00101 } 00102 00103 /*! 00104 \brief Defines a structure to be used to hold a list of specified type, statically initialized. 00105 \param name This will be the name of the defined structure. 00106 \param type This is the type of each list entry. 00107 00108 This macro creates a structure definition that can be used 00109 to hold a list of the entries of type \a type, and allocates an instance 00110 of it, initialized to be empty. 00111 00112 Example usage: 00113 \code 00114 static AST_LIST_HEAD_STATIC(entry_list, entry); 00115 \endcode 00116 00117 This would define \c struct \c entry_list, intended to hold a list of 00118 type \c struct \c entry. 00119 */ 00120 #define AST_LIST_HEAD_STATIC(name, type) \ 00121 struct name { \ 00122 struct type *first; \ 00123 struct type *last; \ 00124 ast_mutex_t lock; \ 00125 } name = { \ 00126 .first = NULL, \ 00127 .last = NULL, \ 00128 .lock = AST_MUTEX_INIT_VALUE, \ 00129 }; 00130 00131 /*! 00132 \brief Initializes a list head structure with a specified first entry. 00133 \param head This is a pointer to the list head structure 00134 \param entry pointer to the list entry that will become the head of the list 00135 00136 This macro initializes a list head structure by setting the head 00137 entry to the supplied value and recreating the embedded lock. 00138 */ 00139 #define AST_LIST_HEAD_SET(head, entry) do { \ 00140 (head)->first = (entry); \ 00141 (head)->last = (entry); \ 00142 ast_mutex_init(&(head)->lock); \ 00143 } while (0) 00144 00145 /*! 00146 \brief Initializes a list head structure with a specified first entry. 00147 \param head This is a pointer to the list head structure 00148 \param entry pointer to the list entry that will become the head of the list 00149 00150 This macro initializes a list head structure by setting the head 00151 entry to the supplied value. 00152 */ 00153 #define AST_LIST_HEAD_SET_NOLOCK(head, entry) do { \ 00154 (head)->first = (entry); \ 00155 (head)->last = (entry); \ 00156 } while (0) 00157 00158 /*! 00159 \brief Declare a forward link structure inside a list entry. 00160 \param type This is the type of each list entry. 00161 00162 This macro declares a structure to be used to link list entries together. 00163 It must be used inside the definition of the structure named in 00164 \a type, as follows: 00165 00166 \code 00167 struct list_entry { 00168 ... 00169 AST_LIST_ENTRY(list_entry) list; 00170 } 00171 \endcode 00172 00173 The field name \a list here is arbitrary, and can be anything you wish. 00174 */ 00175 #define AST_LIST_ENTRY(type) \ 00176 struct { \ 00177 struct type *next; \ 00178 } 00179 00180 /*! 00181 \brief Returns the first entry contained in a list. 00182 \param head This is a pointer to the list head structure 00183 */ 00184 #define AST_LIST_FIRST(head) ((head)->first) 00185 00186 /*! 00187 \brief Returns the next entry in the list after the given entry. 00188 \param elm This is a pointer to the current entry. 00189 \param field This is the name of the field (declared using AST_LIST_ENTRY()) 00190 used to link entries of this list together. 00191 */ 00192 #define AST_LIST_NEXT(elm, field) ((elm)->field.next) 00193 00194 /*! 00195 \brief Checks whether the specified list contains any entries. 00196 \param head This is a pointer to the list head structure 00197 00198 Returns non-zero if the list has entries, zero if not. 00199 */ 00200 #define AST_LIST_EMPTY(head) (AST_LIST_FIRST(head) == NULL) 00201 00202 /*! 00203 \brief Loops over (traverses) the entries in a list. 00204 \param head This is a pointer to the list head structure 00205 \param var This is the name of the variable that will hold a pointer to the 00206 current list entry on each iteration. It must be declared before calling 00207 this macro. 00208 \param field This is the name of the field (declared using AST_LIST_ENTRY()) 00209 used to link entries of this list together. 00210 00211 This macro is use to loop over (traverse) the entries in a list. It uses a 00212 \a for loop, and supplies the enclosed code with a pointer to each list 00213 entry as it loops. It is typically used as follows: 00214 \code 00215 static AST_LIST_HEAD(entry_list, list_entry) entries; 00216 ... 00217 struct list_entry { 00218 ... 00219 AST_LIST_ENTRY(list_entry) list; 00220 } 00221 ... 00222 struct list_entry *current; 00223 ... 00224 AST_LIST_TRAVERSE(&entries, current, list) { 00225 (do something with current here) 00226 } 00227 \endcode 00228 \warning If you modify the forward-link pointer contained in the \a current entry while 00229 inside the loop, the behavior will be unpredictable. At a minimum, the following 00230 macros will modify the forward-link pointer, and should not be used inside 00231 AST_LIST_TRAVERSE() against the entry pointed to by the \a current pointer without 00232 careful consideration of their consequences: 00233 \li AST_LIST_NEXT() (when used as an lvalue) 00234 \li AST_LIST_INSERT_AFTER() 00235 \li AST_LIST_INSERT_HEAD() 00236 \li AST_LIST_INSERT_TAIL() 00237 */ 00238 #define AST_LIST_TRAVERSE(head,var,field) \ 00239 for((var) = (head)->first; (var); (var) = (var)->field.next) 00240 00241 /*! 00242 \brief Loops safely over (traverses) the entries in a list. 00243 \param head This is a pointer to the list head structure 00244 \param var This is the name of the variable that will hold a pointer to the 00245 current list entry on each iteration. It must be declared before calling 00246 this macro. 00247 \param field This is the name of the field (declared using AST_LIST_ENTRY()) 00248 used to link entries of this list together. 00249 00250 This macro is used to safely loop over (traverse) the entries in a list. It 00251 uses a \a for loop, and supplies the enclosed code with a pointer to each list 00252 entry as it loops. It is typically used as follows: 00253 00254 \code 00255 static AST_LIST_HEAD(entry_list, list_entry) entries; 00256 ... 00257 struct list_entry { 00258 ... 00259 AST_LIST_ENTRY(list_entry) list; 00260 } 00261 ... 00262 struct list_entry *current; 00263 ... 00264 AST_LIST_TRAVERSE_SAFE_BEGIN(&entries, current, list) { 00265 (do something with current here) 00266 } 00267 AST_LIST_TRAVERSE_SAFE_END; 00268 \endcode 00269 00270 It differs from AST_LIST_TRAVERSE() in that the code inside the loop can modify 00271 (or even free, after calling AST_LIST_REMOVE_CURRENT()) the entry pointed to by 00272 the \a current pointer without affecting the loop traversal. 00273 */ 00274 #define AST_LIST_TRAVERSE_SAFE_BEGIN(head, var, field) { \ 00275 typeof((head)->first) __list_next; \ 00276 typeof((head)->first) __list_prev = NULL; \ 00277 typeof((head)->first) __new_prev = NULL; \ 00278 for ((var) = (head)->first, __new_prev = (var), \ 00279 __list_next = (var) ? (var)->field.next : NULL; \ 00280 (var); \ 00281 __list_prev = __new_prev, (var) = __list_next, \ 00282 __new_prev = (var), \ 00283 __list_next = (var) ? (var)->field.next : NULL \ 00284 ) 00285 00286 /*! 00287 \brief Removes the \a current entry from a list during a traversal. 00288 \param head This is a pointer to the list head structure 00289 \param field This is the name of the field (declared using AST_LIST_ENTRY()) 00290 used to link entries of this list together. 00291 00292 \note This macro can \b only be used inside an AST_LIST_TRAVERSE_SAFE_BEGIN() 00293 block; it is used to unlink the current entry from the list without affecting 00294 the list traversal (and without having to re-traverse the list to modify the 00295 previous entry, if any). 00296 */ 00297 #define AST_LIST_REMOVE_CURRENT(head, field) \ 00298 __new_prev = __list_prev; \ 00299 if (__list_prev) \ 00300 __list_prev->field.next = __list_next; \ 00301 else \ 00302 (head)->first = __list_next; \ 00303 if (!__list_next) \ 00304 (head)->last = __list_prev; 00305 00306 /*! 00307 \brief Closes a safe loop traversal block. 00308 */ 00309 #define AST_LIST_TRAVERSE_SAFE_END } 00310 00311 /*! 00312 \brief Initializes a list head structure. 00313 \param head This is a pointer to the list head structure 00314 00315 This macro initializes a list head structure by setting the head 00316 entry to \a NULL (empty list) and recreating the embedded lock. 00317 */ 00318 #define AST_LIST_HEAD_INIT(head) { \ 00319 (head)->first = NULL; \ 00320 (head)->last = NULL; \ 00321 ast_mutex_init(&(head)->lock); \ 00322 } 00323 00324 /*! 00325 \brief Destroys a list head structure. 00326 \param head This is a pointer to the list head structure 00327 00328 This macro destroys a list head structure by setting the head 00329 entry to \a NULL (empty list) and destroying the embedded lock. 00330 It does not free the structure from memory. 00331 */ 00332 #define AST_LIST_HEAD_DESTROY(head) { \ 00333 (head)->first = NULL; \ 00334 (head)->last = NULL; \ 00335 ast_mutex_destroy(&(head)->lock); \ 00336 } 00337 00338 /*! 00339 \brief Initializes a list head structure. 00340 \param head This is a pointer to the list head structure 00341 00342 This macro initializes a list head structure by setting the head 00343 entry to \a NULL (empty list) and recreating the embedded lock. 00344 */ 00345 #define AST_LIST_HEAD_INIT_NOLOCK(head) { \ 00346 (head)->first = NULL; \ 00347 (head)->last = NULL; \ 00348 } 00349 00350 /*! 00351 \brief Inserts a list entry after a given entry. 00352 \param head This is a pointer to the list head structure 00353 \param listelm This is a pointer to the entry after which the new entry should 00354 be inserted. 00355 \param elm This is a pointer to the entry to be inserted. 00356 \param field This is the name of the field (declared using AST_LIST_ENTRY()) 00357 used to link entries of this list together. 00358 */ 00359 #define AST_LIST_INSERT_AFTER(head, listelm, elm, field) do { \ 00360 (elm)->field.next = (listelm)->field.next; \ 00361 (listelm)->field.next = (elm); \ 00362 if ((head)->last == (listelm)) \ 00363 (head)->last = (elm); \ 00364 } while (0) 00365 00366 /*! 00367 \brief Inserts a list entry at the head of a list. 00368 \param head This is a pointer to the list head structure 00369 \param elm This is a pointer to the entry to be inserted. 00370 \param field This is the name of the field (declared using AST_LIST_ENTRY()) 00371 used to link entries of this list together. 00372 */ 00373 #define AST_LIST_INSERT_HEAD(head, elm, field) do { \ 00374 (elm)->field.next = (head)->first; \ 00375 (head)->first = (elm); \ 00376 if (!(head)->last) \ 00377 (head)->last = (elm); \ 00378 } while (0) 00379 00380 /*! 00381 \brief Appends a list entry to the tail of a list. 00382 \param head This is a pointer to the list head structure 00383 \param elm This is a pointer to the entry to be appended. 00384 \param field This is the name of the field (declared using AST_LIST_ENTRY()) 00385 used to link entries of this list together. 00386 00387 Note: The link field in the appended entry is \b not modified, so if it is 00388 actually the head of a list itself, the entire list will be appended 00389 temporarily (until the next AST_LIST_INSERT_TAIL is performed). 00390 */ 00391 #define AST_LIST_INSERT_TAIL(head, elm, field) do { \ 00392 if (!(head)->first) { \ 00393 (head)->first = (elm); \ 00394 (head)->last = (elm); \ 00395 } else { \ 00396 (head)->last->field.next = (elm); \ 00397 (head)->last = (elm); \ 00398 } \ 00399 } while (0) 00400 00401 /*! 00402 \brief Removes and returns the head entry from a list. 00403 \param head This is a pointer to the list head structure 00404 \param field This is the name of the field (declared using AST_LIST_ENTRY()) 00405 used to link entries of this list together. 00406 00407 Removes the head entry from the list, and returns a pointer to it. 00408 This macro is safe to call on an empty list. 00409 */ 00410 #define AST_LIST_REMOVE_HEAD(head, field) ({ \ 00411 typeof((head)->first) cur = (head)->first; \ 00412 if (cur) { \ 00413 (head)->first = cur->field.next; \ 00414 cur->field.next = NULL; \ 00415 if ((head)->last == cur) \ 00416 (head)->last = NULL; \ 00417 } \ 00418 cur; \ 00419 }) 00420 00421 /*! 00422 \brief Removes a specific entry from a list. 00423 \param head This is a pointer to the list head structure 00424 \param elm This is a pointer to the entry to be removed. 00425 \param field This is the name of the field (declared using AST_LIST_ENTRY()) 00426 used to link entries of this list together. 00427 \warning The removed entry is \b not freed nor modified in any way. 00428 */ 00429 #define AST_LIST_REMOVE(head, elm, field) do { \ 00430 if ((head)->first == (elm)) { \ 00431 (head)->first = (elm)->field.next; \ 00432 if ((head)->last == (elm)) \ 00433 (head)->last = NULL; \ 00434 } else { \ 00435 typeof(elm) curelm = (head)->first; \ 00436 while (curelm->field.next != (elm)) \ 00437 curelm = curelm->field.next; \ 00438 curelm->field.next = (elm)->field.next; \ 00439 if ((head)->last == (elm)) \ 00440 (head)->last = curelm; \ 00441 } \ 00442 (elm)->field.next = NULL; \ 00443 } while (0) 00444 00445 #endif /* _ASTERISK_LINKEDLISTS_H */