aboutsummaryrefslogtreecommitdiffstats
path: root/include/asterisk/linkedlists.h
blob: d90365920693432227cc35762b910aa56fd7f324 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
#ifndef ASTERISK_LINKEDLISTS_H
#define ASTERISK_LINKEDLISTS_H

#include "asterisk/lock.h"

/*!
  \file linkedlists.h
  \brief A set of macros to manage forward-linked lists.
*/

/*!
  \brief Attempts to lock a list.
  \param head This is a pointer to the list head structure

  This macro attempts to place an exclusive lock in the
  list head structure pointed to by head.
  Returns non-zero on success, 0 on failure
*/
#define AST_LIST_LOCK(head)						\
	ast_mutex_lock(&(head)->lock) 
	
/*!
  \brief Attempts to unlock a list.
  \param head This is a pointer to the list head structure

  This macro attempts to remove an exclusive lock from the
  list head structure pointed to by head. If the list
  was not locked by this thread, this macro has no effect.
*/
#define AST_LIST_UNLOCK(head) 						\
	ast_mutex_unlock(&(head)->lock)

/*!
  \brief Defines a structure to be used to hold a list of specified type.
  \param name This will be the name of the defined structure.
  \param type This is the type of each list entry.

  This macro creates a structure definition that can be used
  to hold a list of the entries of type \a type. It does not actually
  declare (allocate) a structure; to do that, either follow this
  macro with the desired name of the instance you wish to declare,
  or use the specified \a name to declare instances elsewhere.

  Example usage:
  \code
  static AST_LIST_HEAD(entry_list, entry) entries;
  \endcode

  This would define \c struct \c entry_list, and declare an instance of it named
  \a entries, all intended to hold a list of type \c struct \c entry.
*/
#define AST_LIST_HEAD(name, type)					\
struct name {								\
	struct type *first;						\
	ast_mutex_t lock;						\
}

/*!
  \brief Defines a structure to be used to hold a list of specified type, statically initialized.
  \param name This will be the name of the defined structure.
  \param type This is the type of each list entry.

  This macro creates a structure definition that can be used
  to hold a list of the entries of type \a type, and allocates an instance
  of it, initialized to be empty.

  Example usage:
  \code
  static AST_LIST_HEAD_STATIC(entry_list, entry) entries;
  \endcode

  This would define \c struct \c entry_list, and declare an instance of it named
  \a entries, all intended to hold a list of type \c struct \c entry.
*/
#define AST_LIST_HEAD_STATIC(name, type)				\
struct name {							\
	struct type *first;						\
	ast_mutex_t lock;						\
} name = {								\
	.first = NULL,							\
	.lock = AST_MUTEX_INIT_VALUE,					\
};

/*!
  \brief Initializes a list head structure with a specified first entry.
  \param head This is a pointer to the list head structure
  \param entry pointer to the list entry that will become the head of the list

  This macro initializes a list head structure by setting the head
  entry to the supplied value and recreating the embedded lock.
*/
#define AST_LIST_HEAD_SET(head, entry) do {				\
	(head)->first=(entry);						\
	ast_pthread_mutex_init(&(head)->lock,NULL);				\
} while (0)

/*!
  \brief Declare a forward link structure inside a list entry.
  \param type This is the type of each list entry.

  This macro declares a structure to be used to link list entries together.
  It must be used inside the definition of the structure named in
  \a type, as follows:

  \code
  struct list_entry {
  	...
  	AST_LIST_ENTRY(list_entry) list;
  }
  \endcode

  The field name \a list here is arbitrary, and can be anything you wish.
*/
#define AST_LIST_ENTRY(type)						\
struct {								\
	struct type *next;						\
}
 
/*!
  \brief Returns the first entry contained in a list.
  \param head This is a pointer to the list head structure
 */
#define	AST_LIST_FIRST(head)	((head)->first)

/*!
  \brief Returns the next entry in the list after the given entry.
  \param elm This is a pointer to the current entry.
  \param field This is the name of the field (declared using AST_LIST_ENTRY())
  used to link entries of this list together.
*/
#define AST_LIST_NEXT(elm, field)	((elm)->field.next)

/*!
  \brief Checks whether the specified list contains any entries.
  \param head This is a pointer to the list head structure

  Returns non-zero if the list has entries, zero if not.
 */
#define	AST_LIST_EMPTY(head)	(AST_LIST_FIRST(head) == NULL)

/*!
  \brief Loops over (traverses) the entries in a list.
  \param head This is a pointer to the list head structure
  \param var This is the name of the variable that will hold a pointer to the
  current list entry on each iteration. It must be declared before calling
  this macro.
  \param field This is the name of the field (declared using AST_LIST_ENTRY())
  used to link entries of this list together.

  This macro is use to loop over (traverse) the entries in a list. It uses a
  \a for loop, and supplies the enclosed code with a pointer to each list
  entry as it loops. It is typically used as follows:
  \code
  static AST_LIST_HEAD(entry_list, list_entry) entries;
  ...
  struct list_entry {
  	...
  	AST_LIST_ENTRY(list_entry) list;
  }
  ...
  struct list_entry *current;
  ...
  AST_LIST_TRAVERSE(&entries, current, list) {
     (do something with current here)
  }
  \endcode
  \warning If you modify the forward-link pointer contained in the \a current entry while
  inside the loop, the behavior will be unpredictable. At a minimum, the following
  macros will modify the forward-link pointer, and should not be used inside
  AST_LIST_TRAVERSE() against the entry pointed to by the \a current pointer without
  careful consideration of their consequences:
  \li AST_LIST_NEXT() (when used as an lvalue)
  \li AST_LIST_INSERT_AFTER()
  \li AST_LIST_INSERT_HEAD()
  \li AST_LIST_INSERT_TAIL()
*/
#define AST_LIST_TRAVERSE(head,var,field) 				\
	for((var) = (head)->first; (var); (var) = (var)->field.next)

/*!
  \brief Loops safely over (traverses) the entries in a list.
  \param head This is a pointer to the list head structure
  \param var This is the name of the variable that will hold a pointer to the
  current list entry on each iteration. It must be declared before calling
  this macro.
  \param field This is the name of the field (declared using AST_LIST_ENTRY())
  used to link entries of this list together.

  This macro is used to safely loop over (traverse) the entries in a list. It
  uses a \a for loop, and supplies the enclosed code with a pointer to each list
  entry as it loops. It is typically used as follows:

  \code
  static AST_LIST_HEAD(entry_list, list_entry) entries;
  ...
  struct list_entry {
  	...
  	AST_LIST_ENTRY(list_entry) list;
  }
  ...
  struct list_entry *current;
  ...
  AST_LIST_TRAVERSE_SAFE_BEGIN(&entries, current, list) {
     (do something with current here)
  }
  AST_LIST_TRAVERSE_SAFE_END;
  \endcode

  It differs from AST_LIST_TRAVERSE() in that the code inside the loop can modify
  (or even free, after calling AST_LIST_REMOVE_CURRENT()) the entry pointed to by
  the \a current pointer without affecting the loop traversal.
*/
#define AST_LIST_TRAVERSE_SAFE_BEGIN(head, var, field) {				\
	typeof((head)->first) __list_next;						\
	typeof((head)->first) __list_prev = NULL;					\
	for ((var) = (head)->first,  __list_next = (var) ? (var)->field.next : NULL;	\
	     (var);									\
	     __list_prev = (var), (var) = __list_next,					\
	     __list_next = (var) ? (var)->field.next : NULL				\
	    )

/*!
  \brief Removes the \a current entry from a list during a traversal.
  \param head This is a pointer to the list head structure
  \param field This is the name of the field (declared using AST_LIST_ENTRY())
  used to link entries of this list together.

  \note This macro can \b only be used inside an AST_LIST_TRAVERSE_SAFE_BEGIN()
  block; it is used to unlink the current entry from the list without affecting
  the list traversal (and without having to re-traverse the list to modify the
  previous entry, if any).
 */
#define AST_LIST_REMOVE_CURRENT(head, field)						\
	if (__list_prev)								\
		__list_prev->field.next = __list_next;					\
	else										\
		(head)->first = __list_next;

/*!
  \brief Closes a safe loop traversal block.
 */
#define AST_LIST_TRAVERSE_SAFE_END  }

/*!
  \brief Initializes a list head structure.
  \param head This is a pointer to the list head structure

  This macro initializes a list head structure by setting the head
  entry to \a NULL (empty list) and recreating the embedded lock.
*/
#define AST_LIST_HEAD_INIT(head) {					\
	(head)->first = NULL;						\
	ast_pthread_mutex_init(&(head)->lock,NULL);			\
}

/*!
  \brief Inserts a list entry after a given entry.
  \param listelm This is a pointer to the entry after which the new entry should
  be inserted.
  \param elm This is a pointer to the entry to be inserted.
  \param field This is the name of the field (declared using AST_LIST_ENTRY())
  used to link entries of this list together.
 */
#define AST_LIST_INSERT_AFTER(listelm, elm, field) do {			\
	(elm)->field.next = (listelm)->field.next;			\
	(listelm)->field.next = (elm);					\
} while (0)

/*!
  \brief Inserts a list entry at the head of a list.
  \param head This is a pointer to the list head structure
  \param elm This is a pointer to the entry to be inserted.
  \param field This is the name of the field (declared using AST_LIST_ENTRY())
  used to link entries of this list together.
 */
#define AST_LIST_INSERT_HEAD(head, elm, field) do {			\
		(elm)->field.next = (head)->first;			\
		(head)->first = (elm);					\
} while (0)

/*!
  \brief Appends a list entry to the tail of a list.
  \param head This is a pointer to the list head structure
  \param elm This is a pointer to the entry to be appended.
  \param field This is the name of the field (declared using AST_LIST_ENTRY())
  used to link entries of this list together.

  Note: The link field in the appended entry is \b not modified, so if it is
  actually the head of a list itself, the entire list will be appended.
 */
#define AST_LIST_INSERT_TAIL(head, elm, field) do {			\
      if (!(head)->first) {						\
              (head)->first = (elm);					\
      } else {								\
              typeof(elm) curelm = (head)->first;			\
              while (curelm->field.next != NULL)			\
                      curelm = curelm->field.next;			\
              curelm->field.next = (elm);				\
      }									\
} while (0)

/*!
  \brief Removes and returns the head entry from a list.
  \param head This is a pointer to the list head structure
  \param field This is the name of the field (declared using AST_LIST_ENTRY())
  used to link entries of this list together.

  Removes the head entry from the list, and returns a pointer to it. The
  forward-link pointer in the returned entry is \b not cleared.
 */
#define AST_LIST_REMOVE_HEAD(head, field) ({				\
		typeof((head)->first) cur = (head)->first;		\
		(head)->first = (head)->first->field.next;		\
		cur;							\
	})

/*!
  \brief Removes a specific entry from a list.
  \param head This is a pointer to the list head structure
  \param elm This is a pointer to the entry to be removed.
  \param field This is the name of the field (declared using AST_LIST_ENTRY())
  used to link entries of this list together.
  \warning The removed entry is \b not freed nor modified in any way.
 */
#define AST_LIST_REMOVE(head, elm, field) do {			        \
	if ((head)->first == (elm)) {					\
		(head)->first = (elm)->field.next;			\
	}								\
	else {								\
		typeof(elm) curelm = (head)->first;			\
		while (curelm->field.next != (elm))			\
			curelm = curelm->field.next;			\
		curelm->field.next = (elm)->field.next;			\
	}								\
} while (0)

#endif