• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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