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 */

Generated on Wed Oct 28 15:47:54 2009 for Asterisk - the Open Source PBX by  doxygen 1.5.6