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