1 /***************************************************************************
2 * _ _ ____ _
3 * Project ___| | | | _ \| |
4 * / __| | | | |_) | |
5 * | (__| |_| | _ <| |___
6 * \___|\___/|_| \_\_____|
7 *
8 * Copyright (C) Daniel Stenberg, <daniel@haxx.se>, et al.
9 *
10 * This software is licensed as described in the file COPYING, which
11 * you should have received as part of this distribution. The terms
12 * are also available at https://curl.se/docs/copyright.html.
13 *
14 * You may opt to use, copy, modify, merge, publish, distribute and/or sell
15 * copies of the Software, and permit persons to whom the Software is
16 * furnished to do so, under the terms of the COPYING file.
17 *
18 * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY
19 * KIND, either express or implied.
20 *
21 * SPDX-License-Identifier: curl
22 *
23 ***************************************************************************/
24
25 #include "curl_setup.h"
26
27 #include <curl/curl.h>
28
29 #include "llist.h"
30 #include "curl_memory.h"
31
32 /* this must be the last include file */
33 #include "memdebug.h"
34
35 #define LLISTINIT 0x100cc001 /* random pattern */
36 #define NODEINIT 0x12344321 /* random pattern */
37 #define NODEREM 0x54321012 /* random pattern */
38
39
40 #ifdef DEBUGBUILD
41 #define VERIFYNODE(x) verifynode(x)
verifynode(struct Curl_llist_node * n)42 static struct Curl_llist_node *verifynode(struct Curl_llist_node *n)
43 {
44 DEBUGASSERT(!n || (n->_init == NODEINIT));
45 return n;
46 }
47 #else
48 #define VERIFYNODE(x) x
49 #endif
50 /*
51 * @unittest: 1300
52 */
53 void
Curl_llist_init(struct Curl_llist * l,Curl_llist_dtor dtor)54 Curl_llist_init(struct Curl_llist *l, Curl_llist_dtor dtor)
55 {
56 l->_size = 0;
57 l->_dtor = dtor;
58 l->_head = NULL;
59 l->_tail = NULL;
60 #ifdef DEBUGBUILD
61 l->_init = LLISTINIT;
62 #endif
63 }
64
65 /*
66 * Curl_llist_insert_next()
67 *
68 * Inserts a new list element after the given one 'e'. If the given existing
69 * entry is NULL and the list already has elements, the new one will be
70 * inserted first in the list.
71 *
72 * The 'ne' argument should be a pointer into the object to store.
73 *
74 * @unittest: 1300
75 */
76 void
Curl_llist_insert_next(struct Curl_llist * list,struct Curl_llist_node * e,const void * p,struct Curl_llist_node * ne)77 Curl_llist_insert_next(struct Curl_llist *list,
78 struct Curl_llist_node *e, /* may be NULL */
79 const void *p,
80 struct Curl_llist_node *ne)
81 {
82 DEBUGASSERT(list);
83 DEBUGASSERT(list->_init == LLISTINIT);
84 DEBUGASSERT(ne);
85
86 #ifdef DEBUGBUILD
87 ne->_init = NODEINIT;
88 #endif
89 ne->_ptr = (void *) p;
90 ne->_list = list;
91 if(list->_size == 0) {
92 list->_head = ne;
93 list->_head->_prev = NULL;
94 list->_head->_next = NULL;
95 list->_tail = ne;
96 }
97 else {
98 /* if 'e' is NULL here, we insert the new element first in the list */
99 ne->_next = e ? e->_next : list->_head;
100 ne->_prev = e;
101 if(!e) {
102 list->_head->_prev = ne;
103 list->_head = ne;
104 }
105 else if(e->_next) {
106 e->_next->_prev = ne;
107 }
108 else {
109 list->_tail = ne;
110 }
111 if(e)
112 e->_next = ne;
113 }
114
115 ++list->_size;
116 }
117
118 /*
119 * Curl_llist_append()
120 *
121 * Adds a new list element to the end of the list.
122 *
123 * The 'ne' argument should be a pointer into the object to store.
124 *
125 * @unittest: 1300
126 */
127 void
Curl_llist_append(struct Curl_llist * list,const void * p,struct Curl_llist_node * ne)128 Curl_llist_append(struct Curl_llist *list, const void *p,
129 struct Curl_llist_node *ne)
130 {
131 DEBUGASSERT(list);
132 DEBUGASSERT(list->_init == LLISTINIT);
133 DEBUGASSERT(ne);
134 Curl_llist_insert_next(list, list->_tail, p, ne);
135 }
136
Curl_node_take_elem(struct Curl_llist_node * e)137 void *Curl_node_take_elem(struct Curl_llist_node *e)
138 {
139 void *ptr;
140 struct Curl_llist *list;
141 if(!e)
142 return NULL;
143
144 list = e->_list;
145 DEBUGASSERT(list);
146 DEBUGASSERT(list->_init == LLISTINIT);
147 DEBUGASSERT(list->_size);
148 DEBUGASSERT(e->_init == NODEINIT);
149 if(list) {
150 if(e == list->_head) {
151 list->_head = e->_next;
152
153 if(!list->_head)
154 list->_tail = NULL;
155 else
156 e->_next->_prev = NULL;
157 }
158 else {
159 if(e->_prev)
160 e->_prev->_next = e->_next;
161
162 if(!e->_next)
163 list->_tail = e->_prev;
164 else
165 e->_next->_prev = e->_prev;
166 }
167 --list->_size;
168 }
169 ptr = e->_ptr;
170
171 e->_list = NULL;
172 e->_ptr = NULL;
173 e->_prev = NULL;
174 e->_next = NULL;
175 #ifdef DEBUGBUILD
176 e->_init = NODEREM; /* specific pattern on remove - not zero */
177 #endif
178
179 return ptr;
180 }
181
182 /*
183 * @unittest: 1300
184 */
185 void
Curl_node_uremove(struct Curl_llist_node * e,void * user)186 Curl_node_uremove(struct Curl_llist_node *e, void *user)
187 {
188 struct Curl_llist *list;
189 void *ptr;
190 if(!e)
191 return;
192
193 list = e->_list;
194 DEBUGASSERT(list);
195 if(list) {
196 ptr = Curl_node_take_elem(e);
197 if(list->_dtor)
198 list->_dtor(user, ptr);
199 }
200 }
201
Curl_node_remove(struct Curl_llist_node * e)202 void Curl_node_remove(struct Curl_llist_node *e)
203 {
204 Curl_node_uremove(e, NULL);
205 }
206
207 void
Curl_llist_destroy(struct Curl_llist * list,void * user)208 Curl_llist_destroy(struct Curl_llist *list, void *user)
209 {
210 if(list) {
211 DEBUGASSERT(list->_init == LLISTINIT);
212 while(list->_size > 0)
213 Curl_node_uremove(list->_tail, user);
214 }
215 }
216
217 /* Curl_llist_head() returns the first 'struct Curl_llist_node *', which
218 might be NULL */
Curl_llist_head(struct Curl_llist * list)219 struct Curl_llist_node *Curl_llist_head(struct Curl_llist *list)
220 {
221 DEBUGASSERT(list);
222 DEBUGASSERT(list->_init == LLISTINIT);
223 return VERIFYNODE(list->_head);
224 }
225
226 #ifdef UNITTESTS
227 /* Curl_llist_tail() returns the last 'struct Curl_llist_node *', which
228 might be NULL */
Curl_llist_tail(struct Curl_llist * list)229 struct Curl_llist_node *Curl_llist_tail(struct Curl_llist *list)
230 {
231 DEBUGASSERT(list);
232 DEBUGASSERT(list->_init == LLISTINIT);
233 return VERIFYNODE(list->_tail);
234 }
235 #endif
236
237 /* Curl_llist_count() returns a size_t the number of nodes in the list */
Curl_llist_count(struct Curl_llist * list)238 size_t Curl_llist_count(struct Curl_llist *list)
239 {
240 DEBUGASSERT(list);
241 DEBUGASSERT(list->_init == LLISTINIT);
242 return list->_size;
243 }
244
245 /* Curl_node_elem() returns the custom data from a Curl_llist_node */
Curl_node_elem(struct Curl_llist_node * n)246 void *Curl_node_elem(struct Curl_llist_node *n)
247 {
248 DEBUGASSERT(n);
249 DEBUGASSERT(n->_init == NODEINIT);
250 return n->_ptr;
251 }
252
253 /* Curl_node_next() returns the next element in a list from a given
254 Curl_llist_node */
Curl_node_next(struct Curl_llist_node * n)255 struct Curl_llist_node *Curl_node_next(struct Curl_llist_node *n)
256 {
257 DEBUGASSERT(n);
258 DEBUGASSERT(n->_init == NODEINIT);
259 return VERIFYNODE(n->_next);
260 }
261
262 #ifdef UNITTESTS
263
264 /* Curl_node_prev() returns the previous element in a list from a given
265 Curl_llist_node */
Curl_node_prev(struct Curl_llist_node * n)266 struct Curl_llist_node *Curl_node_prev(struct Curl_llist_node *n)
267 {
268 DEBUGASSERT(n);
269 DEBUGASSERT(n->_init == NODEINIT);
270 return VERIFYNODE(n->_prev);
271 }
272
273 #endif
274
Curl_node_llist(struct Curl_llist_node * n)275 struct Curl_llist *Curl_node_llist(struct Curl_llist_node *n)
276 {
277 DEBUGASSERT(n);
278 DEBUGASSERT(!n->_list || n->_init == NODEINIT);
279 return n->_list;
280 }
281
