Mon Mar 20 08:20:12 2006

Asterisk developer's documentation


Main Page | Modules | Alphabetical List | Data Structures | Directories | File List | Data Fields | Globals | Related Pages

linkedlists.h

Go to the documentation of this file.
00001 /*
00002  * Asterisk -- An open source telephony toolkit.
00003  *
00004  * Copyright (C) 1999 - 2005, 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         __list_next = (var) ? (var)->field.next : NULL            \
00283        )
00284 
00285 /*!
00286   \brief Removes the \a current entry from a list during a traversal.
00287   \param head This is a pointer to the list head structure
00288   \param field This is the name of the field (declared using AST_LIST_ENTRY())
00289   used to link entries of this list together.
00290 
00291   \note This macro can \b only be used inside an AST_LIST_TRAVERSE_SAFE_BEGIN()
00292   block; it is used to unlink the current entry from the list without affecting
00293   the list traversal (and without having to re-traverse the list to modify the
00294   previous entry, if any).
00295  */
00296 #define AST_LIST_REMOVE_CURRENT(head, field)                \
00297    __new_prev = __list_prev;                    \
00298    if (__list_prev)                       \
00299       __list_prev->field.next = __list_next;             \
00300    else                             \
00301       (head)->first = __list_next;                 \
00302    if (!__list_next)                      \
00303       (head)->last = __list_prev;
00304 
00305 /*!
00306   \brief Closes a safe loop traversal block.
00307  */
00308 #define AST_LIST_TRAVERSE_SAFE_END  }
00309 
00310 /*!
00311   \brief Initializes a list head structure.
00312   \param head This is a pointer to the list head structure
00313 
00314   This macro initializes a list head structure by setting the head
00315   entry to \a NULL (empty list) and recreating the embedded lock.
00316 */
00317 #define AST_LIST_HEAD_INIT(head) {              \
00318    (head)->first = NULL;                  \
00319    (head)->last = NULL;                \
00320    ast_mutex_init(&(head)->lock);               \
00321 }
00322 
00323 /*!
00324   \brief Destroys a list head structure.
00325   \param head This is a pointer to the list head structure
00326 
00327   This macro destroys a list head structure by setting the head
00328   entry to \a NULL (empty list) and destroying the embedded lock.
00329   It does not free the structure from memory.
00330 */
00331 #define AST_LIST_HEAD_DESTROY(head) {              \
00332    (head)->first = NULL;                  \
00333    (head)->last = NULL;                \
00334    ast_mutex_destroy(&(head)->lock);            \
00335 }
00336 
00337 /*!
00338   \brief Initializes a list head structure.
00339   \param head This is a pointer to the list head structure
00340 
00341   This macro initializes a list head structure by setting the head
00342   entry to \a NULL (empty list) and recreating the embedded lock.
00343 */
00344 #define AST_LIST_HEAD_INIT_NOLOCK(head) {          \
00345    (head)->first = NULL;                  \
00346    (head)->last = NULL;                \
00347 }
00348 
00349 /*!
00350   \brief Inserts a list entry after a given entry.
00351   \param head This is a pointer to the list head structure
00352   \param listelm This is a pointer to the entry after which the new entry should
00353   be inserted.
00354   \param elm This is a pointer to the entry to be inserted.
00355   \param field This is the name of the field (declared using AST_LIST_ENTRY())
00356   used to link entries of this list together.
00357  */
00358 #define AST_LIST_INSERT_AFTER(head, listelm, elm, field) do {     \
00359    (elm)->field.next = (listelm)->field.next;         \
00360    (listelm)->field.next = (elm);               \
00361    if ((head)->last == (listelm))               \
00362       (head)->last = (elm);               \
00363 } while (0)
00364 
00365 /*!
00366   \brief Inserts a list entry at the head of a list.
00367   \param head This is a pointer to the list head structure
00368   \param elm This is a pointer to the entry to be inserted.
00369   \param field This is the name of the field (declared using AST_LIST_ENTRY())
00370   used to link entries of this list together.
00371  */
00372 #define AST_LIST_INSERT_HEAD(head, elm, field) do {         \
00373       (elm)->field.next = (head)->first;        \
00374       (head)->first = (elm);              \
00375       if (!(head)->last)               \
00376          (head)->last = (elm);            \
00377 } while (0)
00378 
00379 /*!
00380   \brief Appends a list entry to the tail of a list.
00381   \param head This is a pointer to the list head structure
00382   \param elm This is a pointer to the entry to be appended.
00383   \param field This is the name of the field (declared using AST_LIST_ENTRY())
00384   used to link entries of this list together.
00385 
00386   Note: The link field in the appended entry is \b not modified, so if it is
00387   actually the head of a list itself, the entire list will be appended
00388   temporarily (until the next AST_LIST_INSERT_TAIL is performed).
00389  */
00390 #define AST_LIST_INSERT_TAIL(head, elm, field) do {         \
00391       if (!(head)->first) {                  \
00392       (head)->first = (elm);              \
00393       (head)->last = (elm);               \
00394       } else {                      \
00395       (head)->last->field.next = (elm);         \
00396       (head)->last = (elm);               \
00397       }                          \
00398 } while (0)
00399 
00400 /*!
00401   \brief Removes and returns the head entry from a list.
00402   \param head This is a pointer to the list head structure
00403   \param field This is the name of the field (declared using AST_LIST_ENTRY())
00404   used to link entries of this list together.
00405 
00406   Removes the head entry from the list, and returns a pointer to it.
00407   This macro is safe to call on an empty list.
00408  */
00409 #define AST_LIST_REMOVE_HEAD(head, field) ({          \
00410       typeof((head)->first) cur = (head)->first;      \
00411       if (cur) {                 \
00412          (head)->first = cur->field.next;    \
00413          cur->field.next = NULL;          \
00414          if ((head)->last == cur)         \
00415             (head)->last = NULL;       \
00416       }                    \
00417       cur;                    \
00418    })
00419 
00420 /*!
00421   \brief Removes a specific entry from a list.
00422   \param head This is a pointer to the list head structure
00423   \param elm This is a pointer to the entry to be removed.
00424   \param field This is the name of the field (declared using AST_LIST_ENTRY())
00425   used to link entries of this list together.
00426   \warning The removed entry is \b not freed nor modified in any way.
00427  */
00428 #define AST_LIST_REMOVE(head, elm, field) do {                \
00429    if ((head)->first == (elm)) {             \
00430       (head)->first = (elm)->field.next;        \
00431       if ((head)->last == (elm))       \
00432          (head)->last = NULL;       \
00433    } else {                      \
00434       typeof(elm) curelm = (head)->first;       \
00435       while (curelm->field.next != (elm))       \
00436          curelm = curelm->field.next;        \
00437       curelm->field.next = (elm)->field.next;         \
00438       if ((head)->last == (elm))          \
00439          (head)->last = curelm;           \
00440    }                       \
00441 } while (0)
00442 
00443 #endif /* _ASTERISK_LINKEDLISTS_H */

Generated on Mon Mar 20 08:20:12 2006 for Asterisk - the Open Source PBX by  doxygen 1.3.9.1