1 /*
2 * Copyright (c) 2012 Tim Ruehsen
3 * Copyright (c) 2015-2021 Free Software Foundation, Inc.
4 *
5 * This file is part of libwget.
6 *
7 * Libwget is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU Lesser General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * Libwget is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU Lesser General Public License for more details.
16 *
17 * You should have received a copy of the GNU Lesser General Public License
18 * along with libwget. If not, see <https://www.gnu.org/licenses/>.
19 *
20 *
21 * Double linked list routines
22 *
23 * Changelog
24 * 25.04.2012 Tim Ruehsen created
25 *
26 */
27
28 #include <config.h>
29
30 #include <stdlib.h>
31 #include <string.h>
32
33 #include <wget.h>
34 #include "private.h"
35
36 /**
37 * \file
38 * \brief Double linked list routines
39 * \defgroup libwget-list Double linked list
40 * @{
41 *
42 * Double linked lists provide fast insertion, removal and
43 * iteration in either direction.
44 *
45 * Each element has pointers to the next and the previous element.<br>
46 * Iteration can be done by calling the wget_list_browse() function,
47 * so the list structure doesn't need to be exposed.
48 *
49 * This datatype is used by the Wget2 tool to implement the job queue (append and remove).
50 *
51 * See wget_list_append() for an example on how to use lists.
52 */
53
54 struct wget_list_st {
55 wget_list
56 *next,
57 *prev;
58 };
59
60 /**
61 * \param[in] list Pointer to Pointer to a double linked list
62 * \param[in] data Pointer to data to be inserted
63 * \param[in] size Size of data in bytes
64 * \return Pointer to the new element or NULL if memory allocation failed
65 *
66 * Append an element to the end of the list.<br>
67 * \p size bytes at \p data will be copied and appended to the list.
68 *
69 * A pointer to the new element will be returned.
70 *
71 * \note The returned pointer must be freed by wget_list_remove() or implicitly by wget_list_free().
72 *
73 * Example:
74 *
75 * \code{.c}
76 * wget_list *list = NULL;
77 * struct mystruct mydata1 = { .x = 1, .y = 25 };
78 * struct mystruct mydata2 = { .x = 5, .y = 99 };
79 * struct mystruct *data;
80 *
81 * wget_list_append(&list, &mydata1, sizeof(mydata1)); // append mydata1 to list
82 * wget_list_append(&list, &mydata2, sizeof(mydata2)); // append mydata2 to list
83 *
84 * data = wget_list_getfirst(list);
85 * printf("data=(%d,%d)\n", data->x, data->y); // prints 'data=(1,25)'
86 *
87 * wget_list_remove(&list, data);
88 *
89 * data = wget_list_getfirst(list);
90 * printf("data=(%d,%d)\n", data->x, data->y); // prints 'data=(5,99)'
91 *
92 * wget_list_free(&list);
93 * \endcode
94 */
95 void *
wget_list_append(wget_list ** list,const void * data,size_t size)96 wget_list_append(wget_list **list, const void *data, size_t size)
97 {
98 // allocate space for node and data in one row
99 wget_list *node = wget_malloc(sizeof(wget_list) + size);
100
101 if (!node)
102 return NULL;
103
104 memcpy(node + 1, data, size);
105
106 if (!*list) {
107 // <*list> is an empty list
108 *list = node;
109 node->next = node->prev = node;
110 } else {
111 node->next = *list;
112 node->prev = (*list)->prev;
113 (*list)->prev->next = node;
114 (*list)->prev = node;
115 }
116
117 return node + 1;
118 }
119
120 /**
121 * \param[in] list Pointer to Pointer to a double linked list
122 * \param[in] data Pointer to data to be inserted
123 * \param[in] size Size of data in bytes
124 * \return Pointer to the new element
125 *
126 * Insert an entry at the beginning of the list.
127 * \p size bytes at \p data will be copied and prepended to the list.
128 *
129 * A pointer to the new element will be returned.
130 * It must be freed by wget_list_remove() or implicitly by wget_list_free().
131 */
wget_list_prepend(wget_list ** list,const void * data,size_t size)132 void *wget_list_prepend(wget_list **list, const void *data, size_t size)
133 {
134 if (!*list) {
135 return wget_list_append(list, data, size);
136 } else {
137 return wget_list_append(&(*list)->prev, data, size);
138 }
139 }
140
141 /**
142 * \param[in] list Pointer to Pointer to a double linked list
143 * \param[in] elem Pointer to a list element returned by wget_list_append() or wget_list_prepend()
144 *
145 * Remove an element from the list.
146 */
wget_list_remove(wget_list ** list,void * elem)147 void wget_list_remove(wget_list **list, void *elem)
148 {
149 wget_list *node = ((wget_list *)elem) - 1;
150
151 if (node->prev == node->next && node == node->prev) {
152 // removing the last node in the list
153 if (*list && node == *list)
154 *list = NULL;
155 } else {
156 node->prev->next = node->next;
157 node->next->prev = node->prev;
158 if (*list && node == *list)
159 *list = node->next;
160 }
161 xfree(node);
162 }
163
164 /**
165 * \param[in] list Pointer to a double linked list
166 * \return Pointer to the first element of the list or %NULL if the list is empty
167 *
168 * Get the first element of a list.
169 */
wget_list_getfirst(const wget_list * list)170 void *wget_list_getfirst(const wget_list *list)
171 {
172 return (void *)(list ? list + 1 : list);
173 }
174
175 /**
176 * \param[in] list Pointer to a double linked list
177 * \return Pointer to the last element of the list or %NULL if the list is empty
178 *
179 * Get the last element of a list.
180 */
wget_list_getlast(const wget_list * list)181 void *wget_list_getlast(const wget_list *list)
182 {
183 return (void *)(list ? list->prev + 1 : list);
184 }
185
186 /**
187 * \param[in] elem Pointer to an element of a linked list
188 * \return Pointer to the next element of the list or %NULL if the list is empty
189 *
190 * Get the next element of a list.
191 */
wget_list_getnext(const void * elem)192 void *wget_list_getnext(const void *elem)
193 {
194 if (elem) {
195 wget_list *node = ((wget_list *)elem) - 1;
196 return node->next + 1;
197 }
198 return NULL;
199 }
200
201 /**
202 * \param[in] list Pointer to a double linked list
203 * \param[in] browse Pointer to callback function which is called for every element in the list.
204 * If the callback functions returns a value not equal to zero, browsing is stopped and
205 * this value will be returned by wget_list_browse.
206 * \param[in] context The context handle that will be passed to the callback function
207 * \return The return value of the last call to the browse function or -1 if \p list is NULL (empty)
208 *
209 * Iterate through all entries of the \p list and call the function \p browse for each.
210 *
211 *
212 * \code{.c}
213 * // assume that list contains C strings.
214 * wget_list *list = NULL;
215 *
216 * static int print_elem(void *context, const char *elem)
217 * {
218 * printf("%s\n",elem);
219 * return 0;
220 * }
221 *
222 * void dump(WGET_LIST *list)
223 * {
224 * wget_list_browse(list, (wget_list_browse_t)print_elem, NULL);
225 * }
226 * \endcode
227 */
wget_list_browse(const wget_list * list,wget_list_browse_fn * browse,void * context)228 int wget_list_browse(const wget_list *list, wget_list_browse_fn *browse, void *context)
229 {
230 if (!list)
231 return -1;
232
233 int ret;
234 const wget_list *end = list->prev, *cur = list;
235
236 while ((ret = browse(context, (void *)(cur + 1))) == 0 && cur != end)
237 cur = cur->next;
238
239 return ret;
240 }
241
242 /**
243 * \param[in] list Pointer to Pointer to a double linked list
244 *
245 * Freeing the list and it's entry.
246 */
wget_list_free(wget_list ** list)247 void wget_list_free(wget_list **list)
248 {
249 while (*list)
250 wget_list_remove(list, *list + 1);
251 }
252
253 /*
254 void wget_list_dump(const WGET_LIST *list)
255 {
256 if (list) {
257 const wget_list *cur = list;
258
259 do {
260 debug_printf("%p: next %p prev %p\n", cur, cur->next, cur->prev);
261 cur = cur->next;
262 } while (cur != list);
263 } else
264 debug_printf("empty\n");
265 }
266 */
267
268 /**@}*/
269