9bf3b90367b44bdb3307d2f0124361e2a9c6e11c
[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         ast_mutex_t lock;                                               \
75 }
76
77 /*!
78   \brief Defines a structure to be used to hold a list of specified type, statically initialized.
79   \param name This will be the name of the defined structure.
80   \param type This is the type of each list entry.
81
82   This macro creates a structure definition that can be used
83   to hold a list of the entries of type \a type, and allocates an instance
84   of it, initialized to be empty.
85
86   Example usage:
87   \code
88   static AST_LIST_HEAD_STATIC(entry_list, entry);
89   \endcode
90
91   This would define \c struct \c entry_list, intended to hold a list of
92   type \c struct \c entry.
93 */
94 #define AST_LIST_HEAD_STATIC(name, type)                                \
95 struct name {                                                           \
96         struct type *first;                                             \
97         ast_mutex_t lock;                                               \
98 } name = {                                                              \
99         .first = NULL,                                                  \
100         .lock = AST_MUTEX_INIT_VALUE,                                   \
101 };
102
103 /*!
104   \brief Initializes a list head structure with a specified first entry.
105   \param head This is a pointer to the list head structure
106   \param entry pointer to the list entry that will become the head of the list
107
108   This macro initializes a list head structure by setting the head
109   entry to the supplied value and recreating the embedded lock.
110 */
111 #define AST_LIST_HEAD_SET(head, entry) do {                             \
112         (head)->first=(entry);                                          \
113         ast_pthread_mutex_init(&(head)->lock,NULL);                             \
114 } while (0)
115
116 /*!
117   \brief Declare a forward link structure inside a list entry.
118   \param type This is the type of each list entry.
119
120   This macro declares a structure to be used to link list entries together.
121   It must be used inside the definition of the structure named in
122   \a type, as follows:
123
124   \code
125   struct list_entry {
126         ...
127         AST_LIST_ENTRY(list_entry) list;
128   }
129   \endcode
130
131   The field name \a list here is arbitrary, and can be anything you wish.
132 */
133 #define AST_LIST_ENTRY(type)                                            \
134 struct {                                                                \
135         struct type *next;                                              \
136 }
137  
138 /*!
139   \brief Returns the first entry contained in a list.
140   \param head This is a pointer to the list head structure
141  */
142 #define AST_LIST_FIRST(head)    ((head)->first)
143
144 /*!
145   \brief Returns the next entry in the list after the given entry.
146   \param elm This is a pointer to the current entry.
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 #define AST_LIST_NEXT(elm, field)       ((elm)->field.next)
151
152 /*!
153   \brief Checks whether the specified list contains any entries.
154   \param head This is a pointer to the list head structure
155
156   Returns non-zero if the list has entries, zero if not.
157  */
158 #define AST_LIST_EMPTY(head)    (AST_LIST_FIRST(head) == NULL)
159
160 /*!
161   \brief Loops over (traverses) the entries in a list.
162   \param head This is a pointer to the list head structure
163   \param var This is the name of the variable that will hold a pointer to the
164   current list entry on each iteration. It must be declared before calling
165   this macro.
166   \param field This is the name of the field (declared using AST_LIST_ENTRY())
167   used to link entries of this list together.
168
169   This macro is use to loop over (traverse) the entries in a list. It uses a
170   \a for loop, and supplies the enclosed code with a pointer to each list
171   entry as it loops. It is typically used as follows:
172   \code
173   static AST_LIST_HEAD(entry_list, list_entry) entries;
174   ...
175   struct list_entry {
176         ...
177         AST_LIST_ENTRY(list_entry) list;
178   }
179   ...
180   struct list_entry *current;
181   ...
182   AST_LIST_TRAVERSE(&entries, current, list) {
183      (do something with current here)
184   }
185   \endcode
186   \warning If you modify the forward-link pointer contained in the \a current entry while
187   inside the loop, the behavior will be unpredictable. At a minimum, the following
188   macros will modify the forward-link pointer, and should not be used inside
189   AST_LIST_TRAVERSE() against the entry pointed to by the \a current pointer without
190   careful consideration of their consequences:
191   \li AST_LIST_NEXT() (when used as an lvalue)
192   \li AST_LIST_INSERT_AFTER()
193   \li AST_LIST_INSERT_HEAD()
194   \li AST_LIST_INSERT_TAIL()
195 */
196 #define AST_LIST_TRAVERSE(head,var,field)                               \
197         for((var) = (head)->first; (var); (var) = (var)->field.next)
198
199 /*!
200   \brief Loops safely over (traverses) the entries in a list.
201   \param head This is a pointer to the list head structure
202   \param var This is the name of the variable that will hold a pointer to the
203   current list entry on each iteration. It must be declared before calling
204   this macro.
205   \param field This is the name of the field (declared using AST_LIST_ENTRY())
206   used to link entries of this list together.
207
208   This macro is used to safely loop over (traverse) the entries in a list. It
209   uses a \a for loop, and supplies the enclosed code with a pointer to each list
210   entry as it loops. It is typically used as follows:
211
212   \code
213   static AST_LIST_HEAD(entry_list, list_entry) entries;
214   ...
215   struct list_entry {
216         ...
217         AST_LIST_ENTRY(list_entry) list;
218   }
219   ...
220   struct list_entry *current;
221   ...
222   AST_LIST_TRAVERSE_SAFE_BEGIN(&entries, current, list) {
223      (do something with current here)
224   }
225   AST_LIST_TRAVERSE_SAFE_END;
226   \endcode
227
228   It differs from AST_LIST_TRAVERSE() in that the code inside the loop can modify
229   (or even free, after calling AST_LIST_REMOVE_CURRENT()) the entry pointed to by
230   the \a current pointer without affecting the loop traversal.
231 */
232 #define AST_LIST_TRAVERSE_SAFE_BEGIN(head, var, field) {                                \
233         typeof((head)->first) __list_next;                                              \
234         typeof((head)->first) __list_prev = NULL;                                       \
235         for ((var) = (head)->first,  __list_next = (var) ? (var)->field.next : NULL;    \
236              (var);                                                                     \
237              __list_prev = (var), (var) = __list_next,                                  \
238              __list_next = (var) ? (var)->field.next : NULL                             \
239             )
240
241 /*!
242   \brief Removes the \a current entry from a list during a traversal.
243   \param head This is a pointer to the list head structure
244   \param field This is the name of the field (declared using AST_LIST_ENTRY())
245   used to link entries of this list together.
246
247   \note This macro can \b only be used inside an AST_LIST_TRAVERSE_SAFE_BEGIN()
248   block; it is used to unlink the current entry from the list without affecting
249   the list traversal (and without having to re-traverse the list to modify the
250   previous entry, if any).
251  */
252 #define AST_LIST_REMOVE_CURRENT(head, field)                                            \
253         if (__list_prev)                                                                \
254                 __list_prev->field.next = __list_next;                                  \
255         else                                                                            \
256                 (head)->first = __list_next;
257
258 /*!
259   \brief Closes a safe loop traversal block.
260  */
261 #define AST_LIST_TRAVERSE_SAFE_END  }
262
263 /*!
264   \brief Initializes a list head structure.
265   \param head This is a pointer to the list head structure
266
267   This macro initializes a list head structure by setting the head
268   entry to \a NULL (empty list) and recreating the embedded lock.
269 */
270 #define AST_LIST_HEAD_INIT(head) {                                      \
271         (head)->first = NULL;                                           \
272         ast_pthread_mutex_init(&(head)->lock,NULL);                     \
273 }
274
275 /*!
276   \brief Inserts a list entry after a given entry.
277   \param listelm This is a pointer to the entry after which the new entry should
278   be inserted.
279   \param elm This is a pointer to the entry to be inserted.
280   \param field This is the name of the field (declared using AST_LIST_ENTRY())
281   used to link entries of this list together.
282  */
283 #define AST_LIST_INSERT_AFTER(listelm, elm, field) do {                 \
284         (elm)->field.next = (listelm)->field.next;                      \
285         (listelm)->field.next = (elm);                                  \
286 } while (0)
287
288 /*!
289   \brief Inserts a list entry at the head of a list.
290   \param head This is a pointer to the list head structure
291   \param elm This is a pointer to the entry to be inserted.
292   \param field This is the name of the field (declared using AST_LIST_ENTRY())
293   used to link entries of this list together.
294  */
295 #define AST_LIST_INSERT_HEAD(head, elm, field) do {                     \
296                 (elm)->field.next = (head)->first;                      \
297                 (head)->first = (elm);                                  \
298 } while (0)
299
300 /*!
301   \brief Appends a list entry to the tail of a list.
302   \param head This is a pointer to the list head structure
303   \param elm This is a pointer to the entry to be appended.
304   \param field This is the name of the field (declared using AST_LIST_ENTRY())
305   used to link entries of this list together.
306
307   Note: The link field in the appended entry is \b not modified, so if it is
308   actually the head of a list itself, the entire list will be appended.
309  */
310 #define AST_LIST_INSERT_TAIL(head, elm, field) do {                     \
311       if (!(head)->first) {                                             \
312               (head)->first = (elm);                                    \
313       } else {                                                          \
314               typeof(elm) curelm = (head)->first;                       \
315               while (curelm->field.next != NULL)                        \
316                       curelm = curelm->field.next;                      \
317               curelm->field.next = (elm);                               \
318       }                                                                 \
319 } while (0)
320
321 /*!
322   \brief Removes and returns the head entry from a list.
323   \param head This is a pointer to the list head structure
324   \param field This is the name of the field (declared using AST_LIST_ENTRY())
325   used to link entries of this list together.
326
327   Removes the head entry from the list, and returns a pointer to it.
328   This macro is safe to call on an empty list.
329  */
330 #define AST_LIST_REMOVE_HEAD(head, field) ({                            \
331                 typeof((head)->first) cur = (head)->first;              \
332                 if (cur) {                                              \
333                         (head)->first = cur->field.next;                \
334                         cur->field.next = NULL;                         \
335                 }                                                       \
336                 cur;                                                    \
337         })
338
339 /*!
340   \brief Removes a specific entry from a list.
341   \param head This is a pointer to the list head structure
342   \param elm This is a pointer to the entry to be removed.
343   \param field This is the name of the field (declared using AST_LIST_ENTRY())
344   used to link entries of this list together.
345   \warning The removed entry is \b not freed nor modified in any way.
346  */
347 #define AST_LIST_REMOVE(head, elm, field) do {                          \
348         if ((head)->first == (elm)) {                                   \
349                 (head)->first = (elm)->field.next;                      \
350         }                                                               \
351         else {                                                          \
352                 typeof(elm) curelm = (head)->first;                     \
353                 while (curelm->field.next != (elm))                     \
354                         curelm = curelm->field.next;                    \
355                 curelm->field.next = (elm)->field.next;                 \
356         }                                                               \
357 } while (0)
358
359 #endif /* _ASTERISK_LINKEDLISTS_H */