49dd3a10dc56454d486eabd8d3f91128ad3ebcdc
[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 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 initial values for a declaration of AST_LIST_HEAD
105 */
106 #define AST_LIST_HEAD_INIT_VALUE        {               \
107         .first = NULL,                                  \
108         .last = NULL,                                   \
109         .lock = AST_MUTEX_INIT_VALUE,                   \
110         }
111
112 /*!
113   \brief Defines initial values for a declaration of AST_LIST_HEAD_NOLOCK
114 */
115 #define AST_LIST_HEAD_NOLOCK_INIT_VALUE {       \
116         .first = NULL,                                  \
117         .last = NULL,                                   \
118         }
119
120 /*!
121   \brief Defines a structure to be used to hold a list of specified type, statically initialized.
122   \param name This will be the name of the defined structure.
123   \param type This is the type of each list entry.
124
125   This macro creates a structure definition that can be used
126   to hold a list of the entries of type \a type, and allocates an instance
127   of it, initialized to be empty.
128
129   Example usage:
130   \code
131   static AST_LIST_HEAD_STATIC(entry_list, entry);
132   \endcode
133
134   This would define \c struct \c entry_list, intended to hold a list of
135   type \c struct \c entry.
136 */
137 #define AST_LIST_HEAD_STATIC(name, type)                                \
138 struct name {                                                           \
139         struct type *first;                                             \
140         struct type *last;                                              \
141         ast_mutex_t lock;                                               \
142 } name = AST_LIST_HEAD_INIT_VALUE
143
144 /*!
145   \brief Defines a structure to be used to hold a list of specified type, statically initialized.
146
147   This is the same as AST_LIST_HEAD_STATIC, except without the lock included.
148 */
149 #define AST_LIST_HEAD_NOLOCK_STATIC(name, type)                         \
150 struct name {                                                           \
151         struct type *first;                                             \
152         struct type *last;                                              \
153 } name = AST_LIST_HEAD_NOLOCK_INIT_VALUE
154
155 /*!
156   \brief Initializes a list head structure with a specified first entry.
157   \param head This is a pointer to the list head structure
158   \param entry pointer to the list entry that will become the head of the list
159
160   This macro initializes a list head structure by setting the head
161   entry to the supplied value and recreating the embedded lock.
162 */
163 #define AST_LIST_HEAD_SET(head, entry) do {                             \
164         (head)->first = (entry);                                        \
165         (head)->last = (entry);                                         \
166         ast_mutex_init(&(head)->lock);                                  \
167 } while (0)
168
169 /*!
170   \brief Initializes a list head structure with a specified first entry.
171   \param head This is a pointer to the list head structure
172   \param entry pointer to the list entry that will become the head of the list
173
174   This macro initializes a list head structure by setting the head
175   entry to the supplied value.
176 */
177 #define AST_LIST_HEAD_SET_NOLOCK(head, entry) do {                      \
178         (head)->first = (entry);                                        \
179         (head)->last = (entry);                                         \
180 } while (0)
181
182 /*!
183   \brief Declare a forward link structure inside a list entry.
184   \param type This is the type of each list entry.
185
186   This macro declares a structure to be used to link list entries together.
187   It must be used inside the definition of the structure named in
188   \a type, as follows:
189
190   \code
191   struct list_entry {
192         ...
193         AST_LIST_ENTRY(list_entry) list;
194   }
195   \endcode
196
197   The field name \a list here is arbitrary, and can be anything you wish.
198 */
199 #define AST_LIST_ENTRY(type)                                            \
200 struct {                                                                \
201         struct type *next;                                              \
202 }
203  
204 /*!
205   \brief Returns the first entry contained in a list.
206   \param head This is a pointer to the list head structure
207  */
208 #define AST_LIST_FIRST(head)    ((head)->first)
209
210 /*!
211   \brief Returns the next entry in the list after the given entry.
212   \param elm This is a pointer to the current entry.
213   \param field This is the name of the field (declared using AST_LIST_ENTRY())
214   used to link entries of this list together.
215 */
216 #define AST_LIST_NEXT(elm, field)       ((elm)->field.next)
217
218 /*!
219   \brief Checks whether the specified list contains any entries.
220   \param head This is a pointer to the list head structure
221
222   Returns non-zero if the list has entries, zero if not.
223  */
224 #define AST_LIST_EMPTY(head)    (AST_LIST_FIRST(head) == NULL)
225
226 /*!
227   \brief Loops over (traverses) the entries in a list.
228   \param head This is a pointer to the list head structure
229   \param var This is the name of the variable that will hold a pointer to the
230   current list entry on each iteration. It must be declared before calling
231   this macro.
232   \param field This is the name of the field (declared using AST_LIST_ENTRY())
233   used to link entries of this list together.
234
235   This macro is use to loop over (traverse) the entries in a list. It uses a
236   \a for loop, and supplies the enclosed code with a pointer to each list
237   entry as it loops. It is typically used as follows:
238   \code
239   static AST_LIST_HEAD(entry_list, list_entry) entries;
240   ...
241   struct list_entry {
242         ...
243         AST_LIST_ENTRY(list_entry) list;
244   }
245   ...
246   struct list_entry *current;
247   ...
248   AST_LIST_TRAVERSE(&entries, current, list) {
249      (do something with current here)
250   }
251   \endcode
252   \warning If you modify the forward-link pointer contained in the \a current entry while
253   inside the loop, the behavior will be unpredictable. At a minimum, the following
254   macros will modify the forward-link pointer, and should not be used inside
255   AST_LIST_TRAVERSE() against the entry pointed to by the \a current pointer without
256   careful consideration of their consequences:
257   \li AST_LIST_NEXT() (when used as an lvalue)
258   \li AST_LIST_INSERT_AFTER()
259   \li AST_LIST_INSERT_HEAD()
260   \li AST_LIST_INSERT_TAIL()
261 */
262 #define AST_LIST_TRAVERSE(head,var,field)                               \
263         for((var) = (head)->first; (var); (var) = (var)->field.next)
264
265 /*!
266   \brief Loops safely over (traverses) the entries in a list.
267   \param head This is a pointer to the list head structure
268   \param var This is the name of the variable that will hold a pointer to the
269   current list entry on each iteration. It must be declared before calling
270   this macro.
271   \param field This is the name of the field (declared using AST_LIST_ENTRY())
272   used to link entries of this list together.
273
274   This macro is used to safely loop over (traverse) the entries in a list. It
275   uses a \a for loop, and supplies the enclosed code with a pointer to each list
276   entry as it loops. It is typically used as follows:
277
278   \code
279   static AST_LIST_HEAD(entry_list, list_entry) entries;
280   ...
281   struct list_entry {
282         ...
283         AST_LIST_ENTRY(list_entry) list;
284   }
285   ...
286   struct list_entry *current;
287   ...
288   AST_LIST_TRAVERSE_SAFE_BEGIN(&entries, current, list) {
289      (do something with current here)
290   }
291   AST_LIST_TRAVERSE_SAFE_END;
292   \endcode
293
294   It differs from AST_LIST_TRAVERSE() in that the code inside the loop can modify
295   (or even free, after calling AST_LIST_REMOVE_CURRENT()) the entry pointed to by
296   the \a current pointer without affecting the loop traversal.
297 */
298 #define AST_LIST_TRAVERSE_SAFE_BEGIN(head, var, field) {                                \
299         typeof((head)->first) __list_next;                                              \
300         typeof((head)->first) __list_prev = NULL;                                       \
301         for ((var) = (head)->first,  __list_next = (var) ? (var)->field.next : NULL;    \
302              (var);                                                                     \
303              __list_prev = (var), (var) = __list_next,                                  \
304              __list_next = (var) ? (var)->field.next : NULL                             \
305             )
306
307 /*!
308   \brief Removes the \a current entry from a list during a traversal.
309   \param head This is a pointer to the list head structure
310   \param field This is the name of the field (declared using AST_LIST_ENTRY())
311   used to link entries of this list together.
312
313   \note This macro can \b only be used inside an AST_LIST_TRAVERSE_SAFE_BEGIN()
314   block; it is used to unlink the current entry from the list without affecting
315   the list traversal (and without having to re-traverse the list to modify the
316   previous entry, if any).
317  */
318 #define AST_LIST_REMOVE_CURRENT(head, field)                                            \
319         if (__list_prev)                                                                \
320                 __list_prev->field.next = __list_next;                                  \
321         else                                                                            \
322                 (head)->first = __list_next;                                            \
323         if (!__list_next)                                                               \
324                 (head)->last = __list_prev;
325
326 /*!
327   \brief Inserts a list entry before the current entry during a traversal.
328   \param head This is a pointer to the list head structure
329   \param elm This is a pointer to the entry to be inserted.
330   \param field This is the name of the field (declared using AST_LIST_ENTRY())
331   used to link entries of this list together.
332
333   \note This macro can \b only be used inside an AST_LIST_TRAVERSE_SAFE_BEGIN()
334   block.
335  */
336 #define AST_LIST_INSERT_BEFORE_CURRENT(head, elm, field) do {           \
337         if (__list_prev) {                                              \
338                 (elm)->field.next = __list_prev->field.next;            \
339                 __list_prev->field.next = elm;                          \
340         } else {                                                        \
341                 (elm)->field.next = (head)->first;                      \
342                 (head)->first = (elm);                                  \
343         }                                                                               \
344 } while (0)
345
346 /*!
347   \brief Closes a safe loop traversal block.
348  */
349 #define AST_LIST_TRAVERSE_SAFE_END  }
350
351 /*!
352   \brief Initializes a list head structure.
353   \param head This is a pointer to the list head structure
354
355   This macro initializes a list head structure by setting the head
356   entry to \a NULL (empty list) and recreating the embedded lock.
357 */
358 #define AST_LIST_HEAD_INIT(head) {                                      \
359         (head)->first = NULL;                                           \
360         (head)->last = NULL;                                            \
361         ast_mutex_init(&(head)->lock);                                  \
362 }
363
364 /*!
365   \brief Destroys a list head structure.
366   \param head This is a pointer to the list head structure
367
368   This macro destroys a list head structure by setting the head
369   entry to \a NULL (empty list) and destroying the embedded lock.
370   It does not free the structure from memory.
371 */
372 #define AST_LIST_HEAD_DESTROY(head) {                                   \
373         (head)->first = NULL;                                           \
374         (head)->last = NULL;                                            \
375         ast_mutex_destroy(&(head)->lock);                               \
376 }
377
378 /*!
379   \brief Initializes a list head structure.
380   \param head This is a pointer to the list head structure
381
382   This macro initializes a list head structure by setting the head
383   entry to \a NULL (empty list) and recreating the embedded lock.
384 */
385 #define AST_LIST_HEAD_INIT_NOLOCK(head) {                               \
386         (head)->first = NULL;                                           \
387         (head)->last = NULL;                                            \
388 }
389
390 /*!
391   \brief Inserts a list entry after a given entry.
392   \param head This is a pointer to the list head structure
393   \param listelm This is a pointer to the entry after which the new entry should
394   be inserted.
395   \param elm This is a pointer to the entry to be inserted.
396   \param field This is the name of the field (declared using AST_LIST_ENTRY())
397   used to link entries of this list together.
398  */
399 #define AST_LIST_INSERT_AFTER(head, listelm, elm, field) do {           \
400         (elm)->field.next = (listelm)->field.next;                      \
401         (listelm)->field.next = (elm);                                  \
402         if ((head)->last == (listelm))                                  \
403                 (head)->last = (elm);                                   \
404 } while (0)
405
406 /*!
407   \brief Inserts a list entry at the head of a list.
408   \param head This is a pointer to the list head structure
409   \param elm This is a pointer to the entry to be inserted.
410   \param field This is the name of the field (declared using AST_LIST_ENTRY())
411   used to link entries of this list together.
412  */
413 #define AST_LIST_INSERT_HEAD(head, elm, field) do {                     \
414                 (elm)->field.next = (head)->first;                      \
415                 (head)->first = (elm);                                  \
416                 if (!(head)->last)                                      \
417                         (head)->last = (elm);                           \
418 } while (0)
419
420 /*!
421   \brief Appends a list entry to the tail of a list.
422   \param head This is a pointer to the list head structure
423   \param elm This is a pointer to the entry to be appended.
424   \param field This is the name of the field (declared using AST_LIST_ENTRY())
425   used to link entries of this list together.
426
427   Note: The link field in the appended entry is \b not modified, so if it is
428   actually the head of a list itself, the entire list will be appended
429   temporarily (until the next AST_LIST_INSERT_TAIL is performed).
430  */
431 #define AST_LIST_INSERT_TAIL(head, elm, field) do {                     \
432       if (!(head)->first) {                                             \
433                 (head)->first = (elm);                                  \
434                 (head)->last = (elm);                                   \
435       } else {                                                          \
436                 (head)->last->field.next = (elm);                       \
437                 (head)->last = (elm);                                   \
438       }                                                                 \
439 } while (0)
440
441 /*!
442   \brief Removes and returns the head entry from a list.
443   \param head This is a pointer to the list head structure
444   \param field This is the name of the field (declared using AST_LIST_ENTRY())
445   used to link entries of this list together.
446
447   Removes the head entry from the list, and returns a pointer to it.
448   This macro is safe to call on an empty list.
449  */
450 #define AST_LIST_REMOVE_HEAD(head, field) ({                            \
451                 typeof((head)->first) cur = (head)->first;              \
452                 if (cur) {                                              \
453                         (head)->first = cur->field.next;                \
454                         cur->field.next = NULL;                         \
455                         if ((head)->last == cur)                        \
456                                 (head)->last = NULL;                    \
457                 }                                                       \
458                 cur;                                                    \
459         })
460
461 /*!
462   \brief Removes a specific entry from 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 removed.
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   \warning The removed entry is \b not freed nor modified in any way.
468  */
469 #define AST_LIST_REMOVE(head, elm, field) do {                          \
470         if ((head)->first == (elm)) {                                   \
471                 (head)->first = (elm)->field.next;                      \
472                 if ((head)->last == (elm))                      \
473                         (head)->last = NULL;                    \
474         } else {                                                                \
475                 typeof(elm) curelm = (head)->first;                     \
476                 while (curelm->field.next != (elm))                     \
477                         curelm = curelm->field.next;                    \
478                 curelm->field.next = (elm)->field.next;                 \
479                 if ((head)->last == (elm))                              \
480                         (head)->last = curelm;                          \
481         }                                                               \
482 } while (0)
483
484 #endif /* _ASTERISK_LINKEDLISTS_H */