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