queue device state changes and handle them serially in a background thread
[asterisk/asterisk.git] / include / asterisk / linkedlists.h
1 #ifndef ASTERISK_LINKEDLISTS_H
2 #define ASTERISK_LINKEDLISTS_H
3
4 #include "asterisk/lock.h"
5
6 /*!
7   \file linkedlists.h
8   \brief A set of macros to manage forward-linked lists.
9 */
10
11 /*!
12   \brief Attempts to lock a list.
13   \param head This is a pointer to the list head structure
14
15   This macro attempts to place an exclusive lock in the
16   list head structure pointed to by head.
17   Returns non-zero on success, 0 on failure
18 */
19 #define AST_LIST_LOCK(head)                                             \
20         ast_mutex_lock(&(head)->lock) 
21         
22 /*!
23   \brief Attempts to unlock a list.
24   \param head This is a pointer to the list head structure
25
26   This macro attempts to remove an exclusive lock from the
27   list head structure pointed to by head. If the list
28   was not locked by this thread, this macro has no effect.
29 */
30 #define AST_LIST_UNLOCK(head)                                           \
31         ast_mutex_unlock(&(head)->lock)
32
33 /*!
34   \brief Defines a structure to be used to hold a list of specified type.
35   \param name This will be the name of the defined structure.
36   \param type This is the type of each list entry.
37
38   This macro creates a structure definition that can be used
39   to hold a list of the entries of type \a type. It does not actually
40   declare (allocate) a structure; to do that, either follow this
41   macro with the desired name of the instance you wish to declare,
42   or use the specified \a name to declare instances elsewhere.
43
44   Example usage:
45   \code
46   static AST_LIST_HEAD(entry_list, entry) entries;
47   \endcode
48
49   This would define \c struct \c entry_list, and declare an instance of it named
50   \a entries, all intended to hold a list of type \c struct \c entry.
51 */
52 #define AST_LIST_HEAD(name, type)                                       \
53 struct name {                                                           \
54         struct type *first;                                             \
55         ast_mutex_t lock;                                               \
56 }
57
58 /*!
59   \brief Defines a structure to be used to hold a list of specified type, statically initialized.
60   \param name This will be the name of the defined structure.
61   \param type This is the type of each list entry.
62
63   This macro creates a structure definition that can be used
64   to hold a list of the entries of type \a type, and allocates an instance
65   of it, initialized to be empty.
66
67   Example usage:
68   \code
69   static AST_LIST_HEAD_STATIC(entry_list, entry);
70   \endcode
71
72   This would define \c struct \c entry_list, intended to hold a list of
73   type \c struct \c entry.
74 */
75 #define AST_LIST_HEAD_STATIC(name, type)                                \
76 struct name {                                                           \
77         struct type *first;                                             \
78         ast_mutex_t lock;                                               \
79 } name = {                                                              \
80         .first = NULL,                                                  \
81         .lock = AST_MUTEX_INIT_VALUE,                                   \
82 };
83
84 /*!
85   \brief Initializes a list head structure with a specified first entry.
86   \param head This is a pointer to the list head structure
87   \param entry pointer to the list entry that will become the head of the list
88
89   This macro initializes a list head structure by setting the head
90   entry to the supplied value and recreating the embedded lock.
91 */
92 #define AST_LIST_HEAD_SET(head, entry) do {                             \
93         (head)->first=(entry);                                          \
94         ast_pthread_mutex_init(&(head)->lock,NULL);                             \
95 } while (0)
96
97 /*!
98   \brief Declare a forward link structure inside a list entry.
99   \param type This is the type of each list entry.
100
101   This macro declares a structure to be used to link list entries together.
102   It must be used inside the definition of the structure named in
103   \a type, as follows:
104
105   \code
106   struct list_entry {
107         ...
108         AST_LIST_ENTRY(list_entry) list;
109   }
110   \endcode
111
112   The field name \a list here is arbitrary, and can be anything you wish.
113 */
114 #define AST_LIST_ENTRY(type)                                            \
115 struct {                                                                \
116         struct type *next;                                              \
117 }
118  
119 /*!
120   \brief Returns the first entry contained in a list.
121   \param head This is a pointer to the list head structure
122  */
123 #define AST_LIST_FIRST(head)    ((head)->first)
124
125 /*!
126   \brief Returns the next entry in the list after the given entry.
127   \param elm This is a pointer to the current entry.
128   \param field This is the name of the field (declared using AST_LIST_ENTRY())
129   used to link entries of this list together.
130 */
131 #define AST_LIST_NEXT(elm, field)       ((elm)->field.next)
132
133 /*!
134   \brief Checks whether the specified list contains any entries.
135   \param head This is a pointer to the list head structure
136
137   Returns non-zero if the list has entries, zero if not.
138  */
139 #define AST_LIST_EMPTY(head)    (AST_LIST_FIRST(head) == NULL)
140
141 /*!
142   \brief Loops over (traverses) the entries in a list.
143   \param head This is a pointer to the list head structure
144   \param var This is the name of the variable that will hold a pointer to the
145   current list entry on each iteration. It must be declared before calling
146   this macro.
147   \param field This is the name of the field (declared using AST_LIST_ENTRY())
148   used to link entries of this list together.
149
150   This macro is use to loop over (traverse) the entries in a list. It uses a
151   \a for loop, and supplies the enclosed code with a pointer to each list
152   entry as it loops. It is typically used as follows:
153   \code
154   static AST_LIST_HEAD(entry_list, list_entry) entries;
155   ...
156   struct list_entry {
157         ...
158         AST_LIST_ENTRY(list_entry) list;
159   }
160   ...
161   struct list_entry *current;
162   ...
163   AST_LIST_TRAVERSE(&entries, current, list) {
164      (do something with current here)
165   }
166   \endcode
167   \warning If you modify the forward-link pointer contained in the \a current entry while
168   inside the loop, the behavior will be unpredictable. At a minimum, the following
169   macros will modify the forward-link pointer, and should not be used inside
170   AST_LIST_TRAVERSE() against the entry pointed to by the \a current pointer without
171   careful consideration of their consequences:
172   \li AST_LIST_NEXT() (when used as an lvalue)
173   \li AST_LIST_INSERT_AFTER()
174   \li AST_LIST_INSERT_HEAD()
175   \li AST_LIST_INSERT_TAIL()
176 */
177 #define AST_LIST_TRAVERSE(head,var,field)                               \
178         for((var) = (head)->first; (var); (var) = (var)->field.next)
179
180 /*!
181   \brief Loops safely over (traverses) the entries in a list.
182   \param head This is a pointer to the list head structure
183   \param var This is the name of the variable that will hold a pointer to the
184   current list entry on each iteration. It must be declared before calling
185   this macro.
186   \param field This is the name of the field (declared using AST_LIST_ENTRY())
187   used to link entries of this list together.
188
189   This macro is used to safely loop over (traverse) the entries in a list. It
190   uses a \a for loop, and supplies the enclosed code with a pointer to each list
191   entry as it loops. It is typically used as follows:
192
193   \code
194   static AST_LIST_HEAD(entry_list, list_entry) entries;
195   ...
196   struct list_entry {
197         ...
198         AST_LIST_ENTRY(list_entry) list;
199   }
200   ...
201   struct list_entry *current;
202   ...
203   AST_LIST_TRAVERSE_SAFE_BEGIN(&entries, current, list) {
204      (do something with current here)
205   }
206   AST_LIST_TRAVERSE_SAFE_END;
207   \endcode
208
209   It differs from AST_LIST_TRAVERSE() in that the code inside the loop can modify
210   (or even free, after calling AST_LIST_REMOVE_CURRENT()) the entry pointed to by
211   the \a current pointer without affecting the loop traversal.
212 */
213 #define AST_LIST_TRAVERSE_SAFE_BEGIN(head, var, field) {                                \
214         typeof((head)->first) __list_next;                                              \
215         typeof((head)->first) __list_prev = NULL;                                       \
216         for ((var) = (head)->first,  __list_next = (var) ? (var)->field.next : NULL;    \
217              (var);                                                                     \
218              __list_prev = (var), (var) = __list_next,                                  \
219              __list_next = (var) ? (var)->field.next : NULL                             \
220             )
221
222 /*!
223   \brief Removes the \a current entry from a list during a traversal.
224   \param head This is a pointer to the list head structure
225   \param field This is the name of the field (declared using AST_LIST_ENTRY())
226   used to link entries of this list together.
227
228   \note This macro can \b only be used inside an AST_LIST_TRAVERSE_SAFE_BEGIN()
229   block; it is used to unlink the current entry from the list without affecting
230   the list traversal (and without having to re-traverse the list to modify the
231   previous entry, if any).
232  */
233 #define AST_LIST_REMOVE_CURRENT(head, field)                                            \
234         if (__list_prev)                                                                \
235                 __list_prev->field.next = __list_next;                                  \
236         else                                                                            \
237                 (head)->first = __list_next;
238
239 /*!
240   \brief Closes a safe loop traversal block.
241  */
242 #define AST_LIST_TRAVERSE_SAFE_END  }
243
244 /*!
245   \brief Initializes a list head structure.
246   \param head This is a pointer to the list head structure
247
248   This macro initializes a list head structure by setting the head
249   entry to \a NULL (empty list) and recreating the embedded lock.
250 */
251 #define AST_LIST_HEAD_INIT(head) {                                      \
252         (head)->first = NULL;                                           \
253         ast_pthread_mutex_init(&(head)->lock,NULL);                     \
254 }
255
256 /*!
257   \brief Inserts a list entry after a given entry.
258   \param listelm This is a pointer to the entry after which the new entry should
259   be inserted.
260   \param elm This is a pointer to the entry to be inserted.
261   \param field This is the name of the field (declared using AST_LIST_ENTRY())
262   used to link entries of this list together.
263  */
264 #define AST_LIST_INSERT_AFTER(listelm, elm, field) do {                 \
265         (elm)->field.next = (listelm)->field.next;                      \
266         (listelm)->field.next = (elm);                                  \
267 } while (0)
268
269 /*!
270   \brief Inserts a list entry at the head of a list.
271   \param head This is a pointer to the list head structure
272   \param elm This is a pointer to the entry to be inserted.
273   \param field This is the name of the field (declared using AST_LIST_ENTRY())
274   used to link entries of this list together.
275  */
276 #define AST_LIST_INSERT_HEAD(head, elm, field) do {                     \
277                 (elm)->field.next = (head)->first;                      \
278                 (head)->first = (elm);                                  \
279 } while (0)
280
281 /*!
282   \brief Appends a list entry to the tail of a list.
283   \param head This is a pointer to the list head structure
284   \param elm This is a pointer to the entry to be appended.
285   \param field This is the name of the field (declared using AST_LIST_ENTRY())
286   used to link entries of this list together.
287
288   Note: The link field in the appended entry is \b not modified, so if it is
289   actually the head of a list itself, the entire list will be appended.
290  */
291 #define AST_LIST_INSERT_TAIL(head, elm, field) do {                     \
292       if (!(head)->first) {                                             \
293               (head)->first = (elm);                                    \
294       } else {                                                          \
295               typeof(elm) curelm = (head)->first;                       \
296               while (curelm->field.next != NULL)                        \
297                       curelm = curelm->field.next;                      \
298               curelm->field.next = (elm);                               \
299       }                                                                 \
300 } while (0)
301
302 /*!
303   \brief Removes and returns the head entry from a list.
304   \param head This is a pointer to the list head structure
305   \param field This is the name of the field (declared using AST_LIST_ENTRY())
306   used to link entries of this list together.
307
308   Removes the head entry from the list, and returns a pointer to it. The
309   forward-link pointer in the returned entry is \b not cleared. This macro
310   is safe to call on an empty list.
311  */
312 #define AST_LIST_REMOVE_HEAD(head, field) ({                            \
313                 typeof((head)->first) cur = (head)->first;              \
314                 if (cur)                                                \
315                         (head)->first = cur->field.next;                \
316                 cur;                                                    \
317         })
318
319 /*!
320   \brief Removes a specific entry from a list.
321   \param head This is a pointer to the list head structure
322   \param elm This is a pointer to the entry to be removed.
323   \param field This is the name of the field (declared using AST_LIST_ENTRY())
324   used to link entries of this list together.
325   \warning The removed entry is \b not freed nor modified in any way.
326  */
327 #define AST_LIST_REMOVE(head, elm, field) do {                          \
328         if ((head)->first == (elm)) {                                   \
329                 (head)->first = (elm)->field.next;                      \
330         }                                                               \
331         else {                                                          \
332                 typeof(elm) curelm = (head)->first;                     \
333                 while (curelm->field.next != (elm))                     \
334                         curelm = curelm->field.next;                    \
335                 curelm->field.next = (elm)->field.next;                 \
336         }                                                               \
337 } while (0)
338
339 #endif