82db0924cbbb8d7179159d1b516f2a421cc44e2c
[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) __new_prev = NULL;                                   \
533         for ((var) = __list_head->first, __new_prev = (var),                            \
534               __list_next = (var) ? (var)->field.next : NULL;                           \
535              (var);                                                                     \
536              __list_prev = __new_prev, (var) = __list_next,                             \
537              __new_prev = (var),                                                        \
538              __list_next = (var) ? (var)->field.next : NULL                             \
539             )
540
541 #define AST_RWLIST_TRAVERSE_SAFE_BEGIN AST_LIST_TRAVERSE_SAFE_BEGIN
542
543 /*!
544  * \brief Removes the \a current entry from a list during a traversal.
545  * \param field This is the name of the field (declared using AST_LIST_ENTRY())
546  * used to link entries of this list together.
547  *
548  * \note This macro can \b only be used inside an AST_LIST_TRAVERSE_SAFE_BEGIN()
549  * block; it is used to unlink the current entry from the list without affecting
550  * the list traversal (and without having to re-traverse the list to modify the
551  * previous entry, if any).
552  */
553 #define AST_LIST_REMOVE_CURRENT(field) do { \
554         __new_prev->field.next = NULL;                                                  \
555         __new_prev = __list_prev;                                                       \
556         if (__list_prev)                                                                \
557                 __list_prev->field.next = __list_next;                                  \
558         else                                                                            \
559                 __list_head->first = __list_next;                                       \
560         if (!__list_next)                                                               \
561                 __list_head->last = __list_prev;                                        \
562         } while (0)
563
564 #define AST_RWLIST_REMOVE_CURRENT AST_LIST_REMOVE_CURRENT
565
566 #define AST_LIST_MOVE_CURRENT(newhead, field) do { \
567         typeof ((newhead)->first) __list_cur = __new_prev;                              \
568         AST_LIST_REMOVE_CURRENT(field);                                                 \
569         AST_LIST_INSERT_TAIL((newhead), __list_cur, field);                             \
570         } while (0)
571
572 #define AST_RWLIST_MOVE_CURRENT AST_LIST_MOVE_CURRENT
573
574 /*!
575  * \brief Inserts a list entry before the current entry during a traversal.
576  * \param elm This is a pointer to the entry to be inserted.
577  * \param field This is the name of the field (declared using AST_LIST_ENTRY())
578  * used to link entries of this list together.
579  *
580  * \note This macro can \b only be used inside an AST_LIST_TRAVERSE_SAFE_BEGIN()
581  * block.
582  */
583 #define AST_LIST_INSERT_BEFORE_CURRENT(elm, field) do {                 \
584         if (__list_prev) {                                              \
585                 (elm)->field.next = __list_prev->field.next;            \
586                 __list_prev->field.next = elm;                          \
587         } else {                                                        \
588                 (elm)->field.next = __list_head->first;                 \
589                 __list_head->first = (elm);                             \
590         }                                                               \
591         __new_prev = (elm);                                             \
592 } while (0)
593
594 #define AST_RWLIST_INSERT_BEFORE_CURRENT AST_LIST_INSERT_BEFORE_CURRENT
595
596 /*!
597  * \brief Closes a safe loop traversal block.
598  */
599 #define AST_LIST_TRAVERSE_SAFE_END  }
600
601 #define AST_RWLIST_TRAVERSE_SAFE_END AST_LIST_TRAVERSE_SAFE_END
602
603 /*!
604  * \brief Initializes a list head structure.
605  * \param head This is a pointer to the list head structure
606  *
607  * This macro initializes a list head structure by setting the head
608  * entry to \a NULL (empty list) and recreating the embedded lock.
609  */
610 #define AST_LIST_HEAD_INIT(head) {                                      \
611         (head)->first = NULL;                                           \
612         (head)->last = NULL;                                            \
613         ast_mutex_init(&(head)->lock);                                  \
614 }
615
616 /*!
617  * \brief Initializes an rwlist head structure.
618  * \param head This is a pointer to the list head structure
619  *
620  * This macro initializes a list head structure by setting the head
621  * entry to \a NULL (empty list) and recreating the embedded lock.
622  */
623 #define AST_RWLIST_HEAD_INIT(head) {                                    \
624         (head)->first = NULL;                                           \
625         (head)->last = NULL;                                            \
626         ast_rwlock_init(&(head)->lock);                                 \
627 }
628
629 /*!
630  * \brief Destroys a list head structure.
631  * \param head This is a pointer to the list head structure
632  *
633  * This macro destroys a list head structure by setting the head
634  * entry to \a NULL (empty list) and destroying the embedded lock.
635  * It does not free the structure from memory.
636  */
637 #define AST_LIST_HEAD_DESTROY(head) {                                   \
638         (head)->first = NULL;                                           \
639         (head)->last = NULL;                                            \
640         ast_mutex_destroy(&(head)->lock);                               \
641 }
642
643 /*!
644  * \brief Destroys an rwlist head structure.
645  * \param head This is a pointer to the list head structure
646  *
647  * This macro destroys a list head structure by setting the head
648  * entry to \a NULL (empty list) and destroying the embedded lock.
649  * It does not free the structure from memory.
650  */
651 #define AST_RWLIST_HEAD_DESTROY(head) {                                 \
652         (head)->first = NULL;                                           \
653         (head)->last = NULL;                                            \
654         ast_rwlock_destroy(&(head)->lock);                              \
655 }
656
657 /*!
658  * \brief Initializes a list head structure.
659  * \param head This is a pointer to the list head structure
660  *
661  * This macro initializes a list head structure by setting the head
662  * entry to \a NULL (empty list). There is no embedded lock handling
663  * with this macro.
664  */
665 #define AST_LIST_HEAD_INIT_NOLOCK(head) {                               \
666         (head)->first = NULL;                                           \
667         (head)->last = NULL;                                            \
668 }
669
670 /*!
671  * \brief Inserts a list entry after a given entry.
672  * \param head This is a pointer to the list head structure
673  * \param listelm This is a pointer to the entry after which the new entry should
674  * be inserted.
675  * \param elm This is a pointer to the entry to be inserted.
676  * \param field This is the name of the field (declared using AST_LIST_ENTRY())
677  * used to link entries of this list together.
678  */
679 #define AST_LIST_INSERT_AFTER(head, listelm, elm, field) do {           \
680         (elm)->field.next = (listelm)->field.next;                      \
681         (listelm)->field.next = (elm);                                  \
682         if ((head)->last == (listelm))                                  \
683                 (head)->last = (elm);                                   \
684 } while (0)
685
686 #define AST_RWLIST_INSERT_AFTER AST_LIST_INSERT_AFTER
687
688 /*!
689  * \brief Inserts a list entry at the head of a list.
690  * \param head This is a pointer to the list head structure
691  * \param elm This is a pointer to the entry to be inserted.
692  * \param field This is the name of the field (declared using AST_LIST_ENTRY())
693  * used to link entries of this list together.
694  */
695 #define AST_LIST_INSERT_HEAD(head, elm, field) do {                     \
696                 (elm)->field.next = (head)->first;                      \
697                 (head)->first = (elm);                                  \
698                 if (!(head)->last)                                      \
699                         (head)->last = (elm);                           \
700 } while (0)
701
702 #define AST_RWLIST_INSERT_HEAD AST_LIST_INSERT_HEAD
703
704 /*!
705  * \brief Appends a list entry to the tail of a list.
706  * \param head This is a pointer to the list head structure
707  * \param elm This is a pointer to the entry to be appended.
708  * \param field This is the name of the field (declared using AST_LIST_ENTRY())
709  * used to link entries of this list together.
710  *
711  * Note: The link field in the appended entry is \b not modified, so if it is
712  * actually the head of a list itself, the entire list will be appended
713  * temporarily (until the next AST_LIST_INSERT_TAIL is performed).
714  */
715 #define AST_LIST_INSERT_TAIL(head, elm, field) do {                     \
716       if (!(head)->first) {                                             \
717                 (head)->first = (elm);                                  \
718                 (head)->last = (elm);                                   \
719       } else {                                                          \
720                 (head)->last->field.next = (elm);                       \
721                 (head)->last = (elm);                                   \
722       }                                                                 \
723 } while (0)
724
725 #define AST_RWLIST_INSERT_TAIL AST_LIST_INSERT_TAIL
726
727 /*!
728  * \brief Inserts a list entry into a alphabetically sorted list
729  * \param head Pointer to the list head structure
730  * \param elm Pointer to the entry to be inserted
731  * \param field Name of the list entry field (declared using AST_LIST_ENTRY())
732  * \param sortfield Name of the field on which the list is sorted
733  * \since 1.6.1
734  */
735 #define AST_LIST_INSERT_SORTALPHA(head, elm, field, sortfield) do { \
736         if (!(head)->first) {                                           \
737                 (head)->first = (elm);                                      \
738                 (head)->last = (elm);                                       \
739         } else {                                                        \
740                 typeof((head)->first) cur = (head)->first, prev = NULL;     \
741                 while (cur && strcmp(cur->sortfield, elm->sortfield) < 0) { \
742                         prev = cur;                                             \
743                         cur = cur->field.next;                                  \
744                 }                                                           \
745                 if (!prev) {                                                \
746                         AST_LIST_INSERT_HEAD(head, elm, field);                 \
747                 } else if (!cur) {                                          \
748                         AST_LIST_INSERT_TAIL(head, elm, field);                 \
749                 } else {                                                    \
750                         AST_LIST_INSERT_AFTER(head, prev, elm, field);          \
751                 }                                                           \
752         }                                                               \
753 } while (0)
754
755 #define AST_RWLIST_INSERT_SORTALPHA     AST_LIST_INSERT_SORTALPHA
756
757 /*!
758  * \brief Appends a whole list to the tail of a list.
759  * \param head This is a pointer to the list head structure
760  * \param list This is a pointer to the list to be appended.
761  * \param field This is the name of the field (declared using AST_LIST_ENTRY())
762  * used to link entries of this list together.
763  *
764  * Note: The source list (the \a list parameter) will be empty after
765  * calling this macro (the list entries are \b moved to the target list).
766  */
767 #define AST_LIST_APPEND_LIST(head, list, field) do {                    \
768         if (!(list)->first) {                                           \
769                 break;                                                  \
770         }                                                               \
771         if (!(head)->first) {                                           \
772                 (head)->first = (list)->first;                          \
773                 (head)->last = (list)->last;                            \
774         } else {                                                        \
775                 (head)->last->field.next = (list)->first;               \
776                 (head)->last = (list)->last;                            \
777         }                                                               \
778         (list)->first = NULL;                                           \
779         (list)->last = NULL;                                            \
780 } while (0)
781
782 #define AST_RWLIST_APPEND_LIST AST_LIST_APPEND_LIST
783
784 /*!
785   \brief Inserts a whole list after a specific entry in a list
786   \param head This is a pointer to the list head structure
787   \param list This is a pointer to the list to be inserted.
788   \param elm This is a pointer to the entry after which the new list should
789   be inserted.
790   \param field This is the name of the field (declared using AST_LIST_ENTRY())
791   used to link entries of the lists together.
792
793   Note: The source list (the \a list parameter) will be empty after
794   calling this macro (the list entries are \b moved to the target list).
795  */
796 #define AST_LIST_INSERT_LIST_AFTER(head, list, elm, field) do {         \
797         (list)->last->field.next = (elm)->field.next;                   \
798         (elm)->field.next = (list)->first;                              \
799         if ((head)->last == elm) {                                      \
800                 (head)->last = (list)->last;                            \
801         }                                                               \
802         (list)->first = NULL;                                           \
803         (list)->last = NULL;                                            \
804 } while(0)
805
806 #define AST_RWLIST_INSERT_LIST_AFTER AST_LIST_INSERT_LIST_AFTER
807
808 /*!
809  * \brief Removes and returns the head entry from a list.
810  * \param head This is a pointer to the list head structure
811  * \param field This is the name of the field (declared using AST_LIST_ENTRY())
812  * used to link entries of this list together.
813  *
814  * Removes the head entry from the list, and returns a pointer to it.
815  * This macro is safe to call on an empty list.
816  */
817 #define AST_LIST_REMOVE_HEAD(head, field) ({                            \
818                 typeof((head)->first) cur = (head)->first;              \
819                 if (cur) {                                              \
820                         (head)->first = cur->field.next;                \
821                         cur->field.next = NULL;                         \
822                         if ((head)->last == cur)                        \
823                                 (head)->last = NULL;                    \
824                 }                                                       \
825                 cur;                                                    \
826         })
827
828 #define AST_RWLIST_REMOVE_HEAD AST_LIST_REMOVE_HEAD
829
830 /*!
831  * \brief Removes a specific entry from a list.
832  * \param head This is a pointer to the list head structure
833  * \param elm This is a pointer to the entry to be removed.
834  * \param field This is the name of the field (declared using AST_LIST_ENTRY())
835  * used to link entries of this list together.
836  * \warning The removed entry is \b not freed nor modified in any way.
837  */
838 #define AST_LIST_REMOVE(head, elm, field) ({                            \
839         __typeof(elm) __res = NULL; \
840         if ((head)->first == (elm)) {                                   \
841                 __res = (head)->first;                      \
842                 (head)->first = (elm)->field.next;                      \
843                 if ((head)->last == (elm))                      \
844                         (head)->last = NULL;                    \
845         } else {                                                                \
846                 typeof(elm) curelm = (head)->first;                     \
847                 while (curelm && (curelm->field.next != (elm)))                 \
848                         curelm = curelm->field.next;                    \
849                 if (curelm) { \
850                         __res = (elm); \
851                         curelm->field.next = (elm)->field.next;                 \
852                         if ((head)->last == (elm))                              \
853                                 (head)->last = curelm;                          \
854                 } \
855         }                                                               \
856         (elm)->field.next = NULL;                                       \
857         (__res); \
858 })
859
860 #define AST_RWLIST_REMOVE AST_LIST_REMOVE
861
862 #endif /* _ASTERISK_LINKEDLISTS_H */