bug in the linkedlists macros where the prev node
[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         typeof((head)->first) __new_prev = NULL;                                        \
302         for ((var) = (head)->first, __new_prev = (var),                                 \
303               __list_next = (var) ? (var)->field.next : NULL;                           \
304              (var);                                                                     \
305              __list_prev = __new_prev, (var) = __list_next,                             \
306              __list_next = (var) ? (var)->field.next : NULL                             \
307             )
308
309 /*!
310   \brief Removes the \a current entry from a list during a traversal.
311   \param head This is a pointer to the list head structure
312   \param field This is the name of the field (declared using AST_LIST_ENTRY())
313   used to link entries of this list together.
314
315   \note This macro can \b only be used inside an AST_LIST_TRAVERSE_SAFE_BEGIN()
316   block; it is used to unlink the current entry from the list without affecting
317   the list traversal (and without having to re-traverse the list to modify the
318   previous entry, if any).
319  */
320 #define AST_LIST_REMOVE_CURRENT(head, field)                                            \
321         __new_prev = __list_prev;                                                       \
322         if (__list_prev)                                                                \
323                 __list_prev->field.next = __list_next;                                  \
324         else                                                                            \
325                 (head)->first = __list_next;                                            \
326         if (!__list_next)                                                               \
327                 (head)->last = __list_prev;
328
329 /*!
330   \brief Inserts a list entry before the current entry during a traversal.
331   \param head This is a pointer to the list head structure
332   \param elm This is a pointer to the entry to be inserted.
333   \param field This is the name of the field (declared using AST_LIST_ENTRY())
334   used to link entries of this list together.
335
336   \note This macro can \b only be used inside an AST_LIST_TRAVERSE_SAFE_BEGIN()
337   block.
338  */
339 #define AST_LIST_INSERT_BEFORE_CURRENT(head, elm, field) do {           \
340         if (__list_prev) {                                              \
341                 (elm)->field.next = __list_prev->field.next;            \
342                 __list_prev->field.next = elm;                          \
343         } else {                                                        \
344                 (elm)->field.next = (head)->first;                      \
345                 (head)->first = (elm);                                  \
346         }                                                               \
347         __new_prev = (elm);                                             \
348 } while (0)
349
350 /*!
351   \brief Closes a safe loop traversal block.
352  */
353 #define AST_LIST_TRAVERSE_SAFE_END  }
354
355 /*!
356   \brief Initializes a list head structure.
357   \param head This is a pointer to the list head structure
358
359   This macro initializes a list head structure by setting the head
360   entry to \a NULL (empty list) and recreating the embedded lock.
361 */
362 #define AST_LIST_HEAD_INIT(head) {                                      \
363         (head)->first = NULL;                                           \
364         (head)->last = NULL;                                            \
365         ast_mutex_init(&(head)->lock);                                  \
366 }
367
368 /*!
369   \brief Destroys a list head structure.
370   \param head This is a pointer to the list head structure
371
372   This macro destroys a list head structure by setting the head
373   entry to \a NULL (empty list) and destroying the embedded lock.
374   It does not free the structure from memory.
375 */
376 #define AST_LIST_HEAD_DESTROY(head) {                                   \
377         (head)->first = NULL;                                           \
378         (head)->last = NULL;                                            \
379         ast_mutex_destroy(&(head)->lock);                               \
380 }
381
382 /*!
383   \brief Initializes a list head structure.
384   \param head This is a pointer to the list head structure
385
386   This macro initializes a list head structure by setting the head
387   entry to \a NULL (empty list) and recreating the embedded lock.
388 */
389 #define AST_LIST_HEAD_INIT_NOLOCK(head) {                               \
390         (head)->first = NULL;                                           \
391         (head)->last = NULL;                                            \
392 }
393
394 /*!
395   \brief Inserts a list entry after a given entry.
396   \param head This is a pointer to the list head structure
397   \param listelm This is a pointer to the entry after which the new entry should
398   be inserted.
399   \param elm This is a pointer to the entry to be inserted.
400   \param field This is the name of the field (declared using AST_LIST_ENTRY())
401   used to link entries of this list together.
402  */
403 #define AST_LIST_INSERT_AFTER(head, listelm, elm, field) do {           \
404         (elm)->field.next = (listelm)->field.next;                      \
405         (listelm)->field.next = (elm);                                  \
406         if ((head)->last == (listelm))                                  \
407                 (head)->last = (elm);                                   \
408 } while (0)
409
410 /*!
411   \brief Inserts a list entry at the head of a list.
412   \param head This is a pointer to the list head structure
413   \param elm This is a pointer to the entry to be inserted.
414   \param field This is the name of the field (declared using AST_LIST_ENTRY())
415   used to link entries of this list together.
416  */
417 #define AST_LIST_INSERT_HEAD(head, elm, field) do {                     \
418                 (elm)->field.next = (head)->first;                      \
419                 (head)->first = (elm);                                  \
420                 if (!(head)->last)                                      \
421                         (head)->last = (elm);                           \
422 } while (0)
423
424 /*!
425   \brief Appends a list entry to the tail of a list.
426   \param head This is a pointer to the list head structure
427   \param elm This is a pointer to the entry to be appended.
428   \param field This is the name of the field (declared using AST_LIST_ENTRY())
429   used to link entries of this list together.
430
431   Note: The link field in the appended entry is \b not modified, so if it is
432   actually the head of a list itself, the entire list will be appended
433   temporarily (until the next AST_LIST_INSERT_TAIL is performed).
434  */
435 #define AST_LIST_INSERT_TAIL(head, elm, field) do {                     \
436       if (!(head)->first) {                                             \
437                 (head)->first = (elm);                                  \
438                 (head)->last = (elm);                                   \
439       } else {                                                          \
440                 (head)->last->field.next = (elm);                       \
441                 (head)->last = (elm);                                   \
442       }                                                                 \
443 } while (0)
444
445 /*!
446   \brief Removes and returns the head entry from a list.
447   \param head This is a pointer to the list head structure
448   \param field This is the name of the field (declared using AST_LIST_ENTRY())
449   used to link entries of this list together.
450
451   Removes the head entry from the list, and returns a pointer to it.
452   This macro is safe to call on an empty list.
453  */
454 #define AST_LIST_REMOVE_HEAD(head, field) ({                            \
455                 typeof((head)->first) cur = (head)->first;              \
456                 if (cur) {                                              \
457                         (head)->first = cur->field.next;                \
458                         cur->field.next = NULL;                         \
459                         if ((head)->last == cur)                        \
460                                 (head)->last = NULL;                    \
461                 }                                                       \
462                 cur;                                                    \
463         })
464
465 /*!
466   \brief Removes a specific entry from a list.
467   \param head This is a pointer to the list head structure
468   \param elm This is a pointer to the entry to be removed.
469   \param field This is the name of the field (declared using AST_LIST_ENTRY())
470   used to link entries of this list together.
471   \warning The removed entry is \b not freed nor modified in any way.
472  */
473 #define AST_LIST_REMOVE(head, elm, field) do {                          \
474         if ((head)->first == (elm)) {                                   \
475                 (head)->first = (elm)->field.next;                      \
476                 if ((head)->last == (elm))                      \
477                         (head)->last = NULL;                    \
478         } else {                                                                \
479                 typeof(elm) curelm = (head)->first;                     \
480                 while (curelm->field.next != (elm))                     \
481                         curelm = curelm->field.next;                    \
482                 curelm->field.next = (elm)->field.next;                 \
483                 if ((head)->last == (elm))                              \
484                         (head)->last = curelm;                          \
485         }                                                               \
486 } while (0)
487
488 #endif /* _ASTERISK_LINKEDLISTS_H */