Fri May 26 01:45:34 2006

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 non-zero on success, 0 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 a structure to be used to hold a list of specified type, statically initialized.
00105   \param name This will be the name of the defined structure.
00106   \param type This is the type of each list entry.
00107 
00108   This macro creates a structure definition that can be used
00109   to hold a list of the entries of type \a type, and allocates an instance
00110   of it, initialized to be empty.
00111 
00112   Example usage:
00113   \code
00114   static AST_LIST_HEAD_STATIC(entry_list, entry);
00115   \endcode
00116 
00117   This would define \c struct \c entry_list, intended to hold a list of
00118   type \c struct \c entry.
00119 */
00120 #define AST_LIST_HEAD_STATIC(name, type)           \
00121 struct name {                       \
00122    struct type *first;                 \
00123    struct type *last;                  \
00124    ast_mutex_t lock;                \
00125 } name = {                       \
00126    .first = NULL,                   \
00127    .last = NULL,                    \
00128    .lock = AST_MUTEX_INIT_VALUE,             \
00129 };
00130 
00131 /*!
00132   \brief Initializes a list head structure with a specified first entry.
00133   \param head This is a pointer to the list head structure
00134   \param entry pointer to the list entry that will become the head of the list
00135 
00136   This macro initializes a list head structure by setting the head
00137   entry to the supplied value and recreating the embedded lock.
00138 */
00139 #define AST_LIST_HEAD_SET(head, entry) do {           \
00140    (head)->first = (entry);               \
00141    (head)->last = (entry);                \
00142    ast_mutex_init(&(head)->lock);               \
00143 } while (0)
00144 
00145 /*!
00146   \brief Initializes a list head structure with a specified first entry.
00147   \param head This is a pointer to the list head structure
00148   \param entry pointer to the list entry that will become the head of the list
00149 
00150   This macro initializes a list head structure by setting the head
00151   entry to the supplied value.
00152 */
00153 #define AST_LIST_HEAD_SET_NOLOCK(head, entry) do {       \
00154    (head)->first = (entry);               \
00155    (head)->last = (entry);                \
00156 } while (0)
00157 
00158 /*!
00159   \brief Declare a forward link structure inside a list entry.
00160   \param type This is the type of each list entry.
00161 
00162   This macro declares a structure to be used to link list entries together.
00163   It must be used inside the definition of the structure named in
00164   \a type, as follows:
00165 
00166   \code
00167   struct list_entry {
00168    ...
00169    AST_LIST_ENTRY(list_entry) list;
00170   }
00171   \endcode
00172 
00173   The field name \a list here is arbitrary, and can be anything you wish.
00174 */
00175 #define AST_LIST_ENTRY(type)                 \
00176 struct {                      \
00177    struct type *next;                  \
00178 }
00179  
00180 /*!
00181   \brief Returns the first entry contained in a list.
00182   \param head This is a pointer to the list head structure
00183  */
00184 #define  AST_LIST_FIRST(head) ((head)->first)
00185 
00186 /*!
00187   \brief Returns the next entry in the list after the given entry.
00188   \param elm This is a pointer to the current entry.
00189   \param field This is the name of the field (declared using AST_LIST_ENTRY())
00190   used to link entries of this list together.
00191 */
00192 #define AST_LIST_NEXT(elm, field)   ((elm)->field.next)
00193 
00194 /*!
00195   \brief Checks whether the specified list contains any entries.
00196   \param head This is a pointer to the list head structure
00197 
00198   Returns non-zero if the list has entries, zero if not.
00199  */
00200 #define  AST_LIST_EMPTY(head) (AST_LIST_FIRST(head) == NULL)
00201 
00202 /*!
00203   \brief Loops over (traverses) the entries in a list.
00204   \param head This is a pointer to the list head structure
00205   \param var This is the name of the variable that will hold a pointer to the
00206   current list entry on each iteration. It must be declared before calling
00207   this macro.
00208   \param field This is the name of the field (declared using AST_LIST_ENTRY())
00209   used to link entries of this list together.
00210 
00211   This macro is use to loop over (traverse) the entries in a list. It uses a
00212   \a for loop, and supplies the enclosed code with a pointer to each list
00213   entry as it loops. It is typically used as follows:
00214   \code
00215   static AST_LIST_HEAD(entry_list, list_entry) entries;
00216   ...
00217   struct list_entry {
00218    ...
00219    AST_LIST_ENTRY(list_entry) list;
00220   }
00221   ...
00222   struct list_entry *current;
00223   ...
00224   AST_LIST_TRAVERSE(&entries, current, list) {
00225      (do something with current here)
00226   }
00227   \endcode
00228   \warning If you modify the forward-link pointer contained in the \a current entry while
00229   inside the loop, the behavior will be unpredictable. At a minimum, the following
00230   macros will modify the forward-link pointer, and should not be used inside
00231   AST_LIST_TRAVERSE() against the entry pointed to by the \a current pointer without
00232   careful consideration of their consequences:
00233   \li AST_LIST_NEXT() (when used as an lvalue)
00234   \li AST_LIST_INSERT_AFTER()
00235   \li AST_LIST_INSERT_HEAD()
00236   \li AST_LIST_INSERT_TAIL()
00237 */
00238 #define AST_LIST_TRAVERSE(head,var,field)             \
00239    for((var) = (head)->first; (var); (var) = (var)->field.next)
00240 
00241 /*!
00242   \brief Loops safely over (traverses) the entries in a list.
00243   \param head This is a pointer to the list head structure
00244   \param var This is the name of the variable that will hold a pointer to the
00245   current list entry on each iteration. It must be declared before calling
00246   this macro.
00247   \param field This is the name of the field (declared using AST_LIST_ENTRY())
00248   used to link entries of this list together.
00249 
00250   This macro is used to safely loop over (traverse) the entries in a list. It
00251   uses a \a for loop, and supplies the enclosed code with a pointer to each list
00252   entry as it loops. It is typically used as follows:
00253 
00254   \code
00255   static AST_LIST_HEAD(entry_list, list_entry) entries;
00256   ...
00257   struct list_entry {
00258    ...
00259    AST_LIST_ENTRY(list_entry) list;
00260   }
00261   ...
00262   struct list_entry *current;
00263   ...
00264   AST_LIST_TRAVERSE_SAFE_BEGIN(&entries, current, list) {
00265      (do something with current here)
00266   }
00267   AST_LIST_TRAVERSE_SAFE_END;
00268   \endcode
00269 
00270   It differs from AST_LIST_TRAVERSE() in that the code inside the loop can modify
00271   (or even free, after calling AST_LIST_REMOVE_CURRENT()) the entry pointed to by
00272   the \a current pointer without affecting the loop traversal.
00273 */
00274 #define AST_LIST_TRAVERSE_SAFE_BEGIN(head, var, field) {          \
00275    typeof((head)->first) __list_next;                 \
00276    typeof((head)->first) __list_prev = NULL;             \
00277    typeof((head)->first) __new_prev = NULL;              \
00278    for ((var) = (head)->first, __new_prev = (var),             \
00279          __list_next = (var) ? (var)->field.next : NULL;          \
00280         (var);                         \
00281         __list_prev = __new_prev, (var) = __list_next,            \
00282         __new_prev = (var),                     \
00283         __list_next = (var) ? (var)->field.next : NULL            \
00284        )
00285 
00286 /*!
00287   \brief Removes the \a current entry from a list during a traversal.
00288   \param head This is a pointer to the list head structure
00289   \param field This is the name of the field (declared using AST_LIST_ENTRY())
00290   used to link entries of this list together.
00291 
00292   \note This macro can \b only be used inside an AST_LIST_TRAVERSE_SAFE_BEGIN()
00293   block; it is used to unlink the current entry from the list without affecting
00294   the list traversal (and without having to re-traverse the list to modify the
00295   previous entry, if any).
00296  */
00297 #define AST_LIST_REMOVE_CURRENT(head, field)                \
00298    __new_prev = __list_prev;                    \
00299    if (__list_prev)                       \
00300       __list_prev->field.next = __list_next;             \
00301    else                             \
00302       (head)->first = __list_next;                 \
00303    if (!__list_next)                      \
00304       (head)->last = __list_prev;
00305 
00306 /*!
00307   \brief Closes a safe loop traversal block.
00308  */
00309 #define AST_LIST_TRAVERSE_SAFE_END  }
00310 
00311 /*!
00312   \brief Initializes a list head structure.
00313   \param head This is a pointer to the list head structure
00314 
00315   This macro initializes a list head structure by setting the head
00316   entry to \a NULL (empty list) and recreating the embedded lock.
00317 */
00318 #define AST_LIST_HEAD_INIT(head) {              \
00319    (head)->first = NULL;                  \
00320    (head)->last = NULL;                \
00321    ast_mutex_init(&(head)->lock);               \
00322 }
00323 
00324 /*!
00325   \brief Destroys a list head structure.
00326   \param head This is a pointer to the list head structure
00327 
00328   This macro destroys a list head structure by setting the head
00329   entry to \a NULL (empty list) and destroying the embedded lock.
00330   It does not free the structure from memory.
00331 */
00332 #define AST_LIST_HEAD_DESTROY(head) {              \
00333    (head)->first = NULL;                  \
00334    (head)->last = NULL;                \
00335    ast_mutex_destroy(&(head)->lock);            \
00336 }
00337 
00338 /*!
00339   \brief Initializes a list head structure.
00340   \param head This is a pointer to the list head structure
00341 
00342   This macro initializes a list head structure by setting the head
00343   entry to \a NULL (empty list) and recreating the embedded lock.
00344 */
00345 #define AST_LIST_HEAD_INIT_NOLOCK(head) {          \
00346    (head)->first = NULL;                  \
00347    (head)->last = NULL;                \
00348 }
00349 
00350 /*!
00351   \brief Inserts a list entry after a given entry.
00352   \param head This is a pointer to the list head structure
00353   \param listelm This is a pointer to the entry after which the new entry should
00354   be inserted.
00355   \param elm This is a pointer to the entry to be inserted.
00356   \param field This is the name of the field (declared using AST_LIST_ENTRY())
00357   used to link entries of this list together.
00358  */
00359 #define AST_LIST_INSERT_AFTER(head, listelm, elm, field) do {     \
00360    (elm)->field.next = (listelm)->field.next;         \
00361    (listelm)->field.next = (elm);               \
00362    if ((head)->last == (listelm))               \
00363       (head)->last = (elm);               \
00364 } while (0)
00365 
00366 /*!
00367   \brief Inserts a list entry at the head of a list.
00368   \param head This is a pointer to the list head structure
00369   \param elm This is a pointer to the entry to be inserted.
00370   \param field This is the name of the field (declared using AST_LIST_ENTRY())
00371   used to link entries of this list together.
00372  */
00373 #define AST_LIST_INSERT_HEAD(head, elm, field) do {         \
00374       (elm)->field.next = (head)->first;        \
00375       (head)->first = (elm);              \
00376       if (!(head)->last)               \
00377          (head)->last = (elm);            \
00378 } while (0)
00379 
00380 /*!
00381   \brief Appends a list entry to the tail of a list.
00382   \param head This is a pointer to the list head structure
00383   \param elm This is a pointer to the entry to be appended.
00384   \param field This is the name of the field (declared using AST_LIST_ENTRY())
00385   used to link entries of this list together.
00386 
00387   Note: The link field in the appended entry is \b not modified, so if it is
00388   actually the head of a list itself, the entire list will be appended
00389   temporarily (until the next AST_LIST_INSERT_TAIL is performed).
00390  */
00391 #define AST_LIST_INSERT_TAIL(head, elm, field) do {         \
00392       if (!(head)->first) {                  \
00393       (head)->first = (elm);              \
00394       (head)->last = (elm);               \
00395       } else {                      \
00396       (head)->last->field.next = (elm);         \
00397       (head)->last = (elm);               \
00398       }                          \
00399 } while (0)
00400 
00401 /*!
00402   \brief Removes and returns the head entry from a list.
00403   \param head This is a pointer to the list head structure
00404   \param field This is the name of the field (declared using AST_LIST_ENTRY())
00405   used to link entries of this list together.
00406 
00407   Removes the head entry from the list, and returns a pointer to it.
00408   This macro is safe to call on an empty list.
00409  */
00410 #define AST_LIST_REMOVE_HEAD(head, field) ({          \
00411       typeof((head)->first) cur = (head)->first;      \
00412       if (cur) {                 \
00413          (head)->first = cur->field.next;    \
00414          cur->field.next = NULL;          \
00415          if ((head)->last == cur)         \
00416             (head)->last = NULL;       \
00417       }                    \
00418       cur;                    \
00419    })
00420 
00421 /*!
00422   \brief Removes a specific entry from a list.
00423   \param head This is a pointer to the list head structure
00424   \param elm This is a pointer to the entry to be removed.
00425   \param field This is the name of the field (declared using AST_LIST_ENTRY())
00426   used to link entries of this list together.
00427   \warning The removed entry is \b not freed nor modified in any way.
00428  */
00429 #define AST_LIST_REMOVE(head, elm, field) do {                \
00430    if ((head)->first == (elm)) {             \
00431       (head)->first = (elm)->field.next;        \
00432       if ((head)->last == (elm))       \
00433          (head)->last = NULL;       \
00434    } else {                      \
00435       typeof(elm) curelm = (head)->first;       \
00436       while (curelm->field.next != (elm))       \
00437          curelm = curelm->field.next;        \
00438       curelm->field.next = (elm)->field.next;         \
00439       if ((head)->last == (elm))          \
00440          (head)->last = curelm;           \
00441    }                       \
00442         (elm)->field.next = NULL;                                       \
00443 } while (0)
00444 
00445 #endif /* _ASTERISK_LINKEDLISTS_H */

Generated on Fri May 26 01:45:34 2006 for Asterisk - the Open Source PBX by  doxygen 1.4.6