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

Generated on Thu Apr 16 06:27:38 2015 for Asterisk - The Open Source Telephony Project by  doxygen 1.5.6