Asterisk - The Open Source Telephony Project  GIT-master-e8cda4b
dlinkedlists.h
Go to the documentation of this file.
1 /*
2  * Asterisk -- An open source telephony toolkit.
3  *
4  * Copyright (C) 2007, Digium, Inc.
5  *
6  * Steve Murphy <murf@digium.com>
7  *
8  * Doubly-Linked List Macros--
9  * Based on linkedlists.h (to the point of plagiarism!), which is by:
10  *
11  * Mark Spencer <markster@digium.com>
12  * Kevin P. Fleming <kpfleming@digium.com>
13  *
14  * See http://www.asterisk.org for more information about
15  * the Asterisk project. Please do not directly contact
16  * any of the maintainers of this project for assistance;
17  * the project provides a web site, mailing lists and IRC
18  * channels for your use.
19  *
20  * This program is free software, distributed under the terms of
21  * the GNU General Public License Version 2. See the LICENSE file
22  * at the top of the source tree.
23  */
24 
25 #ifndef ASTERISK_DLINKEDLISTS_H
26 #define ASTERISK_DLINKEDLISTS_H
27 
28 #include "asterisk/lock.h"
29 
30 /*!
31  * \file dlinkedlists.h
32  * \brief A set of macros to manage doubly-linked lists.
33  */
34 
35 /*!
36  * \brief Locks a list.
37  * \param head This is a pointer to the list head structure
38  *
39  * This macro attempts to place an exclusive lock in the
40  * list head structure pointed to by head.
41  * \retval 0 on success
42  * \retval non-zero on failure
43  * \since 1.6.1
44  */
45 #define AST_DLLIST_LOCK(head) \
46  ast_mutex_lock(&(head)->lock)
47 
48 /*!
49  * \brief Write locks a list.
50  * \param head This is a pointer to the list head structure
51  *
52  * This macro attempts to place an exclusive write lock in the
53  * list head structure pointed to by head.
54  * \retval 0 on success
55  * \retval non-zero on failure
56  * \since 1.6.1
57  */
58 #define AST_RWDLLIST_WRLOCK(head) \
59  ast_rwlock_wrlock(&(head)->lock)
60 
61 /*!
62  * \brief Read locks a list.
63  * \param head This is a pointer to the list head structure
64  *
65  * This macro attempts to place a read lock in the
66  * list head structure pointed to by head.
67  * \retval 0 on success
68  * \retval non-zero on failure
69  * \since 1.6.1
70  */
71 #define AST_RWDLLIST_RDLOCK(head) \
72  ast_rwlock_rdlock(&(head)->lock)
73 
74 /*!
75  * \brief Locks a list, without blocking if the list is locked.
76  * \param head This is a pointer to the list head structure
77  *
78  * This macro attempts to place an exclusive lock in the
79  * list head structure pointed to by head.
80  * \retval 0 on success
81  * \retval non-zero on failure
82  * \since 1.6.1
83  */
84 #define AST_DLLIST_TRYLOCK(head) \
85  ast_mutex_trylock(&(head)->lock)
86 
87 /*!
88  * \brief Write locks a list, without blocking if the list is locked.
89  * \param head This is a pointer to the list head structure
90  *
91  * This macro attempts to place an exclusive write lock in the
92  * list head structure pointed to by head.
93  * \retval 0 on success
94  * \retval non-zero on failure
95  * \since 1.6.1
96  */
97 #define AST_RWDLLIST_TRYWRLOCK(head) \
98  ast_rwlock_trywrlock(&(head)->lock)
99 
100 /*!
101  * \brief Read locks a list, without blocking if the list is locked.
102  * \param head This is a pointer to the list head structure
103  *
104  * This macro attempts to place a read lock in the
105  * list head structure pointed to by head.
106  * \retval 0 on success
107  * \retval non-zero on failure
108  * \since 1.6.1
109  */
110 #define AST_RWDLLIST_TRYRDLOCK(head) \
111  ast_rwlock_tryrdlock(&(head)->lock)
112 
113 /*!
114  * \brief Attempts to unlock a list.
115  * \param head This is a pointer to the list head structure
116  *
117  * This macro attempts to remove an exclusive lock from the
118  * list head structure pointed to by head. If the list
119  * was not locked by this thread, this macro has no effect.
120  * \since 1.6.1
121  */
122 #define AST_DLLIST_UNLOCK(head) \
123  ast_mutex_unlock(&(head)->lock)
124 
125 /*!
126  * \brief Attempts to unlock a read/write based list.
127  * \param head This is a pointer to the list head structure
128  *
129  * This macro attempts to remove a read or write lock from the
130  * list head structure pointed to by head. If the list
131  * was not locked by this thread, this macro has no effect.
132  * \since 1.6.1
133  */
134 #define AST_RWDLLIST_UNLOCK(head) \
135  ast_rwlock_unlock(&(head)->lock)
136 
137 /*!
138  * \brief Defines a structure to be used to hold a list of specified type.
139  * \param name This will be the name of the defined structure.
140  * \param type This is the type of each list entry.
141  *
142  * This macro creates a structure definition that can be used
143  * to hold a list of the entries of type \a type. It does not actually
144  * declare (allocate) a structure; to do that, either follow this
145  * macro with the desired name of the instance you wish to declare,
146  * or use the specified \a name to declare instances elsewhere.
147  *
148  * Example usage:
149  * \code
150  * static AST_DLLIST_HEAD(entry_list, entry) entries;
151  * \endcode
152  *
153  * This would define \c struct \c entry_list, and declare an instance of it named
154  * \a entries, all intended to hold a list of type \c struct \c entry.
155  * \since 1.6.1
156  */
157 #define AST_DLLIST_HEAD(name, type) \
158  struct name { \
159  struct type *first; \
160  struct type *last; \
161  ast_mutex_t lock; \
162  }
163 
164 /*!
165  * \brief Defines a structure to be used to hold a read/write list of specified type.
166  * \param name This will be the name of the defined structure.
167  * \param type This is the type of each list entry.
168  *
169  * This macro creates a structure definition that can be used
170  * to hold a list of the entries of type \a type. It does not actually
171  * declare (allocate) a structure; to do that, either follow this
172  * macro with the desired name of the instance you wish to declare,
173  * or use the specified \a name to declare instances elsewhere.
174  *
175  * Example usage:
176  * \code
177  * static AST_RWDLLIST_HEAD(entry_list, entry) entries;
178  * \endcode
179  *
180  * This would define \c struct \c entry_list, and declare an instance of it named
181  * \a entries, all intended to hold a list of type \c struct \c entry.
182  * \since 1.6.1
183  */
184 #define AST_RWDLLIST_HEAD(name, type) \
185  struct name { \
186  struct type *first; \
187  struct type *last; \
188  ast_rwlock_t lock; \
189  }
190 
191 /*!
192  * \brief Defines a structure to be used to hold a list of specified type (with no lock).
193  * \param name This will be the name of the defined structure.
194  * \param type This is the type of each list entry.
195  *
196  * This macro creates a structure definition that can be used
197  * to hold a list of the entries of type \a type. It does not actually
198  * declare (allocate) a structure; to do that, either follow this
199  * macro with the desired name of the instance you wish to declare,
200  * or use the specified \a name to declare instances elsewhere.
201  *
202  * Example usage:
203  * \code
204  * static AST_DLLIST_HEAD_NOLOCK(entry_list, entry) entries;
205  * \endcode
206  *
207  * This would define \c struct \c entry_list, and declare an instance of it named
208  * \a entries, all intended to hold a list of type \c struct \c entry.
209  * \since 1.6.1
210  */
211 #define AST_DLLIST_HEAD_NOLOCK(name, type) \
212  struct name { \
213  struct type *first; \
214  struct type *last; \
215  }
216 
217 /*!
218  * \brief Defines initial values for a declaration of AST_DLLIST_HEAD
219  * \since 1.6.1
220  */
221 #define AST_DLLIST_HEAD_INIT_VALUE \
222  { \
223  .first = NULL, \
224  .last = NULL, \
225  .lock = AST_MUTEX_INIT_VALUE, \
226  }
227 
228 /*!
229  * \brief Defines initial values for a declaration of AST_RWDLLIST_HEAD
230  * \since 1.6.1
231  */
232 #define AST_RWDLLIST_HEAD_INIT_VALUE \
233  { \
234  .first = NULL, \
235  .last = NULL, \
236  .lock = AST_RWLOCK_INIT_VALUE, \
237  }
238 
239 /*!
240  * \brief Defines initial values for a declaration of AST_DLLIST_HEAD_NOLOCK
241  * \since 1.6.1
242  */
243 #define AST_DLLIST_HEAD_NOLOCK_INIT_VALUE \
244  { \
245  .first = NULL, \
246  .last = NULL, \
247  }
248 
249 /*!
250  * \brief Defines a structure to be used to hold a list of specified type, statically initialized.
251  * \param name This will be the name of the defined structure.
252  * \param type This is the type of each list entry.
253  *
254  * This macro creates a structure definition that can be used
255  * to hold a list of the entries of type \a type, and allocates an instance
256  * of it, initialized to be empty.
257  *
258  * Example usage:
259  * \code
260  * static AST_DLLIST_HEAD_STATIC(entry_list, entry);
261  * \endcode
262  *
263  * This would define \c struct \c entry_list, intended to hold a list of
264  * type \c struct \c entry.
265  * \since 1.6.1
266  */
267 #if defined(AST_MUTEX_INIT_W_CONSTRUCTORS)
268 #define AST_DLLIST_HEAD_STATIC(name, type) \
269  struct name { \
270  struct type *first; \
271  struct type *last; \
272  ast_mutex_t lock; \
273  } name; \
274  static void __attribute__((constructor)) __init_##name(void) \
275  { \
276  AST_DLLIST_HEAD_INIT(&name); \
277  } \
278  static void __attribute__((destructor)) __fini_##name(void) \
279  { \
280  AST_DLLIST_HEAD_DESTROY(&name); \
281  } \
282  struct __dummy_##name
283 #else
284 #define AST_DLLIST_HEAD_STATIC(name, type) \
285  struct name { \
286  struct type *first; \
287  struct type *last; \
288  ast_mutex_t lock; \
289  } name = AST_DLLIST_HEAD_INIT_VALUE
290 #endif
291 
292 /*!
293  * \brief Defines a structure to be used to hold a read/write list of specified type, statically initialized.
294  * \param name This will be the name of the defined structure.
295  * \param type This is the type of each list entry.
296  *
297  * This macro creates a structure definition that can be used
298  * to hold a list of the entries of type \a type, and allocates an instance
299  * of it, initialized to be empty.
300  *
301  * Example usage:
302  * \code
303  * static AST_RWDLLIST_HEAD_STATIC(entry_list, entry);
304  * \endcode
305  *
306  * This would define \c struct \c entry_list, intended to hold a list of
307  * type \c struct \c entry.
308  * \since 1.6.1
309  */
310 #ifndef HAVE_PTHREAD_RWLOCK_INITIALIZER
311 #define AST_RWDLLIST_HEAD_STATIC(name, type) \
312  struct name { \
313  struct type *first; \
314  struct type *last; \
315  ast_rwlock_t lock; \
316  } name; \
317  static void __attribute__((constructor)) __init_##name(void) \
318  { \
319  AST_RWDLLIST_HEAD_INIT(&name); \
320  } \
321  static void __attribute__((destructor)) __fini_##name(void) \
322  { \
323  AST_RWDLLIST_HEAD_DESTROY(&name); \
324  } \
325  struct __dummy_##name
326 #else
327 #define AST_RWDLLIST_HEAD_STATIC(name, type) \
328  struct name { \
329  struct type *first; \
330  struct type *last; \
331  ast_rwlock_t lock; \
332  } name = AST_RWDLLIST_HEAD_INIT_VALUE
333 #endif
334 
335 /*!
336  * \brief Defines a structure to be used to hold a list of specified type, statically initialized.
337  *
338  * This is the same as AST_DLLIST_HEAD_STATIC, except without the lock included.
339  * \since 1.6.1
340  */
341 #define AST_DLLIST_HEAD_NOLOCK_STATIC(name, type) \
342  struct name { \
343  struct type *first; \
344  struct type *last; \
345  } name = AST_DLLIST_HEAD_NOLOCK_INIT_VALUE
346 
347 /*!
348  * \brief Initializes a list head structure with a specified first entry.
349  * \param head This is a pointer to the list head structure
350  * \param entry pointer to the list entry that will become the head of the list
351  *
352  * This macro initializes a list head structure by setting the head
353  * entry to the supplied value and recreating the embedded lock.
354  * \since 1.6.1
355  */
356 #define AST_DLLIST_HEAD_SET(head, entry) \
357  do { \
358  (head)->first = (entry); \
359  (head)->last = (entry); \
360  ast_mutex_init(&(head)->lock); \
361  } while (0)
362 
363 /*!
364  * \brief Initializes an rwlist head structure with a specified first entry.
365  * \param head This is a pointer to the list head structure
366  * \param entry pointer to the list entry that will become the head of the list
367  *
368  * This macro initializes a list head structure by setting the head
369  * entry to the supplied value and recreating the embedded lock.
370  * \since 1.6.1
371  */
372 #define AST_RWDLLIST_HEAD_SET(head, entry) \
373  do { \
374  (head)->first = (entry); \
375  (head)->last = (entry); \
376  ast_rwlock_init(&(head)->lock); \
377  } while (0)
378 
379 /*!
380  * \brief Initializes a list head structure with a specified first entry.
381  * \param head This is a pointer to the list head structure
382  * \param entry pointer to the list entry that will become the head of the list
383  *
384  * This macro initializes a list head structure by setting the head
385  * entry to the supplied value.
386  * \since 1.6.1
387  */
388 #define AST_DLLIST_HEAD_SET_NOLOCK(head, entry) \
389  do { \
390  (head)->first = (entry); \
391  (head)->last = (entry); \
392  } while (0)
393 
394 /*!
395  * \brief Declare previous/forward links inside a list entry.
396  * \param type This is the type of each list entry.
397  *
398  * This macro declares a structure to be used to doubly link list entries together.
399  * It must be used inside the definition of the structure named in
400  * \a type, as follows:
401  *
402  * \code
403  * struct list_entry {
404  * ...
405  * AST_DLLIST_ENTRY(list_entry) list;
406  * }
407  * \endcode
408  *
409  * The field name \a list here is arbitrary, and can be anything you wish.
410  * \since 1.6.1
411  */
412 #define AST_DLLIST_ENTRY(type) AST_DLLIST_HEAD_NOLOCK(, type)
413 
414 #define AST_RWDLLIST_ENTRY AST_DLLIST_ENTRY
415 
416 /*!
417  * \brief Returns the first entry contained in a list.
418  * \param head This is a pointer to the list head structure
419  * \since 1.6.1
420  */
421 #define AST_DLLIST_FIRST(head) ((head)->first)
422 
423 #define AST_RWDLLIST_FIRST AST_DLLIST_FIRST
424 
425 /*!
426  * \brief Returns the last entry contained in a list.
427  * \param head This is a pointer to the list head structure
428  * \since 1.6.1
429  */
430 #define AST_DLLIST_LAST(head) ((head)->last)
431 
432 #define AST_RWDLLIST_LAST AST_DLLIST_LAST
433 
434 #define AST_DLLIST_NEXT_DIRECTION(elm, field, direction) ((elm)->field.direction)
435 
436 #define AST_RWDLLIST_NEXT_DIRECTION AST_DLLIST_NEXT_DIRECTION
437 
438 /*!
439  * \brief Returns the next entry in the list after the given entry.
440  * \param elm This is a pointer to the current entry.
441  * \param field This is the name of the field (declared using AST_DLLIST_ENTRY())
442  * used to link entries of this list together.
443  * \since 1.6.1
444  */
445 #define AST_DLLIST_NEXT(elm, field) AST_DLLIST_NEXT_DIRECTION(elm, field, first)
446 
447 #define AST_RWDLLIST_NEXT AST_DLLIST_NEXT
448 
449 /*!
450  * \brief Returns the previous entry in the list before the given entry.
451  * \param elm This is a pointer to the current entry.
452  * \param field This is the name of the field (declared using AST_DLLIST_ENTRY())
453  * used to link entries of this list together.
454  * \since 1.6.1
455  */
456 #define AST_DLLIST_PREV(elm, field) AST_DLLIST_NEXT_DIRECTION(elm, field, last)
457 
458 #define AST_RWDLLIST_PREV AST_DLLIST_PREV
459 
460 /*!
461  * \brief Checks whether the specified list contains any entries.
462  * \param head This is a pointer to the list head structure
463  *
464  * \return non-zero if the list has entries
465  * \return zero if not.
466  * \since 1.6.1
467  */
468 #define AST_DLLIST_EMPTY(head) (AST_DLLIST_FIRST(head) == NULL)
469 
470 #define AST_RWDLLIST_EMPTY AST_DLLIST_EMPTY
471 
472 /*!
473  * \brief Checks whether the specified list contains the element.
474  * \param head This is a pointer to the list head structure
475  * \param elm This is a pointer to the list element to see if in list.
476  * \param field List node field for the next node information.
477  *
478  * \return elm if the list has elm in it.
479  * \return NULL if not.
480  * \since 11
481  */
482 #define AST_DLLIST_IS_MEMBER(head, elm, field) \
483  ({ \
484  typeof((head)->first) __cur; \
485  typeof((elm)) __elm = (elm); \
486  if (!__elm) { \
487  __cur = NULL; \
488  } else { \
489  __cur = (head)->first; \
490  while (__cur && __cur != __elm) { \
491  __cur = __cur->field.first; \
492  } \
493  } \
494  __cur; \
495  })
496 
497 #define AST_RWDLLIST_IS_MEMBER AST_DLLIST_IS_MEMBER
498 
499 /*!
500  * \brief Traverse a doublly linked list using the specified direction list.
501  *
502  * \param head List head structure pointer.
503  * \param var This is the name of the variable that will hold a pointer to the
504  * current list node on each iteration. It must be declared before calling
505  * this macro.
506  * \param field List node field for the next node information. (declared using AST_DLLIST_ENTRY())
507  * \param start Specified list node to start traversal: first or last
508  *
509  * This macro is use to loop over (traverse) the nodes in a list. It uses a
510  * \a for loop, and supplies the enclosed code with a pointer to each list
511  * node as it loops. It is typically used as follows:
512  * \code
513  * static AST_DLLIST_HEAD(entry_list, list_entry) entries;
514  * ...
515  * struct list_entry {
516  * ...
517  * AST_DLLIST_ENTRY(list_entry) list;
518  * }
519  * ...
520  * struct list_entry *current;
521  * ...
522  * AST_DLLIST_TRAVERSE_DIRECTION(&entries, current, list, first) {
523  * (do something with current here (travers list in forward direction))
524  * }
525  * ...
526  * AST_DLLIST_TRAVERSE_DIRECTION(&entries, current, list, last) {
527  * (do something with current here (travers list in reverse direction))
528  * }
529  * \endcode
530  *
531  * \since 11
532  */
533 #define AST_DLLIST_TRAVERSE_DIRECTION(head, var, field, start) \
534  for ((var) = (head)->start; (var); (var) = AST_DLLIST_NEXT_DIRECTION(var, field, start))
535 
536 #define AST_RWDLLIST_TRAVERSE_DIRECTION AST_DLLIST_TRAVERSE_DIRECTION
537 
538 /*!
539  * \brief Loops over (traverses) the entries in a list.
540  * \param head This is a pointer to the list head structure
541  * \param var This is the name of the variable that will hold a pointer to the
542  * current list entry on each iteration. It must be declared before calling
543  * this macro.
544  * \param field This is the name of the field (declared using AST_DLLIST_ENTRY())
545  * used to link entries of this list together.
546  *
547  * This macro is use to loop over (traverse) the entries in a list. It uses a
548  * \a for loop, and supplies the enclosed code with a pointer to each list
549  * entry as it loops. It is typically used as follows:
550  * \code
551  * static AST_DLLIST_HEAD(entry_list, list_entry) entries;
552  * ...
553  * struct list_entry {
554  * ...
555  * AST_DLLIST_ENTRY(list_entry) list;
556  * }
557  * ...
558  * struct list_entry *current;
559  * ...
560  * AST_DLLIST_TRAVERSE(&entries, current, list) {
561  * (do something with current here)
562  * }
563  * \endcode
564  * \warning If you modify the forward-link pointer contained in the \a current entry while
565  * inside the loop, the behavior will be unpredictable. At a minimum, the following
566  * macros will modify the forward-link pointer, and should not be used inside
567  * AST_DLLIST_TRAVERSE() against the entry pointed to by the \a current pointer without
568  * careful consideration of their consequences:
569  * \li AST_DLLIST_NEXT() (when used as an lvalue)
570  * \li AST_DLLIST_INSERT_AFTER()
571  * \li AST_DLLIST_INSERT_HEAD()
572  * \li AST_DLLIST_INSERT_TAIL()
573  * \since 1.6.1
574  */
575 #define AST_DLLIST_TRAVERSE(head,var,field) \
576  AST_DLLIST_TRAVERSE_DIRECTION(head, var, field, first)
577 
578 #define AST_RWDLLIST_TRAVERSE AST_DLLIST_TRAVERSE
579 
580 /*!
581  * \brief Loops over (traverses) the entries in a list in reverse order, starting at the end.
582  * \param head This is a pointer to the list head structure
583  * \param var This is the name of the variable that will hold a pointer to the
584  * current list entry on each iteration. It must be declared before calling
585  * this macro.
586  * \param field This is the name of the field (declared using AST_DLLIST_ENTRY())
587  * used to link entries of this list together.
588  *
589  * This macro is use to loop over (traverse) the entries in a list in reverse order. It uses a
590  * \a for loop, and supplies the enclosed code with a pointer to each list
591  * entry as it loops. It is typically used as follows:
592  * \code
593  * static AST_DLLIST_HEAD(entry_list, list_entry) entries;
594  * ...
595  * struct list_entry {
596  * ...
597  * AST_DLLIST_ENTRY(list_entry) list;
598  * }
599  * ...
600  * struct list_entry *current;
601  * ...
602  * AST_DLLIST_TRAVERSE_BACKWARDS(&entries, current, list) {
603  * (do something with current here)
604  * }
605  * \endcode
606  * \warning If you modify the forward-link pointer contained in the \a current entry while
607  * inside the loop, the behavior will be unpredictable. At a minimum, the following
608  * macros will modify the forward-link pointer, and should not be used inside
609  * AST_DLLIST_TRAVERSE() against the entry pointed to by the \a current pointer without
610  * careful consideration of their consequences:
611  * \li AST_DLLIST_PREV() (when used as an lvalue)
612  * \li AST_DLLIST_INSERT_BEFORE()
613  * \li AST_DLLIST_INSERT_HEAD()
614  * \li AST_DLLIST_INSERT_TAIL()
615  * \since 1.6.1
616  */
617 #define AST_DLLIST_TRAVERSE_BACKWARDS(head,var,field) \
618  AST_DLLIST_TRAVERSE_DIRECTION(head, var, field, last)
619 
620 #define AST_RWDLLIST_TRAVERSE_BACKWARDS AST_DLLIST_TRAVERSE_BACKWARDS
621 
622 /*!
623  * \brief Safe traversal of a doublly linked list using the specified direction list.
624  *
625  * \param head List head structure pointer.
626  * \param var This is the name of the variable that will hold a pointer to the
627  * current list node on each iteration. It must be declared before calling
628  * this macro.
629  * \param field List node field for the next node information. (declared using AST_DLLIST_ENTRY())
630  * \param start Specified list node to start traversal: first or last
631  *
632  * This macro is used to safely loop over (traverse) the nodes in a list. It
633  * uses a \a for loop, and supplies the enclosed code with a pointer to each list
634  * node as it loops. It is typically used as follows:
635  *
636  * \code
637  * static AST_DLLIST_HEAD(entry_list, list_entry) entries;
638  * ...
639  * struct list_entry {
640  * ...
641  * AST_DLLIST_ENTRY(list_entry) list;
642  * }
643  * ...
644  * struct list_entry *current;
645  * ...
646  * AST_DLLIST_TRAVERSE_DIRECTION_SAFE_BEGIN(&entries, current, list, first) {
647  * (do something with current here (travers list in forward direction))
648  * }
649  * ...
650  * AST_DLLIST_TRAVERSE_DIRECTION_SAFE_BEGIN(&entries, current, list, last) {
651  * (do something with current here (travers list in reverse direction))
652  * }
653  * AST_DLLIST_TRAVERSE_DIRECTION_SAFE_END;
654  * \endcode
655  *
656  * It differs from AST_DLLIST_TRAVERSE() in that the code inside the loop can modify
657  * (or even free, after calling AST_DLLIST_REMOVE_CURRENT()) the entry pointed to by
658  * the \a current pointer without affecting the loop traversal.
659  *
660  * \since 11
661  */
662 #define AST_DLLIST_TRAVERSE_DIRECTION_SAFE_BEGIN(head, var, field, start) \
663  do { \
664  typeof((head)) __list_head = (head); \
665  typeof(__list_head->first) __list_current; \
666  typeof(__list_head->first) __list_first; \
667  typeof(__list_head->first) __list_last; \
668  typeof(__list_head->first) __list_next; \
669  for ((var) = __list_head->start, \
670  __list_current = (var), \
671  __list_first = (var) ? (var)->field.first : NULL, \
672  __list_last = (var) ? (var)->field.last : NULL, \
673  __list_next = (var) ? AST_DLLIST_NEXT_DIRECTION(var, field, start) : NULL; \
674  (var); \
675  (void) __list_current,/* To quiet compiler? */ \
676  (void) __list_first,/* To quiet compiler? */ \
677  (void) __list_last,/* To quiet compiler? */ \
678  (var) = __list_next, \
679  __list_current = (var), \
680  __list_first = (var) ? (var)->field.first : NULL, \
681  __list_last = (var) ? (var)->field.last : NULL, \
682  __list_next = (var) ? AST_DLLIST_NEXT_DIRECTION(var, field, start) : NULL \
683  )
684 
685 #define AST_RWDLLIST_TRAVERSE_DIRECTION_SAFE_BEGIN AST_DLLIST_TRAVERSE_DIRECTION_SAFE_BEGIN
686 
687 /*!
688  * \brief Inserts a list node before the current node during a traversal.
689  * \param elm This is a pointer to the entry to be inserted.
690  * \param field This is the name of the field (declared using AST_DLLIST_ENTRY())
691  * used to link nodes of this list together.
692  *
693  * \since 1.6.1
694  */
695 #define AST_DLLIST_INSERT_BEFORE_CURRENT(elm, field) \
696  do { \
697  typeof((elm)) __elm = (elm); \
698  __elm->field.last = __list_last; \
699  __elm->field.first = __list_current; \
700  if (__list_head->first == __list_current) { \
701  __list_head->first = __elm; \
702  } else { \
703  __list_last->field.first = __elm; \
704  } \
705  __list_current->field.last = __elm; \
706  if (__list_next == __list_last) { \
707  __list_next = __elm; \
708  } \
709  __list_last = __elm; \
710  } while (0)
711 
712 #define AST_RWDLLIST_INSERT_BEFORE_CURRENT AST_DLLIST_INSERT_BEFORE_CURRENT
713 
714 /*!
715  * \brief Inserts a list node after the current node during a traversal.
716  * \param elm This is a pointer to the node to be inserted.
717  * \param field This is the name of the field (declared using AST_DLLIST_ENTRY())
718  * used to link nodes of this list together.
719  *
720  * \since 11
721  */
722 #define AST_DLLIST_INSERT_AFTER_CURRENT(elm, field) \
723  do { \
724  typeof((elm)) __elm = (elm); \
725  __elm->field.first = __list_first; \
726  __elm->field.last = __list_current; \
727  if (__list_head->last == __list_current) { \
728  __list_head->last = __elm; \
729  } else { \
730  __list_first->field.last = __elm; \
731  } \
732  __list_current->field.first = __elm; \
733  if (__list_next == __list_first) { \
734  __list_next = __elm; \
735  } \
736  __list_first = __elm; \
737  } while (0)
738 
739 #define AST_RWDLLIST_INSERT_AFTER_CURRENT AST_DLLIST_INSERT_AFTER_CURRENT
740 
741 /*!
742  * \brief Removes the \a current entry from a list during a traversal.
743  * \param field This is the name of the field (declared using AST_DLLIST_ENTRY())
744  * used to link entries of this list together.
745  *
746  * \note This macro can \b only be used inside an AST_DLLIST_TRAVERSE_SAFE_BEGIN()
747  * block; it is used to unlink the current entry from the list without affecting
748  * the list traversal (and without having to re-traverse the list to modify the
749  * previous entry, if any).
750  * \since 1.6.1
751  */
752 #define AST_DLLIST_REMOVE_CURRENT(field) \
753  do { \
754  if (__list_first) { \
755  __list_first->field.last = __list_last; \
756  } else { \
757  __list_head->last = __list_last; \
758  } \
759  if (__list_last) { \
760  __list_last->field.first = __list_first; \
761  } else { \
762  __list_head->first = __list_first; \
763  } \
764  __list_current->field.first = NULL; \
765  __list_current->field.last = NULL; \
766  __list_current = NULL; \
767  } while (0)
768 
769 #define AST_RWDLLIST_REMOVE_CURRENT AST_DLLIST_REMOVE_CURRENT
770 
771 /*!
772  * \brief Move the current list entry to another list at the tail.
773  *
774  * \note This is a silly macro. It should be done explicitly
775  * otherwise the field parameter must be the same for the two
776  * lists.
777  *
778  * AST_DLLIST_REMOVE_CURRENT(field);
779  * AST_DLLIST_INSERT_TAIL(newhead, var, other_field);
780  */
781 #define AST_DLLIST_MOVE_CURRENT(newhead, field) \
782  do { \
783  typeof ((newhead)->first) __list_cur = __list_current; \
784  AST_DLLIST_REMOVE_CURRENT(field); \
785  AST_DLLIST_INSERT_TAIL((newhead), __list_cur, field); \
786  } while (0)
787 
788 #define AST_RWDLLIST_MOVE_CURRENT AST_DLLIST_MOVE_CURRENT
789 
790 /*!
791  * \brief Move the current list entry to another list at the head.
792  *
793  * \note This is a silly macro. It should be done explicitly
794  * otherwise the field parameter must be the same for the two
795  * lists.
796  *
797  * AST_DLLIST_REMOVE_CURRENT(field);
798  * AST_DLLIST_INSERT_HEAD(newhead, var, other_field);
799  */
800 #define AST_DLLIST_MOVE_CURRENT_BACKWARDS(newhead, field) \
801  do { \
802  typeof ((newhead)->first) __list_cur = __list_current; \
803  AST_DLLIST_REMOVE_CURRENT(field); \
804  AST_DLLIST_INSERT_HEAD((newhead), __list_cur, field); \
805  } while (0)
806 
807 #define AST_RWDLLIST_MOVE_CURRENT_BACKWARDS AST_DLLIST_MOVE_CURRENT_BACKWARDS
808 
809 #define AST_DLLIST_TRAVERSE_DIRECTION_SAFE_END \
810  } while (0)
811 
812 #define AST_RWDLLIST_TRAVERSE_DIRECTION_SAFE_END AST_DLLIST_TRAVERSE_DIRECTION_SAFE_END
813 
814 /*!
815  * \brief Loops safely over (traverses) the entries in a list.
816  * \param head This is a pointer to the list head structure
817  * \param var This is the name of the variable that will hold a pointer to the
818  * current list entry on each iteration. It must be declared before calling
819  * this macro.
820  * \param field This is the name of the field (declared using AST_DLLIST_ENTRY())
821  * used to link entries of this list together.
822  *
823  * This macro is used to safely loop over (traverse) the entries in a list. It
824  * uses a \a for loop, and supplies the enclosed code with a pointer to each list
825  * entry as it loops. It is typically used as follows:
826  *
827  * \code
828  * static AST_DLLIST_HEAD(entry_list, list_entry) entries;
829  * ...
830  * struct list_entry {
831  * ...
832  * AST_DLLIST_ENTRY(list_entry) list;
833  * }
834  * ...
835  * struct list_entry *current;
836  * ...
837  * AST_DLLIST_TRAVERSE_SAFE_BEGIN(&entries, current, list) {
838  * (do something with current here)
839  * }
840  * AST_DLLIST_TRAVERSE_SAFE_END;
841  * \endcode
842  *
843  * It differs from AST_DLLIST_TRAVERSE() in that the code inside the loop can modify
844  * (or even free, after calling AST_DLLIST_REMOVE_CURRENT()) the entry pointed to by
845  * the \a current pointer without affecting the loop traversal.
846  * \since 1.6.1
847  */
848 #define AST_DLLIST_TRAVERSE_SAFE_BEGIN(head, var, field) \
849  AST_DLLIST_TRAVERSE_DIRECTION_SAFE_BEGIN(head, var, field, first)
850 
851 #define AST_RWDLLIST_TRAVERSE_SAFE_BEGIN AST_DLLIST_TRAVERSE_SAFE_BEGIN
852 
853 /*!
854  * \brief Loops safely over (traverses) the entries in a list.
855  * \param head This is a pointer to the list head structure
856  * \param var This is the name of the variable that will hold a pointer to the
857  * current list entry on each iteration. It must be declared before calling
858  * this macro.
859  * \param field This is the name of the field (declared using AST_DLLIST_ENTRY())
860  * used to link entries of this list together.
861  *
862  * This macro is used to safely loop over (traverse) the entries in a list. It
863  * uses a \a for loop, and supplies the enclosed code with a pointer to each list
864  * entry as it loops. It is typically used as follows:
865  *
866  * \code
867  * static AST_DLLIST_HEAD(entry_list, list_entry) entries;
868  * ...
869  * struct list_entry {
870  * ...
871  * AST_DLLIST_ENTRY(list_entry) list;
872  * }
873  * ...
874  * struct list_entry *current;
875  * ...
876  * AST_DLLIST_TRAVERSE_SAFE_BEGIN(&entries, current, list) {
877  * (do something with current here)
878  * }
879  * AST_DLLIST_TRAVERSE_SAFE_END;
880  * \endcode
881  *
882  * It differs from AST_DLLIST_TRAVERSE() in that the code inside the loop can modify
883  * (or even free, after calling AST_DLLIST_REMOVE_CURRENT()) the entry pointed to by
884  * the \a current pointer without affecting the loop traversal.
885  * \since 1.6.1
886  */
887 #define AST_DLLIST_TRAVERSE_BACKWARDS_SAFE_BEGIN(head, var, field) \
888  AST_DLLIST_TRAVERSE_DIRECTION_SAFE_BEGIN(head, var, field, last)
889 
890 #define AST_RWDLLIST_TRAVERSE_BACKWARDS_SAFE_BEGIN AST_DLLIST_TRAVERSE_BACKWARDS_SAFE_BEGIN
891 
892 /*!
893  * \brief Inserts a list entry after the current entry during a backwards traversal. Since
894  * this is a backwards traversal, this will insert the entry AFTER the current
895  * element. Since this is a backwards traveral, though, this would be BEFORE
896  * the current entry in traversal order. Confusing?
897  * \param elm This is a pointer to the entry to be inserted.
898  * \param field This is the name of the field (declared using AST_DLLIST_ENTRY())
899  * used to link entries of this list together.
900  *
901  * \since 1.6.1
902  */
903 #define AST_DLLIST_INSERT_BEFORE_CURRENT_BACKWARDS(elm, field) \
904  AST_DLLIST_INSERT_AFTER_CURRENT(elm, field)
905 
906 #define AST_RWDLLIST_INSERT_BEFORE_CURRENT_BACKWARDS AST_DLLIST_INSERT_BEFORE_CURRENT_BACKWARDS
907 
908 /*!
909  * \brief Closes a safe loop traversal block.
910  * \since 1.6.1
911  */
912 #define AST_DLLIST_TRAVERSE_SAFE_END AST_DLLIST_TRAVERSE_DIRECTION_SAFE_END
913 
914 #define AST_RWDLLIST_TRAVERSE_SAFE_END AST_DLLIST_TRAVERSE_SAFE_END
915 
916 /*!
917  * \brief Closes a safe loop traversal block.
918  * \since 1.6.1
919  */
920 #define AST_DLLIST_TRAVERSE_BACKWARDS_SAFE_END AST_DLLIST_TRAVERSE_DIRECTION_SAFE_END
921 
922 #define AST_RWDLLIST_TRAVERSE_BACKWARDS_SAFE_END AST_DLLIST_TRAVERSE_BACKWARDS_SAFE_END
923 
924 /*!
925  * \brief Initializes a list head structure.
926  * \param head This is a pointer to the list head structure
927  *
928  * This macro initializes a list head structure by setting the head
929  * entry to \a NULL (empty list) and recreating the embedded lock.
930  * \since 1.6.1
931  */
932 #define AST_DLLIST_HEAD_INIT(head) \
933  { \
934  (head)->first = NULL; \
935  (head)->last = NULL; \
936  ast_mutex_init(&(head)->lock); \
937  }
938 
939 /*!
940  * \brief Initializes an rwlist head structure.
941  * \param head This is a pointer to the list head structure
942  *
943  * This macro initializes a list head structure by setting the head
944  * entry to \a NULL (empty list) and recreating the embedded lock.
945  * \since 1.6.1
946  */
947 #define AST_RWDLLIST_HEAD_INIT(head) \
948  { \
949  (head)->first = NULL; \
950  (head)->last = NULL; \
951  ast_rwlock_init(&(head)->lock); \
952  }
953 
954 /*!
955  * \brief Destroys a list head structure.
956  * \param head This is a pointer to the list head structure
957  *
958  * This macro destroys a list head structure by setting the head
959  * entry to \a NULL (empty list) and destroying the embedded lock.
960  * It does not free the structure from memory.
961  * \since 1.6.1
962  */
963 #define AST_DLLIST_HEAD_DESTROY(head) \
964  { \
965  (head)->first = NULL; \
966  (head)->last = NULL; \
967  ast_mutex_destroy(&(head)->lock); \
968  }
969 
970 /*!
971  * \brief Destroys an rwlist head structure.
972  * \param head This is a pointer to the list head structure
973  *
974  * This macro destroys a list head structure by setting the head
975  * entry to \a NULL (empty list) and destroying the embedded lock.
976  * It does not free the structure from memory.
977  * \since 1.6.1
978  */
979 #define AST_RWDLLIST_HEAD_DESTROY(head) \
980  { \
981  (head)->first = NULL; \
982  (head)->last = NULL; \
983  ast_rwlock_destroy(&(head)->lock); \
984  }
985 
986 /*!
987  * \brief Initializes a list head structure.
988  * \param head This is a pointer to the list head structure
989  *
990  * This macro initializes a list head structure by setting the head
991  * entry to \a NULL (empty list). There is no embedded lock handling
992  * with this macro.
993  * \since 1.6.1
994  */
995 #define AST_DLLIST_HEAD_INIT_NOLOCK(head) \
996  { \
997  (head)->first = NULL; \
998  (head)->last = NULL; \
999  }
1000 
1001 /*!
1002  * \brief Inserts a list entry after a given entry.
1003  * \param head This is a pointer to the list head structure
1004  * \param listelm This is a pointer to the entry after which the new entry should
1005  * be inserted.
1006  * \param elm This is a pointer to the entry to be inserted.
1007  * \param field This is the name of the field (declared using AST_DLLIST_ENTRY())
1008  * used to link entries of this list together.
1009  * \since 1.6.1
1010  */
1011 #define AST_DLLIST_INSERT_AFTER(head, listelm, elm, field) \
1012  do { \
1013  typeof((listelm)) __listelm = (listelm); \
1014  typeof((elm)) __elm = (elm); \
1015  __elm->field.first = __listelm->field.first; \
1016  __elm->field.last = __listelm; \
1017  if ((head)->last == __listelm) { \
1018  (head)->last = __elm; \
1019  } else { \
1020  __listelm->field.first->field.last = __elm; \
1021  } \
1022  __listelm->field.first = __elm; \
1023  } while (0)
1024 
1025 #define AST_RWDLLIST_INSERT_AFTER AST_DLLIST_INSERT_AFTER
1026 
1027 /*!
1028  * \brief Inserts a list entry before a given entry.
1029  * \param head This is a pointer to the list head structure
1030  * \param listelm This is a pointer to the entry before which the new entry should
1031  * be inserted.
1032  * \param elm This is a pointer to the entry to be inserted.
1033  * \param field This is the name of the field (declared using AST_DLLIST_ENTRY())
1034  * used to link entries of this list together.
1035  * \since 1.6.1
1036  */
1037 #define AST_DLLIST_INSERT_BEFORE(head, listelm, elm, field) \
1038  do { \
1039  typeof((listelm)) __listelm = (listelm); \
1040  typeof((elm)) __elm = (elm); \
1041  __elm->field.last = __listelm->field.last; \
1042  __elm->field.first = __listelm; \
1043  if ((head)->first == __listelm) { \
1044  (head)->first = __elm; \
1045  } else { \
1046  __listelm->field.last->field.first = __elm; \
1047  } \
1048  __listelm->field.last = __elm; \
1049  } while (0)
1050 
1051 #define AST_RWDLLIST_INSERT_BEFORE AST_DLLIST_INSERT_BEFORE
1052 
1053 /*!
1054  * \brief Inserts a list entry at the head of a list.
1055  * \param head This is a pointer to the list head structure
1056  * \param elm This is a pointer to the entry to be inserted.
1057  * \param field This is the name of the field (declared using AST_DLLIST_ENTRY())
1058  * used to link entries of this list together.
1059  * \since 1.6.1
1060  */
1061 #define AST_DLLIST_INSERT_HEAD(head, elm, field) \
1062  do { \
1063  typeof((elm)) __elm = (elm); \
1064  __elm->field.last = NULL; \
1065  __elm->field.first = (head)->first; \
1066  if (!(head)->first) { \
1067  (head)->last = __elm; \
1068  } else { \
1069  (head)->first->field.last = __elm; \
1070  } \
1071  (head)->first = __elm; \
1072  } while (0)
1073 
1074 #define AST_RWDLLIST_INSERT_HEAD AST_DLLIST_INSERT_HEAD
1075 
1076 /*!
1077  * \brief Appends a list entry to the tail of a list.
1078  * \param head This is a pointer to the list head structure
1079  * \param elm This is a pointer to the entry to be appended.
1080  * \param field This is the name of the field (declared using AST_DLLIST_ENTRY())
1081  * used to link entries of this list together.
1082  *
1083  * Note: The link field in the appended entry is \b not modified, so if it is
1084  * actually the head of a list itself, the entire list will be appended
1085  * temporarily (until the next AST_DLLIST_INSERT_TAIL is performed).
1086  * \since 1.6.1
1087  */
1088 #define AST_DLLIST_INSERT_TAIL(head, elm, field) \
1089  do { \
1090  typeof((elm)) __elm = (elm); \
1091  __elm->field.first = NULL; \
1092  if (!(head)->first) { \
1093  __elm->field.last = NULL; \
1094  (head)->first = __elm; \
1095  } else { \
1096  __elm->field.last = (head)->last; \
1097  (head)->last->field.first = __elm; \
1098  } \
1099  (head)->last = __elm; \
1100  } while (0)
1101 
1102 #define AST_RWDLLIST_INSERT_TAIL AST_DLLIST_INSERT_TAIL
1103 
1104 /*!
1105  * \brief Appends a whole list to the tail of a list.
1106  * \param head This is a pointer to the list head structure
1107  * \param list This is a pointer to the list to be appended.
1108  * \param field This is the name of the field (declared using AST_DLLIST_ENTRY())
1109  * used to link entries of this list together.
1110  *
1111  * Note: The source list (the \a list parameter) will be empty after
1112  * calling this macro (the list entries are \b moved to the target list).
1113  * \since 1.6.1
1114  */
1115 #define AST_DLLIST_APPEND_DLLIST(head, list, field) \
1116  do { \
1117  if (!(head)->first) { \
1118  (head)->first = (list)->first; \
1119  (head)->last = (list)->last; \
1120  } else { \
1121  (head)->last->field.first = (list)->first; \
1122  (list)->first->field.last = (head)->last; \
1123  (head)->last = (list)->last; \
1124  } \
1125  (list)->first = NULL; \
1126  (list)->last = NULL; \
1127  } while (0)
1128 
1129 #define AST_RWDLLIST_APPEND_DLLIST AST_DLLIST_APPEND_DLLIST
1130 
1131 /*!
1132  * \brief Removes and returns the head entry from a list.
1133  * \param head This is a pointer to the list head structure
1134  * \param field This is the name of the field (declared using AST_DLLIST_ENTRY())
1135  * used to link entries of this list together.
1136  *
1137  * Removes the head entry from the list, and returns a pointer to it.
1138  * This macro is safe to call on an empty list.
1139  * \since 1.6.1
1140  */
1141 #define AST_DLLIST_REMOVE_HEAD(head, field) \
1142  ({ \
1143  typeof((head)->first) cur = (head)->first; \
1144  if (cur) { \
1145  (head)->first = cur->field.first; \
1146  if ((head)->first) { \
1147  (head)->first->field.last = NULL; \
1148  } \
1149  cur->field.first = NULL; \
1150  cur->field.last = NULL; \
1151  if ((head)->last == cur) { \
1152  (head)->last = NULL; \
1153  } \
1154  } \
1155  cur; \
1156  })
1157 
1158 #define AST_RWDLLIST_REMOVE_HEAD AST_DLLIST_REMOVE_HEAD
1159 
1160 /*!
1161  * \brief Removes and returns the tail node from a list.
1162  * \param head This is a pointer to the list head structure
1163  * \param field This is the name of the field (declared using AST_DLLIST_ENTRY())
1164  * used to link nodes of this list together.
1165  *
1166  * Removes the tail entry from the list, and returns a pointer to it.
1167  * This macro is safe to call on an empty list.
1168  * \since 11
1169  */
1170 #define AST_DLLIST_REMOVE_TAIL(head, field) \
1171  ({ \
1172  typeof((head)->last) cur = (head)->last; \
1173  if (cur) { \
1174  (head)->last = cur->field.last; \
1175  if ((head)->last) { \
1176  (head)->last->field.first = NULL; \
1177  } \
1178  cur->field.first = NULL; \
1179  cur->field.last = NULL; \
1180  if ((head)->first == cur) { \
1181  (head)->first = NULL; \
1182  } \
1183  } \
1184  cur; \
1185  })
1186 
1187 #define AST_RWDLLIST_REMOVE_TAIL AST_DLLIST_REMOVE_TAIL
1188 
1189 /*!
1190  * \brief Removes a specific entry from a list.
1191  * \param head This is a pointer to the list head structure
1192  * \param elm This is a pointer to the entry to be removed.
1193  * \param field This is the name of the field (declared using AST_DLLIST_ENTRY())
1194  * used to link entries of this list together.
1195  * \warning The removed entry is \b not freed.
1196  * \since 1.6.1
1197  */
1198 #define AST_DLLIST_REMOVE(head, elm, field) \
1199  do { \
1200  typeof((elm)) __elm = (elm); \
1201  if (__elm) { \
1202  if (__elm->field.first) { \
1203  __elm->field.first->field.last = __elm->field.last; \
1204  } else { \
1205  (head)->last = __elm->field.last; \
1206  } \
1207  if (__elm->field.last) { \
1208  __elm->field.last->field.first = __elm->field.first; \
1209  } else { \
1210  (head)->first = __elm->field.first; \
1211  } \
1212  __elm->field.first = NULL; \
1213  __elm->field.last = NULL; \
1214  } \
1215  } while (0)
1216 
1217 #define AST_RWDLLIST_REMOVE AST_DLLIST_REMOVE
1218 
1219 /*!
1220  * \brief Removes a specific node from a list if it is in the list.
1221  * \param head This is a pointer to the list head structure
1222  * \param elm This is a pointer to the node to be removed.
1223  * \param field This is the name of the field (declared using AST_DLLIST_ENTRY())
1224  * used to link nodes of this list together.
1225  * \warning The removed node is \b not freed.
1226  * \return elm if the list had elm in it.
1227  * \return NULL if not.
1228  * \since 11
1229  */
1230 #define AST_DLLIST_REMOVE_VERIFY(head, elm, field) \
1231  ({ \
1232  typeof((elm)) __res = AST_DLLIST_IS_MEMBER(head, elm, field); \
1233  AST_DLLIST_REMOVE(head, __res, field); \
1234  __res; \
1235  })
1236 
1237 #define AST_RWDLLIST_REMOVE_VERIFY AST_DLLIST_REMOVE_VERIFY
1238 
1239 #endif /* _ASTERISK_DLINKEDLISTS_H */
Asterisk locking-related definitions: