headers: Consistent use of typeof and/or __typeof__.
[asterisk/asterisk.git] / include / asterisk / linkedlists.h
1 /*
2  * Asterisk -- An open source telephony toolkit.
3  *
4  * Copyright (C) 1999 - 2006, Digium, Inc.
5  *
6  * Mark Spencer <markster@digium.com>
7  * Kevin P. Fleming <kpfleming@digium.com>
8  *
9  * See http://www.asterisk.org for more information about
10  * the Asterisk project. Please do not directly contact
11  * any of the maintainers of this project for assistance;
12  * the project provides a web site, mailing lists and IRC
13  * channels for your use.
14  *
15  * This program is free software, distributed under the terms of
16  * the GNU General Public License Version 2. See the LICENSE file
17  * at the top of the source tree.
18  */
19
20 #ifndef ASTERISK_LINKEDLISTS_H
21 #define ASTERISK_LINKEDLISTS_H
22
23 #include "asterisk/lock.h"
24
25 /*!
26  * \file linkedlists.h
27  * \brief A set of macros to manage forward-linked lists.
28  */
29
30 /*!
31  * \brief Locks a list.
32  * \param head This is a pointer to the list head structure
33  *
34  * This macro attempts to place an exclusive lock in the
35  * list head structure pointed to by head.
36  * \retval 0 on success
37  * \retval non-zero on failure
38  */
39 #define AST_LIST_LOCK(head)                                             \
40         ast_mutex_lock(&(head)->lock)
41
42 /*!
43  * \brief Write locks a list.
44  * \param head This is a pointer to the list head structure
45  *
46  * This macro attempts to place an exclusive write lock in the
47  * list head structure pointed to by head.
48  * \retval 0 on success
49  * \retval non-zero on failure
50  */
51 #define AST_RWLIST_WRLOCK(head)                                         \
52         ast_rwlock_wrlock(&(head)->lock)
53
54 /*!
55  * \brief Write locks a list, with timeout.
56  * \param head This is a pointer to the list head structure
57  * \param ts Pointer to a timespec structure
58  *
59  * This macro attempts to place an exclusive write lock in the
60  * list head structure pointed to by head.
61  * \retval 0 on success
62  * \retval non-zero on failure
63  *
64  * \since 1.6.1
65  */
66 #define AST_RWLIST_TIMEDWRLOCK(head, ts)        ast_rwlock_timedwrlock(&(head)->lock, ts)
67
68 /*!
69  * \brief Read locks a list.
70  * \param head This is a pointer to the list head structure
71  *
72  * This macro attempts to place a read lock in the
73  * list head structure pointed to by head.
74  * \retval 0 on success
75  * \retval non-zero on failure
76  */
77 #define AST_RWLIST_RDLOCK(head)                                         \
78         ast_rwlock_rdlock(&(head)->lock)
79
80 /*!
81  * \brief Read locks a list, with timeout.
82  * \param head This is a pointer to the list head structure
83  * \param ts Pointer to a timespec structure
84  *
85  * This macro attempts to place a read lock in the
86  * list head structure pointed to by head.
87  * \retval 0 on success
88  * \retval non-zero on failure
89  *
90  * \since 1.6.1
91  */
92 #define AST_RWLIST_TIMEDRDLOCK(head, ts)                                 \
93         ast_rwlock_timedrdlock(&(head)->lock, ts)
94
95 /*!
96  * \brief Locks a list, without blocking if the list is locked.
97  * \param head This is a pointer to the list head structure
98  *
99  * This macro attempts to place an exclusive lock in the
100  * list head structure pointed to by head.
101  * \retval 0 on success
102  * \retval non-zero on failure
103  */
104 #define AST_LIST_TRYLOCK(head)                                          \
105         ast_mutex_trylock(&(head)->lock)
106
107 /*!
108  * \brief Write locks a list, without blocking if the list is locked.
109  * \param head This is a pointer to the list head structure
110  *
111  * This macro attempts to place an exclusive write lock in the
112  * list head structure pointed to by head.
113  * \retval 0 on success
114  * \retval non-zero on failure
115  */
116 #define AST_RWLIST_TRYWRLOCK(head)                                      \
117         ast_rwlock_trywrlock(&(head)->lock)
118
119 /*!
120  * \brief Read locks a list, without blocking if the list is locked.
121  * \param head This is a pointer to the list head structure
122  *
123  * This macro attempts to place a read lock in the
124  * list head structure pointed to by head.
125  * \retval 0 on success
126  * \retval non-zero on failure
127  */
128 #define AST_RWLIST_TRYRDLOCK(head)                                      \
129         ast_rwlock_tryrdlock(&(head)->lock)
130
131 /*!
132  * \brief Attempts to unlock a list.
133  * \param head This is a pointer to the list head structure
134  *
135  * This macro attempts to remove an exclusive lock from the
136  * list head structure pointed to by head. If the list
137  * was not locked by this thread, this macro has no effect.
138  */
139 #define AST_LIST_UNLOCK(head)                                           \
140         ast_mutex_unlock(&(head)->lock)
141
142 /*!
143  * \brief Attempts to unlock a read/write based list.
144  * \param head This is a pointer to the list head structure
145  *
146  * This macro attempts to remove a read or write lock from the
147  * list head structure pointed to by head. If the list
148  * was not locked by this thread, this macro has no effect.
149  */
150 #define AST_RWLIST_UNLOCK(head)                                         \
151         ast_rwlock_unlock(&(head)->lock)
152
153 /*!
154  * \brief Defines a structure to be used to hold a list of specified type.
155  * \param name This will be the name of the defined structure.
156  * \param type This is the type of each list entry.
157  *
158  * This macro creates a structure definition that can be used
159  * to hold a list of the entries of type \a type. It does not actually
160  * declare (allocate) a structure; to do that, either follow this
161  * macro with the desired name of the instance you wish to declare,
162  * or use the specified \a name to declare instances elsewhere.
163  *
164  * Example usage:
165  * \code
166  * static AST_LIST_HEAD(entry_list, entry) entries;
167  * \endcode
168  *
169  * This would define \c struct \c entry_list, and declare an instance of it named
170  * \a entries, all intended to hold a list of type \c struct \c entry.
171  */
172 #define AST_LIST_HEAD(name, type)                                       \
173 struct name {                                                           \
174         struct type *first;                                             \
175         struct type *last;                                              \
176         ast_mutex_t lock;                                               \
177 }
178
179 /*!
180  * \brief Defines a structure to be used to hold a read/write list of specified type.
181  * \param name This will be the name of the defined structure.
182  * \param type This is the type of each list entry.
183  *
184  * This macro creates a structure definition that can be used
185  * to hold a list of the entries of type \a type. It does not actually
186  * declare (allocate) a structure; to do that, either follow this
187  * macro with the desired name of the instance you wish to declare,
188  * or use the specified \a name to declare instances elsewhere.
189  *
190  * Example usage:
191  * \code
192  * static AST_RWLIST_HEAD(entry_list, entry) entries;
193  * \endcode
194  *
195  * This would define \c struct \c entry_list, and declare an instance of it named
196  * \a entries, all intended to hold a list of type \c struct \c entry.
197  */
198 #define AST_RWLIST_HEAD(name, type)                                     \
199 struct name {                                                           \
200         struct type *first;                                             \
201         struct type *last;                                              \
202         ast_rwlock_t lock;                                              \
203 }
204
205 /*!
206  * \brief Defines a structure to be used to hold a list of specified type (with no lock).
207  * \param name This will be the name of the defined structure.
208  * \param type This is the type of each list entry.
209  *
210  * This macro creates a structure definition that can be used
211  * to hold a list of the entries of type \a type. It does not actually
212  * declare (allocate) a structure; to do that, either follow this
213  * macro with the desired name of the instance you wish to declare,
214  * or use the specified \a name to declare instances elsewhere.
215  *
216  * Example usage:
217  * \code
218  * static AST_LIST_HEAD_NOLOCK(entry_list, entry) entries;
219  * \endcode
220  *
221  * This would define \c struct \c entry_list, and declare an instance of it named
222  * \a entries, all intended to hold a list of type \c struct \c entry.
223  */
224 #define AST_LIST_HEAD_NOLOCK(name, type)                                \
225 struct name {                                                           \
226         struct type *first;                                             \
227         struct type *last;                                              \
228 }
229
230 /*!
231  * \brief Defines initial values for a declaration of AST_LIST_HEAD
232  */
233 #define AST_LIST_HEAD_INIT_VALUE        {               \
234         .first = NULL,                                  \
235         .last = NULL,                                   \
236         .lock = AST_MUTEX_INIT_VALUE,                   \
237         }
238
239 /*!
240  * \brief Defines initial values for a declaration of AST_RWLIST_HEAD
241  */
242 #define AST_RWLIST_HEAD_INIT_VALUE      {               \
243         .first = NULL,                                  \
244         .last = NULL,                                   \
245         .lock = AST_RWLOCK_INIT_VALUE,                  \
246         }
247
248 /*!
249  * \brief Defines initial values for a declaration of AST_LIST_HEAD_NOLOCK
250  */
251 #define AST_LIST_HEAD_NOLOCK_INIT_VALUE {       \
252         .first = NULL,                                  \
253         .last = NULL,                                   \
254         }
255
256 /*!
257  * \brief Defines a structure to be used to hold a list of specified type, statically initialized.
258  * \param name This will be the name of the defined structure.
259  * \param type This is the type of each list entry.
260  *
261  * This macro creates a structure definition that can be used
262  * to hold a list of the entries of type \a type, and allocates an instance
263  * of it, initialized to be empty.
264  *
265  * Example usage:
266  * \code
267  * static AST_LIST_HEAD_STATIC(entry_list, entry);
268  * \endcode
269  *
270  * This would define \c struct \c entry_list, intended to hold a list of
271  * type \c struct \c entry.
272  */
273 #if defined(AST_MUTEX_INIT_W_CONSTRUCTORS)
274 #define AST_LIST_HEAD_STATIC(name, type)                                \
275 struct name {                                                           \
276         struct type *first;                                             \
277         struct type *last;                                              \
278         ast_mutex_t lock;                                               \
279 } name;                                                                 \
280 static void  __attribute__((constructor)) __init_##name(void)           \
281 {                                                                       \
282         AST_LIST_HEAD_INIT(&name);                                      \
283 }                                                                       \
284 static void  __attribute__((destructor)) __fini_##name(void)            \
285 {                                                                       \
286         AST_LIST_HEAD_DESTROY(&name);                                   \
287 }                                                                       \
288 struct __dummy_##name
289 #else
290 #define AST_LIST_HEAD_STATIC(name, type)                                \
291 struct name {                                                           \
292         struct type *first;                                             \
293         struct type *last;                                              \
294         ast_mutex_t lock;                                               \
295 } name = AST_LIST_HEAD_INIT_VALUE
296 #endif
297
298 /*!
299  * \brief Defines a structure to be used to hold a read/write list of specified type, statically initialized.
300  * \param name This will be the name of the defined structure.
301  * \param type This is the type of each list entry.
302  *
303  * This macro creates a structure definition that can be used
304  * to hold a list of the entries of type \a type, and allocates an instance
305  * of it, initialized to be empty.
306  *
307  * Example usage:
308  * \code
309  * static AST_RWLIST_HEAD_STATIC(entry_list, entry);
310  * \endcode
311  *
312  * This would define \c struct \c entry_list, intended to hold a list of
313  * type \c struct \c entry.
314  */
315 #ifndef HAVE_PTHREAD_RWLOCK_INITIALIZER
316 #define AST_RWLIST_HEAD_STATIC(name, type)                              \
317 struct name {                                                           \
318         struct type *first;                                             \
319         struct type *last;                                              \
320         ast_rwlock_t lock;                                              \
321 } name;                                                                 \
322 static void  __attribute__((constructor)) __init_##name(void)          \
323 {                                                                       \
324         AST_RWLIST_HEAD_INIT(&name);                                    \
325 }                                                                       \
326 static void  __attribute__((destructor)) __fini_##name(void)           \
327 {                                                                       \
328         AST_RWLIST_HEAD_DESTROY(&name);                                 \
329 }                                                                       \
330 struct __dummy_##name
331 #else
332 #define AST_RWLIST_HEAD_STATIC(name, type)                              \
333 struct name {                                                           \
334         struct type *first;                                             \
335         struct type *last;                                              \
336         ast_rwlock_t lock;                                              \
337 } name = AST_RWLIST_HEAD_INIT_VALUE
338 #endif
339
340 /*!
341  * \brief Defines a structure to be used to hold a list of specified type, statically initialized.
342  *
343  * This is the same as AST_LIST_HEAD_STATIC, except without the lock included.
344  */
345 #define AST_LIST_HEAD_NOLOCK_STATIC(name, type)                         \
346 struct name {                                                           \
347         struct type *first;                                             \
348         struct type *last;                                              \
349 } name = AST_LIST_HEAD_NOLOCK_INIT_VALUE
350
351 /*!
352  * \brief Initializes a list head structure with a specified first entry.
353  * \param head This is a pointer to the list head structure
354  * \param entry pointer to the list entry that will become the head of the list
355  *
356  * This macro initializes a list head structure by setting the head
357  * entry to the supplied value and recreating the embedded lock.
358  */
359 #define AST_LIST_HEAD_SET(head, entry) do {                             \
360         (head)->first = (entry);                                        \
361         (head)->last = (entry);                                         \
362         ast_mutex_init(&(head)->lock);                                  \
363 } while (0)
364
365 /*!
366  * \brief Initializes an rwlist head structure with a specified first entry.
367  * \param head This is a pointer to the list head structure
368  * \param entry pointer to the list entry that will become the head of the list
369  *
370  * This macro initializes a list head structure by setting the head
371  * entry to the supplied value and recreating the embedded lock.
372  */
373 #define AST_RWLIST_HEAD_SET(head, entry) 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  */
387 #define AST_LIST_HEAD_SET_NOLOCK(head, entry) do {                      \
388         (head)->first = (entry);                                        \
389         (head)->last = (entry);                                         \
390 } while (0)
391
392 /*!
393  * \brief Declare a forward link structure inside a list entry.
394  * \param type This is the type of each list entry.
395  *
396  * This macro declares a structure to be used to link list entries together.
397  * It must be used inside the definition of the structure named in
398  * \a type, as follows:
399  *
400  * \code
401  * struct list_entry {
402       ...
403       AST_LIST_ENTRY(list_entry) list;
404  * }
405  * \endcode
406  *
407  * The field name \a list here is arbitrary, and can be anything you wish.
408  */
409 #define AST_LIST_ENTRY(type)                                            \
410 struct {                                                                \
411         struct type *next;                                              \
412 }
413
414 #define AST_RWLIST_ENTRY AST_LIST_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  */
420 #define AST_LIST_FIRST(head)    ((head)->first)
421
422 #define AST_RWLIST_FIRST AST_LIST_FIRST
423
424 /*!
425  * \brief Returns the last entry contained in a list.
426  * \param head This is a pointer to the list head structure
427  */
428 #define AST_LIST_LAST(head)     ((head)->last)
429
430 #define AST_RWLIST_LAST AST_LIST_LAST
431
432 /*!
433  * \brief Returns the next entry in the list after the given entry.
434  * \param elm This is a pointer to the current entry.
435  * \param field This is the name of the field (declared using AST_LIST_ENTRY())
436  * used to link entries of this list together.
437  */
438 #define AST_LIST_NEXT(elm, field)       ((elm)->field.next)
439
440 #define AST_RWLIST_NEXT AST_LIST_NEXT
441
442 /*!
443  * \brief Checks whether the specified list contains any entries.
444  * \param head This is a pointer to the list head structure
445  *
446  * \return zero if the list has entries
447  * \return non-zero if not.
448  */
449 #define AST_LIST_EMPTY(head)    (AST_LIST_FIRST(head) == NULL)
450
451 #define AST_RWLIST_EMPTY AST_LIST_EMPTY
452
453 /*!
454  * \brief Loops over (traverses) the entries in a list.
455  * \param head This is a pointer to the list head structure
456  * \param var This is the name of the variable that will hold a pointer to the
457  * current list entry on each iteration. It must be declared before calling
458  * this macro.
459  * \param field This is the name of the field (declared using AST_LIST_ENTRY())
460  * used to link entries of this list together.
461  *
462  * This macro is use to loop over (traverse) the entries in a list. It uses a
463  * \a for loop, and supplies the enclosed code with a pointer to each list
464  * entry as it loops. It is typically used as follows:
465  * \code
466  * static AST_LIST_HEAD(entry_list, list_entry) entries;
467  * ...
468  * struct list_entry {
469       ...
470       AST_LIST_ENTRY(list_entry) list;
471  * }
472  * ...
473  * struct list_entry *current;
474  * ...
475  * AST_LIST_TRAVERSE(&entries, current, list) {
476      (do something with current here)
477  * }
478  * \endcode
479  * \warning If you modify the forward-link pointer contained in the \a current entry while
480  * inside the loop, the behavior will be unpredictable. At a minimum, the following
481  * macros will modify the forward-link pointer, and should not be used inside
482  * AST_LIST_TRAVERSE() against the entry pointed to by the \a current pointer without
483  * careful consideration of their consequences:
484  * \li AST_LIST_NEXT() (when used as an lvalue)
485  * \li AST_LIST_INSERT_AFTER()
486  * \li AST_LIST_INSERT_HEAD()
487  * \li AST_LIST_INSERT_TAIL()
488  * \li AST_LIST_INSERT_SORTALPHA()
489  */
490 #define AST_LIST_TRAVERSE(head,var,field)                               \
491         for((var) = (head)->first; (var); (var) = (var)->field.next)
492
493 #define AST_RWLIST_TRAVERSE AST_LIST_TRAVERSE
494
495 /*!
496  * \brief Loops safely over (traverses) the entries in a list.
497  * \param head This is a pointer to the list head structure
498  * \param var This is the name of the variable that will hold a pointer to the
499  * current list entry on each iteration. It must be declared before calling
500  * this macro.
501  * \param field This is the name of the field (declared using AST_LIST_ENTRY())
502  * used to link entries of this list together.
503  *
504  * This macro is used to safely loop over (traverse) the entries in a list. It
505  * uses a \a for loop, and supplies the enclosed code with a pointer to each list
506  * entry as it loops. It is typically used as follows:
507  *
508  * \code
509  * static AST_LIST_HEAD(entry_list, list_entry) entries;
510  * ...
511  * struct list_entry {
512       ...
513       AST_LIST_ENTRY(list_entry) list;
514  * }
515  * ...
516  * struct list_entry *current;
517  * ...
518  * AST_LIST_TRAVERSE_SAFE_BEGIN(&entries, current, list) {
519      (do something with current here)
520  * }
521  * AST_LIST_TRAVERSE_SAFE_END;
522  * \endcode
523  *
524  * It differs from AST_LIST_TRAVERSE() in that the code inside the loop can modify
525  * (or even free, after calling AST_LIST_REMOVE_CURRENT()) the entry pointed to by
526  * the \a current pointer without affecting the loop traversal.
527  */
528 #define AST_LIST_TRAVERSE_SAFE_BEGIN(head, var, field) {                                \
529         typeof((head)) __list_head = head;                                                                      \
530         typeof(__list_head->first) __list_next;                                                         \
531         typeof(__list_head->first) __list_prev = NULL;                                          \
532         typeof(__list_head->first) __list_current;                                                      \
533         for ((var) = __list_head->first,                                                                        \
534                 __list_current = (var),                                                                                 \
535                 __list_next = (var) ? (var)->field.next : NULL;                                 \
536                 (var);                                                                                                                  \
537                 __list_prev = __list_current,                                                                   \
538                 (var) = __list_next,                                                                                    \
539                 __list_current = (var),                                                                                 \
540                 __list_next = (var) ? (var)->field.next : NULL,                                 \
541                 (void) __list_prev /* To quiet compiler? */                                             \
542                 )
543
544 #define AST_RWLIST_TRAVERSE_SAFE_BEGIN AST_LIST_TRAVERSE_SAFE_BEGIN
545
546 /*!
547  * \brief Removes the \a current entry from a list during a traversal.
548  * \param field This is the name of the field (declared using AST_LIST_ENTRY())
549  * used to link entries of this list together.
550  *
551  * \note This macro can \b only be used inside an AST_LIST_TRAVERSE_SAFE_BEGIN()
552  * block; it is used to unlink the current entry from the list without affecting
553  * the list traversal (and without having to re-traverse the list to modify the
554  * previous entry, if any).
555  */
556 #define AST_LIST_REMOVE_CURRENT(field) do {                                                     \
557                 __list_current->field.next = NULL;                                                              \
558                 __list_current = __list_prev;                                                                   \
559                 if (__list_prev) {                                                                                              \
560                         __list_prev->field.next = __list_next;                                          \
561                 } else {                                                                                                                \
562                         __list_head->first = __list_next;                                                       \
563                 }                                                                                                                               \
564                 if (!__list_next) {                                                                                             \
565                         __list_head->last = __list_prev;                                                        \
566                 }                                                                                                                               \
567         } while (0)
568
569 #define AST_RWLIST_REMOVE_CURRENT AST_LIST_REMOVE_CURRENT
570
571 /*!
572  * \brief Move the current list entry to another list.
573  *
574  * \note This is a silly macro.  It should be done explicitly
575  * otherwise the field parameter must be the same for the two
576  * lists.
577  *
578  * AST_LIST_REMOVE_CURRENT(field);
579  * AST_LIST_INSERT_TAIL(newhead, var, other_field);
580  */
581 #define AST_LIST_MOVE_CURRENT(newhead, field) do {                      \
582         typeof ((newhead)->first) __extracted = __list_current; \
583         AST_LIST_REMOVE_CURRENT(field);                                                 \
584         AST_LIST_INSERT_TAIL((newhead), __extracted, field);    \
585         } while (0)
586
587 #define AST_RWLIST_MOVE_CURRENT AST_LIST_MOVE_CURRENT
588
589 /*!
590  * \brief Inserts a list entry before the current entry during a traversal.
591  * \param elm This is a pointer to the entry to be inserted.
592  * \param field This is the name of the field (declared using AST_LIST_ENTRY())
593  * used to link entries of this list together.
594  *
595  * \note This macro can \b only be used inside an AST_LIST_TRAVERSE_SAFE_BEGIN()
596  * block.
597  */
598 #define AST_LIST_INSERT_BEFORE_CURRENT(elm, field) do {         \
599         if (__list_prev) {                                                                              \
600                 (elm)->field.next = __list_prev->field.next;            \
601                 __list_prev->field.next = elm;                                          \
602         } else {                                                                                                \
603                 (elm)->field.next = __list_head->first;                         \
604                 __list_head->first = (elm);                                                     \
605         }                                                                                                               \
606         __list_prev = (elm);                                                                    \
607 } while (0)
608
609 #define AST_RWLIST_INSERT_BEFORE_CURRENT AST_LIST_INSERT_BEFORE_CURRENT
610
611 /*!
612  * \brief Closes a safe loop traversal block.
613  */
614 #define AST_LIST_TRAVERSE_SAFE_END  }
615
616 #define AST_RWLIST_TRAVERSE_SAFE_END AST_LIST_TRAVERSE_SAFE_END
617
618 /*!
619  * \brief Initializes a list head structure.
620  * \param head This is a pointer to the list head structure
621  *
622  * This macro initializes a list head structure by setting the head
623  * entry to \a NULL (empty list) and recreating the embedded lock.
624  */
625 #define AST_LIST_HEAD_INIT(head) {                                      \
626         (head)->first = NULL;                                           \
627         (head)->last = NULL;                                            \
628         ast_mutex_init(&(head)->lock);                                  \
629 }
630
631 /*!
632  * \brief Initializes an rwlist head structure.
633  * \param head This is a pointer to the list head structure
634  *
635  * This macro initializes a list head structure by setting the head
636  * entry to \a NULL (empty list) and recreating the embedded lock.
637  */
638 #define AST_RWLIST_HEAD_INIT(head) {                                    \
639         (head)->first = NULL;                                           \
640         (head)->last = NULL;                                            \
641         ast_rwlock_init(&(head)->lock);                                 \
642 }
643
644 /*!
645  * \brief Destroys a list head structure.
646  * \param head This is a pointer to the list head structure
647  *
648  * This macro destroys a list head structure by setting the head
649  * entry to \a NULL (empty list) and destroying the embedded lock.
650  * It does not free the structure from memory.
651  */
652 #define AST_LIST_HEAD_DESTROY(head) {                                   \
653         (head)->first = NULL;                                           \
654         (head)->last = NULL;                                            \
655         ast_mutex_destroy(&(head)->lock);                               \
656 }
657
658 /*!
659  * \brief Destroys an rwlist head structure.
660  * \param head This is a pointer to the list head structure
661  *
662  * This macro destroys a list head structure by setting the head
663  * entry to \a NULL (empty list) and destroying the embedded lock.
664  * It does not free the structure from memory.
665  */
666 #define AST_RWLIST_HEAD_DESTROY(head) {                                 \
667         (head)->first = NULL;                                           \
668         (head)->last = NULL;                                            \
669         ast_rwlock_destroy(&(head)->lock);                              \
670 }
671
672 /*!
673  * \brief Initializes a list head structure.
674  * \param head This is a pointer to the list head structure
675  *
676  * This macro initializes a list head structure by setting the head
677  * entry to \a NULL (empty list). There is no embedded lock handling
678  * with this macro.
679  */
680 #define AST_LIST_HEAD_INIT_NOLOCK(head) {                               \
681         (head)->first = NULL;                                           \
682         (head)->last = NULL;                                            \
683 }
684
685 /*!
686  * \brief Inserts a list entry after a given entry.
687  * \param head This is a pointer to the list head structure
688  * \param listelm This is a pointer to the entry after which the new entry should
689  * be inserted.
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_LIST_ENTRY())
692  * used to link entries of this list together.
693  */
694 #define AST_LIST_INSERT_AFTER(head, listelm, elm, field) do {           \
695         (elm)->field.next = (listelm)->field.next;                      \
696         (listelm)->field.next = (elm);                                  \
697         if ((head)->last == (listelm))                                  \
698                 (head)->last = (elm);                                   \
699 } while (0)
700
701 #define AST_RWLIST_INSERT_AFTER AST_LIST_INSERT_AFTER
702
703 /*!
704  * \brief Inserts a list entry at the head of a list.
705  * \param head This is a pointer to the list head structure
706  * \param elm This is a pointer to the entry to be inserted.
707  * \param field This is the name of the field (declared using AST_LIST_ENTRY())
708  * used to link entries of this list together.
709  */
710 #define AST_LIST_INSERT_HEAD(head, elm, field) do {                     \
711                 (elm)->field.next = (head)->first;                      \
712                 (head)->first = (elm);                                  \
713                 if (!(head)->last)                                      \
714                         (head)->last = (elm);                           \
715 } while (0)
716
717 #define AST_RWLIST_INSERT_HEAD AST_LIST_INSERT_HEAD
718
719 /*!
720  * \brief Appends a list entry to the tail of a list.
721  * \param head This is a pointer to the list head structure
722  * \param elm This is a pointer to the entry to be appended.
723  * \param field This is the name of the field (declared using AST_LIST_ENTRY())
724  * used to link entries of this list together.
725  *
726  * Note: The link field in the appended entry is \b not modified, so if it is
727  * actually the head of a list itself, the entire list will be appended
728  * temporarily (until the next AST_LIST_INSERT_TAIL is performed).
729  */
730 #define AST_LIST_INSERT_TAIL(head, elm, field) do {                     \
731       if (!(head)->first) {                                             \
732                 (head)->first = (elm);                                  \
733                 (head)->last = (elm);                                   \
734       } else {                                                          \
735                 (head)->last->field.next = (elm);                       \
736                 (head)->last = (elm);                                   \
737       }                                                                 \
738 } while (0)
739
740 #define AST_RWLIST_INSERT_TAIL AST_LIST_INSERT_TAIL
741
742 /*!
743  * \brief Inserts a list entry into a alphabetically sorted list
744  * \param head Pointer to the list head structure
745  * \param elm Pointer to the entry to be inserted
746  * \param field Name of the list entry field (declared using AST_LIST_ENTRY())
747  * \param sortfield Name of the field on which the list is sorted
748  * \since 1.6.1
749  */
750 #define AST_LIST_INSERT_SORTALPHA(head, elm, field, sortfield) do {     \
751         if (!(head)->first) {                                               \
752                 (head)->first = (elm);                                          \
753                 (head)->last = (elm);                                           \
754         } else {                                                            \
755                 typeof((head)->first) __cur = (head)->first, __prev = NULL;     \
756                 while (__cur && strcmp(__cur->sortfield, elm->sortfield) < 0) { \
757                         __prev = __cur;                                             \
758                         __cur = __cur->field.next;                                  \
759                 }                                                               \
760                 if (!__prev) {                                                  \
761                         AST_LIST_INSERT_HEAD(head, elm, field);                     \
762                 } else if (!__cur) {                                            \
763                         AST_LIST_INSERT_TAIL(head, elm, field);                     \
764                 } else {                                                        \
765                         AST_LIST_INSERT_AFTER(head, __prev, elm, field);            \
766                 }                                                               \
767         }                                                                   \
768 } while (0)
769
770 #define AST_RWLIST_INSERT_SORTALPHA     AST_LIST_INSERT_SORTALPHA
771
772 /*!
773  * \brief Appends a whole list to the tail of a list.
774  * \param head This is a pointer to the list head structure
775  * \param list This is a pointer to the list to be appended.
776  * \param field This is the name of the field (declared using AST_LIST_ENTRY())
777  * used to link entries of this list together.
778  *
779  * Note: The source list (the \a list parameter) will be empty after
780  * calling this macro (the list entries are \b moved to the target list).
781  */
782 #define AST_LIST_APPEND_LIST(head, list, field) do {                    \
783         if (!(list)->first) {                                           \
784                 break;                                                  \
785         }                                                               \
786         if (!(head)->first) {                                           \
787                 (head)->first = (list)->first;                          \
788                 (head)->last = (list)->last;                            \
789         } else {                                                        \
790                 (head)->last->field.next = (list)->first;               \
791                 (head)->last = (list)->last;                            \
792         }                                                               \
793         (list)->first = NULL;                                           \
794         (list)->last = NULL;                                            \
795 } while (0)
796
797 #define AST_RWLIST_APPEND_LIST AST_LIST_APPEND_LIST
798
799 /*!
800   \brief Inserts a whole list after a specific entry in a list
801   \param head This is a pointer to the list head structure
802   \param list This is a pointer to the list to be inserted.
803   \param elm This is a pointer to the entry after which the new list should
804   be inserted.
805   \param field This is the name of the field (declared using AST_LIST_ENTRY())
806   used to link entries of the lists together.
807
808   Note: The source list (the \a list parameter) will be empty after
809   calling this macro (the list entries are \b moved to the target list).
810  */
811 #define AST_LIST_INSERT_LIST_AFTER(head, list, elm, field) do {         \
812         (list)->last->field.next = (elm)->field.next;                   \
813         (elm)->field.next = (list)->first;                              \
814         if ((head)->last == elm) {                                      \
815                 (head)->last = (list)->last;                            \
816         }                                                               \
817         (list)->first = NULL;                                           \
818         (list)->last = NULL;                                            \
819 } while(0)
820
821 #define AST_RWLIST_INSERT_LIST_AFTER AST_LIST_INSERT_LIST_AFTER
822
823 /*!
824  * \brief Removes and returns the head entry from a list.
825  * \param head This is a pointer to the list head structure
826  * \param field This is the name of the field (declared using AST_LIST_ENTRY())
827  * used to link entries of this list together.
828  *
829  * Removes the head entry from the list, and returns a pointer to it.
830  * This macro is safe to call on an empty list.
831  */
832 #define AST_LIST_REMOVE_HEAD(head, field) ({                            \
833                 typeof((head)->first) __cur = (head)->first;            \
834                 if (__cur) {                                            \
835                         (head)->first = __cur->field.next;              \
836                         __cur->field.next = NULL;                       \
837                         if ((head)->last == __cur)                      \
838                                 (head)->last = NULL;                    \
839                 }                                                       \
840                 __cur;                                                  \
841         })
842
843 #define AST_RWLIST_REMOVE_HEAD AST_LIST_REMOVE_HEAD
844
845 /*!
846  * \brief Removes a specific entry from a list.
847  * \param head This is a pointer to the list head structure
848  * \param elm This is a pointer to the entry to be removed.
849  * \param field This is the name of the field (declared using AST_LIST_ENTRY())
850  * used to link entries of this list together.
851  * \retval elm if elm was in the list.
852  * \retval NULL if elm was not in the list or elm was NULL.
853  * \warning The removed entry is \b not freed.
854  */
855 #define AST_LIST_REMOVE(head, elm, field)                                               \
856         ({                                                                                                                      \
857                 typeof(elm) __elm = (elm);                                                              \
858                 if (__elm) {                                                                                    \
859                         if ((head)->first == __elm) {                                           \
860                                 (head)->first = __elm->field.next;                              \
861                                 __elm->field.next = NULL;                                               \
862                                 if ((head)->last == __elm) {                                    \
863                                         (head)->last = NULL;                                            \
864                                 }                                                                                               \
865                         } else {                                                                                        \
866                                 typeof(elm) __prev = (head)->first;                             \
867                                 while (__prev && __prev->field.next != __elm) { \
868                                         __prev = __prev->field.next;                            \
869                                 }                                                                                               \
870                                 if (__prev) {                                                                   \
871                                         __prev->field.next = __elm->field.next;         \
872                                         __elm->field.next = NULL;                                       \
873                                         if ((head)->last == __elm) {                            \
874                                                 (head)->last = __prev;                                  \
875                                         }                                                                                       \
876                                 } else {                                                                                \
877                                         __elm = NULL;                                                           \
878                                 }                                                                                               \
879                         }                                                                                                       \
880                 }                                                                                                               \
881                 __elm;                                                                                                  \
882         })
883
884 #define AST_RWLIST_REMOVE AST_LIST_REMOVE
885
886 #endif /* _ASTERISK_LINKEDLISTS_H */