incorporates r159808 from branches/1.4:
[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 Read locks a list.
56   \param head This is a pointer to the list head structure
57
58   This macro attempts to place a read lock in the
59   list head structure pointed to by head.
60   \retval 0 on success
61   \retval non-zero on failure
62 */
63 #define AST_RWLIST_RDLOCK(head)                                         \
64         ast_rwlock_rdlock(&(head)->lock)
65         
66 /*!
67   \brief Locks a list, without blocking if the list is locked.
68   \param head This is a pointer to the list head structure
69
70   This macro attempts to place an exclusive lock in the
71   list head structure pointed to by head.
72   \retval 0 on success
73   \retval non-zero on failure
74 */
75 #define AST_LIST_TRYLOCK(head)                                          \
76         ast_mutex_trylock(&(head)->lock) 
77
78 /*!
79   \brief Write locks a list, without blocking if the list is locked.
80   \param head This is a pointer to the list head structure
81
82   This macro attempts to place an exclusive write lock in the
83   list head structure pointed to by head.
84   \retval 0 on success
85   \retval non-zero on failure
86 */
87 #define AST_RWLIST_TRYWRLOCK(head)                                      \
88         ast_rwlock_trywrlock(&(head)->lock)
89
90 /*!
91   \brief Read locks a list, without blocking if the list is locked.
92   \param head This is a pointer to the list head structure
93
94   This macro attempts to place a read lock in the
95   list head structure pointed to by head.
96   \retval 0 on success
97   \retval non-zero on failure
98 */
99 #define AST_RWLIST_TRYRDLOCK(head)                                      \
100         ast_rwlock_tryrdlock(&(head)->lock)
101         
102 /*!
103   \brief Attempts to unlock a list.
104   \param head This is a pointer to the list head structure
105
106   This macro attempts to remove an exclusive lock from the
107   list head structure pointed to by head. If the list
108   was not locked by this thread, this macro has no effect.
109 */
110 #define AST_LIST_UNLOCK(head)                                           \
111         ast_mutex_unlock(&(head)->lock)
112
113 /*!
114   \brief Attempts to unlock a read/write based list.
115   \param head This is a pointer to the list head structure
116
117   This macro attempts to remove a read or write lock from the
118   list head structure pointed to by head. If the list
119   was not locked by this thread, this macro has no effect.
120 */
121 #define AST_RWLIST_UNLOCK(head)                                         \
122         ast_rwlock_unlock(&(head)->lock)
123
124 /*!
125   \brief Defines a structure to be used to hold a list of specified type.
126   \param name This will be the name of the defined structure.
127   \param type This is the type of each list entry.
128
129   This macro creates a structure definition that can be used
130   to hold a list of the entries of type \a type. It does not actually
131   declare (allocate) a structure; to do that, either follow this
132   macro with the desired name of the instance you wish to declare,
133   or use the specified \a name to declare instances elsewhere.
134
135   Example usage:
136   \code
137   static AST_LIST_HEAD(entry_list, entry) entries;
138   \endcode
139
140   This would define \c struct \c entry_list, and declare an instance of it named
141   \a entries, all intended to hold a list of type \c struct \c entry.
142 */
143 #define AST_LIST_HEAD(name, type)                                       \
144 struct name {                                                           \
145         struct type *first;                                             \
146         struct type *last;                                              \
147         ast_mutex_t lock;                                               \
148 }
149
150 /*!
151   \brief Defines a structure to be used to hold a read/write list of specified type.
152   \param name This will be the name of the defined structure.
153   \param type This is the type of each list entry.
154
155   This macro creates a structure definition that can be used
156   to hold a list of the entries of type \a type. It does not actually
157   declare (allocate) a structure; to do that, either follow this
158   macro with the desired name of the instance you wish to declare,
159   or use the specified \a name to declare instances elsewhere.
160
161   Example usage:
162   \code
163   static AST_RWLIST_HEAD(entry_list, entry) entries;
164   \endcode
165
166   This would define \c struct \c entry_list, and declare an instance of it named
167   \a entries, all intended to hold a list of type \c struct \c entry.
168 */
169 #define AST_RWLIST_HEAD(name, type)                                     \
170 struct name {                                                           \
171         struct type *first;                                             \
172         struct type *last;                                              \
173         ast_rwlock_t lock;                                              \
174 }
175
176 /*!
177   \brief Defines a structure to be used to hold a list of specified type (with no lock).
178   \param name This will be the name of the defined structure.
179   \param type This is the type of each list entry.
180
181   This macro creates a structure definition that can be used
182   to hold a list of the entries of type \a type. It does not actually
183   declare (allocate) a structure; to do that, either follow this
184   macro with the desired name of the instance you wish to declare,
185   or use the specified \a name to declare instances elsewhere.
186
187   Example usage:
188   \code
189   static AST_LIST_HEAD_NOLOCK(entry_list, entry) entries;
190   \endcode
191
192   This would define \c struct \c entry_list, and declare an instance of it named
193   \a entries, all intended to hold a list of type \c struct \c entry.
194 */
195 #define AST_LIST_HEAD_NOLOCK(name, type)                                \
196 struct name {                                                           \
197         struct type *first;                                             \
198         struct type *last;                                              \
199 }
200
201 /*!
202   \brief Defines initial values for a declaration of AST_LIST_HEAD
203 */
204 #define AST_LIST_HEAD_INIT_VALUE        {               \
205         .first = NULL,                                  \
206         .last = NULL,                                   \
207         .lock = AST_MUTEX_INIT_VALUE,                   \
208         }
209
210 /*!
211   \brief Defines initial values for a declaration of AST_RWLIST_HEAD
212 */
213 #define AST_RWLIST_HEAD_INIT_VALUE      {               \
214         .first = NULL,                                  \
215         .last = NULL,                                   \
216         .lock = AST_RWLOCK_INIT_VALUE,                  \
217         }
218
219 /*!
220   \brief Defines initial values for a declaration of AST_LIST_HEAD_NOLOCK
221 */
222 #define AST_LIST_HEAD_NOLOCK_INIT_VALUE {       \
223         .first = NULL,                                  \
224         .last = NULL,                                   \
225         }
226
227 /*!
228   \brief Defines a structure to be used to hold a list of specified type, statically initialized.
229   \param name This will be the name of the defined structure.
230   \param type This is the type of each list entry.
231
232   This macro creates a structure definition that can be used
233   to hold a list of the entries of type \a type, and allocates an instance
234   of it, initialized to be empty.
235
236   Example usage:
237   \code
238   static AST_LIST_HEAD_STATIC(entry_list, entry);
239   \endcode
240
241   This would define \c struct \c entry_list, intended to hold a list of
242   type \c struct \c entry.
243 */
244 #if defined(AST_MUTEX_INIT_W_CONSTRUCTORS)
245 #define AST_LIST_HEAD_STATIC(name, type)                                \
246 struct name {                                                           \
247         struct type *first;                                             \
248         struct type *last;                                              \
249         ast_mutex_t lock;                                               \
250 } name;                                                                 \
251 static void  __attribute__((constructor)) __init_##name(void)           \
252 {                                                                       \
253         AST_LIST_HEAD_INIT(&name);                                      \
254 }                                                                       \
255 static void  __attribute__((destructor)) __fini_##name(void)            \
256 {                                                                       \
257         AST_LIST_HEAD_DESTROY(&name);                                   \
258 }                                                                       \
259 struct __dummy_##name
260 #else
261 #define AST_LIST_HEAD_STATIC(name, type)                                \
262 struct name {                                                           \
263         struct type *first;                                             \
264         struct type *last;                                              \
265         ast_mutex_t lock;                                               \
266 } name = AST_LIST_HEAD_INIT_VALUE
267 #endif
268
269 /*!
270   \brief Defines a structure to be used to hold a read/write list of specified type, statically initialized.
271   \param name This will be the name of the defined structure.
272   \param type This is the type of each list entry.
273
274   This macro creates a structure definition that can be used
275   to hold a list of the entries of type \a type, and allocates an instance
276   of it, initialized to be empty.
277
278   Example usage:
279   \code
280   static AST_RWLIST_HEAD_STATIC(entry_list, entry);
281   \endcode
282
283   This would define \c struct \c entry_list, intended to hold a list of
284   type \c struct \c entry.
285 */
286 #ifndef AST_RWLOCK_INIT_VALUE
287 #define AST_RWLIST_HEAD_STATIC(name, type)                              \
288 struct name {                                                           \
289         struct type *first;                                             \
290         struct type *last;                                              \
291         ast_rwlock_t lock;                                              \
292 } name;                                                                 \
293 static void  __attribute__((constructor)) __init_##name(void)          \
294 {                                                                       \
295         AST_RWLIST_HEAD_INIT(&name);                                    \
296 }                                                                       \
297 static void  __attribute__((destructor)) __fini_##name(void)           \
298 {                                                                       \
299         AST_RWLIST_HEAD_DESTROY(&name);                                 \
300 }                                                                       \
301 struct __dummy_##name
302 #else
303 #define AST_RWLIST_HEAD_STATIC(name, type)                              \
304 struct name {                                                           \
305         struct type *first;                                             \
306         struct type *last;                                              \
307         ast_rwlock_t lock;                                              \
308 } name = AST_RWLIST_HEAD_INIT_VALUE
309 #endif
310
311 /*!
312   \brief Defines a structure to be used to hold a list of specified type, statically initialized.
313
314   This is the same as AST_LIST_HEAD_STATIC, except without the lock included.
315 */
316 #define AST_LIST_HEAD_NOLOCK_STATIC(name, type)                         \
317 struct name {                                                           \
318         struct type *first;                                             \
319         struct type *last;                                              \
320 } name = AST_LIST_HEAD_NOLOCK_INIT_VALUE
321
322 /*!
323   \brief Initializes a list head structure with a specified first entry.
324   \param head This is a pointer to the list head structure
325   \param entry pointer to the list entry that will become the head of the list
326
327   This macro initializes a list head structure by setting the head
328   entry to the supplied value and recreating the embedded lock.
329 */
330 #define AST_LIST_HEAD_SET(head, entry) do {                             \
331         (head)->first = (entry);                                        \
332         (head)->last = (entry);                                         \
333         ast_mutex_init(&(head)->lock);                                  \
334 } while (0)
335
336 /*!
337   \brief Initializes an rwlist head structure with a specified first entry.
338   \param head This is a pointer to the list head structure
339   \param entry pointer to the list entry that will become the head of the list
340
341   This macro initializes a list head structure by setting the head
342   entry to the supplied value and recreating the embedded lock.
343 */
344 #define AST_RWLIST_HEAD_SET(head, entry) do {                           \
345         (head)->first = (entry);                                        \
346         (head)->last = (entry);                                         \
347         ast_rwlock_init(&(head)->lock);                                 \
348 } while (0)
349
350 /*!
351   \brief Initializes a list head structure with a specified first entry.
352   \param head This is a pointer to the list head structure
353   \param entry pointer to the list entry that will become the head of the list
354
355   This macro initializes a list head structure by setting the head
356   entry to the supplied value.
357 */
358 #define AST_LIST_HEAD_SET_NOLOCK(head, entry) do {                      \
359         (head)->first = (entry);                                        \
360         (head)->last = (entry);                                         \
361 } while (0)
362
363 /*!
364   \brief Declare a forward link structure inside a list entry.
365   \param type This is the type of each list entry.
366
367   This macro declares a structure to be used to link list entries together.
368   It must be used inside the definition of the structure named in
369   \a type, as follows:
370
371   \code
372   struct list_entry {
373         ...
374         AST_LIST_ENTRY(list_entry) list;
375   }
376   \endcode
377
378   The field name \a list here is arbitrary, and can be anything you wish.
379 */
380 #define AST_LIST_ENTRY(type)                                            \
381 struct {                                                                \
382         struct type *next;                                              \
383 }
384
385 #define AST_RWLIST_ENTRY AST_LIST_ENTRY
386  
387 /*!
388   \brief Returns the first entry contained in a list.
389   \param head This is a pointer to the list head structure
390  */
391 #define AST_LIST_FIRST(head)    ((head)->first)
392
393 #define AST_RWLIST_FIRST AST_LIST_FIRST
394
395 /*!
396   \brief Returns the last entry contained in a list.
397   \param head This is a pointer to the list head structure
398  */
399 #define AST_LIST_LAST(head)     ((head)->last)
400
401 #define AST_RWLIST_LAST AST_LIST_LAST
402
403 /*!
404   \brief Returns the next entry in the list after the given entry.
405   \param elm This is a pointer to the current entry.
406   \param field This is the name of the field (declared using AST_LIST_ENTRY())
407   used to link entries of this list together.
408 */
409 #define AST_LIST_NEXT(elm, field)       ((elm)->field.next)
410
411 #define AST_RWLIST_NEXT AST_LIST_NEXT
412
413 /*!
414   \brief Checks whether the specified list contains any entries.
415   \param head This is a pointer to the list head structure
416
417   \return non-zero if the list has entries
418   \return zero if not.
419  */
420 #define AST_LIST_EMPTY(head)    (AST_LIST_FIRST(head) == NULL)
421
422 #define AST_RWLIST_EMPTY AST_LIST_EMPTY
423
424 /*!
425   \brief Loops over (traverses) the entries in a list.
426   \param head This is a pointer to the list head structure
427   \param var This is the name of the variable that will hold a pointer to the
428   current list entry on each iteration. It must be declared before calling
429   this macro.
430   \param field This is the name of the field (declared using AST_LIST_ENTRY())
431   used to link entries of this list together.
432
433   This macro is use to loop over (traverse) the entries in a list. It uses a
434   \a for loop, and supplies the enclosed code with a pointer to each list
435   entry as it loops. It is typically used as follows:
436   \code
437   static AST_LIST_HEAD(entry_list, list_entry) entries;
438   ...
439   struct list_entry {
440         ...
441         AST_LIST_ENTRY(list_entry) list;
442   }
443   ...
444   struct list_entry *current;
445   ...
446   AST_LIST_TRAVERSE(&entries, current, list) {
447      (do something with current here)
448   }
449   \endcode
450   \warning If you modify the forward-link pointer contained in the \a current entry while
451   inside the loop, the behavior will be unpredictable. At a minimum, the following
452   macros will modify the forward-link pointer, and should not be used inside
453   AST_LIST_TRAVERSE() against the entry pointed to by the \a current pointer without
454   careful consideration of their consequences:
455   \li AST_LIST_NEXT() (when used as an lvalue)
456   \li AST_LIST_INSERT_AFTER()
457   \li AST_LIST_INSERT_HEAD()
458   \li AST_LIST_INSERT_TAIL()
459   \li AST_LIST_INSERT_SORTALPHA()
460 */
461 #define AST_LIST_TRAVERSE(head,var,field)                               \
462         for((var) = (head)->first; (var); (var) = (var)->field.next)
463
464 #define AST_RWLIST_TRAVERSE AST_LIST_TRAVERSE
465
466 /*!
467   \brief Loops safely over (traverses) the entries in a list.
468   \param head This is a pointer to the list head structure
469   \param var This is the name of the variable that will hold a pointer to the
470   current list entry on each iteration. It must be declared before calling
471   this macro.
472   \param field This is the name of the field (declared using AST_LIST_ENTRY())
473   used to link entries of this list together.
474
475   This macro is used to safely loop over (traverse) the entries in a list. It
476   uses a \a for loop, and supplies the enclosed code with a pointer to each list
477   entry as it loops. It is typically used as follows:
478
479   \code
480   static AST_LIST_HEAD(entry_list, list_entry) entries;
481   ...
482   struct list_entry {
483         ...
484         AST_LIST_ENTRY(list_entry) list;
485   }
486   ...
487   struct list_entry *current;
488   ...
489   AST_LIST_TRAVERSE_SAFE_BEGIN(&entries, current, list) {
490      (do something with current here)
491   }
492   AST_LIST_TRAVERSE_SAFE_END;
493   \endcode
494
495   It differs from AST_LIST_TRAVERSE() in that the code inside the loop can modify
496   (or even free, after calling AST_LIST_REMOVE_CURRENT()) the entry pointed to by
497   the \a current pointer without affecting the loop traversal.
498 */
499 #define AST_LIST_TRAVERSE_SAFE_BEGIN(head, var, field) {                                \
500         typeof((head)) __list_head = head;                                              \
501         typeof(__list_head->first) __list_next;                                         \
502         typeof(__list_head->first) __list_prev = NULL;                                  \
503         typeof(__list_head->first) __new_prev = NULL;                                   \
504         for ((var) = __list_head->first, __new_prev = (var),                            \
505               __list_next = (var) ? (var)->field.next : NULL;                           \
506              (var);                                                                     \
507              __list_prev = __new_prev, (var) = __list_next,                             \
508              __new_prev = (var),                                                        \
509              __list_next = (var) ? (var)->field.next : NULL                             \
510             )
511
512 #define AST_RWLIST_TRAVERSE_SAFE_BEGIN AST_LIST_TRAVERSE_SAFE_BEGIN
513
514 /*!
515   \brief Removes the \a current entry from a list during a traversal.
516   \param field This is the name of the field (declared using AST_LIST_ENTRY())
517   used to link entries of this list together.
518
519   \note This macro can \b only be used inside an AST_LIST_TRAVERSE_SAFE_BEGIN()
520   block; it is used to unlink the current entry from the list without affecting
521   the list traversal (and without having to re-traverse the list to modify the
522   previous entry, if any).
523  */
524 #define AST_LIST_REMOVE_CURRENT(field) do { \
525         __new_prev->field.next = NULL;                                                  \
526         __new_prev = __list_prev;                                                       \
527         if (__list_prev)                                                                \
528                 __list_prev->field.next = __list_next;                                  \
529         else                                                                            \
530                 __list_head->first = __list_next;                                       \
531         if (!__list_next)                                                               \
532                 __list_head->last = __list_prev;                                        \
533         } while (0)
534
535 #define AST_RWLIST_REMOVE_CURRENT AST_LIST_REMOVE_CURRENT
536
537 #define AST_LIST_MOVE_CURRENT(newhead, field) do { \
538         typeof ((newhead)->first) __list_cur = __new_prev;                              \
539         AST_LIST_REMOVE_CURRENT(field);                                                 \
540         AST_LIST_INSERT_TAIL((newhead), __list_cur, field);                             \
541         } while (0)
542
543 #define AST_RWLIST_MOVE_CURRENT AST_LIST_MOVE_CURRENT
544
545 /*!
546   \brief Inserts a list entry before the current entry during a traversal.
547   \param elm This is a pointer to the entry to be inserted.
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.
553  */
554 #define AST_LIST_INSERT_BEFORE_CURRENT(elm, field) do {                 \
555         if (__list_prev) {                                              \
556                 (elm)->field.next = __list_prev->field.next;            \
557                 __list_prev->field.next = elm;                          \
558         } else {                                                        \
559                 (elm)->field.next = __list_head->first;                 \
560                 __list_head->first = (elm);                             \
561         }                                                               \
562         __new_prev = (elm);                                             \
563 } while (0)
564
565 #define AST_RWLIST_INSERT_BEFORE_CURRENT AST_LIST_INSERT_BEFORE_CURRENT
566
567 /*!
568   \brief Closes a safe loop traversal block.
569  */
570 #define AST_LIST_TRAVERSE_SAFE_END  }
571
572 #define AST_RWLIST_TRAVERSE_SAFE_END AST_LIST_TRAVERSE_SAFE_END
573
574 /*!
575   \brief Initializes a list head structure.
576   \param head This is a pointer to the list head structure
577
578   This macro initializes a list head structure by setting the head
579   entry to \a NULL (empty list) and recreating the embedded lock.
580 */
581 #define AST_LIST_HEAD_INIT(head) {                                      \
582         (head)->first = NULL;                                           \
583         (head)->last = NULL;                                            \
584         ast_mutex_init(&(head)->lock);                                  \
585 }
586
587 /*!
588   \brief Initializes an rwlist head structure.
589   \param head This is a pointer to the list head structure
590
591   This macro initializes a list head structure by setting the head
592   entry to \a NULL (empty list) and recreating the embedded lock.
593 */
594 #define AST_RWLIST_HEAD_INIT(head) {                                    \
595         (head)->first = NULL;                                           \
596         (head)->last = NULL;                                            \
597         ast_rwlock_init(&(head)->lock);                                 \
598 }
599
600 /*!
601   \brief Destroys a list head structure.
602   \param head This is a pointer to the list head structure
603
604   This macro destroys a list head structure by setting the head
605   entry to \a NULL (empty list) and destroying the embedded lock.
606   It does not free the structure from memory.
607 */
608 #define AST_LIST_HEAD_DESTROY(head) {                                   \
609         (head)->first = NULL;                                           \
610         (head)->last = NULL;                                            \
611         ast_mutex_destroy(&(head)->lock);                               \
612 }
613
614 /*!
615   \brief Destroys an rwlist head structure.
616   \param head This is a pointer to the list head structure
617
618   This macro destroys a list head structure by setting the head
619   entry to \a NULL (empty list) and destroying the embedded lock.
620   It does not free the structure from memory.
621 */
622 #define AST_RWLIST_HEAD_DESTROY(head) {                                 \
623         (head)->first = NULL;                                           \
624         (head)->last = NULL;                                            \
625         ast_rwlock_destroy(&(head)->lock);                              \
626 }
627
628 /*!
629   \brief Initializes a list head structure.
630   \param head This is a pointer to the list head structure
631
632   This macro initializes a list head structure by setting the head
633   entry to \a NULL (empty list). There is no embedded lock handling
634   with this macro.
635 */
636 #define AST_LIST_HEAD_INIT_NOLOCK(head) {                               \
637         (head)->first = NULL;                                           \
638         (head)->last = NULL;                                            \
639 }
640
641 /*!
642   \brief Inserts a list entry after a given entry.
643   \param head This is a pointer to the list head structure
644   \param listelm This is a pointer to the entry after which the new entry should
645   be inserted.
646   \param elm This is a pointer to the entry to be inserted.
647   \param field This is the name of the field (declared using AST_LIST_ENTRY())
648   used to link entries of this list together.
649  */
650 #define AST_LIST_INSERT_AFTER(head, listelm, elm, field) do {           \
651         (elm)->field.next = (listelm)->field.next;                      \
652         (listelm)->field.next = (elm);                                  \
653         if ((head)->last == (listelm))                                  \
654                 (head)->last = (elm);                                   \
655 } while (0)
656
657 #define AST_RWLIST_INSERT_AFTER AST_LIST_INSERT_AFTER
658
659 /*!
660   \brief Inserts a list entry at the head of a list.
661   \param head This is a pointer to the list head structure
662   \param elm This is a pointer to the entry to be inserted.
663   \param field This is the name of the field (declared using AST_LIST_ENTRY())
664   used to link entries of this list together.
665  */
666 #define AST_LIST_INSERT_HEAD(head, elm, field) do {                     \
667                 (elm)->field.next = (head)->first;                      \
668                 (head)->first = (elm);                                  \
669                 if (!(head)->last)                                      \
670                         (head)->last = (elm);                           \
671 } while (0)
672
673 #define AST_RWLIST_INSERT_HEAD AST_LIST_INSERT_HEAD
674
675 /*!
676   \brief Appends a list entry to the tail of a list.
677   \param head This is a pointer to the list head structure
678   \param elm This is a pointer to the entry to be appended.
679   \param field This is the name of the field (declared using AST_LIST_ENTRY())
680   used to link entries of this list together.
681
682   Note: The link field in the appended entry is \b not modified, so if it is
683   actually the head of a list itself, the entire list will be appended
684   temporarily (until the next AST_LIST_INSERT_TAIL is performed).
685  */
686 #define AST_LIST_INSERT_TAIL(head, elm, field) do {                     \
687       if (!(head)->first) {                                             \
688                 (head)->first = (elm);                                  \
689                 (head)->last = (elm);                                   \
690       } else {                                                          \
691                 (head)->last->field.next = (elm);                       \
692                 (head)->last = (elm);                                   \
693       }                                                                 \
694 } while (0)
695
696 #define AST_RWLIST_INSERT_TAIL AST_LIST_INSERT_TAIL
697
698 /*!
699  * \brief Inserts a list entry into a alphabetically sorted list
700  * \param head Pointer to the list head structure
701  * \param elm Pointer to the entry to be inserted
702  * \param field Name of the list entry field (declared using AST_LIST_ENTRY())
703  * \param sortfield Name of the field on which the list is sorted
704  */
705 #define AST_LIST_INSERT_SORTALPHA(head, elm, field, sortfield) do { \
706         if (!(head)->first) {                                           \
707                 (head)->first = (elm);                                      \
708                 (head)->last = (elm);                                       \
709         } else {                                                        \
710                 typeof((head)->first) cur = (head)->first, prev = NULL;     \
711                 while (cur && strcmp(cur->sortfield, elm->sortfield) < 0) { \
712                         prev = cur;                                             \
713                         cur = cur->field.next;                                  \
714                 }                                                           \
715                 if (!prev) {                                                \
716                         AST_LIST_INSERT_HEAD(head, elm, field);                 \
717                 } else if (!cur) {                                          \
718                         AST_LIST_INSERT_TAIL(head, elm, field);                 \
719                 } else {                                                    \
720                         AST_LIST_INSERT_AFTER(head, prev, elm, field);          \
721                 }                                                           \
722         }                                                               \
723 } while (0)
724
725 #define AST_RWLIST_INSERT_SORTALPHA     AST_LIST_INSERT_SORTALPHA
726
727 /*!
728   \brief Appends a whole list to the tail of a list.
729   \param head This is a pointer to the list head structure
730   \param list This is a pointer to the list to be appended.
731   \param field This is the name of the field (declared using AST_LIST_ENTRY())
732   used to link entries of this list together.
733
734   Note: The source list (the \a list parameter) will be empty after
735   calling this macro (the list entries are \b moved to the target list).
736  */
737 #define AST_LIST_APPEND_LIST(head, list, field) do {                    \
738       if (!(head)->first) {                                             \
739                 (head)->first = (list)->first;                          \
740                 (head)->last = (list)->last;                            \
741       } else {                                                          \
742                 (head)->last->field.next = (list)->first;               \
743                 (head)->last = (list)->last;                            \
744       }                                                                 \
745       (list)->first = NULL;                                             \
746       (list)->last = NULL;                                              \
747 } while (0)
748
749 #define AST_RWLIST_APPEND_LIST AST_LIST_APPEND_LIST
750
751 /*!
752   \brief Removes and returns the head entry from a list.
753   \param head This is a pointer to the list head structure
754   \param field This is the name of the field (declared using AST_LIST_ENTRY())
755   used to link entries of this list together.
756
757   Removes the head entry from the list, and returns a pointer to it.
758   This macro is safe to call on an empty list.
759  */
760 #define AST_LIST_REMOVE_HEAD(head, field) ({                            \
761                 typeof((head)->first) cur = (head)->first;              \
762                 if (cur) {                                              \
763                         (head)->first = cur->field.next;                \
764                         cur->field.next = NULL;                         \
765                         if ((head)->last == cur)                        \
766                                 (head)->last = NULL;                    \
767                 }                                                       \
768                 cur;                                                    \
769         })
770
771 #define AST_RWLIST_REMOVE_HEAD AST_LIST_REMOVE_HEAD
772
773 /*!
774   \brief Removes a specific entry from a list.
775   \param head This is a pointer to the list head structure
776   \param elm This is a pointer to the entry to be removed.
777   \param field This is the name of the field (declared using AST_LIST_ENTRY())
778   used to link entries of this list together.
779   \warning The removed entry is \b not freed nor modified in any way.
780  */
781 #define AST_LIST_REMOVE(head, elm, field) ({                            \
782         __typeof(elm) __res = NULL; \
783         if ((head)->first == (elm)) {                                   \
784                 __res = (head)->first;                      \
785                 (head)->first = (elm)->field.next;                      \
786                 if ((head)->last == (elm))                      \
787                         (head)->last = NULL;                    \
788         } else {                                                                \
789                 typeof(elm) curelm = (head)->first;                     \
790                 while (curelm && (curelm->field.next != (elm)))                 \
791                         curelm = curelm->field.next;                    \
792                 if (curelm) { \
793                         __res = (elm); \
794                         curelm->field.next = (elm)->field.next;                 \
795                         if ((head)->last == (elm))                              \
796                                 (head)->last = curelm;                          \
797                 } \
798         }                                                               \
799         (elm)->field.next = NULL;                                       \
800         (__res); \
801 })
802
803 #define AST_RWLIST_REMOVE AST_LIST_REMOVE
804
805 #endif /* _ASTERISK_LINKEDLISTS_H */