Thu Oct 11 06:42:07 2012

Asterisk developer's documentation


linkedlists.h

Go to the documentation of this file.
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 */

Generated on Thu Oct 11 06:42:08 2012 for Asterisk - the Open Source PBX by  doxygen 1.5.6