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