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 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 Removes and returns the head entry from a list. 00434 \param head This is a pointer to the list head structure 00435 \param field This is the name of the field (declared using AST_LIST_ENTRY()) 00436 used to link entries of this list together. 00437 00438 Removes the head entry from the list, and returns a pointer to it. 00439 This macro is safe to call on an empty list. 00440 */ 00441 #define AST_LIST_REMOVE_HEAD(head, field) ({ \ 00442 typeof((head)->first) cur = (head)->first; \ 00443 if (cur) { \ 00444 (head)->first = cur->field.next; \ 00445 cur->field.next = NULL; \ 00446 if ((head)->last == cur) \ 00447 (head)->last = NULL; \ 00448 } \ 00449 cur; \ 00450 }) 00451 00452 /*! 00453 \brief Removes a specific entry from a list. 00454 \param head This is a pointer to the list head structure 00455 \param elm This is a pointer to the entry to be removed. 00456 \param field This is the name of the field (declared using AST_LIST_ENTRY()) 00457 used to link entries of this list together. 00458 \warning The removed entry is \b not freed nor modified in any way. 00459 */ 00460 #define AST_LIST_REMOVE(head, elm, field) do { \ 00461 if ((head)->first == (elm)) { \ 00462 (head)->first = (elm)->field.next; \ 00463 if ((head)->last == (elm)) \ 00464 (head)->last = NULL; \ 00465 } else { \ 00466 typeof(elm) curelm = (head)->first; \ 00467 while (curelm && (curelm->field.next != (elm))) \ 00468 curelm = curelm->field.next; \ 00469 if (curelm) { \ 00470 curelm->field.next = (elm)->field.next; \ 00471 if ((head)->last == (elm)) \ 00472 (head)->last = curelm; \ 00473 } \ 00474 } \ 00475 (elm)->field.next = NULL; \ 00476 } while (0) 00477 00478 #endif /* _ASTERISK_LINKEDLISTS_H */