3264b9e1a1d44ff25a83eb6d25e5723255cc154c
[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   Returns non-zero on success, 0 on failure
37 */
38 #define AST_LIST_LOCK(head)                                             \
39         ast_mutex_lock(&(head)->lock) 
40         
41 /*!
42   \brief Locks a list, without blocking if the list is locked.
43   \param head This is a pointer to the list head structure
44
45   This macro attempts to place an exclusive lock in the
46   list head structure pointed to by head.
47   Returns non-zero on success, 0 on failure
48 */
49 #define AST_LIST_TRYLOCK(head)                                          \
50         ast_mutex_trylock(&(head)->lock) 
51         
52 /*!
53   \brief Attempts to unlock a list.
54   \param head This is a pointer to the list head structure
55
56   This macro attempts to remove an exclusive lock from the
57   list head structure pointed to by head. If the list
58   was not locked by this thread, this macro has no effect.
59 */
60 #define AST_LIST_UNLOCK(head)                                           \
61         ast_mutex_unlock(&(head)->lock)
62
63 /*!
64   \brief Defines a structure to be used to hold a list of specified type.
65   \param name This will be the name of the defined structure.
66   \param type This is the type of each list entry.
67
68   This macro creates a structure definition that can be used
69   to hold a list of the entries of type \a type. It does not actually
70   declare (allocate) a structure; to do that, either follow this
71   macro with the desired name of the instance you wish to declare,
72   or use the specified \a name to declare instances elsewhere.
73
74   Example usage:
75   \code
76   static AST_LIST_HEAD(entry_list, entry) entries;
77   \endcode
78
79   This would define \c struct \c entry_list, and declare an instance of it named
80   \a entries, all intended to hold a list of type \c struct \c entry.
81 */
82 #define AST_LIST_HEAD(name, type)                                       \
83 struct name {                                                           \
84         struct type *first;                                             \
85         struct type *last;                                              \
86         ast_mutex_t lock;                                               \
87 }
88
89 /*!
90   \brief Defines a structure to be used to hold a list of specified type (with no lock).
91   \param name This will be the name of the defined structure.
92   \param type This is the type of each list entry.
93
94   This macro creates a structure definition that can be used
95   to hold a list of the entries of type \a type. It does not actually
96   declare (allocate) a structure; to do that, either follow this
97   macro with the desired name of the instance you wish to declare,
98   or use the specified \a name to declare instances elsewhere.
99
100   Example usage:
101   \code
102   static AST_LIST_HEAD_NOLOCK(entry_list, entry) entries;
103   \endcode
104
105   This would define \c struct \c entry_list, and declare an instance of it named
106   \a entries, all intended to hold a list of type \c struct \c entry.
107 */
108 #define AST_LIST_HEAD_NOLOCK(name, type)                                \
109 struct name {                                                           \
110         struct type *first;                                             \
111         struct type *last;                                              \
112 }
113
114 /*!
115   \brief Defines initial values for a declaration of AST_LIST_HEAD
116 */
117 #define AST_LIST_HEAD_INIT_VALUE        {               \
118         .first = NULL,                                  \
119         .last = NULL,                                   \
120         .lock = AST_MUTEX_INIT_VALUE,                   \
121         }
122
123 /*!
124   \brief Defines initial values for a declaration of AST_LIST_HEAD_NOLOCK
125 */
126 #define AST_LIST_HEAD_NOLOCK_INIT_VALUE {       \
127         .first = NULL,                                  \
128         .last = NULL,                                   \
129         }
130
131 /*!
132   \brief Defines a structure to be used to hold a list of specified type, statically initialized.
133   \param name This will be the name of the defined structure.
134   \param type This is the type of each list entry.
135
136   This macro creates a structure definition that can be used
137   to hold a list of the entries of type \a type, and allocates an instance
138   of it, initialized to be empty.
139
140   Example usage:
141   \code
142   static AST_LIST_HEAD_STATIC(entry_list, entry);
143   \endcode
144
145   This would define \c struct \c entry_list, intended to hold a list of
146   type \c struct \c entry.
147 */
148 #if defined(AST_MUTEX_INIT_W_CONSTRUCTORS)
149 #define AST_LIST_HEAD_STATIC(name, type)                                \
150 struct name {                                                           \
151         struct type *first;                                             \
152         struct type *last;                                              \
153         ast_mutex_t lock;                                               \
154 } name;                                                                 \
155 static void  __attribute__ ((constructor)) init_##name(void)            \
156 {                                                                       \
157         AST_LIST_HEAD_INIT(&name);                                      \
158 }                                                                       \
159 static void  __attribute__ ((destructor)) fini_##name(void)             \
160 {                                                                       \
161         AST_LIST_HEAD_DESTROY(&name);                                   \
162 }                                                                       \
163 struct __dummy_##name
164 #else
165 #define AST_LIST_HEAD_STATIC(name, type)                                \
166 struct name {                                                           \
167         struct type *first;                                             \
168         struct type *last;                                              \
169         ast_mutex_t lock;                                               \
170 } name = AST_LIST_HEAD_INIT_VALUE
171 #endif
172
173 /*!
174   \brief Defines a structure to be used to hold a list of specified type, statically initialized.
175
176   This is the same as AST_LIST_HEAD_STATIC, except without the lock included.
177 */
178 #define AST_LIST_HEAD_NOLOCK_STATIC(name, type)                         \
179 struct name {                                                           \
180         struct type *first;                                             \
181         struct type *last;                                              \
182 } name = AST_LIST_HEAD_NOLOCK_INIT_VALUE
183
184 /*!
185   \brief Initializes a list head structure with a specified first entry.
186   \param head This is a pointer to the list head structure
187   \param entry pointer to the list entry that will become the head of the list
188
189   This macro initializes a list head structure by setting the head
190   entry to the supplied value and recreating the embedded lock.
191 */
192 #define AST_LIST_HEAD_SET(head, entry) do {                             \
193         (head)->first = (entry);                                        \
194         (head)->last = (entry);                                         \
195         ast_mutex_init(&(head)->lock);                                  \
196 } while (0)
197
198 /*!
199   \brief Initializes a list head structure with a specified first entry.
200   \param head This is a pointer to the list head structure
201   \param entry pointer to the list entry that will become the head of the list
202
203   This macro initializes a list head structure by setting the head
204   entry to the supplied value.
205 */
206 #define AST_LIST_HEAD_SET_NOLOCK(head, entry) do {                      \
207         (head)->first = (entry);                                        \
208         (head)->last = (entry);                                         \
209 } while (0)
210
211 /*!
212   \brief Declare a forward link structure inside a list entry.
213   \param type This is the type of each list entry.
214
215   This macro declares a structure to be used to link list entries together.
216   It must be used inside the definition of the structure named in
217   \a type, as follows:
218
219   \code
220   struct list_entry {
221         ...
222         AST_LIST_ENTRY(list_entry) list;
223   }
224   \endcode
225
226   The field name \a list here is arbitrary, and can be anything you wish.
227 */
228 #define AST_LIST_ENTRY(type)                                            \
229 struct {                                                                \
230         struct type *next;                                              \
231 }
232  
233 /*!
234   \brief Returns the first entry contained in a list.
235   \param head This is a pointer to the list head structure
236  */
237 #define AST_LIST_FIRST(head)    ((head)->first)
238
239 /*!
240   \brief Returns the last entry contained in a list.
241   \param head This is a pointer to the list head structure
242  */
243 #define AST_LIST_LAST(head)     ((head)->last)
244
245 /*!
246   \brief Returns the next entry in the list after the given entry.
247   \param elm This is a pointer to the current entry.
248   \param field This is the name of the field (declared using AST_LIST_ENTRY())
249   used to link entries of this list together.
250 */
251 #define AST_LIST_NEXT(elm, field)       ((elm)->field.next)
252
253 /*!
254   \brief Checks whether the specified list contains any entries.
255   \param head This is a pointer to the list head structure
256
257   Returns non-zero if the list has entries, zero if not.
258  */
259 #define AST_LIST_EMPTY(head)    (AST_LIST_FIRST(head) == NULL)
260
261 /*!
262   \brief Loops over (traverses) the entries in a list.
263   \param head This is a pointer to the list head structure
264   \param var This is the name of the variable that will hold a pointer to the
265   current list entry on each iteration. It must be declared before calling
266   this macro.
267   \param field This is the name of the field (declared using AST_LIST_ENTRY())
268   used to link entries of this list together.
269
270   This macro is use to loop over (traverse) the entries in a list. It uses a
271   \a for loop, and supplies the enclosed code with a pointer to each list
272   entry as it loops. It is typically used as follows:
273   \code
274   static AST_LIST_HEAD(entry_list, list_entry) entries;
275   ...
276   struct list_entry {
277         ...
278         AST_LIST_ENTRY(list_entry) list;
279   }
280   ...
281   struct list_entry *current;
282   ...
283   AST_LIST_TRAVERSE(&entries, current, list) {
284      (do something with current here)
285   }
286   \endcode
287   \warning If you modify the forward-link pointer contained in the \a current entry while
288   inside the loop, the behavior will be unpredictable. At a minimum, the following
289   macros will modify the forward-link pointer, and should not be used inside
290   AST_LIST_TRAVERSE() against the entry pointed to by the \a current pointer without
291   careful consideration of their consequences:
292   \li AST_LIST_NEXT() (when used as an lvalue)
293   \li AST_LIST_INSERT_AFTER()
294   \li AST_LIST_INSERT_HEAD()
295   \li AST_LIST_INSERT_TAIL()
296 */
297 #define AST_LIST_TRAVERSE(head,var,field)                               \
298         for((var) = (head)->first; (var); (var) = (var)->field.next)
299
300 /*!
301   \brief Loops safely over (traverses) the entries in a list.
302   \param head This is a pointer to the list head structure
303   \param var This is the name of the variable that will hold a pointer to the
304   current list entry on each iteration. It must be declared before calling
305   this macro.
306   \param field This is the name of the field (declared using AST_LIST_ENTRY())
307   used to link entries of this list together.
308
309   This macro is used to safely loop over (traverse) the entries in a list. It
310   uses a \a for loop, and supplies the enclosed code with a pointer to each list
311   entry as it loops. It is typically used as follows:
312
313   \code
314   static AST_LIST_HEAD(entry_list, list_entry) entries;
315   ...
316   struct list_entry {
317         ...
318         AST_LIST_ENTRY(list_entry) list;
319   }
320   ...
321   struct list_entry *current;
322   ...
323   AST_LIST_TRAVERSE_SAFE_BEGIN(&entries, current, list) {
324      (do something with current here)
325   }
326   AST_LIST_TRAVERSE_SAFE_END;
327   \endcode
328
329   It differs from AST_LIST_TRAVERSE() in that the code inside the loop can modify
330   (or even free, after calling AST_LIST_REMOVE_CURRENT()) the entry pointed to by
331   the \a current pointer without affecting the loop traversal.
332 */
333 #define AST_LIST_TRAVERSE_SAFE_BEGIN(head, var, field) {                                \
334         typeof((head)->first) __list_next;                                              \
335         typeof((head)->first) __list_prev = NULL;                                       \
336         typeof((head)->first) __new_prev = NULL;                                        \
337         for ((var) = (head)->first, __new_prev = (var),                                 \
338               __list_next = (var) ? (var)->field.next : NULL;                           \
339              (var);                                                                     \
340              __list_prev = __new_prev, (var) = __list_next,                             \
341              __new_prev = (var),                                                        \
342              __list_next = (var) ? (var)->field.next : NULL                             \
343             )
344
345 /*!
346   \brief Removes the \a current entry from a list during a traversal.
347   \param head This is a pointer to the list head structure
348   \param field This is the name of the field (declared using AST_LIST_ENTRY())
349   used to link entries of this list together.
350
351   \note This macro can \b only be used inside an AST_LIST_TRAVERSE_SAFE_BEGIN()
352   block; it is used to unlink the current entry from the list without affecting
353   the list traversal (and without having to re-traverse the list to modify the
354   previous entry, if any).
355  */
356 #define AST_LIST_REMOVE_CURRENT(head, field)                                            \
357         __new_prev = __list_prev;                                                       \
358         if (__list_prev)                                                                \
359                 __list_prev->field.next = __list_next;                                  \
360         else                                                                            \
361                 (head)->first = __list_next;                                            \
362         if (!__list_next)                                                               \
363                 (head)->last = __list_prev;
364
365 /*!
366   \brief Inserts a list entry before the current entry during a traversal.
367   \param head This is a pointer to the list head structure
368   \param elm This is a pointer to the entry to be inserted.
369   \param field This is the name of the field (declared using AST_LIST_ENTRY())
370   used to link entries of this list together.
371
372   \note This macro can \b only be used inside an AST_LIST_TRAVERSE_SAFE_BEGIN()
373   block.
374  */
375 #define AST_LIST_INSERT_BEFORE_CURRENT(head, elm, field) do {           \
376         if (__list_prev) {                                              \
377                 (elm)->field.next = __list_prev->field.next;            \
378                 __list_prev->field.next = elm;                          \
379         } else {                                                        \
380                 (elm)->field.next = (head)->first;                      \
381                 (head)->first = (elm);                                  \
382         }                                                               \
383         __new_prev = (elm);                                             \
384 } while (0)
385
386 /*!
387   \brief Closes a safe loop traversal block.
388  */
389 #define AST_LIST_TRAVERSE_SAFE_END  }
390
391 /*!
392   \brief Initializes a list head structure.
393   \param head This is a pointer to the list head structure
394
395   This macro initializes a list head structure by setting the head
396   entry to \a NULL (empty list) and recreating the embedded lock.
397 */
398 #define AST_LIST_HEAD_INIT(head) {                                      \
399         (head)->first = NULL;                                           \
400         (head)->last = NULL;                                            \
401         ast_mutex_init(&(head)->lock);                                  \
402 }
403
404 /*!
405   \brief Destroys a list head structure.
406   \param head This is a pointer to the list head structure
407
408   This macro destroys a list head structure by setting the head
409   entry to \a NULL (empty list) and destroying the embedded lock.
410   It does not free the structure from memory.
411 */
412 #define AST_LIST_HEAD_DESTROY(head) {                                   \
413         (head)->first = NULL;                                           \
414         (head)->last = NULL;                                            \
415         ast_mutex_destroy(&(head)->lock);                               \
416 }
417
418 /*!
419   \brief Initializes a list head structure.
420   \param head This is a pointer to the list head structure
421
422   This macro initializes a list head structure by setting the head
423   entry to \a NULL (empty list). There is no embedded lock handling
424   with this macro.
425 */
426 #define AST_LIST_HEAD_INIT_NOLOCK(head) {                               \
427         (head)->first = NULL;                                           \
428         (head)->last = NULL;                                            \
429 }
430
431 /*!
432   \brief Inserts a list entry after a given entry.
433   \param head This is a pointer to the list head structure
434   \param listelm This is a pointer to the entry after which the new entry should
435   be inserted.
436   \param elm This is a pointer to the entry to be inserted.
437   \param field This is the name of the field (declared using AST_LIST_ENTRY())
438   used to link entries of this list together.
439  */
440 #define AST_LIST_INSERT_AFTER(head, listelm, elm, field) do {           \
441         (elm)->field.next = (listelm)->field.next;                      \
442         (listelm)->field.next = (elm);                                  \
443         if ((head)->last == (listelm))                                  \
444                 (head)->last = (elm);                                   \
445 } while (0)
446
447 /*!
448   \brief Inserts a list entry at the head of a list.
449   \param head This is a pointer to the list head structure
450   \param elm This is a pointer to the entry to be inserted.
451   \param field This is the name of the field (declared using AST_LIST_ENTRY())
452   used to link entries of this list together.
453  */
454 #define AST_LIST_INSERT_HEAD(head, elm, field) do {                     \
455                 (elm)->field.next = (head)->first;                      \
456                 (head)->first = (elm);                                  \
457                 if (!(head)->last)                                      \
458                         (head)->last = (elm);                           \
459 } while (0)
460
461 /*!
462   \brief Appends a list entry to the tail of a list.
463   \param head This is a pointer to the list head structure
464   \param elm This is a pointer to the entry to be appended.
465   \param field This is the name of the field (declared using AST_LIST_ENTRY())
466   used to link entries of this list together.
467
468   Note: The link field in the appended entry is \b not modified, so if it is
469   actually the head of a list itself, the entire list will be appended
470   temporarily (until the next AST_LIST_INSERT_TAIL is performed).
471  */
472 #define AST_LIST_INSERT_TAIL(head, elm, field) do {                     \
473       if (!(head)->first) {                                             \
474                 (head)->first = (elm);                                  \
475                 (head)->last = (elm);                                   \
476       } else {                                                          \
477                 (head)->last->field.next = (elm);                       \
478                 (head)->last = (elm);                                   \
479       }                                                                 \
480 } while (0)
481
482 /*!
483   \brief Appends a whole list to the tail of a list.
484   \param head This is a pointer to the list head structure
485   \param list This is a pointer to the list to be appended.
486   \param field This is the name of the field (declared using AST_LIST_ENTRY())
487   used to link entries of this list together.
488  */
489 #define AST_LIST_APPEND_LIST(head, list, field) do {                    \
490       if (!(head)->first) {                                             \
491                 (head)->first = (list)->first;                          \
492                 (head)->last = (list)->last;                            \
493       } else {                                                          \
494                 (head)->last->field.next = (list)->first;               \
495                 (head)->last = (list)->last;                            \
496       }                                                                 \
497 } while (0)
498
499 /*!
500   \brief Removes and returns the head entry from a list.
501   \param head This is a pointer to the list head structure
502   \param field This is the name of the field (declared using AST_LIST_ENTRY())
503   used to link entries of this list together.
504
505   Removes the head entry from the list, and returns a pointer to it.
506   This macro is safe to call on an empty list.
507  */
508 #define AST_LIST_REMOVE_HEAD(head, field) ({                            \
509                 typeof((head)->first) cur = (head)->first;              \
510                 if (cur) {                                              \
511                         (head)->first = cur->field.next;                \
512                         cur->field.next = NULL;                         \
513                         if ((head)->last == cur)                        \
514                                 (head)->last = NULL;                    \
515                 }                                                       \
516                 cur;                                                    \
517         })
518
519 /*!
520   \brief Removes a specific entry from a list.
521   \param head This is a pointer to the list head structure
522   \param elm This is a pointer to the entry to be removed.
523   \param field This is the name of the field (declared using AST_LIST_ENTRY())
524   used to link entries of this list together.
525   \warning The removed entry is \b not freed nor modified in any way.
526  */
527 #define AST_LIST_REMOVE(head, elm, field) do {                          \
528         if ((head)->first == (elm)) {                                   \
529                 (head)->first = (elm)->field.next;                      \
530                 if ((head)->last == (elm))                      \
531                         (head)->last = NULL;                    \
532         } else {                                                                \
533                 typeof(elm) curelm = (head)->first;                     \
534                 while (curelm && (curelm->field.next != (elm)))                 \
535                         curelm = curelm->field.next;                    \
536                 if (curelm) { \
537                         curelm->field.next = (elm)->field.next;                 \
538                         if ((head)->last == (elm))                              \
539                                 (head)->last = curelm;                          \
540                 } \
541         }                                                               \
542         (elm)->field.next = NULL;                                       \
543 } while (0)
544
545 #endif /* _ASTERISK_LINKEDLISTS_H */