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 #include "private-lib-core.h"
26
27 #ifdef LWS_HAVE_SYS_TYPES_H
28 #include <sys/types.h>
29 #endif
30
31 void
lws_dll_add_head(struct lws_dll * d,struct lws_dll * phead)32 lws_dll_add_head(struct lws_dll *d, struct lws_dll *phead)
33 {
34 if (!lws_dll_is_detached(d, phead)) {
35 assert(0); /* only wholly detached things can be added */
36 return;
37 }
38
39 /* our next guy is current first guy, if any */
40 if (phead->next != d)
41 d->next = phead->next;
42
43 /* if there is a next guy, set his prev ptr to our next ptr */
44 if (d->next)
45 d->next->prev = d;
46 /* there is nobody previous to us, we are the head */
47 d->prev = NULL;
48
49 /* set the first guy to be us */
50 phead->next = d;
51
52 /* if there was nothing on the list before, we are also now the tail */
53 if (!phead->prev)
54 phead->prev = d;
55
56 assert(d->prev != d);
57 assert(d->next != d);
58 }
59
60 void
lws_dll_add_tail(struct lws_dll * d,struct lws_dll * phead)61 lws_dll_add_tail(struct lws_dll *d, struct lws_dll *phead)
62 {
63 if (!lws_dll_is_detached(d, phead)) {
64 assert(0); /* only wholly detached things can be added */
65 return;
66 }
67
68 /* our previous guy is current last guy */
69 d->prev = phead->prev;
70 /* if there is a prev guy, set his next ptr to our prev ptr */
71 if (d->prev)
72 d->prev->next = d;
73 /* our next ptr is NULL */
74 d->next = NULL;
75 /* set the last guy to be us */
76 phead->prev = d;
77
78 /* list head is also us if we're the first */
79 if (!phead->next)
80 phead->next = d;
81
82 assert(d->prev != d);
83 assert(d->next != d);
84 }
85
86 void
lws_dll_insert(struct lws_dll * n,struct lws_dll * target,struct lws_dll * phead,int before)87 lws_dll_insert(struct lws_dll *n, struct lws_dll *target,
88 struct lws_dll *phead, int before)
89 {
90 if (!lws_dll_is_detached(n, phead)) {
91 assert(0); /* only wholly detached things can be inserted */
92 return;
93 }
94 if (!target) {
95 /*
96 * the case where there's no target identified degenerates to
97 * a simple add at head or tail
98 */
99 if (before) {
100 lws_dll_add_head(n, phead);
101 return;
102 }
103 lws_dll_add_tail(n, phead);
104 return;
105 }
106
107 /*
108 * in the case there's a target "cursor", we have to do the work to
109 * stitch the new guy in appropriately
110 */
111
112 if (before) {
113 /*
114 * we go before dd
115 * DDp <-> DD <-> DDn --> DDp <-> us <-> DD <-> DDn
116 */
117 /* we point forward to dd */
118 n->next = target;
119 /* we point back to what dd used to point back to */
120 n->prev = target->prev;
121 /* DDp points forward to us now */
122 if (target->prev)
123 target->prev->next = n;
124 /* DD points back to us now */
125 target->prev = n;
126
127 /* if target was the head, we are now the head */
128 if (phead->next == target)
129 phead->next = n;
130
131 /* since we are before another guy, we cannot become the tail */
132
133 } else {
134 /*
135 * we go after dd
136 * DDp <-> DD <-> DDn --> DDp <-> DD <-> us <-> DDn
137 */
138 /* we point forward to what dd used to point forward to */
139 n->next = target->next;
140 /* we point back to dd */
141 n->prev = target;
142 /* DDn points back to us */
143 if (target->next)
144 target->next->prev = n;
145 /* DD points forward to us */
146 target->next = n;
147
148 /* if target was the tail, we are now the tail */
149 if (phead->prev == target)
150 phead->prev = n;
151
152 /* since we go after another guy, we cannot become the head */
153 }
154 }
155
156 /* situation is:
157 *
158 * HEAD: struct lws_dll * = &entry1
159 *
160 * Entry 1: struct lws_dll .pprev = &HEAD , .next = Entry 2
161 * Entry 2: struct lws_dll .pprev = &entry1 , .next = &entry2
162 * Entry 3: struct lws_dll .pprev = &entry2 , .next = NULL
163 *
164 * Delete Entry1:
165 *
166 * - HEAD = &entry2
167 * - Entry2: .pprev = &HEAD, .next = &entry3
168 * - Entry3: .pprev = &entry2, .next = NULL
169 *
170 * Delete Entry2:
171 *
172 * - HEAD = &entry1
173 * - Entry1: .pprev = &HEAD, .next = &entry3
174 * - Entry3: .pprev = &entry1, .next = NULL
175 *
176 * Delete Entry3:
177 *
178 * - HEAD = &entry1
179 * - Entry1: .pprev = &HEAD, .next = &entry2
180 * - Entry2: .pprev = &entry1, .next = NULL
181 *
182 */
183
184 void
lws_dll_remove(struct lws_dll * d)185 lws_dll_remove(struct lws_dll *d)
186 {
187 if (!d->prev && !d->next)
188 return;
189
190 /*
191 * remove us
192 *
193 * USp <-> us <-> USn --> USp <-> USn
194 */
195
196 /* if we have a next guy, set his prev to our prev */
197 if (d->next)
198 d->next->prev = d->prev;
199
200 /* set our prev guy to our next guy instead of us */
201 if (d->prev)
202 d->prev->next = d->next;
203
204 /* we're out of the list, we should not point anywhere any more */
205 d->prev = NULL;
206 d->next = NULL;
207 }
208
209 void
lws_dll_remove_track_tail(struct lws_dll * d,struct lws_dll * phead)210 lws_dll_remove_track_tail(struct lws_dll *d, struct lws_dll *phead)
211 {
212 if (lws_dll_is_detached(d, phead)) {
213 assert(phead->prev != d);
214 assert(phead->next != d);
215 return;
216 }
217
218 /* if we have a next guy, set his prev to our prev */
219 if (d->next)
220 d->next->prev = d->prev;
221
222 /* if we have a previous guy, set his next to our next */
223 if (d->prev)
224 d->prev->next = d->next;
225
226 if (phead->prev == d)
227 phead->prev = d->prev;
228
229 if (phead->next == d)
230 phead->next = d->next;
231
232 /* we're out of the list, we should not point anywhere any more */
233 d->prev = NULL;
234 d->next = NULL;
235 }
236
237
238 int
lws_dll_foreach_safe(struct lws_dll * phead,void * user,int (* cb)(struct lws_dll * d,void * user))239 lws_dll_foreach_safe(struct lws_dll *phead, void *user,
240 int (*cb)(struct lws_dll *d, void *user))
241 {
242 lws_start_foreach_dll_safe(struct lws_dll *, p, tp, phead->next) {
243 if (cb(p, user))
244 return 1;
245 } lws_end_foreach_dll_safe(p, tp);
246
247 return 0;
248 }
249