Asterisk.org: Developer Documentation (28 Oct 2009)

Wed Oct 28 15:47:54 2009

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