Asterisk - The Open Source Telephony Project GIT-master-f3e88d3
dlinkedlists.h
Go to the documentation of this file.
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
32 *
33 * \brief A set of macros to manage doubly-linked lists.
34 */
35
36/*!
37 * \brief Locks a list.
38 * \param head This is a pointer to the list head structure
39 *
40 * This macro attempts to place an exclusive lock in the
41 * list head structure pointed to by head.
42 * \retval 0 on success
43 * \retval non-zero on failure
44 * \since 1.6.1
45 */
46#define AST_DLLIST_LOCK(head) \
47 ast_mutex_lock(&(head)->lock)
48
49/*!
50 * \brief Write locks a list.
51 * \param head This is a pointer to the list head structure
52 *
53 * This macro attempts to place an exclusive write lock in the
54 * list head structure pointed to by head.
55 * \retval 0 on success
56 * \retval non-zero on failure
57 * \since 1.6.1
58 */
59#define AST_RWDLLIST_WRLOCK(head) \
60 ast_rwlock_wrlock(&(head)->lock)
61
62/*!
63 * \brief Read locks a list.
64 * \param head This is a pointer to the list head structure
65 *
66 * This macro attempts to place a read lock in the
67 * list head structure pointed to by head.
68 * \retval 0 on success
69 * \retval non-zero on failure
70 * \since 1.6.1
71 */
72#define AST_RWDLLIST_RDLOCK(head) \
73 ast_rwlock_rdlock(&(head)->lock)
74
75/*!
76 * \brief Locks a list, without blocking if the list is locked.
77 * \param head This is a pointer to the list head structure
78 *
79 * This macro attempts to place an exclusive lock in the
80 * list head structure pointed to by head.
81 * \retval 0 on success
82 * \retval non-zero on failure
83 * \since 1.6.1
84 */
85#define AST_DLLIST_TRYLOCK(head) \
86 ast_mutex_trylock(&(head)->lock)
87
88/*!
89 * \brief Write locks a list, without blocking if the list is locked.
90 * \param head This is a pointer to the list head structure
91 *
92 * This macro attempts to place an exclusive write lock in the
93 * list head structure pointed to by head.
94 * \retval 0 on success
95 * \retval non-zero on failure
96 * \since 1.6.1
97 */
98#define AST_RWDLLIST_TRYWRLOCK(head) \
99 ast_rwlock_trywrlock(&(head)->lock)
100
101/*!
102 * \brief Read locks a list, without blocking if the list is locked.
103 * \param head This is a pointer to the list head structure
104 *
105 * This macro attempts to place a read lock in the
106 * list head structure pointed to by head.
107 * \retval 0 on success
108 * \retval non-zero on failure
109 * \since 1.6.1
110 */
111#define AST_RWDLLIST_TRYRDLOCK(head) \
112 ast_rwlock_tryrdlock(&(head)->lock)
113
114/*!
115 * \brief Attempts to unlock a list.
116 * \param head This is a pointer to the list head structure
117 *
118 * This macro attempts to remove an exclusive lock from the
119 * list head structure pointed to by head. If the list
120 * was not locked by this thread, this macro has no effect.
121 * \since 1.6.1
122 */
123#define AST_DLLIST_UNLOCK(head) \
124 ast_mutex_unlock(&(head)->lock)
125
126/*!
127 * \brief Attempts to unlock a read/write based list.
128 * \param head This is a pointer to the list head structure
129 *
130 * This macro attempts to remove a read or write lock from the
131 * list head structure pointed to by head. If the list
132 * was not locked by this thread, this macro has no effect.
133 * \since 1.6.1
134 */
135#define AST_RWDLLIST_UNLOCK(head) \
136 ast_rwlock_unlock(&(head)->lock)
137
138/*!
139 * \brief Defines a structure to be used to hold a list of specified type.
140 * \param name This will be the name of the defined structure.
141 * \param type This is the type of each list entry.
142 *
143 * This macro creates a structure definition that can be used
144 * to hold a list of the entries of type \a type. It does not actually
145 * declare (allocate) a structure; to do that, either follow this
146 * macro with the desired name of the instance you wish to declare,
147 * or use the specified \a name to declare instances elsewhere.
148 *
149 * Example usage:
150 * \code
151 * static AST_DLLIST_HEAD(entry_list, entry) entries;
152 * \endcode
153 *
154 * This would define \c struct \c entry_list, and declare an instance of it named
155 * \a entries, all intended to hold a list of type \c struct \c entry.
156 * \since 1.6.1
157 */
158#define AST_DLLIST_HEAD(name, type) \
159 struct name { \
160 struct type *first; \
161 struct type *last; \
162 ast_mutex_t lock; \
163 }
164
165/*!
166 * \brief Defines a structure to be used to hold a read/write list of specified type.
167 * \param name This will be the name of the defined structure.
168 * \param type This is the type of each list entry.
169 *
170 * This macro creates a structure definition that can be used
171 * to hold a list of the entries of type \a type. It does not actually
172 * declare (allocate) a structure; to do that, either follow this
173 * macro with the desired name of the instance you wish to declare,
174 * or use the specified \a name to declare instances elsewhere.
175 *
176 * Example usage:
177 * \code
178 * static AST_RWDLLIST_HEAD(entry_list, entry) entries;
179 * \endcode
180 *
181 * This would define \c struct \c entry_list, and declare an instance of it named
182 * \a entries, all intended to hold a list of type \c struct \c entry.
183 * \since 1.6.1
184 */
185#define AST_RWDLLIST_HEAD(name, type) \
186 struct name { \
187 struct type *first; \
188 struct type *last; \
189 ast_rwlock_t lock; \
190 }
191
192/*!
193 * \brief Defines a structure to be used to hold a list of specified type (with no lock).
194 * \param name This will be the name of the defined structure.
195 * \param type This is the type of each list entry.
196 *
197 * This macro creates a structure definition that can be used
198 * to hold a list of the entries of type \a type. It does not actually
199 * declare (allocate) a structure; to do that, either follow this
200 * macro with the desired name of the instance you wish to declare,
201 * or use the specified \a name to declare instances elsewhere.
202 *
203 * Example usage:
204 * \code
205 * static AST_DLLIST_HEAD_NOLOCK(entry_list, entry) entries;
206 * \endcode
207 *
208 * This would define \c struct \c entry_list, and declare an instance of it named
209 * \a entries, all intended to hold a list of type \c struct \c entry.
210 * \since 1.6.1
211 */
212#define AST_DLLIST_HEAD_NOLOCK(name, type) \
213 struct name { \
214 struct type *first; \
215 struct type *last; \
216 }
217
218/*!
219 * \brief Defines initial values for a declaration of AST_DLLIST_HEAD
220 * \since 1.6.1
221 */
222#define AST_DLLIST_HEAD_INIT_VALUE \
223 { \
224 .first = NULL, \
225 .last = NULL, \
226 .lock = AST_MUTEX_INIT_VALUE, \
227 }
228
229/*!
230 * \brief Defines initial values for a declaration of AST_RWDLLIST_HEAD
231 * \since 1.6.1
232 */
233#define AST_RWDLLIST_HEAD_INIT_VALUE \
234 { \
235 .first = NULL, \
236 .last = NULL, \
237 .lock = AST_RWLOCK_INIT_VALUE, \
238 }
239
240/*!
241 * \brief Defines initial values for a declaration of AST_DLLIST_HEAD_NOLOCK
242 * \since 1.6.1
243 */
244#define AST_DLLIST_HEAD_NOLOCK_INIT_VALUE \
245 { \
246 .first = NULL, \
247 .last = NULL, \
248 }
249
250/*!
251 * \brief Defines a structure to be used to hold a list of specified type, statically initialized.
252 * \param name This will be the name of the defined structure.
253 * \param type This is the type of each list entry.
254 *
255 * This macro creates a structure definition that can be used
256 * to hold a list of the entries of type \a type, and allocates an instance
257 * of it, initialized to be empty.
258 *
259 * Example usage:
260 * \code
261 * static AST_DLLIST_HEAD_STATIC(entry_list, entry);
262 * \endcode
263 *
264 * This would define \c struct \c entry_list, intended to hold a list of
265 * type \c struct \c entry.
266 * \since 1.6.1
267 */
268#if defined(AST_MUTEX_INIT_W_CONSTRUCTORS)
269#define AST_DLLIST_HEAD_STATIC(name, type) \
270 struct name { \
271 struct type *first; \
272 struct type *last; \
273 ast_mutex_t lock; \
274 } name; \
275 static void __attribute__((constructor)) __init_##name(void) \
276 { \
277 AST_DLLIST_HEAD_INIT(&name); \
278 } \
279 static void __attribute__((destructor)) __fini_##name(void) \
280 { \
281 AST_DLLIST_HEAD_DESTROY(&name); \
282 } \
283 struct __dummy_##name
284#else
285#define AST_DLLIST_HEAD_STATIC(name, type) \
286 struct name { \
287 struct type *first; \
288 struct type *last; \
289 ast_mutex_t lock; \
290 } name = AST_DLLIST_HEAD_INIT_VALUE
291#endif
292
293/*!
294 * \brief Defines a structure to be used to hold a read/write list of specified type, statically initialized.
295 * \param name This will be the name of the defined structure.
296 * \param type This is the type of each list entry.
297 *
298 * This macro creates a structure definition that can be used
299 * to hold a list of the entries of type \a type, and allocates an instance
300 * of it, initialized to be empty.
301 *
302 * Example usage:
303 * \code
304 * static AST_RWDLLIST_HEAD_STATIC(entry_list, entry);
305 * \endcode
306 *
307 * This would define \c struct \c entry_list, intended to hold a list of
308 * type \c struct \c entry.
309 * \since 1.6.1
310 */
311#ifndef HAVE_PTHREAD_RWLOCK_INITIALIZER
312#define AST_RWDLLIST_HEAD_STATIC(name, type) \
313 struct name { \
314 struct type *first; \
315 struct type *last; \
316 ast_rwlock_t lock; \
317 } name; \
318 static void __attribute__((constructor)) __init_##name(void) \
319 { \
320 AST_RWDLLIST_HEAD_INIT(&name); \
321 } \
322 static void __attribute__((destructor)) __fini_##name(void) \
323 { \
324 AST_RWDLLIST_HEAD_DESTROY(&name); \
325 } \
326 struct __dummy_##name
327#else
328#define AST_RWDLLIST_HEAD_STATIC(name, type) \
329 struct name { \
330 struct type *first; \
331 struct type *last; \
332 ast_rwlock_t lock; \
333 } name = AST_RWDLLIST_HEAD_INIT_VALUE
334#endif
335
336/*!
337 * \brief Defines a structure to be used to hold a list of specified type, statically initialized.
338 *
339 * This is the same as AST_DLLIST_HEAD_STATIC, except without the lock included.
340 * \since 1.6.1
341 */
342#define AST_DLLIST_HEAD_NOLOCK_STATIC(name, type) \
343 struct name { \
344 struct type *first; \
345 struct type *last; \
346 } name = AST_DLLIST_HEAD_NOLOCK_INIT_VALUE
347
348/*!
349 * \brief Initializes a list head structure with a specified first entry.
350 * \param head This is a pointer to the list head structure
351 * \param entry pointer to the list entry that will become the head of the list
352 *
353 * This macro initializes a list head structure by setting the head
354 * entry to the supplied value and recreating the embedded lock.
355 * \since 1.6.1
356 */
357#define AST_DLLIST_HEAD_SET(head, entry) \
358 do { \
359 (head)->first = (entry); \
360 (head)->last = (entry); \
361 ast_mutex_init(&(head)->lock); \
362 } while (0)
363
364/*!
365 * \brief Initializes an rwlist head structure with a specified first entry.
366 * \param head This is a pointer to the list head structure
367 * \param entry pointer to the list entry that will become the head of the list
368 *
369 * This macro initializes a list head structure by setting the head
370 * entry to the supplied value and recreating the embedded lock.
371 * \since 1.6.1
372 */
373#define AST_RWDLLIST_HEAD_SET(head, entry) \
374 do { \
375 (head)->first = (entry); \
376 (head)->last = (entry); \
377 ast_rwlock_init(&(head)->lock); \
378 } while (0)
379
380/*!
381 * \brief Initializes a list head structure with a specified first entry.
382 * \param head This is a pointer to the list head structure
383 * \param entry pointer to the list entry that will become the head of the list
384 *
385 * This macro initializes a list head structure by setting the head
386 * entry to the supplied value.
387 * \since 1.6.1
388 */
389#define AST_DLLIST_HEAD_SET_NOLOCK(head, entry) \
390 do { \
391 (head)->first = (entry); \
392 (head)->last = (entry); \
393 } while (0)
394
395/*!
396 * \brief Declare previous/forward links inside a list entry.
397 * \param type This is the type of each list entry.
398 *
399 * This macro declares a structure to be used to doubly link list entries together.
400 * It must be used inside the definition of the structure named in
401 * \a type, as follows:
402 *
403 * \code
404 * struct list_entry {
405 * ...
406 * AST_DLLIST_ENTRY(list_entry) list;
407 * }
408 * \endcode
409 *
410 * The field name \a list here is arbitrary, and can be anything you wish.
411 * \since 1.6.1
412 */
413#define AST_DLLIST_ENTRY(type) AST_DLLIST_HEAD_NOLOCK(, type)
414
415#define AST_RWDLLIST_ENTRY AST_DLLIST_ENTRY
416
417/*!
418 * \brief Returns the first entry contained in a list.
419 * \param head This is a pointer to the list head structure
420 * \since 1.6.1
421 */
422#define AST_DLLIST_FIRST(head) ((head)->first)
423
424#define AST_RWDLLIST_FIRST AST_DLLIST_FIRST
425
426/*!
427 * \brief Returns the last entry contained in a list.
428 * \param head This is a pointer to the list head structure
429 * \since 1.6.1
430 */
431#define AST_DLLIST_LAST(head) ((head)->last)
432
433#define AST_RWDLLIST_LAST AST_DLLIST_LAST
434
435#define AST_DLLIST_NEXT_DIRECTION(elm, field, direction) ((elm)->field.direction)
436
437#define AST_RWDLLIST_NEXT_DIRECTION AST_DLLIST_NEXT_DIRECTION
438
439/*!
440 * \brief Returns the next entry in the list after the given entry.
441 * \param elm This is a pointer to the current entry.
442 * \param field This is the name of the field (declared using AST_DLLIST_ENTRY())
443 * used to link entries of this list together.
444 * \since 1.6.1
445 */
446#define AST_DLLIST_NEXT(elm, field) AST_DLLIST_NEXT_DIRECTION(elm, field, first)
447
448#define AST_RWDLLIST_NEXT AST_DLLIST_NEXT
449
450/*!
451 * \brief Returns the previous entry in the list before the given entry.
452 * \param elm This is a pointer to the current entry.
453 * \param field This is the name of the field (declared using AST_DLLIST_ENTRY())
454 * used to link entries of this list together.
455 * \since 1.6.1
456 */
457#define AST_DLLIST_PREV(elm, field) AST_DLLIST_NEXT_DIRECTION(elm, field, last)
458
459#define AST_RWDLLIST_PREV AST_DLLIST_PREV
460
461/*!
462 * \brief Checks whether the specified list contains any entries.
463 * \param head This is a pointer to the list head structure
464 *
465 * \return non-zero if the list has entries
466 * \return zero if not.
467 * \since 1.6.1
468 */
469#define AST_DLLIST_EMPTY(head) (AST_DLLIST_FIRST(head) == NULL)
470
471#define AST_RWDLLIST_EMPTY AST_DLLIST_EMPTY
472
473/*!
474 * \brief Checks whether the specified list contains the element.
475 * \param head This is a pointer to the list head structure
476 * \param elm This is a pointer to the list element to see if in list.
477 * \param field List node field for the next node information.
478 *
479 * \return elm if the list has elm in it.
480 * \return NULL if not.
481 * \since 11
482 */
483#define AST_DLLIST_IS_MEMBER(head, elm, field) \
484 ({ \
485 typeof((head)->first) __cur; \
486 typeof((elm)) __elm = (elm); \
487 if (!__elm) { \
488 __cur = NULL; \
489 } else { \
490 __cur = (head)->first; \
491 while (__cur && __cur != __elm) { \
492 __cur = __cur->field.first; \
493 } \
494 } \
495 __cur; \
496 })
497
498#define AST_RWDLLIST_IS_MEMBER AST_DLLIST_IS_MEMBER
499
500/*!
501 * \brief Traverse a doubly linked list using the specified direction list.
502 *
503 * \param head List head structure pointer.
504 * \param var This is the name of the variable that will hold a pointer to the
505 * current list node on each iteration. It must be declared before calling
506 * this macro.
507 * \param field List node field for the next node information. (declared using AST_DLLIST_ENTRY())
508 * \param start Specified list node to start traversal: first or last
509 *
510 * This macro is use to loop over (traverse) the nodes in a list. It uses a
511 * \a for loop, and supplies the enclosed code with a pointer to each list
512 * node as it loops. It is typically used as follows:
513 * \code
514 * static AST_DLLIST_HEAD(entry_list, list_entry) entries;
515 * ...
516 * struct list_entry {
517 * ...
518 * AST_DLLIST_ENTRY(list_entry) list;
519 * }
520 * ...
521 * struct list_entry *current;
522 * ...
523 * AST_DLLIST_TRAVERSE_DIRECTION(&entries, current, list, first) {
524 * (do something with current here (travers list in forward direction))
525 * }
526 * ...
527 * AST_DLLIST_TRAVERSE_DIRECTION(&entries, current, list, last) {
528 * (do something with current here (travers list in reverse direction))
529 * }
530 * \endcode
531 *
532 * \since 11
533 */
534#define AST_DLLIST_TRAVERSE_DIRECTION(head, var, field, start) \
535 for ((var) = (head)->start; (var); (var) = AST_DLLIST_NEXT_DIRECTION(var, field, start))
536
537#define AST_RWDLLIST_TRAVERSE_DIRECTION AST_DLLIST_TRAVERSE_DIRECTION
538
539/*!
540 * \brief Loops over (traverses) the entries in a list.
541 * \param head This is a pointer to the list head structure
542 * \param var This is the name of the variable that will hold a pointer to the
543 * current list entry on each iteration. It must be declared before calling
544 * this macro.
545 * \param field This is the name of the field (declared using AST_DLLIST_ENTRY())
546 * used to link entries of this list together.
547 *
548 * This macro is use to loop over (traverse) the entries in a list. It uses a
549 * \a for loop, and supplies the enclosed code with a pointer to each list
550 * entry as it loops. It is typically used as follows:
551 * \code
552 * static AST_DLLIST_HEAD(entry_list, list_entry) entries;
553 * ...
554 * struct list_entry {
555 * ...
556 * AST_DLLIST_ENTRY(list_entry) list;
557 * }
558 * ...
559 * struct list_entry *current;
560 * ...
561 * AST_DLLIST_TRAVERSE(&entries, current, list) {
562 * (do something with current here)
563 * }
564 * \endcode
565 * \warning If you modify the forward-link pointer contained in the \a current entry while
566 * inside the loop, the behavior will be unpredictable. At a minimum, the following
567 * macros will modify the forward-link pointer, and should not be used inside
568 * AST_DLLIST_TRAVERSE() against the entry pointed to by the \a current pointer without
569 * careful consideration of their consequences:
570 * \li AST_DLLIST_NEXT() (when used as an lvalue)
571 * \li AST_DLLIST_INSERT_AFTER()
572 * \li AST_DLLIST_INSERT_HEAD()
573 * \li AST_DLLIST_INSERT_TAIL()
574 * \since 1.6.1
575 */
576#define AST_DLLIST_TRAVERSE(head,var,field) \
577 AST_DLLIST_TRAVERSE_DIRECTION(head, var, field, first)
578
579#define AST_RWDLLIST_TRAVERSE AST_DLLIST_TRAVERSE
580
581/*!
582 * \brief Loops over (traverses) the entries in a list in reverse order, starting at the end.
583 * \param head This is a pointer to the list head structure
584 * \param var This is the name of the variable that will hold a pointer to the
585 * current list entry on each iteration. It must be declared before calling
586 * this macro.
587 * \param field This is the name of the field (declared using AST_DLLIST_ENTRY())
588 * used to link entries of this list together.
589 *
590 * This macro is use to loop over (traverse) the entries in a list in reverse order. It uses a
591 * \a for loop, and supplies the enclosed code with a pointer to each list
592 * entry as it loops. It is typically used as follows:
593 * \code
594 * static AST_DLLIST_HEAD(entry_list, list_entry) entries;
595 * ...
596 * struct list_entry {
597 * ...
598 * AST_DLLIST_ENTRY(list_entry) list;
599 * }
600 * ...
601 * struct list_entry *current;
602 * ...
603 * AST_DLLIST_TRAVERSE_BACKWARDS(&entries, current, list) {
604 * (do something with current here)
605 * }
606 * \endcode
607 * \warning If you modify the forward-link pointer contained in the \a current entry while
608 * inside the loop, the behavior will be unpredictable. At a minimum, the following
609 * macros will modify the forward-link pointer, and should not be used inside
610 * AST_DLLIST_TRAVERSE() against the entry pointed to by the \a current pointer without
611 * careful consideration of their consequences:
612 * \li AST_DLLIST_PREV() (when used as an lvalue)
613 * \li AST_DLLIST_INSERT_BEFORE()
614 * \li AST_DLLIST_INSERT_HEAD()
615 * \li AST_DLLIST_INSERT_TAIL()
616 * \since 1.6.1
617 */
618#define AST_DLLIST_TRAVERSE_BACKWARDS(head,var,field) \
619 AST_DLLIST_TRAVERSE_DIRECTION(head, var, field, last)
620
621#define AST_RWDLLIST_TRAVERSE_BACKWARDS AST_DLLIST_TRAVERSE_BACKWARDS
622
623/*!
624 * \brief Safe traversal of a doubly linked list using the specified direction list.
625 *
626 * \param head List head structure pointer.
627 * \param var This is the name of the variable that will hold a pointer to the
628 * current list node on each iteration. It must be declared before calling
629 * this macro.
630 * \param field List node field for the next node information. (declared using AST_DLLIST_ENTRY())
631 * \param start Specified list node to start traversal: first or last
632 *
633 * This macro is used to safely loop over (traverse) the nodes in a list. It
634 * uses a \a for loop, and supplies the enclosed code with a pointer to each list
635 * node as it loops. It is typically used as follows:
636 *
637 * \code
638 * static AST_DLLIST_HEAD(entry_list, list_entry) entries;
639 * ...
640 * struct list_entry {
641 * ...
642 * AST_DLLIST_ENTRY(list_entry) list;
643 * }
644 * ...
645 * struct list_entry *current;
646 * ...
647 * AST_DLLIST_TRAVERSE_DIRECTION_SAFE_BEGIN(&entries, current, list, first) {
648 * (do something with current here (travers list in forward direction))
649 * }
650 * ...
651 * AST_DLLIST_TRAVERSE_DIRECTION_SAFE_BEGIN(&entries, current, list, last) {
652 * (do something with current here (travers list in reverse direction))
653 * }
654 * AST_DLLIST_TRAVERSE_DIRECTION_SAFE_END;
655 * \endcode
656 *
657 * It differs from AST_DLLIST_TRAVERSE() in that the code inside the loop can modify
658 * (or even free, after calling AST_DLLIST_REMOVE_CURRENT()) the entry pointed to by
659 * the \a current pointer without affecting the loop traversal.
660 *
661 * \since 11
662 */
663#define AST_DLLIST_TRAVERSE_DIRECTION_SAFE_BEGIN(head, var, field, start) \
664 do { \
665 typeof((head)) __list_head = (head); \
666 typeof(__list_head->first) __list_current; \
667 typeof(__list_head->first) __list_first; \
668 typeof(__list_head->first) __list_last; \
669 typeof(__list_head->first) __list_next; \
670 for ((var) = __list_head->start, \
671 __list_current = (var), \
672 __list_first = (var) ? (var)->field.first : NULL, \
673 __list_last = (var) ? (var)->field.last : NULL, \
674 __list_next = (var) ? AST_DLLIST_NEXT_DIRECTION(var, field, start) : NULL; \
675 (var); \
676 (void) __list_current,/* To quiet compiler? */ \
677 (void) __list_first,/* To quiet compiler? */ \
678 (void) __list_last,/* To quiet compiler? */ \
679 (var) = __list_next, \
680 __list_current = (var), \
681 __list_first = (var) ? (var)->field.first : NULL, \
682 __list_last = (var) ? (var)->field.last : NULL, \
683 __list_next = (var) ? AST_DLLIST_NEXT_DIRECTION(var, field, start) : NULL \
684 )
685
686#define AST_RWDLLIST_TRAVERSE_DIRECTION_SAFE_BEGIN AST_DLLIST_TRAVERSE_DIRECTION_SAFE_BEGIN
687
688/*!
689 * \brief Inserts a list node before the current node during a traversal.
690 * \param elm This is a pointer to the entry to be inserted.
691 * \param field This is the name of the field (declared using AST_DLLIST_ENTRY())
692 * used to link nodes of this list together.
693 *
694 * \since 1.6.1
695 */
696#define AST_DLLIST_INSERT_BEFORE_CURRENT(elm, field) \
697 do { \
698 typeof((elm)) __elm = (elm); \
699 __elm->field.last = __list_last; \
700 __elm->field.first = __list_current; \
701 if (__list_head->first == __list_current) { \
702 __list_head->first = __elm; \
703 } else { \
704 __list_last->field.first = __elm; \
705 } \
706 __list_current->field.last = __elm; \
707 if (__list_next == __list_last) { \
708 __list_next = __elm; \
709 } \
710 __list_last = __elm; \
711 } while (0)
712
713#define AST_RWDLLIST_INSERT_BEFORE_CURRENT AST_DLLIST_INSERT_BEFORE_CURRENT
714
715/*!
716 * \brief Inserts a list node after the current node during a traversal.
717 * \param elm This is a pointer to the node to be inserted.
718 * \param field This is the name of the field (declared using AST_DLLIST_ENTRY())
719 * used to link nodes of this list together.
720 *
721 * \since 11
722 */
723#define AST_DLLIST_INSERT_AFTER_CURRENT(elm, field) \
724 do { \
725 typeof((elm)) __elm = (elm); \
726 __elm->field.first = __list_first; \
727 __elm->field.last = __list_current; \
728 if (__list_head->last == __list_current) { \
729 __list_head->last = __elm; \
730 } else { \
731 __list_first->field.last = __elm; \
732 } \
733 __list_current->field.first = __elm; \
734 if (__list_next == __list_first) { \
735 __list_next = __elm; \
736 } \
737 __list_first = __elm; \
738 } while (0)
739
740#define AST_RWDLLIST_INSERT_AFTER_CURRENT AST_DLLIST_INSERT_AFTER_CURRENT
741
742/*!
743 * \brief Removes the \a current entry from a list during a traversal.
744 * \param field This is the name of the field (declared using AST_DLLIST_ENTRY())
745 * used to link entries of this list together.
746 *
747 * \note This macro can \b only be used inside an AST_DLLIST_TRAVERSE_SAFE_BEGIN()
748 * block; it is used to unlink the current entry from the list without affecting
749 * the list traversal (and without having to re-traverse the list to modify the
750 * previous entry, if any).
751 * \since 1.6.1
752 */
753#define AST_DLLIST_REMOVE_CURRENT(field) \
754 do { \
755 if (__list_first) { \
756 __list_first->field.last = __list_last; \
757 } else { \
758 __list_head->last = __list_last; \
759 } \
760 if (__list_last) { \
761 __list_last->field.first = __list_first; \
762 } else { \
763 __list_head->first = __list_first; \
764 } \
765 __list_current->field.first = NULL; \
766 __list_current->field.last = NULL; \
767 __list_current = NULL; \
768 } while (0)
769
770#define AST_RWDLLIST_REMOVE_CURRENT AST_DLLIST_REMOVE_CURRENT
771
772/*!
773 * \brief Move the current list entry to another list at the tail.
774 *
775 * \note This is a silly macro. It should be done explicitly
776 * otherwise the field parameter must be the same for the two
777 * lists.
778 *
779 * AST_DLLIST_REMOVE_CURRENT(field);
780 * AST_DLLIST_INSERT_TAIL(newhead, var, other_field);
781 */
782#define AST_DLLIST_MOVE_CURRENT(newhead, field) \
783 do { \
784 typeof ((newhead)->first) __list_cur = __list_current; \
785 AST_DLLIST_REMOVE_CURRENT(field); \
786 AST_DLLIST_INSERT_TAIL((newhead), __list_cur, field); \
787 } while (0)
788
789#define AST_RWDLLIST_MOVE_CURRENT AST_DLLIST_MOVE_CURRENT
790
791/*!
792 * \brief Move the current list entry to another list at the head.
793 *
794 * \note This is a silly macro. It should be done explicitly
795 * otherwise the field parameter must be the same for the two
796 * lists.
797 *
798 * AST_DLLIST_REMOVE_CURRENT(field);
799 * AST_DLLIST_INSERT_HEAD(newhead, var, other_field);
800 */
801#define AST_DLLIST_MOVE_CURRENT_BACKWARDS(newhead, field) \
802 do { \
803 typeof ((newhead)->first) __list_cur = __list_current; \
804 AST_DLLIST_REMOVE_CURRENT(field); \
805 AST_DLLIST_INSERT_HEAD((newhead), __list_cur, field); \
806 } while (0)
807
808#define AST_RWDLLIST_MOVE_CURRENT_BACKWARDS AST_DLLIST_MOVE_CURRENT_BACKWARDS
809
810#define AST_DLLIST_TRAVERSE_DIRECTION_SAFE_END \
811 } while (0)
812
813#define AST_RWDLLIST_TRAVERSE_DIRECTION_SAFE_END AST_DLLIST_TRAVERSE_DIRECTION_SAFE_END
814
815/*!
816 * \brief Loops safely over (traverses) the entries in a list.
817 * \param head This is a pointer to the list head structure
818 * \param var This is the name of the variable that will hold a pointer to the
819 * current list entry on each iteration. It must be declared before calling
820 * this macro.
821 * \param field This is the name of the field (declared using AST_DLLIST_ENTRY())
822 * used to link entries of this list together.
823 *
824 * This macro is used to safely loop over (traverse) the entries in a list. It
825 * uses a \a for loop, and supplies the enclosed code with a pointer to each list
826 * entry as it loops. It is typically used as follows:
827 *
828 * \code
829 * static AST_DLLIST_HEAD(entry_list, list_entry) entries;
830 * ...
831 * struct list_entry {
832 * ...
833 * AST_DLLIST_ENTRY(list_entry) list;
834 * }
835 * ...
836 * struct list_entry *current;
837 * ...
838 * AST_DLLIST_TRAVERSE_SAFE_BEGIN(&entries, current, list) {
839 * (do something with current here)
840 * }
841 * AST_DLLIST_TRAVERSE_SAFE_END;
842 * \endcode
843 *
844 * It differs from AST_DLLIST_TRAVERSE() in that the code inside the loop can modify
845 * (or even free, after calling AST_DLLIST_REMOVE_CURRENT()) the entry pointed to by
846 * the \a current pointer without affecting the loop traversal.
847 * \since 1.6.1
848 */
849#define AST_DLLIST_TRAVERSE_SAFE_BEGIN(head, var, field) \
850 AST_DLLIST_TRAVERSE_DIRECTION_SAFE_BEGIN(head, var, field, first)
851
852#define AST_RWDLLIST_TRAVERSE_SAFE_BEGIN AST_DLLIST_TRAVERSE_SAFE_BEGIN
853
854/*!
855 * \brief Loops safely over (traverses) the entries in a list.
856 * \param head This is a pointer to the list head structure
857 * \param var This is the name of the variable that will hold a pointer to the
858 * current list entry on each iteration. It must be declared before calling
859 * this macro.
860 * \param field This is the name of the field (declared using AST_DLLIST_ENTRY())
861 * used to link entries of this list together.
862 *
863 * This macro is used to safely loop over (traverse) the entries in a list. It
864 * uses a \a for loop, and supplies the enclosed code with a pointer to each list
865 * entry as it loops. It is typically used as follows:
866 *
867 * \code
868 * static AST_DLLIST_HEAD(entry_list, list_entry) entries;
869 * ...
870 * struct list_entry {
871 * ...
872 * AST_DLLIST_ENTRY(list_entry) list;
873 * }
874 * ...
875 * struct list_entry *current;
876 * ...
877 * AST_DLLIST_TRAVERSE_SAFE_BEGIN(&entries, current, list) {
878 * (do something with current here)
879 * }
880 * AST_DLLIST_TRAVERSE_SAFE_END;
881 * \endcode
882 *
883 * It differs from AST_DLLIST_TRAVERSE() in that the code inside the loop can modify
884 * (or even free, after calling AST_DLLIST_REMOVE_CURRENT()) the entry pointed to by
885 * the \a current pointer without affecting the loop traversal.
886 * \since 1.6.1
887 */
888#define AST_DLLIST_TRAVERSE_BACKWARDS_SAFE_BEGIN(head, var, field) \
889 AST_DLLIST_TRAVERSE_DIRECTION_SAFE_BEGIN(head, var, field, last)
890
891#define AST_RWDLLIST_TRAVERSE_BACKWARDS_SAFE_BEGIN AST_DLLIST_TRAVERSE_BACKWARDS_SAFE_BEGIN
892
893/*!
894 * \brief Inserts a list entry after the current entry during a backwards traversal. Since
895 * this is a backwards traversal, this will insert the entry AFTER the current
896 * element. Since this is a backwards traveral, though, this would be BEFORE
897 * the current entry in traversal order. Confusing?
898 * \param elm This is a pointer to the entry to be inserted.
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 * \since 1.6.1
903 */
904#define AST_DLLIST_INSERT_BEFORE_CURRENT_BACKWARDS(elm, field) \
905 AST_DLLIST_INSERT_AFTER_CURRENT(elm, field)
906
907#define AST_RWDLLIST_INSERT_BEFORE_CURRENT_BACKWARDS AST_DLLIST_INSERT_BEFORE_CURRENT_BACKWARDS
908
909/*!
910 * \brief Closes a safe loop traversal block.
911 * \since 1.6.1
912 */
913#define AST_DLLIST_TRAVERSE_SAFE_END AST_DLLIST_TRAVERSE_DIRECTION_SAFE_END
914
915#define AST_RWDLLIST_TRAVERSE_SAFE_END AST_DLLIST_TRAVERSE_SAFE_END
916
917/*!
918 * \brief Closes a safe loop traversal block.
919 * \since 1.6.1
920 */
921#define AST_DLLIST_TRAVERSE_BACKWARDS_SAFE_END AST_DLLIST_TRAVERSE_DIRECTION_SAFE_END
922
923#define AST_RWDLLIST_TRAVERSE_BACKWARDS_SAFE_END AST_DLLIST_TRAVERSE_BACKWARDS_SAFE_END
924
925/*!
926 * \brief Initializes a list head structure.
927 * \param head This is a pointer to the list head structure
928 *
929 * This macro initializes a list head structure by setting the head
930 * entry to \a NULL (empty list) and recreating the embedded lock.
931 * \since 1.6.1
932 */
933#define AST_DLLIST_HEAD_INIT(head) \
934 { \
935 (head)->first = NULL; \
936 (head)->last = NULL; \
937 ast_mutex_init(&(head)->lock); \
938 }
939
940/*!
941 * \brief Initializes an rwlist head structure.
942 * \param head This is a pointer to the list head structure
943 *
944 * This macro initializes a list head structure by setting the head
945 * entry to \a NULL (empty list) and recreating the embedded lock.
946 * \since 1.6.1
947 */
948#define AST_RWDLLIST_HEAD_INIT(head) \
949 { \
950 (head)->first = NULL; \
951 (head)->last = NULL; \
952 ast_rwlock_init(&(head)->lock); \
953 }
954
955/*!
956 * \brief Destroys a list head structure.
957 * \param head This is a pointer to the list head structure
958 *
959 * This macro destroys a list head structure by setting the head
960 * entry to \a NULL (empty list) and destroying the embedded lock.
961 * It does not free the structure from memory.
962 * \since 1.6.1
963 */
964#define AST_DLLIST_HEAD_DESTROY(head) \
965 { \
966 (head)->first = NULL; \
967 (head)->last = NULL; \
968 ast_mutex_destroy(&(head)->lock); \
969 }
970
971/*!
972 * \brief Destroys an rwlist head structure.
973 * \param head This is a pointer to the list head structure
974 *
975 * This macro destroys a list head structure by setting the head
976 * entry to \a NULL (empty list) and destroying the embedded lock.
977 * It does not free the structure from memory.
978 * \since 1.6.1
979 */
980#define AST_RWDLLIST_HEAD_DESTROY(head) \
981 { \
982 (head)->first = NULL; \
983 (head)->last = NULL; \
984 ast_rwlock_destroy(&(head)->lock); \
985 }
986
987/*!
988 * \brief Initializes a list head structure.
989 * \param head This is a pointer to the list head structure
990 *
991 * This macro initializes a list head structure by setting the head
992 * entry to \a NULL (empty list). There is no embedded lock handling
993 * with this macro.
994 * \since 1.6.1
995 */
996#define AST_DLLIST_HEAD_INIT_NOLOCK(head) \
997 { \
998 (head)->first = NULL; \
999 (head)->last = NULL; \
1000 }
1001
1002/*!
1003 * \brief Inserts a list entry after a given entry.
1004 * \param head This is a pointer to the list head structure
1005 * \param listelm This is a pointer to the entry after which the new entry should
1006 * be inserted.
1007 * \param elm This is a pointer to the entry to be inserted.
1008 * \param field This is the name of the field (declared using AST_DLLIST_ENTRY())
1009 * used to link entries of this list together.
1010 * \since 1.6.1
1011 */
1012#define AST_DLLIST_INSERT_AFTER(head, listelm, elm, field) \
1013 do { \
1014 typeof((listelm)) __listelm = (listelm); \
1015 typeof((elm)) __elm = (elm); \
1016 __elm->field.first = __listelm->field.first; \
1017 __elm->field.last = __listelm; \
1018 if ((head)->last == __listelm) { \
1019 (head)->last = __elm; \
1020 } else { \
1021 __listelm->field.first->field.last = __elm; \
1022 } \
1023 __listelm->field.first = __elm; \
1024 } while (0)
1025
1026#define AST_RWDLLIST_INSERT_AFTER AST_DLLIST_INSERT_AFTER
1027
1028/*!
1029 * \brief Inserts a list entry before a given entry.
1030 * \param head This is a pointer to the list head structure
1031 * \param listelm This is a pointer to the entry before which the new entry should
1032 * be inserted.
1033 * \param elm This is a pointer to the entry to be inserted.
1034 * \param field This is the name of the field (declared using AST_DLLIST_ENTRY())
1035 * used to link entries of this list together.
1036 * \since 1.6.1
1037 */
1038#define AST_DLLIST_INSERT_BEFORE(head, listelm, elm, field) \
1039 do { \
1040 typeof((listelm)) __listelm = (listelm); \
1041 typeof((elm)) __elm = (elm); \
1042 __elm->field.last = __listelm->field.last; \
1043 __elm->field.first = __listelm; \
1044 if ((head)->first == __listelm) { \
1045 (head)->first = __elm; \
1046 } else { \
1047 __listelm->field.last->field.first = __elm; \
1048 } \
1049 __listelm->field.last = __elm; \
1050 } while (0)
1051
1052#define AST_RWDLLIST_INSERT_BEFORE AST_DLLIST_INSERT_BEFORE
1053
1054/*!
1055 * \brief Inserts a list entry at the head of a list.
1056 * \param head This is a pointer to the list head structure
1057 * \param elm This is a pointer to the entry to be inserted.
1058 * \param field This is the name of the field (declared using AST_DLLIST_ENTRY())
1059 * used to link entries of this list together.
1060 * \since 1.6.1
1061 */
1062#define AST_DLLIST_INSERT_HEAD(head, elm, field) \
1063 do { \
1064 typeof((elm)) __elm = (elm); \
1065 __elm->field.last = NULL; \
1066 __elm->field.first = (head)->first; \
1067 if (!(head)->first) { \
1068 (head)->last = __elm; \
1069 } else { \
1070 (head)->first->field.last = __elm; \
1071 } \
1072 (head)->first = __elm; \
1073 } while (0)
1074
1075#define AST_RWDLLIST_INSERT_HEAD AST_DLLIST_INSERT_HEAD
1076
1077/*!
1078 * \brief Appends a list entry to the tail of a list.
1079 * \param head This is a pointer to the list head structure
1080 * \param elm This is a pointer to the entry to be appended.
1081 * \param field This is the name of the field (declared using AST_DLLIST_ENTRY())
1082 * used to link entries of this list together.
1083 *
1084 * Note: The link field in the appended entry is \b not modified, so if it is
1085 * actually the head of a list itself, the entire list will be appended
1086 * temporarily (until the next AST_DLLIST_INSERT_TAIL is performed).
1087 * \since 1.6.1
1088 */
1089#define AST_DLLIST_INSERT_TAIL(head, elm, field) \
1090 do { \
1091 typeof((elm)) __elm = (elm); \
1092 __elm->field.first = NULL; \
1093 if (!(head)->first) { \
1094 __elm->field.last = NULL; \
1095 (head)->first = __elm; \
1096 } else { \
1097 __elm->field.last = (head)->last; \
1098 (head)->last->field.first = __elm; \
1099 } \
1100 (head)->last = __elm; \
1101 } while (0)
1102
1103#define AST_RWDLLIST_INSERT_TAIL AST_DLLIST_INSERT_TAIL
1104
1105/*!
1106 * \brief Appends a whole list to the tail of a list.
1107 * \param head This is a pointer to the list head structure
1108 * \param list This is a pointer to the list to be appended.
1109 * \param field This is the name of the field (declared using AST_DLLIST_ENTRY())
1110 * used to link entries of this list together.
1111 *
1112 * Note: The source list (the \a list parameter) will be empty after
1113 * calling this macro (the list entries are \b moved to the target list).
1114 * \since 1.6.1
1115 */
1116#define AST_DLLIST_APPEND_DLLIST(head, list, field) \
1117 do { \
1118 if (!(head)->first) { \
1119 (head)->first = (list)->first; \
1120 (head)->last = (list)->last; \
1121 } else { \
1122 (head)->last->field.first = (list)->first; \
1123 (list)->first->field.last = (head)->last; \
1124 (head)->last = (list)->last; \
1125 } \
1126 (list)->first = NULL; \
1127 (list)->last = NULL; \
1128 } while (0)
1129
1130#define AST_RWDLLIST_APPEND_DLLIST AST_DLLIST_APPEND_DLLIST
1131
1132/*!
1133 * \brief Removes and returns the head entry from a list.
1134 * \param head This is a pointer to the list head structure
1135 * \param field This is the name of the field (declared using AST_DLLIST_ENTRY())
1136 * used to link entries of this list together.
1137 *
1138 * Removes the head entry from the list, and returns a pointer to it.
1139 * This macro is safe to call on an empty list.
1140 * \since 1.6.1
1141 */
1142#define AST_DLLIST_REMOVE_HEAD(head, field) \
1143 ({ \
1144 typeof((head)->first) cur = (head)->first; \
1145 if (cur) { \
1146 (head)->first = cur->field.first; \
1147 if ((head)->first) { \
1148 (head)->first->field.last = NULL; \
1149 } \
1150 cur->field.first = NULL; \
1151 cur->field.last = NULL; \
1152 if ((head)->last == cur) { \
1153 (head)->last = NULL; \
1154 } \
1155 } \
1156 cur; \
1157 })
1158
1159#define AST_RWDLLIST_REMOVE_HEAD AST_DLLIST_REMOVE_HEAD
1160
1161/*!
1162 * \brief Removes and returns the tail node from a list.
1163 * \param head This is a pointer to the list head structure
1164 * \param field This is the name of the field (declared using AST_DLLIST_ENTRY())
1165 * used to link nodes of this list together.
1166 *
1167 * Removes the tail entry from the list, and returns a pointer to it.
1168 * This macro is safe to call on an empty list.
1169 * \since 11
1170 */
1171#define AST_DLLIST_REMOVE_TAIL(head, field) \
1172 ({ \
1173 typeof((head)->last) cur = (head)->last; \
1174 if (cur) { \
1175 (head)->last = cur->field.last; \
1176 if ((head)->last) { \
1177 (head)->last->field.first = NULL; \
1178 } \
1179 cur->field.first = NULL; \
1180 cur->field.last = NULL; \
1181 if ((head)->first == cur) { \
1182 (head)->first = NULL; \
1183 } \
1184 } \
1185 cur; \
1186 })
1187
1188#define AST_RWDLLIST_REMOVE_TAIL AST_DLLIST_REMOVE_TAIL
1189
1190/*!
1191 * \brief Removes a specific entry from a list.
1192 * \param head This is a pointer to the list head structure
1193 * \param elm This is a pointer to the entry to be removed.
1194 * \param field This is the name of the field (declared using AST_DLLIST_ENTRY())
1195 * used to link entries of this list together.
1196 * \warning The removed entry is \b not freed.
1197 * \since 1.6.1
1198 */
1199#define AST_DLLIST_REMOVE(head, elm, field) \
1200 do { \
1201 typeof((elm)) __elm = (elm); \
1202 if (__elm) { \
1203 if (__elm->field.first) { \
1204 __elm->field.first->field.last = __elm->field.last; \
1205 } else { \
1206 (head)->last = __elm->field.last; \
1207 } \
1208 if (__elm->field.last) { \
1209 __elm->field.last->field.first = __elm->field.first; \
1210 } else { \
1211 (head)->first = __elm->field.first; \
1212 } \
1213 __elm->field.first = NULL; \
1214 __elm->field.last = NULL; \
1215 } \
1216 } while (0)
1217
1218#define AST_RWDLLIST_REMOVE AST_DLLIST_REMOVE
1219
1220/*!
1221 * \brief Removes a specific node from a list if it is in the list.
1222 * \param head This is a pointer to the list head structure
1223 * \param elm This is a pointer to the node to be removed.
1224 * \param field This is the name of the field (declared using AST_DLLIST_ENTRY())
1225 * used to link nodes of this list together.
1226 * \warning The removed node is \b not freed.
1227 * \return elm if the list had elm in it.
1228 * \return NULL if not.
1229 * \since 11
1230 */
1231#define AST_DLLIST_REMOVE_VERIFY(head, elm, field) \
1232 ({ \
1233 typeof((elm)) __res = AST_DLLIST_IS_MEMBER(head, elm, field); \
1234 AST_DLLIST_REMOVE(head, __res, field); \
1235 __res; \
1236 })
1237
1238#define AST_RWDLLIST_REMOVE_VERIFY AST_DLLIST_REMOVE_VERIFY
1239
1240#endif /* _ASTERISK_DLINKEDLISTS_H */
Asterisk locking-related definitions: