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