3dcd9a5630874b7fe21b739c9fa4b7803a82cad3
[asterisk/asterisk.git] / include / asterisk / linkedlists.h
1 /*
2  * Asterisk -- An open source telephony toolkit.
3  *
4  * Copyright (C) 1999 - 2005, 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 Attempts to lock 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 Attempts to unlock a list.
43   \param head This is a pointer to the list head structure
44
45   This macro attempts to remove an exclusive lock from the
46   list head structure pointed to by head. If the list
47   was not locked by this thread, this macro has no effect.
48 */
49 #define AST_LIST_UNLOCK(head)                                           \
50         ast_mutex_unlock(&(head)->lock)
51
52 /*!
53   \brief Defines a structure to be used to hold a list of specified type.
54   \param name This will be the name of the defined structure.
55   \param type This is the type of each list entry.
56
57   This macro creates a structure definition that can be used
58   to hold a list of the entries of type \a type. It does not actually
59   declare (allocate) a structure; to do that, either follow this
60   macro with the desired name of the instance you wish to declare,
61   or use the specified \a name to declare instances elsewhere.
62
63   Example usage:
64   \code
65   static AST_LIST_HEAD(entry_list, entry) entries;
66   \endcode
67
68   This would define \c struct \c entry_list, and declare an instance of it named
69   \a entries, all intended to hold a list of type \c struct \c entry.
70 */
71 #define AST_LIST_HEAD(name, type)                                       \
72 struct name {                                                           \
73         struct type *first;                                             \
74         struct type *last;                                              \
75         ast_mutex_t lock;                                               \
76 }
77
78 /*!
79   \brief Defines a structure to be used to hold a list of specified type (with no lock).
80   \param name This will be the name of the defined structure.
81   \param type This is the type of each list entry.
82
83   This macro creates a structure definition that can be used
84   to hold a list of the entries of type \a type. It does not actually
85   declare (allocate) a structure; to do that, either follow this
86   macro with the desired name of the instance you wish to declare,
87   or use the specified \a name to declare instances elsewhere.
88
89   Example usage:
90   \code
91   static AST_LIST_HEAD_NOLOCK(entry_list, entry) entries;
92   \endcode
93
94   This would define \c struct \c entry_list, and declare an instance of it named
95   \a entries, all intended to hold a list of type \c struct \c entry.
96 */
97 #define AST_LIST_HEAD_NOLOCK(name, type)                                \
98 struct name {                                                           \
99         struct type *first;                                             \
100         struct type *last;                                              \
101 }
102
103 /*!
104   \brief Defines a structure to be used to hold a list of specified type, statically initialized.
105   \param name This will be the name of the defined structure.
106   \param type This is the type of each list entry.
107
108   This macro creates a structure definition that can be used
109   to hold a list of the entries of type \a type, and allocates an instance
110   of it, initialized to be empty.
111
112   Example usage:
113   \code
114   static AST_LIST_HEAD_STATIC(entry_list, entry);
115   \endcode
116
117   This would define \c struct \c entry_list, intended to hold a list of
118   type \c struct \c entry.
119 */
120 #define AST_LIST_HEAD_STATIC(name, type)                                \
121 struct name {                                                           \
122         struct type *first;                                             \
123         struct type *last;                                              \
124         ast_mutex_t lock;                                               \
125 } name = {                                                              \
126         .first = NULL,                                                  \
127         .last = NULL,                                                   \
128         .lock = AST_MUTEX_INIT_VALUE,                                   \
129 };
130
131 /*!
132   \brief Initializes a list head structure with a specified first entry.
133   \param head This is a pointer to the list head structure
134   \param entry pointer to the list entry that will become the head of the list
135
136   This macro initializes a list head structure by setting the head
137   entry to the supplied value and recreating the embedded lock.
138 */
139 #define AST_LIST_HEAD_SET(head, entry) do {                             \
140         (head)->first = (entry);                                        \
141         (head)->last = NULL;                                            \
142         ast_mutex_init(&(head)->lock);                                  \
143 } while (0)
144
145 /*!
146   \brief Initializes a list head structure with a specified first entry.
147   \param head This is a pointer to the list head structure
148   \param entry pointer to the list entry that will become the head of the list
149
150   This macro initializes a list head structure by setting the head
151   entry to the supplied value.
152 */
153 #define AST_LIST_HEAD_SET_NOLOCK(head, entry) do {                      \
154         (head)->first = (entry);                                        \
155         (head)->last = NULL;                                            \
156 } while (0)
157
158 /*!
159   \brief Declare a forward link structure inside a list entry.
160   \param type This is the type of each list entry.
161
162   This macro declares a structure to be used to link list entries together.
163   It must be used inside the definition of the structure named in
164   \a type, as follows:
165
166   \code
167   struct list_entry {
168         ...
169         AST_LIST_ENTRY(list_entry) list;
170   }
171   \endcode
172
173   The field name \a list here is arbitrary, and can be anything you wish.
174 */
175 #define AST_LIST_ENTRY(type)                                            \
176 struct {                                                                \
177         struct type *next;                                              \
178 }
179  
180 /*!
181   \brief Returns the first entry contained in a list.
182   \param head This is a pointer to the list head structure
183  */
184 #define AST_LIST_FIRST(head)    ((head)->first)
185
186 /*!
187   \brief Returns the next entry in the list after the given entry.
188   \param elm This is a pointer to the current entry.
189   \param field This is the name of the field (declared using AST_LIST_ENTRY())
190   used to link entries of this list together.
191 */
192 #define AST_LIST_NEXT(elm, field)       ((elm)->field.next)
193
194 /*!
195   \brief Checks whether the specified list contains any entries.
196   \param head This is a pointer to the list head structure
197
198   Returns non-zero if the list has entries, zero if not.
199  */
200 #define AST_LIST_EMPTY(head)    (AST_LIST_FIRST(head) == NULL)
201
202 /*!
203   \brief Loops over (traverses) the entries in a list.
204   \param head This is a pointer to the list head structure
205   \param var This is the name of the variable that will hold a pointer to the
206   current list entry on each iteration. It must be declared before calling
207   this macro.
208   \param field This is the name of the field (declared using AST_LIST_ENTRY())
209   used to link entries of this list together.
210
211   This macro is use to loop over (traverse) the entries in a list. It uses a
212   \a for loop, and supplies the enclosed code with a pointer to each list
213   entry as it loops. It is typically used as follows:
214   \code
215   static AST_LIST_HEAD(entry_list, list_entry) entries;
216   ...
217   struct list_entry {
218         ...
219         AST_LIST_ENTRY(list_entry) list;
220   }
221   ...
222   struct list_entry *current;
223   ...
224   AST_LIST_TRAVERSE(&entries, current, list) {
225      (do something with current here)
226   }
227   \endcode
228   \warning If you modify the forward-link pointer contained in the \a current entry while
229   inside the loop, the behavior will be unpredictable. At a minimum, the following
230   macros will modify the forward-link pointer, and should not be used inside
231   AST_LIST_TRAVERSE() against the entry pointed to by the \a current pointer without
232   careful consideration of their consequences:
233   \li AST_LIST_NEXT() (when used as an lvalue)
234   \li AST_LIST_INSERT_AFTER()
235   \li AST_LIST_INSERT_HEAD()
236   \li AST_LIST_INSERT_TAIL()
237 */
238 #define AST_LIST_TRAVERSE(head,var,field)                               \
239         for((var) = (head)->first; (var); (var) = (var)->field.next)
240
241 /*!
242   \brief Loops safely over (traverses) the entries in a list.
243   \param head This is a pointer to the list head structure
244   \param var This is the name of the variable that will hold a pointer to the
245   current list entry on each iteration. It must be declared before calling
246   this macro.
247   \param field This is the name of the field (declared using AST_LIST_ENTRY())
248   used to link entries of this list together.
249
250   This macro is used to safely loop over (traverse) the entries in a list. It
251   uses a \a for loop, and supplies the enclosed code with a pointer to each list
252   entry as it loops. It is typically used as follows:
253
254   \code
255   static AST_LIST_HEAD(entry_list, list_entry) entries;
256   ...
257   struct list_entry {
258         ...
259         AST_LIST_ENTRY(list_entry) list;
260   }
261   ...
262   struct list_entry *current;
263   ...
264   AST_LIST_TRAVERSE_SAFE_BEGIN(&entries, current, list) {
265      (do something with current here)
266   }
267   AST_LIST_TRAVERSE_SAFE_END;
268   \endcode
269
270   It differs from AST_LIST_TRAVERSE() in that the code inside the loop can modify
271   (or even free, after calling AST_LIST_REMOVE_CURRENT()) the entry pointed to by
272   the \a current pointer without affecting the loop traversal.
273 */
274 #define AST_LIST_TRAVERSE_SAFE_BEGIN(head, var, field) {                                \
275         typeof((head)->first) __list_next;                                              \
276         typeof((head)->first) __list_prev = NULL;                                       \
277         for ((var) = (head)->first,  __list_next = (var) ? (var)->field.next : NULL;    \
278              (var);                                                                     \
279              __list_prev = (var), (var) = __list_next,                                  \
280              __list_next = (var) ? (var)->field.next : NULL                             \
281             )
282
283 /*!
284   \brief Removes the \a current entry from a list during a traversal.
285   \param head This is a pointer to the list head structure
286   \param field This is the name of the field (declared using AST_LIST_ENTRY())
287   used to link entries of this list together.
288
289   \note This macro can \b only be used inside an AST_LIST_TRAVERSE_SAFE_BEGIN()
290   block; it is used to unlink the current entry from the list without affecting
291   the list traversal (and without having to re-traverse the list to modify the
292   previous entry, if any).
293  */
294 #define AST_LIST_REMOVE_CURRENT(head, field)                                            \
295         if (__list_prev)                                                                \
296                 __list_prev->field.next = __list_next;                                  \
297         else                                                                            \
298                 (head)->first = __list_next;                                            \
299         if (!__list_next)                                                               \
300                 (head)->last = __list_prev;
301
302 /*!
303   \brief Closes a safe loop traversal block.
304  */
305 #define AST_LIST_TRAVERSE_SAFE_END  }
306
307 /*!
308   \brief Initializes a list head structure.
309   \param head This is a pointer to the list head structure
310
311   This macro initializes a list head structure by setting the head
312   entry to \a NULL (empty list) and recreating the embedded lock.
313 */
314 #define AST_LIST_HEAD_INIT(head) {                                      \
315         (head)->first = NULL;                                           \
316         (head)->last = NULL;                                            \
317         ast_mutex_init(&(head)->lock);                                  \
318 }
319
320 /*!
321   \brief Destroys a list head structure.
322   \param head This is a pointer to the list head structure
323
324   This macro destroys a list head structure by setting the head
325   entry to \a NULL (empty list) and destroying the embedded lock.
326   It does not free the structure from memory.
327 */
328 #define AST_LIST_HEAD_DESTROY(head) {                                   \
329         (head)->first = NULL;                                           \
330         (head)->last = NULL;                                            \
331         ast_mutex_destroy(&(head)->lock);                               \
332 }
333
334 /*!
335   \brief Initializes a list head structure.
336   \param head This is a pointer to the list head structure
337
338   This macro initializes a list head structure by setting the head
339   entry to \a NULL (empty list) and recreating the embedded lock.
340 */
341 #define AST_LIST_HEAD_INIT_NOLOCK(head) {                               \
342         (head)->first = NULL;                                           \
343         (head)->last = NULL;                                            \
344 }
345
346 /*!
347   \brief Inserts a list entry after a given entry.
348   \param head This is a pointer to the list head structure
349   \param listelm This is a pointer to the entry after which the new entry should
350   be inserted.
351   \param elm This is a pointer to the entry to be inserted.
352   \param field This is the name of the field (declared using AST_LIST_ENTRY())
353   used to link entries of this list together.
354  */
355 #define AST_LIST_INSERT_AFTER(head, listelm, elm, field) do {           \
356         (elm)->field.next = (listelm)->field.next;                      \
357         (listelm)->field.next = (elm);                                  \
358         if ((head)->last == (listelm))                                  \
359                 (head)->last = (elm);                                   \
360 } while (0)
361
362 /*!
363   \brief Inserts a list entry at the head of a list.
364   \param head This is a pointer to the list head structure
365   \param elm This is a pointer to the entry to be inserted.
366   \param field This is the name of the field (declared using AST_LIST_ENTRY())
367   used to link entries of this list together.
368  */
369 #define AST_LIST_INSERT_HEAD(head, elm, field) do {                     \
370                 (elm)->field.next = (head)->first;                      \
371                 (head)->first = (elm);                                  \
372 } while (0)
373
374 /*!
375   \brief Appends a list entry to the tail of a list.
376   \param head This is a pointer to the list head structure
377   \param elm This is a pointer to the entry to be appended.
378   \param field This is the name of the field (declared using AST_LIST_ENTRY())
379   used to link entries of this list together.
380
381   Note: The link field in the appended entry is \b not modified, so if it is
382   actually the head of a list itself, the entire list will be appended.
383  */
384 #define AST_LIST_INSERT_TAIL(head, elm, field) do {                     \
385       if (!(head)->first) {                                             \
386                 (head)->first = (elm);                                  \
387                 (head)->last = (elm);                                   \
388       } else {                                                          \
389                 (head)->last->field.next = (elm);                       \
390                 (head)->last = (elm);                                   \
391       }                                                                 \
392 } while (0)
393
394 /*!
395   \brief Removes and returns the head entry from a list.
396   \param head This is a pointer to the list head structure
397   \param field This is the name of the field (declared using AST_LIST_ENTRY())
398   used to link entries of this list together.
399
400   Removes the head entry from the list, and returns a pointer to it.
401   This macro is safe to call on an empty list.
402  */
403 #define AST_LIST_REMOVE_HEAD(head, field) ({                            \
404                 typeof((head)->first) cur = (head)->first;              \
405                 if (cur) {                                              \
406                         (head)->first = cur->field.next;                \
407                         cur->field.next = NULL;                         \
408                         if ((head)->last == cur)                        \
409                                 (head)->last = NULL;                    \
410                 }                                                       \
411                 cur;                                                    \
412         })
413
414 /*!
415   \brief Removes a specific entry from a list.
416   \param head This is a pointer to the list head structure
417   \param elm This is a pointer to the entry to be removed.
418   \param field This is the name of the field (declared using AST_LIST_ENTRY())
419   used to link entries of this list together.
420   \warning The removed entry is \b not freed nor modified in any way.
421  */
422 #define AST_LIST_REMOVE(head, elm, field) do {                          \
423         if ((head)->first == (elm)) {                                   \
424                 (head)->first = (elm)->field.next;                      \
425         }                                                               \
426         else {                                                          \
427                 typeof(elm) curelm = (head)->first;                     \
428                 while (curelm->field.next != (elm))                     \
429                         curelm = curelm->field.next;                    \
430                 curelm->field.next = (elm)->field.next;                 \
431         }                                                               \
432         if ((head)->last == elm)                                        \
433                 (head)->last = NULL;                                    \
434 } while (0)
435
436 #endif /* _ASTERISK_LINKEDLISTS_H */