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 #define lws_start_foreach_ll(type, it, start)\
45 { \
46 type it = start; \
47 while (it) {
48
49 /**
50 * lws_end_foreach_ll(): linkedlist iterator helper end
51 *
52 * \param it: same iterator var name given when starting
53 * \param nxt: member name in the iterator pointing to next list element
54 *
55 * This helper is the partner for lws_start_foreach_ll() that ends the
56 * while loop.
57 */
58
59 #define lws_end_foreach_ll(it, nxt) \
60 it = it->nxt; \
61 } \
62 }
63
64 /**
65 * lws_start_foreach_ll_safe(): linkedlist iterator helper start safe against delete
66 *
67 * \param type: type of iteration, eg, struct xyz *
68 * \param it: iterator var name to create
69 * \param start: start of list
70 * \param nxt: member name in the iterator pointing to next list element
71 *
72 * This helper creates an iterator and starts a while (it) {
73 * loop. The iterator runs through the linked list starting at start and
74 * ends when it gets a NULL.
75 * The while loop should be terminated using lws_end_foreach_ll_safe().
76 * Performs storage of next increment for situations where iterator can become invalidated
77 * during iteration.
78 */
79 #define lws_start_foreach_ll_safe(type, it, start, nxt)\
80 { \
81 type it = start; \
82 while (it) { \
83 type next_##it = it->nxt;
84
85 /**
86 * lws_end_foreach_ll_safe(): linkedlist iterator helper end (pre increment storage)
87 *
88 * \param it: same iterator var name given when starting
89 *
90 * This helper is the partner for lws_start_foreach_ll_safe() that ends the
91 * while loop. It uses the precreated next_ variable already stored during
92 * start.
93 */
94
95 #define lws_end_foreach_ll_safe(it) \
96 it = next_##it; \
97 } \
98 }
99
100 /**
101 * lws_start_foreach_llp(): linkedlist pointer iterator helper start
102 *
103 * \param type: type of iteration, eg, struct xyz **
104 * \param it: iterator var name to create
105 * \param start: start of list
106 *
107 * This helper creates an iterator and starts a while (it) {
108 * loop. The iterator runs through the linked list starting at the
109 * address of start and ends when it gets a NULL.
110 * The while loop should be terminated using lws_start_foreach_llp().
111 *
112 * This helper variant iterates using a pointer to the previous linked-list
113 * element. That allows you to easily delete list members by rewriting the
114 * previous pointer to the element's next pointer.
115 */
116 #define lws_start_foreach_llp(type, it, start)\
117 { \
118 type it = &(start); \
119 while (*(it)) {
120
121 #define lws_start_foreach_llp_safe(type, it, start, nxt)\
122 { \
123 type it = &(start); \
124 type next; \
125 while (*(it)) { \
126 next = &((*(it))->nxt); \
127
128 /**
129 * lws_end_foreach_llp(): linkedlist pointer iterator helper end
130 *
131 * \param it: same iterator var name given when starting
132 * \param nxt: member name in the iterator pointing to next list element
133 *
134 * This helper is the partner for lws_start_foreach_llp() that ends the
135 * while loop.
136 */
137
138 #define lws_end_foreach_llp(it, nxt) \
139 it = &(*(it))->nxt; \
140 } \
141 }
142
143 #define lws_end_foreach_llp_safe(it) \
144 it = next; \
145 } \
146 }
147
148 #define lws_ll_fwd_insert(\
149 ___new_object, /* pointer to new object */ \
150 ___m_list, /* member for next list object ptr */ \
151 ___list_head /* list head */ \
152 ) {\
153 ___new_object->___m_list = ___list_head; \
154 ___list_head = ___new_object; \
155 }
156
157 #define lws_ll_fwd_remove(\
158 ___type, /* type of listed object */ \
159 ___m_list, /* member for next list object ptr */ \
160 ___target, /* object to remove from list */ \
161 ___list_head /* list head */ \
162 ) { \
163 lws_start_foreach_llp(___type **, ___ppss, ___list_head) { \
164 if (*___ppss == ___target) { \
165 *___ppss = ___target->___m_list; \
166 break; \
167 } \
168 } lws_end_foreach_llp(___ppss, ___m_list); \
169 }
170
171
172 /*
173 * doubly linked-list
174 */
175
176 #if defined (LWS_WITH_DEPRECATED_LWS_DLL)
177
178 /*
179 * This is going away in v4.1. You can set the cmake option above to keep it
180 * around temporarily. Migrate your stuff to the more capable and robust
181 * lws_dll2 below
182 */
183
184 struct lws_dll {
185 struct lws_dll *prev;
186 struct lws_dll *next;
187 };
188
189 /*
190 * these all point to the composed list objects... you have to use the
191 * lws_container_of() helper to recover the start of the containing struct
192 */
193
194 #define lws_dll_add_front lws_dll_add_head
195
196 LWS_VISIBLE LWS_EXTERN void
197 lws_dll_add_head(struct lws_dll *d, struct lws_dll *phead);
198
199 LWS_VISIBLE LWS_EXTERN void
200 lws_dll_add_tail(struct lws_dll *d, struct lws_dll *phead);
201
202 LWS_VISIBLE LWS_EXTERN void
203 lws_dll_insert(struct lws_dll *d, struct lws_dll *target,
204 struct lws_dll *phead, int before);
205
206 static LWS_INLINE struct lws_dll *
lws_dll_get_head(struct lws_dll * phead)207 lws_dll_get_head(struct lws_dll *phead) { return phead->next; }
208
209 static LWS_INLINE struct lws_dll *
lws_dll_get_tail(struct lws_dll * phead)210 lws_dll_get_tail(struct lws_dll *phead) { return phead->prev; }
211
212 /*
213 * caution, this doesn't track the tail in the head struct. Use
214 * lws_dll_remove_track_tail() instead of this if you want tail tracking. Using
215 * this means you can't use lws_dll_add_tail() amd
216 */
217 LWS_VISIBLE LWS_EXTERN void
218 lws_dll_remove(struct lws_dll *d) LWS_WARN_DEPRECATED;
219
220 LWS_VISIBLE LWS_EXTERN void
221 lws_dll_remove_track_tail(struct lws_dll *d, struct lws_dll *phead);
222
223 /* another way to do lws_start_foreach_dll_safe() on a list via a cb */
224
225 LWS_VISIBLE LWS_EXTERN int
226 lws_dll_foreach_safe(struct lws_dll *phead, void *user,
227 int (*cb)(struct lws_dll *d, void *user));
228
229 #define lws_dll_is_detached(___dll, __head) \
230 (!(___dll)->prev && !(___dll)->next && (__head)->prev != (___dll))
231
232 #endif
233
234 /*
235 * lws_dll2_owner / lws_dll2 : more capable version of lws_dll. Differences:
236 *
237 * - there's an explicit lws_dll2_owner struct which holds head, tail and
238 * count of members.
239 *
240 * - list members all hold a pointer to their owner. So user code does not
241 * have to track anything about exactly what lws_dll2_owner list the object
242 * is a member of.
243 *
244 * - you can use lws_dll unless you want the member count or the ability to
245 * not track exactly which list it's on.
246 *
247 * - layout is compatible with lws_dll (but lws_dll apis will not update the
248 * new stuff)
249 */
250
251
252 struct lws_dll2;
253 struct lws_dll2_owner;
254
255 typedef struct lws_dll2 {
256 struct lws_dll2 *prev;
257 struct lws_dll2 *next;
258 struct lws_dll2_owner *owner;
259 } lws_dll2_t;
260
261 typedef struct lws_dll2_owner {
262 struct lws_dll2 *tail;
263 struct lws_dll2 *head;
264
265 uint32_t count;
266 } lws_dll2_owner_t;
267
268 static LWS_INLINE int
lws_dll2_is_detached(const struct lws_dll2 * d)269 lws_dll2_is_detached(const struct lws_dll2 *d) { return !d->owner; }
270
271 static LWS_INLINE const struct lws_dll2_owner *
lws_dll2_owner(const struct lws_dll2 * d)272 lws_dll2_owner(const struct lws_dll2 *d) { return d->owner; }
273
274 static LWS_INLINE struct lws_dll2 *
lws_dll2_get_head(struct lws_dll2_owner * owner)275 lws_dll2_get_head(struct lws_dll2_owner *owner) { return owner->head; }
276
277 static LWS_INLINE struct lws_dll2 *
lws_dll2_get_tail(struct lws_dll2_owner * owner)278 lws_dll2_get_tail(struct lws_dll2_owner *owner) { return owner->tail; }
279
280 LWS_VISIBLE LWS_EXTERN void
281 lws_dll2_add_head(struct lws_dll2 *d, struct lws_dll2_owner *owner);
282
283 LWS_VISIBLE LWS_EXTERN void
284 lws_dll2_add_tail(struct lws_dll2 *d, struct lws_dll2_owner *owner);
285
286 LWS_VISIBLE LWS_EXTERN void
287 lws_dll2_remove(struct lws_dll2 *d);
288
289 LWS_VISIBLE LWS_EXTERN int
290 lws_dll2_foreach_safe(struct lws_dll2_owner *owner, void *user,
291 int (*cb)(struct lws_dll2 *d, void *user));
292
293 LWS_VISIBLE LWS_EXTERN void
294 lws_dll2_clear(struct lws_dll2 *d);
295
296 LWS_VISIBLE LWS_EXTERN void
297 lws_dll2_owner_clear(struct lws_dll2_owner *d);
298
299 LWS_VISIBLE LWS_EXTERN void
300 lws_dll2_add_before(struct lws_dll2 *d, struct lws_dll2 *after);
301
302 LWS_VISIBLE LWS_EXTERN void
303 lws_dll2_add_sorted(lws_dll2_t *d, lws_dll2_owner_t *own,
304 int (*compare)(const lws_dll2_t *d, const lws_dll2_t *i));
305
306 #if defined(_DEBUG)
307 void
308 lws_dll2_describe(struct lws_dll2_owner *owner, const char *desc);
309 #else
310 #define lws_dll2_describe(x, y)
311 #endif
312
313 /*
314 * these are safe against the current container object getting deleted,
315 * since the hold his next in a temp and go to that next. ___tmp is
316 * the temp.
317 */
318
319 #define lws_start_foreach_dll_safe(___type, ___it, ___tmp, ___start) \
320 { \
321 ___type ___it = ___start; \
322 while (___it) { \
323 ___type ___tmp = (___it)->next;
324
325 #define lws_end_foreach_dll_safe(___it, ___tmp) \
326 ___it = ___tmp; \
327 } \
328 }
329
330 #define lws_start_foreach_dll(___type, ___it, ___start) \
331 { \
332 ___type ___it = ___start; \
333 while (___it) {
334
335 #define lws_end_foreach_dll(___it) \
336 ___it = (___it)->next; \
337 } \
338 }
339
340 ///@}
341
342