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
137 /*
138 * @unittest: 1300
139 */
140 void
Curl_node_uremove(struct Curl_llist_node * e,void * user)141 Curl_node_uremove(struct Curl_llist_node *e, void *user)
142 {
143 void *ptr;
144 struct Curl_llist *list;
145 if(!e)
146 return;
147
148 list = e->_list;
149 DEBUGASSERT(list);
150 DEBUGASSERT(list->_init == LLISTINIT);
151 DEBUGASSERT(list->_size);
152 DEBUGASSERT(e->_init == NODEINIT);
153 if(e == list->_head) {
154 list->_head = e->_next;
155
156 if(!list->_head)
157 list->_tail = NULL;
158 else
159 e->_next->_prev = NULL;
160 }
161 else {
162 if(e->_prev)
163 e->_prev->_next = e->_next;
164
165 if(!e->_next)
166 list->_tail = e->_prev;
167 else
168 e->_next->_prev = e->_prev;
169 }
170
171 ptr = e->_ptr;
172
173 e->_list = NULL;
174 e->_ptr = NULL;
175 e->_prev = NULL;
176 e->_next = NULL;
177 #ifdef DEBUGBUILD
178 e->_init = NODEREM; /* specific pattern on remove - not zero */
179 #endif
180
181 --list->_size;
182
183 /* call the dtor() last for when it actually frees the 'e' memory itself */
184 if(list->_dtor)
185 list->_dtor(user, ptr);
186 }
187
Curl_node_remove(struct Curl_llist_node * e)188 void Curl_node_remove(struct Curl_llist_node *e)
189 {
190 Curl_node_uremove(e, NULL);
191 }
192
193 void
Curl_llist_destroy(struct Curl_llist * list,void * user)194 Curl_llist_destroy(struct Curl_llist *list, void *user)
195 {
196 if(list) {
197 DEBUGASSERT(list->_init == LLISTINIT);
198 while(list->_size > 0)
199 Curl_node_uremove(list->_tail, user);
200 }
201 }
202
203 /* Curl_llist_head() returns the first 'struct Curl_llist_node *', which
204 might be NULL */
Curl_llist_head(struct Curl_llist * list)205 struct Curl_llist_node *Curl_llist_head(struct Curl_llist *list)
206 {
207 DEBUGASSERT(list);
208 DEBUGASSERT(list->_init == LLISTINIT);
209 return VERIFYNODE(list->_head);
210 }
211
212 #ifdef UNITTESTS
213 /* Curl_llist_tail() returns the last 'struct Curl_llist_node *', which
214 might be NULL */
Curl_llist_tail(struct Curl_llist * list)215 struct Curl_llist_node *Curl_llist_tail(struct Curl_llist *list)
216 {
217 DEBUGASSERT(list);
218 DEBUGASSERT(list->_init == LLISTINIT);
219 return VERIFYNODE(list->_tail);
220 }
221 #endif
222
223 /* Curl_llist_count() returns a size_t the number of nodes in the list */
Curl_llist_count(struct Curl_llist * list)224 size_t Curl_llist_count(struct Curl_llist *list)
225 {
226 DEBUGASSERT(list);
227 DEBUGASSERT(list->_init == LLISTINIT);
228 return list->_size;
229 }
230
231 /* Curl_node_elem() returns the custom data from a Curl_llist_node */
Curl_node_elem(struct Curl_llist_node * n)232 void *Curl_node_elem(struct Curl_llist_node *n)
233 {
234 DEBUGASSERT(n);
235 DEBUGASSERT(n->_init == NODEINIT);
236 return n->_ptr;
237 }
238
239 /* Curl_node_next() returns the next element in a list from a given
240 Curl_llist_node */
Curl_node_next(struct Curl_llist_node * n)241 struct Curl_llist_node *Curl_node_next(struct Curl_llist_node *n)
242 {
243 DEBUGASSERT(n);
244 DEBUGASSERT(n->_init == NODEINIT);
245 return VERIFYNODE(n->_next);
246 }
247
248 #ifdef UNITTESTS
249
250 /* Curl_node_prev() returns the previous element in a list from a given
251 Curl_llist_node */
Curl_node_prev(struct Curl_llist_node * n)252 struct Curl_llist_node *Curl_node_prev(struct Curl_llist_node *n)
253 {
254 DEBUGASSERT(n);
255 DEBUGASSERT(n->_init == NODEINIT);
256 return VERIFYNODE(n->_prev);
257 }
258
259 #endif
260
Curl_node_llist(struct Curl_llist_node * n)261 struct Curl_llist *Curl_node_llist(struct Curl_llist_node *n)
262 {
263 DEBUGASSERT(n);
264 DEBUGASSERT(!n->_list || n->_init == NODEINIT);
265 return n->_list;
266 }
267
