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