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 Locks 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 \retval 0 on success 00037 \retval non-zero on failure 00038 */ 00039 #define AST_LIST_LOCK(head) \ 00040 ast_mutex_lock(&(head)->lock) 00041 00042 /*! 00043 \brief Write locks a list. 00044 \param head This is a pointer to the list head structure 00045 00046 This macro attempts to place an exclusive write lock in the 00047 list head structure pointed to by head. 00048 \retval 0 on success 00049 \retval non-zero on failure 00050 */ 00051 #define AST_RWLIST_WRLOCK(head) \ 00052 ast_rwlock_wrlock(&(head)->lock) 00053 00054 /*! 00055 \brief Write locks a list, with timeout. 00056 \param head This is a pointer to the list head structure 00057 \param tv Pointer to a timeval structure 00058 00059 This macro attempts to place an exclusive write lock in the 00060 list head structure pointed to by head. 00061 \retval 0 on success 00062 \retval non-zero on failure 00063 */ 00064 #define AST_RWLIST_TIMEDWRLOCK(head,tv) ast_rwlock_timedwrlock(&(head)->lock, tv) 00065 00066 /*! 00067 \brief Read locks a list. 00068 \param head This is a pointer to the list head structure 00069 00070 This macro attempts to place a read lock in the 00071 list head structure pointed to by head. 00072 \retval 0 on success 00073 \retval non-zero on failure 00074 */ 00075 #define AST_RWLIST_RDLOCK(head) \ 00076 ast_rwlock_rdlock(&(head)->lock) 00077 00078 /*! 00079 \brief Read locks a list, with timeout. 00080 \param head This is a pointer to the list head structure 00081 \param tv Pointer to a timeval structure 00082 00083 This macro attempts to place a read lock in the 00084 list head structure pointed to by head. 00085 \retval 0 on success 00086 \retval non-zero on failure 00087 */ 00088 #define AST_RWLIST_TIMEDRDLOCK(head,tv) \ 00089 ast_rwlock_timedrdlock(&(head)->lock, tv) 00090 00091 /*! 00092 \brief Locks a list, without blocking if the list is locked. 00093 \param head This is a pointer to the list head structure 00094 00095 This macro attempts to place an exclusive lock in the 00096 list head structure pointed to by head. 00097 \retval 0 on success 00098 \retval non-zero on failure 00099 */ 00100 #define AST_LIST_TRYLOCK(head) \ 00101 ast_mutex_trylock(&(head)->lock) 00102 00103 /*! 00104 \brief Write locks a list, without blocking if the list is locked. 00105 \param head This is a pointer to the list head structure 00106 00107 This macro attempts to place an exclusive write lock in the 00108 list head structure pointed to by head. 00109 \retval 0 on success 00110 \retval non-zero on failure 00111 */ 00112 #define AST_RWLIST_TRYWRLOCK(head) \ 00113 ast_rwlock_trywrlock(&(head)->lock) 00114 00115 /*! 00116 \brief Read locks a list, without blocking if the list is locked. 00117 \param head This is a pointer to the list head structure 00118 00119 This macro attempts to place a read lock in the 00120 list head structure pointed to by head. 00121 \retval 0 on success 00122 \retval non-zero on failure 00123 */ 00124 #define AST_RWLIST_TRYRDLOCK(head) \ 00125 ast_rwlock_tryrdlock(&(head)->lock) 00126 00127 /*! 00128 \brief Attempts to unlock a list. 00129 \param head This is a pointer to the list head structure 00130 00131 This macro attempts to remove an exclusive lock from the 00132 list head structure pointed to by head. If the list 00133 was not locked by this thread, this macro has no effect. 00134 */ 00135 #define AST_LIST_UNLOCK(head) \ 00136 ast_mutex_unlock(&(head)->lock) 00137 00138 /*! 00139 \brief Attempts to unlock a read/write based list. 00140 \param head This is a pointer to the list head structure 00141 00142 This macro attempts to remove a read or write lock from the 00143 list head structure pointed to by head. If the list 00144 was not locked by this thread, this macro has no effect. 00145 */ 00146 #define AST_RWLIST_UNLOCK(head) \ 00147 ast_rwlock_unlock(&(head)->lock) 00148 00149 /*! 00150 \brief Defines a structure to be used to hold a list of specified type. 00151 \param name This will be the name of the defined structure. 00152 \param type This is the type of each list entry. 00153 00154 This macro creates a structure definition that can be used 00155 to hold a list of the entries of type \a type. It does not actually 00156 declare (allocate) a structure; to do that, either follow this 00157 macro with the desired name of the instance you wish to declare, 00158 or use the specified \a name to declare instances elsewhere. 00159 00160 Example usage: 00161 \code 00162 static AST_LIST_HEAD(entry_list, entry) entries; 00163 \endcode 00164 00165 This would define \c struct \c entry_list, and declare an instance of it named 00166 \a entries, all intended to hold a list of type \c struct \c entry. 00167 */ 00168 #define AST_LIST_HEAD(name, type) \ 00169 struct name { \ 00170 struct type *first; \ 00171 struct type *last; \ 00172 ast_mutex_t lock; \ 00173 } 00174 00175 /*! 00176 \brief Defines a structure to be used to hold a read/write list of specified type. 00177 \param name This will be the name of the defined structure. 00178 \param type This is the type of each list entry. 00179 00180 This macro creates a structure definition that can be used 00181 to hold a list of the entries of type \a type. It does not actually 00182 declare (allocate) a structure; to do that, either follow this 00183 macro with the desired name of the instance you wish to declare, 00184 or use the specified \a name to declare instances elsewhere. 00185 00186 Example usage: 00187 \code 00188 static AST_RWLIST_HEAD(entry_list, entry) entries; 00189 \endcode 00190 00191 This would define \c struct \c entry_list, and declare an instance of it named 00192 \a entries, all intended to hold a list of type \c struct \c entry. 00193 */ 00194 #define AST_RWLIST_HEAD(name, type) \ 00195 struct name { \ 00196 struct type *first; \ 00197 struct type *last; \ 00198 ast_rwlock_t lock; \ 00199 } 00200 00201 /*! 00202 \brief Defines a structure to be used to hold a list of specified type (with no lock). 00203 \param name This will be the name of the defined structure. 00204 \param type This is the type of each list entry. 00205 00206 This macro creates a structure definition that can be used 00207 to hold a list of the entries of type \a type. It does not actually 00208 declare (allocate) a structure; to do that, either follow this 00209 macro with the desired name of the instance you wish to declare, 00210 or use the specified \a name to declare instances elsewhere. 00211 00212 Example usage: 00213 \code 00214 static AST_LIST_HEAD_NOLOCK(entry_list, entry) entries; 00215 \endcode 00216 00217 This would define \c struct \c entry_list, and declare an instance of it named 00218 \a entries, all intended to hold a list of type \c struct \c entry. 00219 */ 00220 #define AST_LIST_HEAD_NOLOCK(name, type) \ 00221 struct name { \ 00222 struct type *first; \ 00223 struct type *last; \ 00224 } 00225 00226 /*! 00227 \brief Defines initial values for a declaration of AST_LIST_HEAD 00228 */ 00229 #define AST_LIST_HEAD_INIT_VALUE { \ 00230 .first = NULL, \ 00231 .last = NULL, \ 00232 .lock = AST_MUTEX_INIT_VALUE, \ 00233 } 00234 00235 /*! 00236 \brief Defines initial values for a declaration of AST_RWLIST_HEAD 00237 */ 00238 #define AST_RWLIST_HEAD_INIT_VALUE { \ 00239 .first = NULL, \ 00240 .last = NULL, \ 00241 .lock = AST_RWLOCK_INIT_VALUE, \ 00242 } 00243 00244 /*! 00245 \brief Defines initial values for a declaration of AST_LIST_HEAD_NOLOCK 00246 */ 00247 #define AST_LIST_HEAD_NOLOCK_INIT_VALUE { \ 00248 .first = NULL, \ 00249 .last = NULL, \ 00250 } 00251 00252 /*! 00253 \brief Defines a structure to be used to hold a list of specified type, statically initialized. 00254 \param name This will be the name of the defined structure. 00255 \param type This is the type of each list entry. 00256 00257 This macro creates a structure definition that can be used 00258 to hold a list of the entries of type \a type, and allocates an instance 00259 of it, initialized to be empty. 00260 00261 Example usage: 00262 \code 00263 static AST_LIST_HEAD_STATIC(entry_list, entry); 00264 \endcode 00265 00266 This would define \c struct \c entry_list, intended to hold a list of 00267 type \c struct \c entry. 00268 */ 00269 #if defined(AST_MUTEX_INIT_W_CONSTRUCTORS) 00270 #define AST_LIST_HEAD_STATIC(name, type) \ 00271 struct name { \ 00272 struct type *first; \ 00273 struct type *last; \ 00274 ast_mutex_t lock; \ 00275 } name; \ 00276 static void __attribute__((constructor)) __init_##name(void) \ 00277 { \ 00278 AST_LIST_HEAD_INIT(&name); \ 00279 } \ 00280 static void __attribute__((destructor)) __fini_##name(void) \ 00281 { \ 00282 AST_LIST_HEAD_DESTROY(&name); \ 00283 } \ 00284 struct __dummy_##name 00285 #else 00286 #define AST_LIST_HEAD_STATIC(name, type) \ 00287 struct name { \ 00288 struct type *first; \ 00289 struct type *last; \ 00290 ast_mutex_t lock; \ 00291 } name = AST_LIST_HEAD_INIT_VALUE 00292 #endif 00293 00294 /*! 00295 \brief Defines a structure to be used to hold a read/write list of specified type, statically initialized. 00296 \param name This will be the name of the defined structure. 00297 \param type This is the type of each list entry. 00298 00299 This macro creates a structure definition that can be used 00300 to hold a list of the entries of type \a type, and allocates an instance 00301 of it, initialized to be empty. 00302 00303 Example usage: 00304 \code 00305 static AST_RWLIST_HEAD_STATIC(entry_list, entry); 00306 \endcode 00307 00308 This would define \c struct \c entry_list, intended to hold a list of 00309 type \c struct \c entry. 00310 */ 00311 #ifndef HAVE_PTHREAD_RWLOCK_INITIALIZER 00312 #define AST_RWLIST_HEAD_STATIC(name, type) \ 00313 struct name { \ 00314 struct type *first; \ 00315 struct type *last; \ 00316 ast_rwlock_t lock; \ 00317 } name; \ 00318 static void __attribute__((constructor)) __init_##name(void) \ 00319 { \ 00320 AST_RWLIST_HEAD_INIT(&name); \ 00321 } \ 00322 static void __attribute__((destructor)) __fini_##name(void) \ 00323 { \ 00324 AST_RWLIST_HEAD_DESTROY(&name); \ 00325 } \ 00326 struct __dummy_##name 00327 #else 00328 #define AST_RWLIST_HEAD_STATIC(name, type) \ 00329 struct name { \ 00330 struct type *first; \ 00331 struct type *last; \ 00332 ast_rwlock_t lock; \ 00333 } name = AST_RWLIST_HEAD_INIT_VALUE 00334 #endif 00335 00336 /*! 00337 \brief Defines a structure to be used to hold a list of specified type, statically initialized. 00338 00339 This is the same as AST_LIST_HEAD_STATIC, except without the lock included. 00340 */ 00341 #define AST_LIST_HEAD_NOLOCK_STATIC(name, type) \ 00342 struct name { \ 00343 struct type *first; \ 00344 struct type *last; \ 00345 } name = AST_LIST_HEAD_NOLOCK_INIT_VALUE 00346 00347 /*! 00348 \brief Initializes a list head structure with a specified first entry. 00349 \param head This is a pointer to the list head structure 00350 \param entry pointer to the list entry that will become the head of the list 00351 00352 This macro initializes a list head structure by setting the head 00353 entry to the supplied value and recreating the embedded lock. 00354 */ 00355 #define AST_LIST_HEAD_SET(head, entry) do { \ 00356 (head)->first = (entry); \ 00357 (head)->last = (entry); \ 00358 ast_mutex_init(&(head)->lock); \ 00359 } while (0) 00360 00361 /*! 00362 \brief Initializes an rwlist head structure with a specified first entry. 00363 \param head This is a pointer to the list head structure 00364 \param entry pointer to the list entry that will become the head of the list 00365 00366 This macro initializes a list head structure by setting the head 00367 entry to the supplied value and recreating the embedded lock. 00368 */ 00369 #define AST_RWLIST_HEAD_SET(head, entry) do { \ 00370 (head)->first = (entry); \ 00371 (head)->last = (entry); \ 00372 ast_rwlock_init(&(head)->lock); \ 00373 } while (0) 00374 00375 /*! 00376 \brief Initializes a list head structure with a specified first entry. 00377 \param head This is a pointer to the list head structure 00378 \param entry pointer to the list entry that will become the head of the list 00379 00380 This macro initializes a list head structure by setting the head 00381 entry to the supplied value. 00382 */ 00383 #define AST_LIST_HEAD_SET_NOLOCK(head, entry) do { \ 00384 (head)->first = (entry); \ 00385 (head)->last = (entry); \ 00386 } while (0) 00387 00388 /*! 00389 \brief Declare a forward link structure inside a list entry. 00390 \param type This is the type of each list entry. 00391 00392 This macro declares a structure to be used to link list entries together. 00393 It must be used inside the definition of the structure named in 00394 \a type, as follows: 00395 00396 \code 00397 struct list_entry { 00398 ... 00399 AST_LIST_ENTRY(list_entry) list; 00400 } 00401 \endcode 00402 00403 The field name \a list here is arbitrary, and can be anything you wish. 00404 */ 00405 #define AST_LIST_ENTRY(type) \ 00406 struct { \ 00407 struct type *next; \ 00408 } 00409 00410 #define AST_RWLIST_ENTRY AST_LIST_ENTRY 00411 00412 /*! 00413 \brief Returns the first entry contained in a list. 00414 \param head This is a pointer to the list head structure 00415 */ 00416 #define AST_LIST_FIRST(head) ((head)->first) 00417 00418 #define AST_RWLIST_FIRST AST_LIST_FIRST 00419 00420 /*! 00421 \brief Returns the last entry contained in a list. 00422 \param head This is a pointer to the list head structure 00423 */ 00424 #define AST_LIST_LAST(head) ((head)->last) 00425 00426 #define AST_RWLIST_LAST AST_LIST_LAST 00427 00428 /*! 00429 \brief Returns the next entry in the list after the given entry. 00430 \param elm This is a pointer to the current entry. 00431 \param field This is the name of the field (declared using AST_LIST_ENTRY()) 00432 used to link entries of this list together. 00433 */ 00434 #define AST_LIST_NEXT(elm, field) ((elm)->field.next) 00435 00436 #define AST_RWLIST_NEXT AST_LIST_NEXT 00437 00438 /*! 00439 \brief Checks whether the specified list contains any entries. 00440 \param head This is a pointer to the list head structure 00441 00442 \return non-zero if the list has entries 00443 \return zero if not. 00444 */ 00445 #define AST_LIST_EMPTY(head) (AST_LIST_FIRST(head) == NULL) 00446 00447 #define AST_RWLIST_EMPTY AST_LIST_EMPTY 00448 00449 /*! 00450 \brief Loops over (traverses) the entries in a list. 00451 \param head This is a pointer to the list head structure 00452 \param var This is the name of the variable that will hold a pointer to the 00453 current list entry on each iteration. It must be declared before calling 00454 this macro. 00455 \param field This is the name of the field (declared using AST_LIST_ENTRY()) 00456 used to link entries of this list together. 00457 00458 This macro is use to loop over (traverse) the entries in a list. It uses a 00459 \a for loop, and supplies the enclosed code with a pointer to each list 00460 entry as it loops. It is typically used as follows: 00461 \code 00462 static AST_LIST_HEAD(entry_list, list_entry) entries; 00463 ... 00464 struct list_entry { 00465 ... 00466 AST_LIST_ENTRY(list_entry) list; 00467 } 00468 ... 00469 struct list_entry *current; 00470 ... 00471 AST_LIST_TRAVERSE(&entries, current, list) { 00472 (do something with current here) 00473 } 00474 \endcode 00475 \warning If you modify the forward-link pointer contained in the \a current entry while 00476 inside the loop, the behavior will be unpredictable. At a minimum, the following 00477 macros will modify the forward-link pointer, and should not be used inside 00478 AST_LIST_TRAVERSE() against the entry pointed to by the \a current pointer without 00479 careful consideration of their consequences: 00480 \li AST_LIST_NEXT() (when used as an lvalue) 00481 \li AST_LIST_INSERT_AFTER() 00482 \li AST_LIST_INSERT_HEAD() 00483 \li AST_LIST_INSERT_TAIL() 00484 */ 00485 #define AST_LIST_TRAVERSE(head,var,field) \ 00486 for((var) = (head)->first; (var); (var) = (var)->field.next) 00487 00488 #define AST_RWLIST_TRAVERSE AST_LIST_TRAVERSE 00489 00490 /*! 00491 \brief Loops safely over (traverses) the entries in a list. 00492 \param head This is a pointer to the list head structure 00493 \param var This is the name of the variable that will hold a pointer to the 00494 current list entry on each iteration. It must be declared before calling 00495 this macro. 00496 \param field This is the name of the field (declared using AST_LIST_ENTRY()) 00497 used to link entries of this list together. 00498 00499 This macro is used to safely loop over (traverse) the entries in a list. It 00500 uses a \a for loop, and supplies the enclosed code with a pointer to each list 00501 entry as it loops. It is typically used as follows: 00502 00503 \code 00504 static AST_LIST_HEAD(entry_list, list_entry) entries; 00505 ... 00506 struct list_entry { 00507 ... 00508 AST_LIST_ENTRY(list_entry) list; 00509 } 00510 ... 00511 struct list_entry *current; 00512 ... 00513 AST_LIST_TRAVERSE_SAFE_BEGIN(&entries, current, list) { 00514 (do something with current here) 00515 } 00516 AST_LIST_TRAVERSE_SAFE_END; 00517 \endcode 00518 00519 It differs from AST_LIST_TRAVERSE() in that the code inside the loop can modify 00520 (or even free, after calling AST_LIST_REMOVE_CURRENT()) the entry pointed to by 00521 the \a current pointer without affecting the loop traversal. 00522 */ 00523 #define AST_LIST_TRAVERSE_SAFE_BEGIN(head, var, field) { \ 00524 typeof((head)) __list_head = head; \ 00525 typeof(__list_head->first) __list_next; \ 00526 typeof(__list_head->first) __list_prev = NULL; \ 00527 typeof(__list_head->first) __new_prev = NULL; \ 00528 for ((var) = __list_head->first, __new_prev = (var), \ 00529 __list_next = (var) ? (var)->field.next : NULL; \ 00530 (var); \ 00531 __list_prev = __new_prev, (var) = __list_next, \ 00532 __new_prev = (var), \ 00533 __list_next = (var) ? (var)->field.next : NULL \ 00534 ) 00535 00536 #define AST_RWLIST_TRAVERSE_SAFE_BEGIN AST_LIST_TRAVERSE_SAFE_BEGIN 00537 00538 /*! 00539 \brief Removes the \a current entry from a list during a traversal. 00540 \param field This is the name of the field (declared using AST_LIST_ENTRY()) 00541 used to link entries of this list together. 00542 00543 \note This macro can \b only be used inside an AST_LIST_TRAVERSE_SAFE_BEGIN() 00544 block; it is used to unlink the current entry from the list without affecting 00545 the list traversal (and without having to re-traverse the list to modify the 00546 previous entry, if any). 00547 */ 00548 #define AST_LIST_REMOVE_CURRENT(field) do { \ 00549 __new_prev->field.next = NULL; \ 00550 __new_prev = __list_prev; \ 00551 if (__list_prev) \ 00552 __list_prev->field.next = __list_next; \ 00553 else \ 00554 __list_head->first = __list_next; \ 00555 if (!__list_next) \ 00556 __list_head->last = __list_prev; \ 00557 } while (0) 00558 00559 #define AST_RWLIST_REMOVE_CURRENT AST_LIST_REMOVE_CURRENT 00560 00561 #define AST_LIST_MOVE_CURRENT(newhead, field) do { \ 00562 typeof ((newhead)->first) __list_cur = __new_prev; \ 00563 AST_LIST_REMOVE_CURRENT(field); \ 00564 AST_LIST_INSERT_TAIL((newhead), __list_cur, field); \ 00565 } while (0) 00566 00567 #define AST_RWLIST_MOVE_CURRENT AST_LIST_MOVE_CURRENT 00568 00569 /*! 00570 \brief Inserts a list entry before the current entry during a traversal. 00571 \param elm This is a pointer to the entry to be inserted. 00572 \param field This is the name of the field (declared using AST_LIST_ENTRY()) 00573 used to link entries of this list together. 00574 00575 \note This macro can \b only be used inside an AST_LIST_TRAVERSE_SAFE_BEGIN() 00576 block. 00577 */ 00578 #define AST_LIST_INSERT_BEFORE_CURRENT(elm, field) do { \ 00579 if (__list_prev) { \ 00580 (elm)->field.next = __list_prev->field.next; \ 00581 __list_prev->field.next = elm; \ 00582 } else { \ 00583 (elm)->field.next = __list_head->first; \ 00584 __list_head->first = (elm); \ 00585 } \ 00586 __new_prev = (elm); \ 00587 } while (0) 00588 00589 #define AST_RWLIST_INSERT_BEFORE_CURRENT AST_LIST_INSERT_BEFORE_CURRENT 00590 00591 /*! 00592 \brief Closes a safe loop traversal block. 00593 */ 00594 #define AST_LIST_TRAVERSE_SAFE_END } 00595 00596 #define AST_RWLIST_TRAVERSE_SAFE_END AST_LIST_TRAVERSE_SAFE_END 00597 00598 /*! 00599 \brief Initializes a list head structure. 00600 \param head This is a pointer to the list head structure 00601 00602 This macro initializes a list head structure by setting the head 00603 entry to \a NULL (empty list) and recreating the embedded lock. 00604 */ 00605 #define AST_LIST_HEAD_INIT(head) { \ 00606 (head)->first = NULL; \ 00607 (head)->last = NULL; \ 00608 ast_mutex_init(&(head)->lock); \ 00609 } 00610 00611 /*! 00612 \brief Initializes an rwlist head structure. 00613 \param head This is a pointer to the list head structure 00614 00615 This macro initializes a list head structure by setting the head 00616 entry to \a NULL (empty list) and recreating the embedded lock. 00617 */ 00618 #define AST_RWLIST_HEAD_INIT(head) { \ 00619 (head)->first = NULL; \ 00620 (head)->last = NULL; \ 00621 ast_rwlock_init(&(head)->lock); \ 00622 } 00623 00624 /*! 00625 \brief Destroys a list head structure. 00626 \param head This is a pointer to the list head structure 00627 00628 This macro destroys a list head structure by setting the head 00629 entry to \a NULL (empty list) and destroying the embedded lock. 00630 It does not free the structure from memory. 00631 */ 00632 #define AST_LIST_HEAD_DESTROY(head) { \ 00633 (head)->first = NULL; \ 00634 (head)->last = NULL; \ 00635 ast_mutex_destroy(&(head)->lock); \ 00636 } 00637 00638 /*! 00639 \brief Destroys an rwlist head structure. 00640 \param head This is a pointer to the list head structure 00641 00642 This macro destroys a list head structure by setting the head 00643 entry to \a NULL (empty list) and destroying the embedded lock. 00644 It does not free the structure from memory. 00645 */ 00646 #define AST_RWLIST_HEAD_DESTROY(head) { \ 00647 (head)->first = NULL; \ 00648 (head)->last = NULL; \ 00649 ast_rwlock_destroy(&(head)->lock); \ 00650 } 00651 00652 /*! 00653 \brief Initializes a list head structure. 00654 \param head This is a pointer to the list head structure 00655 00656 This macro initializes a list head structure by setting the head 00657 entry to \a NULL (empty list). There is no embedded lock handling 00658 with this macro. 00659 */ 00660 #define AST_LIST_HEAD_INIT_NOLOCK(head) { \ 00661 (head)->first = NULL; \ 00662 (head)->last = NULL; \ 00663 } 00664 00665 /*! 00666 \brief Inserts a list entry after a given entry. 00667 \param head This is a pointer to the list head structure 00668 \param listelm This is a pointer to the entry after which the new entry should 00669 be inserted. 00670 \param elm This is a pointer to the entry to be inserted. 00671 \param field This is the name of the field (declared using AST_LIST_ENTRY()) 00672 used to link entries of this list together. 00673 */ 00674 #define AST_LIST_INSERT_AFTER(head, listelm, elm, field) do { \ 00675 (elm)->field.next = (listelm)->field.next; \ 00676 (listelm)->field.next = (elm); \ 00677 if ((head)->last == (listelm)) \ 00678 (head)->last = (elm); \ 00679 } while (0) 00680 00681 #define AST_RWLIST_INSERT_AFTER AST_LIST_INSERT_AFTER 00682 00683 /*! 00684 \brief Inserts a list entry at the head of a list. 00685 \param head This is a pointer to the list head structure 00686 \param elm This is a pointer to the entry to be inserted. 00687 \param field This is the name of the field (declared using AST_LIST_ENTRY()) 00688 used to link entries of this list together. 00689 */ 00690 #define AST_LIST_INSERT_HEAD(head, elm, field) do { \ 00691 (elm)->field.next = (head)->first; \ 00692 (head)->first = (elm); \ 00693 if (!(head)->last) \ 00694 (head)->last = (elm); \ 00695 } while (0) 00696 00697 #define AST_RWLIST_INSERT_HEAD AST_LIST_INSERT_HEAD 00698 00699 /*! 00700 \brief Appends a list entry to the tail of a list. 00701 \param head This is a pointer to the list head structure 00702 \param elm This is a pointer to the entry to be appended. 00703 \param field This is the name of the field (declared using AST_LIST_ENTRY()) 00704 used to link entries of this list together. 00705 00706 Note: The link field in the appended entry is \b not modified, so if it is 00707 actually the head of a list itself, the entire list will be appended 00708 temporarily (until the next AST_LIST_INSERT_TAIL is performed). 00709 */ 00710 #define AST_LIST_INSERT_TAIL(head, elm, field) do { \ 00711 if (!(head)->first) { \ 00712 (head)->first = (elm); \ 00713 (head)->last = (elm); \ 00714 } else { \ 00715 (head)->last->field.next = (elm); \ 00716 (head)->last = (elm); \ 00717 } \ 00718 } while (0) 00719 00720 #define AST_RWLIST_INSERT_TAIL AST_LIST_INSERT_TAIL 00721 00722 /*! 00723 \brief Appends a whole list to the tail of a list. 00724 \param head This is a pointer to the list head structure 00725 \param list This is a pointer to the list to be appended. 00726 \param field This is the name of the field (declared using AST_LIST_ENTRY()) 00727 used to link entries of this list together. 00728 00729 Note: The source list (the \a list parameter) will be empty after 00730 calling this macro (the list entries are \b moved to the target list). 00731 */ 00732 #define AST_LIST_APPEND_LIST(head, list, field) do { \ 00733 if (!(list)->first) { \ 00734 break; \ 00735 } \ 00736 if (!(head)->first) { \ 00737 (head)->first = (list)->first; \ 00738 (head)->last = (list)->last; \ 00739 } else { \ 00740 (head)->last->field.next = (list)->first; \ 00741 (head)->last = (list)->last; \ 00742 } \ 00743 (list)->first = NULL; \ 00744 (list)->last = NULL; \ 00745 } while (0) 00746 00747 #define AST_RWLIST_APPEND_LIST AST_LIST_APPEND_LIST 00748 00749 /*! 00750 \brief Inserts a whole list after a specific entry in a list 00751 \param head This is a pointer to the list head structure 00752 \param list This is a pointer to the list to be inserted. 00753 \param elm This is a pointer to the entry after which the new list should 00754 be inserted. 00755 \param field This is the name of the field (declared using AST_LIST_ENTRY()) 00756 used to link entries of the lists together. 00757 00758 Note: The source list (the \a list parameter) will be empty after 00759 calling this macro (the list entries are \b moved to the target list). 00760 */ 00761 #define AST_LIST_INSERT_LIST_AFTER(head, list, elm, field) do { \ 00762 (list)->last->field.next = (elm)->field.next; \ 00763 (elm)->field.next = (list)->first; \ 00764 if ((head)->last == elm) { \ 00765 (head)->last = (list)->last; \ 00766 } \ 00767 (list)->first = NULL; \ 00768 (list)->last = NULL; \ 00769 } while(0) 00770 00771 #define AST_RWLIST_INSERT_LIST_AFTER AST_LIST_INSERT_LIST_AFTER 00772 00773 /*! 00774 * \brief Removes and returns the head entry from a list. 00775 * \param head This is a pointer to the list head structure 00776 * \param field This is the name of the field (declared using AST_LIST_ENTRY()) 00777 * used to link entries of this list together. 00778 * 00779 * Removes the head entry from the list, and returns a pointer to it. 00780 * This macro is safe to call on an empty list. 00781 */ 00782 #define AST_LIST_REMOVE_HEAD(head, field) ({ \ 00783 typeof((head)->first) cur = (head)->first; \ 00784 if (cur) { \ 00785 (head)->first = cur->field.next; \ 00786 cur->field.next = NULL; \ 00787 if ((head)->last == cur) \ 00788 (head)->last = NULL; \ 00789 } \ 00790 cur; \ 00791 }) 00792 00793 #define AST_RWLIST_REMOVE_HEAD AST_LIST_REMOVE_HEAD 00794 00795 /*! 00796 \brief Removes a specific entry from a list. 00797 \param head This is a pointer to the list head structure 00798 \param elm This is a pointer to the entry to be removed. 00799 \param field This is the name of the field (declared using AST_LIST_ENTRY()) 00800 used to link entries of this list together. 00801 \warning The removed entry is \b not freed nor modified in any way. 00802 */ 00803 #define AST_LIST_REMOVE(head, elm, field) ({ \ 00804 __typeof(elm) __res = NULL; \ 00805 if ((head)->first == (elm)) { \ 00806 __res = (head)->first; \ 00807 (head)->first = (elm)->field.next; \ 00808 if ((head)->last == (elm)) \ 00809 (head)->last = NULL; \ 00810 } else { \ 00811 typeof(elm) curelm = (head)->first; \ 00812 while (curelm && (curelm->field.next != (elm))) \ 00813 curelm = curelm->field.next; \ 00814 if (curelm) { \ 00815 __res = (elm); \ 00816 curelm->field.next = (elm)->field.next; \ 00817 if ((head)->last == (elm)) \ 00818 (head)->last = curelm; \ 00819 } \ 00820 } \ 00821 (elm)->field.next = NULL; \ 00822 (__res); \ 00823 }) 00824 00825 #define AST_RWLIST_REMOVE AST_LIST_REMOVE 00826 00827 #endif /* _ASTERISK_LINKEDLISTS_H */