List improvements from kpfleming (bugs #3166,#3140)
[asterisk/asterisk.git] / include / asterisk / linkedlists.h
1 #ifndef ASTERISK_LINKEDLISTS_H
2 #define ASTERISK_LINKEDLISTS_H
3
4 #include <asterisk/lock.h>
5
6 /*!
7   \file linkedlists.h
8   \brief A set of macros to manage forward-linked lists.
9 */
10
11 /*!
12   \brief Attempts to lock a list.
13   \param head This is a pointer to the list head structure
14
15   This macro attempts to place an exclusive lock in the
16   list head structure pointed to by head.
17   Returns non-zero on success, 0 on failure
18 */
19 #define AST_LIST_LOCK(head)                                             \
20         ast_mutex_lock(&(head)->lock) 
21         
22 /*!
23   \brief Attempts to unlock a list.
24   \param head This is a pointer to the list head structure
25
26   This macro attempts to remove an exclusive lock from the
27   list head structure pointed to by head. If the list
28   was not locked by this thread, this macro has no effect.
29 */
30 #define AST_LIST_UNLOCK(head)                                           \
31         ast_mutex_unlock(&(head)->lock)
32
33 /*!
34   \brief Defines a structure to be used to hold a list of specified type.
35   \param name This will be the name of the defined structure.
36   \param type This is the type of each list entry.
37
38   This macro creates a structure definition that can be used
39   to hold a list of the entries of type \a type. It does not actually
40   declare (allocate) a structure; to do that, either follow this
41   macro with the desired name of the instance you wish to declare,
42   or use the specified \a name to declare instances elsewhere. It is
43   frequently used as follows:
44   \code
45   static AST_LIST_HEAD(entry_list, entry) entries;
46   \endcode
47   This would define \a struct \a entry_list, and declare an instance of it named
48   \a entries, all intended to hold a list of type \a struct \a entry.
49 */
50 #define AST_LIST_HEAD(name, type)                                       \
51 struct name {                                                           \
52         struct type *first;                                             \
53         ast_mutex_t lock;                                               \
54 }
55
56 /*!
57   \brief Initializes a list head structure with a specified first entry.
58   \param head This is a pointer to the list head structure
59   \param entry pointer to the list entry that will become the head of the list
60
61   This macro initializes a list head structure by setting the head
62   entry to the supplied value and recreating the embedded lock.
63 */
64 #define AST_LIST_HEAD_SET(head,entry) do {                              \
65         (head)->first=(entry);                                          \
66         ast_pthread_mutex_init(&(head)->lock,NULL);                             \
67 } while (0)
68
69 /*!
70   \brief Declare a forward link structure inside a list entry.
71   \param type This is the type of each list entry.
72
73   This macro declares a structure to be used to link list entries together.
74   It must be used inside the definition of the structure named in
75   \a type, as follows:
76   \code
77   struct list_entry {
78         ...
79         AST_LIST_ENTRY(list_entry) list;
80   }
81   \endcode
82   The field name \a list here is arbitrary, and can be anything you wish.
83 */
84 #define AST_LIST_ENTRY(type)                                            \
85 struct {                                                                \
86         struct type *next;                                              \
87 }
88  
89 /*!
90   \brief Returns the first entry contained in a list.
91   \param head This is a pointer to the list head structure
92  */
93 #define AST_LIST_FIRST(head)    ((head)->first)
94
95 /*!
96   \brief Returns the next entry in the list after the given entry.
97   \param elm This is a pointer to the current entry.
98   \param field This is the name of the field (declared using AST_LIST_ENTRY())
99   used to link entries of this list together.
100 */
101 #define AST_LIST_NEXT(elm, field)       ((elm)->field.next)
102
103 /*!
104   \brief Checks whether the specified list contains any entries.
105   \param head This is a pointer to the list head structure
106
107   Returns non-zero if the list has entries, zero if not.
108  */
109 #define AST_LIST_EMPTY(head)    (AST_LIST_FIRST(head) == NULL)
110
111 /*!
112   \brief Loops over (traverses) the entries in a list.
113   \param head This is a pointer to the list head structure
114   \param var This is the name of the variable that will hold a pointer to the
115   current list entry on each iteration. It must be declared before calling
116   this macro.
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   This macro is use to loop over (traverse) the entries in a list. It uses a
121   \a for loop, and supplies the enclosed code with a pointer to each list
122   entry as it loops. It is typically used as follows:
123   \code
124   static AST_LIST_HEAD(entry_list, list_entry) entries;
125   ...
126   struct list_entry {
127         ...
128         AST_LIST_ENTRY(list_entry) list;
129   }
130   ...
131   struct list_entry *current;
132   ...
133   AST_LIST_TRAVERSE(&entries, current, list) {
134      (do something with current here)
135   }
136   \endcode
137   \warning If you modify the forward-link pointer contained in the \a current entry while
138   inside the loop, the behavior will be unpredictable. At a minimum, the following
139   macros will modify the forward-link pointer, and should not be used inside
140   AST_LIST_TRAVERSE() against the entry pointed to by the \a current pointer without
141   careful consideration of their consequences:
142   \li AST_LIST_NEXT() (when used as an lvalue)
143   \li AST_LIST_INSERT_AFTER()
144   \li AST_LIST_INSERT_HEAD()
145   \li AST_LIST_INSERT_TAIL()
146 */
147 #define AST_LIST_TRAVERSE(head,var,field)                               \
148         for((var) = (head)->first; (var); (var) = (var)->field.next)
149
150 /*!
151   \brief Loops safely over (traverses) the entries in a list.
152   \param head This is a pointer to the list head structure
153   \param var This is the name of the variable that will hold a pointer to the
154   current list entry on each iteration. It must be declared before calling
155   this macro.
156   \param field This is the name of the field (declared using AST_LIST_ENTRY())
157   used to link entries of this list together.
158
159   This macro is used to safely loop over (traverse) the entries in a list. It
160   uses a \a for loop, and supplies the enclosed code with a pointer to each list
161   entry as it loops. It is typically used as follows:
162   \code
163   static AST_LIST_HEAD(entry_list, list_entry) entries;
164   ...
165   struct list_entry {
166         ...
167         AST_LIST_ENTRY(list_entry) list;
168   }
169   ...
170   struct list_entry *current;
171   ...
172   AST_LIST_TRAVERSE_SAFE_BEGIN(&entries, current, list_entry, list) {
173      (do something with current here)
174   }
175   AST_LIST_TRAVERSE_SAFE_END
176   \endcode
177
178   It differs from AST_LIST_TRAVERSE in that the code inside the loop can modify
179   (or even free) the entry pointed to by the \a current pointer without affecting
180   the loop traversal.
181 */
182 #define AST_LIST_TRAVERSE_SAFE_BEGIN(head, var, field) {                                \
183         typeof((head)->first) __list_next;                                              \
184         for ((var) = (head)->first,  __list_next = (var) ? (var)->field.next : NULL;    \
185              (var);                                                                     \
186              (var) = __list_next,  __list_next = (var) ? (var)->field.next : NULL       \
187             )
188
189 /*!
190   \brief Closes a safe loop traversal block.
191  */
192 #define AST_LIST_TRAVERSE_SAFE_END  }
193
194 /*!
195   \brief Initializes a list head structure.
196   \param head This is a pointer to the list head structure
197
198   This macro initializes a list head structure by setting the head
199   entry to \a NULL (empty list) and recreating the embedded lock.
200 */
201 #define AST_LIST_HEAD_INIT(head) {                                              \
202         (head)->first = NULL;                                           \
203         ast_pthread_mutex_init(&(head)->lock,NULL);                             \
204 }
205
206 /*!
207   \brief Inserts a list entry after a given entry.
208   \param listelm This is a pointer to the entry after which the new entry should
209   be inserted.
210   \param elm This is a pointer to the entry to be inserted.
211   \param field This is the name of the field (declared using AST_LIST_ENTRY())
212   used to link entries of this list together.
213  */
214 #define AST_LIST_INSERT_AFTER(listelm, elm, field) do {         \
215         (elm)->field.next = (listelm)->field.next;                      \
216         (listelm)->field.next = (elm);                          \
217 } while (0)
218
219 /*!
220   \brief Inserts a list entry at the head of a list.
221   \param head This is a pointer to the list head structure
222   \param elm This is a pointer to the entry to be inserted.
223   \param field This is the name of the field (declared using AST_LIST_ENTRY())
224   used to link entries of this list together.
225  */
226 #define AST_LIST_INSERT_HEAD(head, elm, field) do {                     \
227                 (elm)->field.next = (head)->first;                      \
228                 (head)->first = (elm);                                  \
229 } while (0)
230
231 /*!
232   \brief Inserts a list entry at the tail of a list.
233   \param head This is a pointer to the list head structure
234   \param elm This is a pointer to the entry to be inserted.
235   \param field This is the name of the field (declared using AST_LIST_ENTRY())
236   used to link entries of this list together.
237  */
238 #define AST_LIST_INSERT_TAIL(head, elm, field) do {                   \
239       typeof(elm) curelm = (head)->first;                             \
240       if (!curelm) {                                                  \
241               AST_LIST_INSERT_HEAD(head, elm, field);                 \
242       } else {                                                        \
243               while (curelm->field.next!=NULL) {                      \
244                       curelm=curelm->field.next;                      \
245               }                                                       \
246               AST_LIST_INSERT_AFTER(curelm, elm, field);              \
247       }                                                               \
248 } while (0)
249
250 /*!
251   \brief Removes and returns the head entry from a list.
252   \param head This is a pointer to the list head structure
253   \param field This is the name of the field (declared using AST_LIST_ENTRY())
254   used to link entries of this list together.
255
256   Removes the head entry from the list, and returns a pointer to it. The
257   forward-link pointer in the returned entry is \b not cleared.
258  */
259 #define AST_LIST_REMOVE_HEAD(head, field) ({                                    \
260                 typeof((head)->first) cur = (head)->first;                      \
261                 (head)->first = (head)->first->field.next;                      \
262                 cur;                                                            \
263         })
264
265 /*!
266   \brief Removes a specific entry from a list.
267   \param head This is a pointer to the list head structure
268   \param elm This is a pointer to the entry to be removed.
269   \param field This is the name of the field (declared using AST_LIST_ENTRY())
270   used to link entries of this list together.
271   \warning The removed entry is \b not freed nor modified in any way.
272  */
273 #define AST_LIST_REMOVE(head, elm, field) do {                          \
274         if ((head)->first == (elm)) {                                   \
275                 AST_LIST_REMOVE_HEAD((head), field);                    \
276         }                                                               \
277         else {                                                          \
278                 typeof(elm) curelm = (head)->first;                     \
279                 while( curelm->field.next != (elm) )                    \
280                         curelm = curelm->field.next;                    \
281                 curelm->field.next =                                    \
282                     curelm->field.next->field.next;                     \
283         }                                                               \
284 } while (0)
285
286 #endif