2f42fdd39c6a60327e1d997ead5ec8cf58bf2e4e
[asterisk/asterisk.git] / include / asterisk / dlinkedlists.h
1 /*
2  * Asterisk -- An open source telephony toolkit.
3  *
4  * Copyright (C) 2007, Digium, Inc.
5  *
6  * Steve Murphy <murf@digium.com>
7  * 
8  * Doubly-Linked List Macros--
9  * Based on linkedlists.h (to the point of plagiarism!), which is by:
10  *
11  * Mark Spencer <markster@digium.com>
12  * Kevin P. Fleming <kpfleming@digium.com>
13  *
14  * See http://www.asterisk.org for more information about
15  * the Asterisk project. Please do not directly contact
16  * any of the maintainers of this project for assistance;
17  * the project provides a web site, mailing lists and IRC
18  * channels for your use.
19  *
20  * This program is free software, distributed under the terms of
21  * the GNU General Public License Version 2. See the LICENSE file
22  * at the top of the source tree.
23  */
24
25 #ifndef ASTERISK_DLINKEDLISTS_H
26 #define ASTERISK_DLINKEDLISTS_H
27
28 #include "asterisk/lock.h"
29
30 /*!
31   \file dlinkedlists.h
32   \brief A set of macros to manage doubly-linked lists.
33 */
34
35 /*!
36   \brief Locks a list.
37   \param head This is a pointer to the list head structure
38
39   This macro attempts to place an exclusive lock in the
40   list head structure pointed to by head.
41   \retval 0 on success
42   \retval non-zero on failure
43 */
44 #define AST_DLLIST_LOCK(head)                                           \
45         ast_mutex_lock(&(head)->lock) 
46
47 /*!
48   \brief Write locks a list.
49   \param head This is a pointer to the list head structure
50
51   This macro attempts to place an exclusive write lock in the
52   list head structure pointed to by head.
53   \retval 0 on success
54   \retval non-zero on failure
55 */
56 #define AST_RWDLLIST_WRLOCK(head)                                         \
57         ast_rwlock_wrlock(&(head)->lock)
58
59 /*!
60   \brief Read locks a list.
61   \param head This is a pointer to the list head structure
62
63   This macro attempts to place a read lock in the
64   list head structure pointed to by head.
65   \retval 0 on success
66   \retval non-zero on failure
67 */
68 #define AST_RWDLLIST_RDLOCK(head)                                         \
69         ast_rwlock_rdlock(&(head)->lock)
70         
71 /*!
72   \brief Locks a list, without blocking if the list is locked.
73   \param head This is a pointer to the list head structure
74
75   This macro attempts to place an exclusive lock in the
76   list head structure pointed to by head.
77   \retval 0 on success
78   \retval non-zero on failure
79 */
80 #define AST_DLLIST_TRYLOCK(head)                                                \
81         ast_mutex_trylock(&(head)->lock) 
82
83 /*!
84   \brief Write locks a list, without blocking if the list is locked.
85   \param head This is a pointer to the list head structure
86
87   This macro attempts to place an exclusive write lock in the
88   list head structure pointed to by head.
89   \retval 0 on success
90   \retval non-zero on failure
91 */
92 #define AST_RWDLLIST_TRYWRLOCK(head)                                      \
93         ast_rwlock_trywrlock(&(head)->lock)
94
95 /*!
96   \brief Read 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 a read 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_RWDLLIST_TRYRDLOCK(head)                                      \
105         ast_rwlock_tryrdlock(&(head)->lock)
106         
107 /*!
108   \brief Attempts to unlock a list.
109   \param head This is a pointer to the list head structure
110
111   This macro attempts to remove an exclusive lock from the
112   list head structure pointed to by head. If the list
113   was not locked by this thread, this macro has no effect.
114 */
115 #define AST_DLLIST_UNLOCK(head)                                                 \
116         ast_mutex_unlock(&(head)->lock)
117
118 /*!
119   \brief Attempts to unlock a read/write based list.
120   \param head This is a pointer to the list head structure
121
122   This macro attempts to remove a read or write lock from the
123   list head structure pointed to by head. If the list
124   was not locked by this thread, this macro has no effect.
125 */
126 #define AST_RWDLLIST_UNLOCK(head)                                         \
127         ast_rwlock_unlock(&(head)->lock)
128
129 /*!
130   \brief Defines a structure to be used to hold a list of specified type.
131   \param name This will be the name of the defined structure.
132   \param type This is the type of each list entry.
133
134   This macro creates a structure definition that can be used
135   to hold a list of the entries of type \a type. It does not actually
136   declare (allocate) a structure; to do that, either follow this
137   macro with the desired name of the instance you wish to declare,
138   or use the specified \a name to declare instances elsewhere.
139
140   Example usage:
141   \code
142   static AST_DLLIST_HEAD(entry_list, entry) entries;
143   \endcode
144
145   This would define \c struct \c entry_list, and declare an instance of it named
146   \a entries, all intended to hold a list of type \c struct \c entry.
147 */
148 #define AST_DLLIST_HEAD(name, type)                                     \
149 struct name {                                                           \
150         struct type *first;                                             \
151         struct type *last;                                              \
152         ast_mutex_t lock;                                               \
153 }
154
155 /*!
156   \brief Defines a structure to be used to hold a read/write list of specified type.
157   \param name This will be the name of the defined structure.
158   \param type This is the type of each list entry.
159
160   This macro creates a structure definition that can be used
161   to hold a list of the entries of type \a type. It does not actually
162   declare (allocate) a structure; to do that, either follow this
163   macro with the desired name of the instance you wish to declare,
164   or use the specified \a name to declare instances elsewhere.
165
166   Example usage:
167   \code
168   static AST_RWDLLIST_HEAD(entry_list, entry) entries;
169   \endcode
170
171   This would define \c struct \c entry_list, and declare an instance of it named
172   \a entries, all intended to hold a list of type \c struct \c entry.
173 */
174 #define AST_RWDLLIST_HEAD(name, type)                                     \
175 struct name {                                                           \
176         struct type *first;                                             \
177         struct type *last;                                              \
178         ast_rwlock_t lock;                                              \
179 }
180
181 /*!
182   \brief Defines a structure to be used to hold a list of specified type (with no lock).
183   \param name This will be the name of the defined structure.
184   \param type This is the type of each list entry.
185
186   This macro creates a structure definition that can be used
187   to hold a list of the entries of type \a type. It does not actually
188   declare (allocate) a structure; to do that, either follow this
189   macro with the desired name of the instance you wish to declare,
190   or use the specified \a name to declare instances elsewhere.
191
192   Example usage:
193   \code
194   static AST_DLLIST_HEAD_NOLOCK(entry_list, entry) entries;
195   \endcode
196
197   This would define \c struct \c entry_list, and declare an instance of it named
198   \a entries, all intended to hold a list of type \c struct \c entry.
199 */
200 #define AST_DLLIST_HEAD_NOLOCK(name, type)                              \
201 struct name {                                                           \
202         struct type *first;                                             \
203         struct type *last;                                              \
204 }
205
206 /*!
207   \brief Defines initial values for a declaration of AST_DLLIST_HEAD
208 */
209 #define AST_DLLIST_HEAD_INIT_VALUE      {               \
210         .first = NULL,                                  \
211         .last = NULL,                                   \
212         .lock = AST_MUTEX_INIT_VALUE,                   \
213         }
214
215 /*!
216   \brief Defines initial values for a declaration of AST_RWDLLIST_HEAD
217 */
218 #define AST_RWDLLIST_HEAD_INIT_VALUE      {               \
219         .first = NULL,                                  \
220         .last = NULL,                                   \
221         .lock = AST_RWLOCK_INIT_VALUE,                  \
222         }
223
224 /*!
225   \brief Defines initial values for a declaration of AST_DLLIST_HEAD_NOLOCK
226 */
227 #define AST_DLLIST_HEAD_NOLOCK_INIT_VALUE       {       \
228         .first = NULL,                                  \
229         .last = NULL,                                   \
230         }
231
232 /*!
233   \brief Defines a structure to be used to hold a list of specified type, statically initialized.
234   \param name This will be the name of the defined structure.
235   \param type This is the type of each list entry.
236
237   This macro creates a structure definition that can be used
238   to hold a list of the entries of type \a type, and allocates an instance
239   of it, initialized to be empty.
240
241   Example usage:
242   \code
243   static AST_DLLIST_HEAD_STATIC(entry_list, entry);
244   \endcode
245
246   This would define \c struct \c entry_list, intended to hold a list of
247   type \c struct \c entry.
248 */
249 #if defined(AST_MUTEX_INIT_W_CONSTRUCTORS)
250 #define AST_DLLIST_HEAD_STATIC(name, type)                              \
251 struct name {                                                           \
252         struct type *first;                                             \
253         struct type *last;                                              \
254         ast_mutex_t lock;                                               \
255 } name;                                                                 \
256 static void  __attribute__ ((constructor)) __init_##name(void)          \
257 {                                                                       \
258         AST_DLLIST_HEAD_INIT(&name);                                    \
259 }                                                                       \
260 static void  __attribute__ ((destructor)) __fini_##name(void)           \
261 {                                                                       \
262         AST_DLLIST_HEAD_DESTROY(&name);                                 \
263 }                                                                       \
264 struct __dummy_##name
265 #else
266 #define AST_DLLIST_HEAD_STATIC(name, type)                              \
267 struct name {                                                           \
268         struct type *first;                                             \
269         struct type *last;                                              \
270         ast_mutex_t lock;                                               \
271 } name = AST_DLLIST_HEAD_INIT_VALUE
272 #endif
273
274 /*!
275   \brief Defines a structure to be used to hold a read/write list of specified type, statically initialized.
276   \param name This will be the name of the defined structure.
277   \param type This is the type of each list entry.
278
279   This macro creates a structure definition that can be used
280   to hold a list of the entries of type \a type, and allocates an instance
281   of it, initialized to be empty.
282
283   Example usage:
284   \code
285   static AST_RWDLLIST_HEAD_STATIC(entry_list, entry);
286   \endcode
287
288   This would define \c struct \c entry_list, intended to hold a list of
289   type \c struct \c entry.
290 */
291 #ifndef AST_RWLOCK_INIT_VALUE
292 #define AST_RWDLLIST_HEAD_STATIC(name, type)                              \
293 struct name {                                                           \
294         struct type *first;                                             \
295         struct type *last;                                              \
296         ast_rwlock_t lock;                                              \
297 } name;                                                                 \
298 static void  __attribute__ ((constructor)) __init_##name(void)          \
299 {                                                                       \
300         AST_RWDLLIST_HEAD_INIT(&name);                                    \
301 }                                                                       \
302 static void  __attribute__ ((destructor)) __fini_##name(void)           \
303 {                                                                       \
304         AST_RWDLLIST_HEAD_DESTROY(&name);                                 \
305 }                                                                       \
306 struct __dummy_##name
307 #else
308 #define AST_RWDLLIST_HEAD_STATIC(name, type)                              \
309 struct name {                                                           \
310         struct type *first;                                             \
311         struct type *last;                                              \
312         ast_rwlock_t lock;                                              \
313 } name = AST_RWDLLIST_HEAD_INIT_VALUE
314 #endif
315
316 /*!
317   \brief Defines a structure to be used to hold a list of specified type, statically initialized.
318
319   This is the same as AST_DLLIST_HEAD_STATIC, except without the lock included.
320 */
321 #define AST_DLLIST_HEAD_NOLOCK_STATIC(name, type)                               \
322 struct name {                                                           \
323         struct type *first;                                             \
324         struct type *last;                                              \
325 } name = AST_DLLIST_HEAD_NOLOCK_INIT_VALUE
326
327 /*!
328   \brief Initializes a list head structure with a specified first entry.
329   \param head This is a pointer to the list head structure
330   \param entry pointer to the list entry that will become the head of the list
331
332   This macro initializes a list head structure by setting the head
333   entry to the supplied value and recreating the embedded lock.
334 */
335 #define AST_DLLIST_HEAD_SET(head, entry) do {                           \
336         (head)->first = (entry);                                        \
337         (head)->last = (entry);                                         \
338         ast_mutex_init(&(head)->lock);                                  \
339 } while (0)
340
341 /*!
342   \brief Initializes an rwlist head structure with a specified first entry.
343   \param head This is a pointer to the list head structure
344   \param entry pointer to the list entry that will become the head of the list
345
346   This macro initializes a list head structure by setting the head
347   entry to the supplied value and recreating the embedded lock.
348 */
349 #define AST_RWDLLIST_HEAD_SET(head, entry) do {                           \
350         (head)->first = (entry);                                        \
351         (head)->last = (entry);                                         \
352         ast_rwlock_init(&(head)->lock);                                 \
353 } while (0)
354
355 /*!
356   \brief Initializes a list head structure with a specified first entry.
357   \param head This is a pointer to the list head structure
358   \param entry pointer to the list entry that will become the head of the list
359
360   This macro initializes a list head structure by setting the head
361   entry to the supplied value.
362 */
363 #define AST_DLLIST_HEAD_SET_NOLOCK(head, entry) do {                    \
364         (head)->first = (entry);                                        \
365         (head)->last = (entry);                                         \
366 } while (0)
367
368 /*!
369   \brief Declare previous/forward links inside a list entry.
370   \param type This is the type of each list entry.
371
372   This macro declares a structure to be used to doubly link list entries together.
373   It must be used inside the definition of the structure named in
374   \a type, as follows:
375
376   \code
377   struct list_entry {
378         ...
379         AST_DLLIST_ENTRY(list_entry) list;
380   }
381   \endcode
382
383   The field name \a list here is arbitrary, and can be anything you wish.
384 */
385 #define AST_DLLIST_ENTRY(type)                  \
386 struct {                                                                \
387         struct type *prev;                                              \
388         struct type *next;                                              \
389 }
390
391 #define AST_RWDLLIST_ENTRY AST_DLLIST_ENTRY
392  
393 /*!
394   \brief Returns the first entry contained in a list.
395   \param head This is a pointer to the list head structure
396  */
397 #define AST_DLLIST_FIRST(head)  ((head)->first)
398
399 #define AST_RWDLLIST_FIRST AST_DLLIST_FIRST
400
401 /*!
402   \brief Returns the last entry contained in a list.
403   \param head This is a pointer to the list head structure
404  */
405 #define AST_DLLIST_LAST(head)   ((head)->last)
406
407 #define AST_RWDLLIST_LAST AST_DLLIST_LAST
408
409 /*!
410   \brief Returns the next entry in the list after the given entry.
411   \param elm This is a pointer to the current entry.
412   \param field This is the name of the field (declared using AST_DLLIST_ENTRY())
413   used to link entries of this list together.
414 */
415 #define AST_DLLIST_NEXT(elm, field)     ((elm)->field.next)
416
417 #define AST_RWDLLIST_NEXT AST_DLLIST_NEXT
418
419 /*!
420   \brief Returns the previous entry in the list before the given entry.
421   \param elm This is a pointer to the current entry.
422   \param field This is the name of the field (declared using AST_DLLIST_ENTRY())
423   used to link entries of this list together.
424 */
425 #define AST_DLLIST_PREV(elm, field)     ((elm)->field.prev)
426
427 #define AST_RWDLLIST_PREV AST_DLLIST_PREV
428
429 /*!
430   \brief Checks whether the specified list contains any entries.
431   \param head This is a pointer to the list head structure
432
433   \return non-zero if the list has entries
434   \return zero if not.
435  */
436 #define AST_DLLIST_EMPTY(head)  (AST_DLLIST_FIRST(head) == NULL)
437
438 #define AST_RWDLLIST_EMPTY AST_DLLIST_EMPTY
439
440 /*!
441   \brief Loops over (traverses) the entries in a list.
442   \param head This is a pointer to the list head structure
443   \param var This is the name of the variable that will hold a pointer to the
444   current list entry on each iteration. It must be declared before calling
445   this macro.
446   \param field This is the name of the field (declared using AST_DLLIST_ENTRY())
447   used to link entries of this list together.
448
449   This macro is use to loop over (traverse) the entries in a list. It uses a
450   \a for loop, and supplies the enclosed code with a pointer to each list
451   entry as it loops. It is typically used as follows:
452   \code
453   static AST_DLLIST_HEAD(entry_list, list_entry) entries;
454   ...
455   struct list_entry {
456         ...
457         AST_DLLIST_ENTRY(list_entry) list;
458   }
459   ...
460   struct list_entry *current;
461   ...
462   AST_DLLIST_TRAVERSE(&entries, current, list) {
463      (do something with current here)
464   }
465   \endcode
466   \warning If you modify the forward-link pointer contained in the \a current entry while
467   inside the loop, the behavior will be unpredictable. At a minimum, the following
468   macros will modify the forward-link pointer, and should not be used inside
469   AST_DLLIST_TRAVERSE() against the entry pointed to by the \a current pointer without
470   careful consideration of their consequences:
471   \li AST_DLLIST_NEXT() (when used as an lvalue)
472   \li AST_DLLIST_INSERT_AFTER()
473   \li AST_DLLIST_INSERT_HEAD()
474   \li AST_DLLIST_INSERT_TAIL()
475 */
476 #define AST_DLLIST_TRAVERSE(head,var,field)                             \
477         for((var) = (head)->first; (var); (var) = (var)->field.next)
478
479 #define AST_RWDLLIST_TRAVERSE AST_DLLIST_TRAVERSE
480
481 /*!
482   \brief Loops over (traverses) the entries in a list in reverse order, starting at the end.
483   \param head This is a pointer to the list head structure
484   \param var This is the name of the variable that will hold a pointer to the
485   current list entry on each iteration. It must be declared before calling
486   this macro.
487   \param field This is the name of the field (declared using AST_DLLIST_ENTRY())
488   used to link entries of this list together.
489
490   This macro is use to loop over (traverse) the entries in a list in reverse order. It uses a
491   \a for loop, and supplies the enclosed code with a pointer to each list
492   entry as it loops. It is typically used as follows:
493   \code
494   static AST_DLLIST_HEAD(entry_list, list_entry) entries;
495   ...
496   struct list_entry {
497         ...
498         AST_DLLIST_ENTRY(list_entry) list;
499   }
500   ...
501   struct list_entry *current;
502   ...
503   AST_DLLIST_TRAVERSE_BACKWARDS(&entries, current, list) {
504      (do something with current here)
505   }
506   \endcode
507   \warning If you modify the forward-link pointer contained in the \a current entry while
508   inside the loop, the behavior will be unpredictable. At a minimum, the following
509   macros will modify the forward-link pointer, and should not be used inside
510   AST_DLLIST_TRAVERSE() against the entry pointed to by the \a current pointer without
511   careful consideration of their consequences:
512   \li AST_DLLIST_PREV() (when used as an lvalue)
513   \li AST_DLLIST_INSERT_BEFORE()
514   \li AST_DLLIST_INSERT_HEAD()
515   \li AST_DLLIST_INSERT_TAIL()
516 */
517 #define AST_DLLIST_TRAVERSE_BACKWARDS(head,var,field)                           \
518         for((var) = (head)->last; (var); (var) = (var)->field.prev)
519
520 #define AST_RWDLLIST_TRAVERSE_BACKWARDS AST_DLLIST_TRAVERSE_BACKWARDS
521
522 /*!
523   \brief Loops safely over (traverses) the entries in a list.
524   \param head This is a pointer to the list head structure
525   \param var This is the name of the variable that will hold a pointer to the
526   current list entry on each iteration. It must be declared before calling
527   this macro.
528   \param field This is the name of the field (declared using AST_DLLIST_ENTRY())
529   used to link entries of this list together.
530
531   This macro is used to safely loop over (traverse) the entries in a list. It
532   uses a \a for loop, and supplies the enclosed code with a pointer to each list
533   entry as it loops. It is typically used as follows:
534
535   \code
536   static AST_DLLIST_HEAD(entry_list, list_entry) entries;
537   ...
538   struct list_entry {
539         ...
540         AST_DLLIST_ENTRY(list_entry) list;
541   }
542   ...
543   struct list_entry *current;
544   ...
545   AST_DLLIST_TRAVERSE_SAFE_BEGIN(&entries, current, list) {
546      (do something with current here)
547   }
548   AST_DLLIST_TRAVERSE_SAFE_END;
549   \endcode
550
551   It differs from AST_DLLIST_TRAVERSE() in that the code inside the loop can modify
552   (or even free, after calling AST_DLLIST_REMOVE_CURRENT()) the entry pointed to by
553   the \a current pointer without affecting the loop traversal.
554 */
555 #define AST_DLLIST_TRAVERSE_SAFE_BEGIN(head, var, field) {                              \
556         typeof((head)) __list_head = head;                                              \
557         typeof(__list_head->first) __list_next;                                         \
558         typeof(__list_head->first) __list_prev = NULL;                                  \
559         typeof(__list_head->first) __new_prev = NULL;                                   \
560         for ((var) = __list_head->first, __new_prev = (var),                            \
561               __list_next = (var) ? (var)->field.next : NULL;                           \
562              (var);                                                                     \
563              __list_prev = __new_prev, (var) = __list_next,                             \
564              __new_prev = (var),                                                        \
565              __list_next = (var) ? (var)->field.next : NULL                             \
566             )
567
568 #define AST_RWDLLIST_TRAVERSE_SAFE_BEGIN AST_DLLIST_TRAVERSE_SAFE_BEGIN
569
570 /*!
571   \brief Loops safely over (traverses) the entries in a list.
572   \param head This is a pointer to the list head structure
573   \param var This is the name of the variable that will hold a pointer to the
574   current list entry on each iteration. It must be declared before calling
575   this macro.
576   \param field This is the name of the field (declared using AST_DLLIST_ENTRY())
577   used to link entries of this list together.
578
579   This macro is used to safely loop over (traverse) the entries in a list. It
580   uses a \a for loop, and supplies the enclosed code with a pointer to each list
581   entry as it loops. It is typically used as follows:
582
583   \code
584   static AST_DLLIST_HEAD(entry_list, list_entry) entries;
585   ...
586   struct list_entry {
587         ...
588         AST_DLLIST_ENTRY(list_entry) list;
589   }
590   ...
591   struct list_entry *current;
592   ...
593   AST_DLLIST_TRAVERSE_SAFE_BEGIN(&entries, current, list) {
594      (do something with current here)
595   }
596   AST_DLLIST_TRAVERSE_SAFE_END;
597   \endcode
598
599   It differs from AST_DLLIST_TRAVERSE() in that the code inside the loop can modify
600   (or even free, after calling AST_DLLIST_REMOVE_CURRENT()) the entry pointed to by
601   the \a current pointer without affecting the loop traversal.
602 */
603 #define AST_DLLIST_TRAVERSE_BACKWARDS_SAFE_BEGIN(head, var, field) {                            \
604         typeof((head)) __list_head = head;                                              \
605         typeof(__list_head->first) __list_next;                                         \
606         typeof(__list_head->first) __list_prev = NULL;                                  \
607         typeof(__list_head->first) __new_prev = NULL;                                   \
608         for ((var) = __list_head->last, __new_prev = (var),                             \
609                          __list_next = NULL, __list_prev = (var) ? (var)->field.prev : NULL;    \
610              (var);                                                                     \
611              __list_next = __new_prev, (var) = __list_prev,                             \
612              __new_prev = (var),                                                        \
613              __list_prev = (var) ? (var)->field.prev : NULL                             \
614             )
615
616 #define AST_RWDLLIST_TRAVERSE_BACKWARDS_SAFE_BEGIN AST_DLLIST_TRAVERSE_BACKWARDS_SAFE_BEGIN
617
618 /*!
619   \brief Removes the \a current entry from a list during a traversal.
620   \param field This is the name of the field (declared using AST_DLLIST_ENTRY())
621   used to link entries of this list together.
622
623   \note This macro can \b only be used inside an AST_DLLIST_TRAVERSE_SAFE_BEGIN()
624   block; it is used to unlink the current entry from the list without affecting
625   the list traversal (and without having to re-traverse the list to modify the
626   previous entry, if any).
627  */
628 #define AST_DLLIST_REMOVE_CURRENT(field) do {                   \
629         __new_prev->field.next = NULL;                                          \
630         __new_prev->field.prev = NULL;                                          \
631         if (__list_next)                                                                        \
632                 __new_prev = __list_prev;                                               \
633         else                                                                                            \
634                 __new_prev = NULL;                                                              \
635         if (__list_prev) {                                  \
636                 if (__list_next)                                                                \
637                         __list_next->field.prev = __list_prev;          \
638                 __list_prev->field.next = __list_next;                  \
639         } else {                                            \
640                 __list_head->first = __list_next;                               \
641                 if (__list_next)                                                                \
642                         __list_next->field.prev = NULL;                         \
643         }                                                                                                       \
644         if (!__list_next)                                                                       \
645                 __list_head->last = __list_prev;                                \
646         } while (0)
647
648 #define AST_RWDLLIST_REMOVE_CURRENT AST_DLLIST_REMOVE_CURRENT
649
650 #define AST_DLLIST_MOVE_CURRENT(newhead, field) do { \
651         typeof ((newhead)->first) __list_cur = __new_prev;                              \
652         AST_DLLIST_REMOVE_CURRENT(field);                                                       \
653         AST_DLLIST_INSERT_TAIL((newhead), __list_cur, field);                           \
654         } while (0)
655
656 #define AST_RWDLLIST_MOVE_CURRENT AST_DLLIST_MOVE_CURRENT
657
658 #define AST_DLLIST_MOVE_CURRENT_BACKWARDS(newhead, field) do { \
659         typeof ((newhead)->first) __list_cur = __new_prev;                      \
660         if (!__list_next) {                                                                                     \
661                 AST_DLLIST_REMOVE_CURRENT(field);                                               \
662                 __new_prev = NULL;                                                                              \
663                 AST_DLLIST_INSERT_HEAD((newhead), __list_cur, field);   \
664         } else {                                                                                                        \
665                 AST_DLLIST_REMOVE_CURRENT(field);                                               \
666                 AST_DLLIST_INSERT_HEAD((newhead), __list_cur, field);   \
667         }} while (0)
668
669 #define AST_RWDLLIST_MOVE_CURRENT_BACKWARDS AST_DLLIST_MOVE_CURRENT
670
671 /*!
672   \brief Inserts a list entry before the current entry during a traversal.
673   \param elm This is a pointer to the entry to be inserted.
674   \param field This is the name of the field (declared using AST_DLLIST_ENTRY())
675   used to link entries of this list together.
676
677   \note This macro can \b only be used inside an AST_DLLIST_TRAVERSE_SAFE_BEGIN()
678   block.
679  */
680 #define AST_DLLIST_INSERT_BEFORE_CURRENT(elm, field) do {       \
681         if (__list_prev) {                                                                              \
682                 (elm)->field.next = __list_prev->field.next;            \
683                 (elm)->field.prev = __list_prev;                                        \
684                 if (__list_prev->field.next)                        \
685                         __list_prev->field.next->field.prev = (elm);    \
686                 __list_prev->field.next = (elm);                                        \
687         } else {                                                                                                \
688                 (elm)->field.next = __list_head->first;                 \
689                 __list_head->first->field.prev = (elm);                 \
690                 (elm)->field.prev = NULL;                                               \
691                 __list_head->first = (elm);                                             \
692         }                                                                                                       \
693 } while (0)
694
695 #define AST_RWDLLIST_INSERT_BEFORE_CURRENT AST_DLLIST_INSERT_BEFORE_CURRENT
696
697 /*!
698   \brief Inserts a list entry after the current entry during a backwards traversal. Since
699          this is a backwards traversal, this will insert the entry AFTER the current
700          element. Since this is a backwards traveral, though, this would be BEFORE
701          the current entry in traversal order. Confusing? 
702   \param elm This is a pointer to the entry to be inserted.
703   \param field This is the name of the field (declared using AST_DLLIST_ENTRY())
704   used to link entries of this list together.
705
706   \note This macro can \b only be used inside an AST_DLLIST_TRAVERSE_BACKWARDS_SAFE_BEGIN()
707   block. If you use this with the AST_DLLIST_TRAVERSE_SAFE_BEGIN(), be prepared for
708   strange things!
709  */
710 #define AST_DLLIST_INSERT_BEFORE_CURRENT_BACKWARDS(elm, field) do {                     \
711         if (__list_next) {                                                              \
712                 (elm)->field.next = __list_next;                        \
713                 (elm)->field.prev = __new_prev;                         \
714                 __new_prev->field.next = (elm);                         \
715                 __list_next->field.prev = (elm);                        \
716         } else {                                                                                \
717                 (elm)->field.prev = __list_head->last;          \
718                 (elm)->field.next = NULL;                                       \
719                 __list_head->last->field.next = (elm);          \
720                 __list_head->last = (elm);                                      \
721         }                                                                                               \
722 } while (0)
723
724 #define AST_RWDLLIST_INSERT_BEFORE_CURRENT_BACKWARDS AST_DLLIST_INSERT_BEFORE_CURRENT_BACKWARDS
725
726 /*!
727   \brief Closes a safe loop traversal block.
728  */
729 #define AST_DLLIST_TRAVERSE_SAFE_END  }
730
731 #define AST_RWDLLIST_TRAVERSE_SAFE_END AST_DLLIST_TRAVERSE_SAFE_END
732
733 /*!
734   \brief Closes a safe loop traversal block.
735  */
736 #define AST_DLLIST_TRAVERSE_BACKWARDS_SAFE_END  }
737
738 #define AST_RWDLLIST_TRAVERSE_BACKWARDS_SAFE_END AST_DLLIST_TRAVERSE_BACKWARDS_SAFE_END
739
740 /*!
741   \brief Initializes a list head structure.
742   \param head This is a pointer to the list head structure
743
744   This macro initializes a list head structure by setting the head
745   entry to \a NULL (empty list) and recreating the embedded lock.
746 */
747 #define AST_DLLIST_HEAD_INIT(head) {                                    \
748         (head)->first = NULL;                                           \
749         (head)->last = NULL;                                            \
750         ast_mutex_init(&(head)->lock);                                  \
751 }
752
753 /*!
754   \brief Initializes an rwlist head structure.
755   \param head This is a pointer to the list head structure
756
757   This macro initializes a list head structure by setting the head
758   entry to \a NULL (empty list) and recreating the embedded lock.
759 */
760 #define AST_RWDLLIST_HEAD_INIT(head) {                                    \
761         (head)->first = NULL;                                           \
762         (head)->last = NULL;                                            \
763         ast_rwlock_init(&(head)->lock);                                 \
764 }
765
766 /*!
767   \brief Destroys a list head structure.
768   \param head This is a pointer to the list head structure
769
770   This macro destroys a list head structure by setting the head
771   entry to \a NULL (empty list) and destroying the embedded lock.
772   It does not free the structure from memory.
773 */
774 #define AST_DLLIST_HEAD_DESTROY(head) {                                 \
775         (head)->first = NULL;                                           \
776         (head)->last = NULL;                                            \
777         ast_mutex_destroy(&(head)->lock);                               \
778 }
779
780 /*!
781   \brief Destroys an rwlist head structure.
782   \param head This is a pointer to the list head structure
783
784   This macro destroys a list head structure by setting the head
785   entry to \a NULL (empty list) and destroying the embedded lock.
786   It does not free the structure from memory.
787 */
788 #define AST_RWDLLIST_HEAD_DESTROY(head) {                                 \
789         (head)->first = NULL;                                           \
790         (head)->last = NULL;                                            \
791         ast_rwlock_destroy(&(head)->lock);                              \
792 }
793
794 /*!
795   \brief Initializes a list head structure.
796   \param head This is a pointer to the list head structure
797
798   This macro initializes a list head structure by setting the head
799   entry to \a NULL (empty list). There is no embedded lock handling
800   with this macro.
801 */
802 #define AST_DLLIST_HEAD_INIT_NOLOCK(head) {                             \
803         (head)->first = NULL;                                           \
804         (head)->last = NULL;                                            \
805 }
806
807 /*!
808   \brief Inserts a list entry after a given entry.
809   \param head This is a pointer to the list head structure
810   \param listelm This is a pointer to the entry after which the new entry should
811   be inserted.
812   \param elm This is a pointer to the entry to be inserted.
813   \param field This is the name of the field (declared using AST_DLLIST_ENTRY())
814   used to link entries of this list together.
815  */
816 #define AST_DLLIST_INSERT_AFTER(head, listelm, elm, field) do {         \
817         (elm)->field.next = (listelm)->field.next;                      \
818         (elm)->field.prev = (listelm);                  \
819         if ((listelm)->field.next)                              \
820                 (listelm)->field.next->field.prev = (elm);      \
821         (listelm)->field.next = (elm);                                  \
822         if ((head)->last == (listelm))                                  \
823                 (head)->last = (elm);                                   \
824 } while (0)
825
826 #define AST_RWDLLIST_INSERT_AFTER AST_DLLIST_INSERT_AFTER
827
828 /*!
829   \brief Inserts a list entry before a given entry.
830   \param head This is a pointer to the list head structure
831   \param listelm This is a pointer to the entry before which the new entry should
832   be inserted.
833   \param elm This is a pointer to the entry to be inserted.
834   \param field This is the name of the field (declared using AST_DLLIST_ENTRY())
835   used to link entries of this list together.
836  */
837 #define AST_DLLIST_INSERT_BEFORE(head, listelm, elm, field) do {                \
838         (elm)->field.next = (listelm);                  \
839         (elm)->field.prev = (listelm)->field.prev;                      \
840         if ((listelm)->field.prev)                              \
841                 (listelm)->field.prev->field.next = (elm);      \
842         (listelm)->field.prev = (elm);                                  \
843         if ((head)->first == (listelm))                                 \
844                 (head)->first = (elm);                                  \
845 } while (0)
846
847 #define AST_RWDLLIST_INSERT_BEFORE AST_DLLIST_INSERT_BEFORE
848
849 /*!
850   \brief Inserts a list entry at the head of a list.
851   \param head This is a pointer to the list head structure
852   \param elm This is a pointer to the entry to be inserted.
853   \param field This is the name of the field (declared using AST_DLLIST_ENTRY())
854   used to link entries of this list together.
855  */
856 #define AST_DLLIST_INSERT_HEAD(head, elm, field) do {                   \
857                 (elm)->field.next = (head)->first;                      \
858                 if ((head)->first)                          \
859                         (head)->first->field.prev = (elm);                      \
860                 (elm)->field.prev = NULL;                       \
861                 (head)->first = (elm);                                  \
862                 if (!(head)->last)                                      \
863                         (head)->last = (elm);                           \
864 } while (0)
865
866 #define AST_RWDLLIST_INSERT_HEAD AST_DLLIST_INSERT_HEAD
867
868 /*!
869   \brief Appends a list entry to the tail of a list.
870   \param head This is a pointer to the list head structure
871   \param elm This is a pointer to the entry to be appended.
872   \param field This is the name of the field (declared using AST_DLLIST_ENTRY())
873   used to link entries of this list together.
874
875   Note: The link field in the appended entry is \b not modified, so if it is
876   actually the head of a list itself, the entire list will be appended
877   temporarily (until the next AST_DLLIST_INSERT_TAIL is performed).
878  */
879 #define AST_DLLIST_INSERT_TAIL(head, elm, field) do {   \
880       if (!(head)->first) {                                             \
881                 (head)->first = (elm);                                  \
882                 (head)->last = (elm);                   \
883                 (elm)->field.next = NULL;                               \
884                 (elm)->field.prev = NULL;                               \
885       } else {                                                                  \
886                 (head)->last->field.next = (elm);               \
887                 (elm)->field.prev = (head)->last;               \
888                 (elm)->field.next = NULL;                               \
889                 (head)->last = (elm);                                   \
890       }                                                                                 \
891 } while (0)
892
893 #define AST_RWDLLIST_INSERT_TAIL AST_DLLIST_INSERT_TAIL
894
895 /*!
896   \brief Appends a whole list to the tail of a list.
897   \param head This is a pointer to the list head structure
898   \param list This is a pointer to the list to be appended.
899   \param field This is the name of the field (declared using AST_DLLIST_ENTRY())
900   used to link entries of this list together.
901
902   Note: The source list (the \a list parameter) will be empty after
903   calling this macro (the list entries are \b moved to the target list).
904  */
905 #define AST_DLLIST_APPEND_DLLIST(head, list, field) do {                        \
906       if (!(head)->first) {                                             \
907                 (head)->first = (list)->first;                          \
908                 (head)->last = (list)->last;                            \
909       } else {                                                          \
910                 (head)->last->field.next = (list)->first;               \
911                 (list)->first->field.prev = (head)->last;               \
912                 (head)->last = (list)->last;                            \
913       }                                                                 \
914       (list)->first = NULL;                                             \
915       (list)->last = NULL;                                              \
916 } while (0)
917
918 #define AST_RWDLLIST_APPEND_DLLIST AST_DLLIST_APPEND_DLLIST
919
920 /*!
921   \brief Removes and returns the head entry from a list.
922   \param head This is a pointer to the list head structure
923   \param field This is the name of the field (declared using AST_DLLIST_ENTRY())
924   used to link entries of this list together.
925
926   Removes the head entry from the list, and returns a pointer to it.
927   This macro is safe to call on an empty list.
928  */
929 #define AST_DLLIST_REMOVE_HEAD(head, field) ({                          \
930                 typeof((head)->first) cur = (head)->first;              \
931                 if (cur) {                                              \
932                         (head)->first = cur->field.next;                \
933                         if (cur->field.next)                \
934                                 cur->field.next->field.prev = NULL;     \
935                         cur->field.next = NULL;                         \
936                         if ((head)->last == cur)                        \
937                                 (head)->last = NULL;                    \
938                 }                                                       \
939                 cur;                                                    \
940         })
941
942 #define AST_RWDLLIST_REMOVE_HEAD AST_DLLIST_REMOVE_HEAD
943
944 /*!
945   \brief Removes a specific entry from a list.
946   \param head This is a pointer to the list head structure
947   \param elm This is a pointer to the entry to be removed.
948   \param field This is the name of the field (declared using AST_DLLIST_ENTRY())
949   used to link entries of this list together.
950   \warning The removed entry is \b not freed nor modified in any way.
951  */
952 #define AST_DLLIST_REMOVE(head, elm, field) ({                          \
953         __typeof(elm) __res = (elm);                                            \
954         if ((head)->first == (elm)) {                                                           \
955                 (head)->first = (elm)->field.next;                                              \
956                 if ((elm)->field.next)                                                                  \
957                         (elm)->field.next->field.prev = NULL;                           \
958                 if ((head)->last == (elm))                                                              \
959                         (head)->last = NULL;                                                            \
960         } else {                                                                                                                \
961                 (elm)->field.prev->field.next = (elm)->field.next;                      \
962                 if ((elm)->field.next)                                                                                  \
963                         (elm)->field.next->field.prev = (elm)->field.prev;                      \
964                 if ((head)->last == (elm))                                                                              \
965                         (head)->last = (elm)->field.prev;                                                       \
966         }                                                                                                                                       \
967         (elm)->field.next = NULL;                                                                                       \
968         (elm)->field.prev = NULL;                                                                                       \
969         (__res);                                                                                                                        \
970 })
971
972 #define AST_RWDLLIST_REMOVE AST_DLLIST_REMOVE
973
974 #endif /* _ASTERISK_DLINKEDLISTS_H */