1/*
2 * libwebsockets - small server side websockets and web server implementation
3 *
4 * Copyright (C) 2010 - 2019 Andy Green <andy@warmcat.com>
5 *
6 * Permission is hereby granted, free of charge, to any person obtaining a copy
7 * of this software and associated documentation files (the "Software"), to
8 * deal in the Software without restriction, including without limitation the
9 * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
10 * sell copies of the Software, and to permit persons to whom the Software is
11 * furnished to do so, subject to the following conditions:
12 *
13 * The above copyright notice and this permission notice shall be included in
14 * all copies or substantial portions of the Software.
15 *
16 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
19 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
21 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
22 * IN THE SOFTWARE.
23 */
24
25/** \defgroup ll linked-lists
26* ##Linked list apis
27*
28* simple single and doubly-linked lists
29*/
30///@{
31
32/**
33 * lws_start_foreach_ll(): linkedlist iterator helper start
34 *
35 * \param type: type of iteration, eg, struct xyz *
36 * \param it: iterator var name to create
37 * \param start: start of list
38 *
39 * This helper creates an iterator and starts a while (it) {
40 * loop. The iterator runs through the linked list starting at start and
41 * ends when it gets a NULL.
42 * The while loop should be terminated using lws_start_foreach_ll().
43 *
44 * Notice you can't use continue; to go around this iterator. You must
45 * goto a label placed at the lws_end_foreach_ll().
46 */
47#define lws_start_foreach_ll(type, it, start)\
48{ \
49 type it = start; \
50 while (it) {
51
52/**
53 * lws_end_foreach_ll(): linkedlist iterator helper end
54 *
55 * \param it: same iterator var name given when starting
56 * \param nxt: member name in the iterator pointing to next list element
57 *
58 * This helper is the partner for lws_start_foreach_ll() that ends the
59 * while loop.
60 *
61 * Notice you can't use continue; to go around this iterator. You must
62 * goto a label placed at the lws_end_foreach_ll().
63 */
64
65#define lws_end_foreach_ll(it, nxt) \
66 it = it->nxt; \
67 } \
68}
69
70/**
71 * lws_start_foreach_ll_safe(): linkedlist iterator helper start safe against delete
72 *
73 * \param type: type of iteration, eg, struct xyz *
74 * \param it: iterator var name to create
75 * \param start: start of list
76 * \param nxt: member name in the iterator pointing to next list element
77 *
78 * This helper creates an iterator and starts a while (it) {
79 * loop. The iterator runs through the linked list starting at start and
80 * ends when it gets a NULL.
81 * The while loop should be terminated using lws_end_foreach_ll_safe().
82 * Performs storage of next increment for situations where iterator can become invalidated
83 * during iteration.
84 *
85 * Notice you can't use continue; to go around this iterator. You must
86 * goto a label placed at the lws_end_foreach_ll_safe().
87 */
88#define lws_start_foreach_ll_safe(type, it, start, nxt)\
89{ \
90 type it = start; \
91 while (it) { \
92 type next_##it = it->nxt;
93
94/**
95 * lws_end_foreach_ll_safe(): linkedlist iterator helper end (pre increment storage)
96 *
97 * \param it: same iterator var name given when starting
98 *
99 * This helper is the partner for lws_start_foreach_ll_safe() that ends the
100 * while loop. It uses the precreated next_ variable already stored during
101 * start.
102 *
103 * Notice you can't use continue; to go around this iterator. You must
104 * goto a label placed at the lws_end_foreach_ll_safe().
105 */
106
107#define lws_end_foreach_ll_safe(it) \
108 it = next_##it; \
109 } \
110}
111
112/**
113 * lws_start_foreach_llp(): linkedlist pointer iterator helper start
114 *
115 * \param type: type of iteration, eg, struct xyz **
116 * \param it: iterator var name to create
117 * \param start: start of list
118 *
119 * This helper creates an iterator and starts a while (it) {
120 * loop. The iterator runs through the linked list starting at the
121 * address of start and ends when it gets a NULL.
122 * The while loop should be terminated using lws_start_foreach_llp().
123 *
124 * This helper variant iterates using a pointer to the previous linked-list
125 * element. That allows you to easily delete list members by rewriting the
126 * previous pointer to the element's next pointer.
127 *
128 * Notice you can't use continue; to go around this iterator. You must
129 * goto a label placed at the lws_end_foreach_llp() / ..._safe().
130 */
131#define lws_start_foreach_llp(type, it, start)\
132{ \
133 type it = &(start); \
134 while (*(it)) {
135
136#define lws_start_foreach_llp_safe(type, it, start, nxt)\
137{ \
138 type it = &(start); \
139 type next; \
140 while (*(it)) { \
141 next = &((*(it))->nxt); \
142
143/**
144 * lws_end_foreach_llp(): linkedlist pointer iterator helper end
145 *
146 * \param it: same iterator var name given when starting
147 * \param nxt: member name in the iterator pointing to next list element
148 *
149 * This helper is the partner for lws_start_foreach_llp() that ends the
150 * while loop.
151 *
152 * Notice you can't use continue; to go around this iterator. You must
153 * goto a label placed at the lws_end_foreach_llp() / ..._safe().
154 */
155
156#define lws_end_foreach_llp(it, nxt) \
157 it = &(*(it))->nxt; \
158 } \
159}
160
161#define lws_end_foreach_llp_safe(it) \
162 it = next; \
163 } \
164}
165
166#define lws_ll_fwd_insert(\
167 ___new_object, /* pointer to new object */ \
168 ___m_list, /* member for next list object ptr */ \
169 ___list_head /* list head */ \
170 ) {\
171 ___new_object->___m_list = ___list_head; \
172 ___list_head = ___new_object; \
173 }
174
175#define lws_ll_fwd_remove(\
176 ___type, /* type of listed object */ \
177 ___m_list, /* member for next list object ptr */ \
178 ___target, /* object to remove from list */ \
179 ___list_head /* list head */ \
180 ) { \
181 lws_start_foreach_llp(___type **, ___ppss, ___list_head) { \
182 if (*___ppss == ___target) { \
183 *___ppss = ___target->___m_list; \
184 break; \
185 } \
186 } lws_end_foreach_llp(___ppss, ___m_list); \
187 }
188
189
190/*
191 * doubly linked-list
192 */
193
194/*
195 * lws_dll2_owner / lws_dll2 : more capable version of lws_dll. Differences:
196 *
197 * - there's an explicit lws_dll2_owner struct which holds head, tail and
198 * count of members.
199 *
200 * - list members all hold a pointer to their owner. So user code does not
201 * have to track anything about exactly what lws_dll2_owner list the object
202 * is a member of.
203 *
204 * - you can use lws_dll unless you want the member count or the ability to
205 * not track exactly which list it's on.
206 *
207 * - layout is compatible with lws_dll (but lws_dll apis will not update the
208 * new stuff)
209 */
210
211
212struct lws_dll2;
213struct lws_dll2_owner;
214
215typedef struct lws_dll2 {
216 struct lws_dll2 *prev;
217 struct lws_dll2 *next;
218 struct lws_dll2_owner *owner;
219} lws_dll2_t;
220
221typedef struct lws_dll2_owner {
222 struct lws_dll2 *tail;
223 struct lws_dll2 *head;
224
225 uint32_t count;
226} lws_dll2_owner_t;
227
228LWS_VISIBLE LWS_EXTERN int
229lws_dll2_is_detached(const struct lws_dll2 *d);
230
231static LWS_INLINE const struct lws_dll2_owner *
232lws_dll2_owner(const struct lws_dll2 *d) { return d->owner; }
233
234static LWS_INLINE struct lws_dll2 *
235lws_dll2_get_head(struct lws_dll2_owner *owner) { return owner->head; }
236
237static LWS_INLINE struct lws_dll2 *
238lws_dll2_get_tail(struct lws_dll2_owner *owner) { return owner->tail; }
239
240LWS_VISIBLE LWS_EXTERN void
241lws_dll2_add_head(struct lws_dll2 *d, struct lws_dll2_owner *owner);
242
243LWS_VISIBLE LWS_EXTERN void
244lws_dll2_add_tail(struct lws_dll2 *d, struct lws_dll2_owner *owner);
245
246LWS_VISIBLE LWS_EXTERN void
247lws_dll2_remove(struct lws_dll2 *d);
248
249typedef int (*lws_dll2_foreach_cb_t)(struct lws_dll2 *d, void *user);
250
251LWS_VISIBLE LWS_EXTERN int
252lws_dll2_foreach_safe(struct lws_dll2_owner *owner, void *user,
253 lws_dll2_foreach_cb_t cb);
254
255LWS_VISIBLE LWS_EXTERN void
256lws_dll2_clear(struct lws_dll2 *d);
257
258LWS_VISIBLE LWS_EXTERN void
259lws_dll2_owner_clear(struct lws_dll2_owner *d);
260
261LWS_VISIBLE LWS_EXTERN void
262lws_dll2_add_before(struct lws_dll2 *d, struct lws_dll2 *after);
263
264LWS_VISIBLE LWS_EXTERN void
265lws_dll2_add_insert(struct lws_dll2 *d, struct lws_dll2 *prev);
266
267LWS_VISIBLE LWS_EXTERN void
268lws_dll2_add_sorted(lws_dll2_t *d, lws_dll2_owner_t *own,
269 int (*compare)(const lws_dll2_t *d, const lws_dll2_t *i));
270
271LWS_VISIBLE LWS_EXTERN void
272lws_dll2_add_sorted_priv(lws_dll2_t *d, lws_dll2_owner_t *own, void *priv,
273 int (*compare3)(void *priv, const lws_dll2_t *d,
274 const lws_dll2_t *i));
275
276LWS_VISIBLE LWS_EXTERN void *
277_lws_dll2_search_sz_pl(lws_dll2_owner_t *own, const char *name, size_t namelen,
278 size_t dll2_ofs, size_t ptr_ofs);
279
280/*
281 * Searches objects in an owner list linearly and returns one with a given
282 * member C-string matching a supplied length-provided string if it exists, else
283 * NULL.
284 */
285
286#define lws_dll2_search_sz_pl(own, name, namelen, type, membd2list, membptr) \
287 ((type *)_lws_dll2_search_sz_pl(own, name, namelen, \
288 offsetof(type, membd2list), \
289 offsetof(type, membptr)))
290
291#if defined(_DEBUG)
292void
293lws_dll2_describe(struct lws_dll2_owner *owner, const char *desc);
294#else
295#define lws_dll2_describe(x, y)
296#endif
297
298/*
299 * these are safe against the current container object getting deleted,
300 * since the hold his next in a temp and go to that next. ___tmp is
301 * the temp.
302 */
303
304#define lws_start_foreach_dll_safe(___type, ___it, ___tmp, ___start) \
305{ \
306 ___type ___it = ___start; \
307 while (___it) { \
308 ___type ___tmp = (___it)->next;
309
310#define lws_end_foreach_dll_safe(___it, ___tmp) \
311 ___it = ___tmp; \
312 } \
313}
314
315#define lws_start_foreach_dll(___type, ___it, ___start) \
316{ \
317 ___type ___it = ___start; \
318 while (___it) {
319
320#define lws_end_foreach_dll(___it) \
321 ___it = (___it)->next; \
322 } \
323}
324
325///@}
326
327