1 /*
2 bctoolbox
3 Copyright (C) 2016 Belledonne Communications SARL
4
5 This program is free software: you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published by
7 the Free Software Foundation, either version 2 of the License, or
8 (at your option) any later version.
9
10 This program is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU General Public License for more details.
14
15 You should have received a copy of the GNU General Public License
16 along with this program. If not, see <http://www.gnu.org/licenses/>.
17 */
18
19 #ifdef HAVE_CONFIG_H
20 #include "config.h"
21 #endif
22
23 #define _CRT_RAND_S
24 #include <stddef.h>
25 #include <stdlib.h>
26 #include <sys/stat.h>
27
28 #ifndef _WIN32
29 #include <unistd.h>
30 #include <sys/time.h> /*for gettimeofday*/
31 #include <dirent.h> /* available on POSIX system only */
32 #else
33 #include <direct.h>
34 #endif
35 #include "bctoolbox/port.h"
36 #include "bctoolbox/logging.h"
37 #include "bctoolbox/list.h"
38
39
bctbx_list_new(void * data)40 bctbx_list_t* bctbx_list_new(void *data){
41 bctbx_list_t* new_elem=bctbx_new0(bctbx_list_t,1);
42 new_elem->data=data;
43 return new_elem;
44 }
bctbx_list_next(const bctbx_list_t * elem)45 bctbx_list_t* bctbx_list_next(const bctbx_list_t *elem) {
46 return elem->next;
47 }
bctbx_list_get_data(const bctbx_list_t * elem)48 void* bctbx_list_get_data(const bctbx_list_t *elem) {
49 return elem->data;
50 }
bctbx_list_append_link(bctbx_list_t * elem,bctbx_list_t * new_elem)51 bctbx_list_t* bctbx_list_append_link(bctbx_list_t* elem,bctbx_list_t *new_elem){
52 bctbx_list_t* it=elem;
53 if (elem==NULL) return new_elem;
54 if (new_elem==NULL) return elem;
55 while (it->next!=NULL) it=bctbx_list_next(it);
56 it->next=new_elem;
57 new_elem->prev=it;
58 return elem;
59 }
60
bctbx_list_append(bctbx_list_t * elem,void * data)61 bctbx_list_t* bctbx_list_append(bctbx_list_t* elem, void * data){
62 bctbx_list_t* new_elem=bctbx_list_new(data);
63 return bctbx_list_append_link(elem,new_elem);
64 }
65
bctbx_list_prepend_link(bctbx_list_t * elem,bctbx_list_t * new_elem)66 bctbx_list_t* bctbx_list_prepend_link(bctbx_list_t* elem, bctbx_list_t *new_elem){
67 if (elem!=NULL) {
68 new_elem->next=elem;
69 elem->prev=new_elem;
70 }
71 return new_elem;
72 }
73
bctbx_list_prepend(bctbx_list_t * elem,void * data)74 bctbx_list_t* bctbx_list_prepend(bctbx_list_t* elem, void *data){
75 return bctbx_list_prepend_link(elem,bctbx_list_new(data));
76 }
77
bctbx_list_last_elem(const bctbx_list_t * l)78 bctbx_list_t * bctbx_list_last_elem(const bctbx_list_t *l){
79 if (l==NULL) return NULL;
80 while(l->next){
81 l=l->next;
82 }
83 return (bctbx_list_t*)l;
84 }
85
bctbx_list_first_elem(const bctbx_list_t * l)86 bctbx_list_t * bctbx_list_first_elem(const bctbx_list_t *l){
87 if (l==NULL) return NULL;
88 while(l->prev){
89 l=l->prev;
90 }
91 return (bctbx_list_t*)l;
92 }
93
bctbx_list_concat(bctbx_list_t * first,bctbx_list_t * second)94 bctbx_list_t* bctbx_list_concat(bctbx_list_t* first, bctbx_list_t* second){
95 bctbx_list_t* it=first;
96 if (it==NULL) return second;
97 if (second==NULL) return first;
98 while(it->next!=NULL) it=bctbx_list_next(it);
99 it->next=second;
100 second->prev=it;
101 return first;
102 }
103
bctbx_list_free(bctbx_list_t * list)104 bctbx_list_t* bctbx_list_free(bctbx_list_t* list){
105 bctbx_list_t* elem = list;
106 bctbx_list_t* tmp;
107 if (list==NULL) return NULL;
108 while(elem->next!=NULL) {
109 tmp = elem;
110 elem = elem->next;
111 bctbx_free(tmp);
112 }
113 bctbx_free(elem);
114 return NULL;
115 }
116
bctbx_list_free_with_data(bctbx_list_t * list,bctbx_list_free_func freefunc)117 bctbx_list_t * bctbx_list_free_with_data(bctbx_list_t *list, bctbx_list_free_func freefunc){
118 bctbx_list_t* elem = list;
119 bctbx_list_t* tmp;
120 if (list==NULL) return NULL;
121 while(elem->next!=NULL) {
122 tmp = elem;
123 elem = elem->next;
124 freefunc(tmp->data);
125 bctbx_free(tmp);
126 }
127 freefunc(elem->data);
128 bctbx_free(elem);
129 return NULL;
130 }
131
132
_bctbx_list_remove(bctbx_list_t * first,void * data,int warn_if_not_found)133 bctbx_list_t* _bctbx_list_remove(bctbx_list_t* first, void *data, int warn_if_not_found){
134 bctbx_list_t* it;
135 it=bctbx_list_find(first,data);
136 if (it) return bctbx_list_erase_link(first,it);
137 else if (warn_if_not_found){
138 bctbx_warning("bctbx_list_remove: no element with %p data was in the list", data);
139 }
140 return first;
141 }
142
bctbx_list_remove(bctbx_list_t * first,void * data)143 bctbx_list_t* bctbx_list_remove(bctbx_list_t* first, void *data){
144 return _bctbx_list_remove(first, data, TRUE);
145 }
146
bctbx_list_remove_custom(bctbx_list_t * first,bctbx_compare_func compare_func,const void * user_data)147 bctbx_list_t * bctbx_list_remove_custom(bctbx_list_t *first, bctbx_compare_func compare_func, const void *user_data) {
148 bctbx_list_t *cur;
149 bctbx_list_t *elem = first;
150 while (elem != NULL) {
151 cur = elem;
152 elem = elem->next;
153 if (compare_func(cur->data, user_data) == 0) {
154 first = bctbx_list_remove(first, cur->data);
155 }
156 }
157 return first;
158 }
159
bctbx_list_size(const bctbx_list_t * first)160 size_t bctbx_list_size(const bctbx_list_t* first){
161 size_t n=0;
162 while(first!=NULL){
163 ++n;
164 first=first->next;
165 }
166 return n;
167 }
168
bctbx_list_for_each(const bctbx_list_t * list,bctbx_list_iterate_func func)169 void bctbx_list_for_each(const bctbx_list_t* list, bctbx_list_iterate_func func){
170 for(;list!=NULL;list=list->next){
171 func(list->data);
172 }
173 }
174
bctbx_list_for_each2(const bctbx_list_t * list,bctbx_list_iterate2_func func,void * user_data)175 void bctbx_list_for_each2(const bctbx_list_t* list, bctbx_list_iterate2_func func, void *user_data){
176 for(;list!=NULL;list=list->next){
177 func(list->data,user_data);
178 }
179 }
180
bctbx_list_pop_front(bctbx_list_t * list,void ** front_data)181 bctbx_list_t * bctbx_list_pop_front(bctbx_list_t *list, void **front_data){
182 bctbx_list_t *front_elem=list;
183 if (front_elem==NULL){
184 *front_data=NULL;
185 return NULL;
186 }
187 *front_data=front_elem->data;
188 list=bctbx_list_unlink(list,front_elem);
189 bctbx_free(front_elem);
190 return list;
191 }
192
bctbx_list_unlink(bctbx_list_t * list,bctbx_list_t * elem)193 bctbx_list_t* bctbx_list_unlink(bctbx_list_t* list, bctbx_list_t* elem){
194 bctbx_list_t* ret;
195 if (elem==list){
196 ret=elem->next;
197 elem->prev=NULL;
198 elem->next=NULL;
199 if (ret!=NULL) ret->prev=NULL;
200 return ret;
201 }
202 elem->prev->next=elem->next;
203 if (elem->next!=NULL) elem->next->prev=elem->prev;
204 elem->next=NULL;
205 elem->prev=NULL;
206 return list;
207 }
208
bctbx_list_erase_link(bctbx_list_t * list,bctbx_list_t * elem)209 bctbx_list_t * bctbx_list_erase_link(bctbx_list_t* list, bctbx_list_t* elem){
210 bctbx_list_t *ret=bctbx_list_unlink(list,elem);
211 bctbx_free(elem);
212 return ret;
213 }
214
bctbx_list_find(bctbx_list_t * list,const void * data)215 bctbx_list_t* bctbx_list_find(bctbx_list_t* list, const void *data){
216 for(;list!=NULL;list=list->next){
217 if (list->data==data) return list;
218 }
219 return NULL;
220 }
221
bctbx_list_find_custom(const bctbx_list_t * list,bctbx_compare_func compare_func,const void * user_data)222 bctbx_list_t* bctbx_list_find_custom(const bctbx_list_t* list, bctbx_compare_func compare_func, const void *user_data){
223 for(;list!=NULL;list=list->next){
224 if (compare_func(list->data,user_data)==0) return (bctbx_list_t *)list;
225 }
226 return NULL;
227 }
228
bctbx_list_delete_custom(bctbx_list_t * list,bctbx_compare_func compare_func,const void * user_data)229 bctbx_list_t *bctbx_list_delete_custom(bctbx_list_t *list, bctbx_compare_func compare_func, const void *user_data){
230 bctbx_list_t *elem=bctbx_list_find_custom(list,compare_func,user_data);
231 if (elem!=NULL){
232 list=bctbx_list_erase_link(list,elem);
233 }
234 return list;
235 }
236
bctbx_list_nth_data(const bctbx_list_t * list,int index)237 void * bctbx_list_nth_data(const bctbx_list_t* list, int index){
238 int i;
239 for(i=0;list!=NULL;list=list->next,++i){
240 if (i==index) return list->data;
241 }
242 bctbx_error("bctbx_list_nth_data: no such index in list.");
243 return NULL;
244 }
245
bctbx_list_position(const bctbx_list_t * list,bctbx_list_t * elem)246 int bctbx_list_position(const bctbx_list_t* list, bctbx_list_t* elem){
247 int i;
248 for(i=0;list!=NULL;list=list->next,++i){
249 if (elem==list) return i;
250 }
251 bctbx_error("bctbx_list_position: no such element in list.");
252 return -1;
253 }
254
bctbx_list_index(const bctbx_list_t * list,void * data)255 int bctbx_list_index(const bctbx_list_t* list, void *data){
256 int i;
257 for(i=0;list!=NULL;list=list->next,++i){
258 if (data==list->data) return i;
259 }
260 bctbx_error("bctbx_list_index: no such element in list.");
261 return -1;
262 }
263
bctbx_list_insert_sorted(bctbx_list_t * list,void * data,bctbx_compare_func compare_func)264 bctbx_list_t* bctbx_list_insert_sorted(bctbx_list_t* list, void *data, bctbx_compare_func compare_func){
265 bctbx_list_t* it,*previt=NULL;
266 bctbx_list_t* nelem;
267 bctbx_list_t* ret=list;
268 if (list==NULL) return bctbx_list_append(list,data);
269 else{
270 nelem=bctbx_list_new(data);
271 for(it=list;it!=NULL;it=it->next){
272 previt=it;
273 if (compare_func(data,it->data)<=0){
274 nelem->prev=it->prev;
275 nelem->next=it;
276 if (it->prev!=NULL)
277 it->prev->next=nelem;
278 else{
279 ret=nelem;
280 }
281 it->prev=nelem;
282 return ret;
283 }
284 }
285 previt->next=nelem;
286 nelem->prev=previt;
287 }
288 return ret;
289 }
290
bctbx_list_insert(bctbx_list_t * list,bctbx_list_t * before,void * data)291 bctbx_list_t* bctbx_list_insert(bctbx_list_t* list, bctbx_list_t* before, void *data){
292 bctbx_list_t* elem;
293 if (list==NULL || before==NULL) return bctbx_list_append(list,data);
294 for(elem=list;elem!=NULL;elem=bctbx_list_next(elem)){
295 if (elem==before){
296 if (elem->prev==NULL)
297 return bctbx_list_prepend(list,data);
298 else{
299 bctbx_list_t* nelem=bctbx_list_new(data);
300 nelem->prev=elem->prev;
301 nelem->next=elem;
302 elem->prev->next=nelem;
303 elem->prev=nelem;
304 }
305 }
306 }
307 return list;
308 }
309
bctbx_list_copy(const bctbx_list_t * list)310 bctbx_list_t* bctbx_list_copy(const bctbx_list_t* list){
311 bctbx_list_t* copy=NULL;
312 const bctbx_list_t* iter;
313 for(iter=list;iter!=NULL;iter=bctbx_list_next(iter)){
314 copy=bctbx_list_append(copy,iter->data);
315 }
316 return copy;
317 }
318
bctbx_list_copy_with_data(const bctbx_list_t * list,bctbx_list_copy_func copyfunc)319 bctbx_list_t* bctbx_list_copy_with_data(const bctbx_list_t* list, bctbx_list_copy_func copyfunc){
320 bctbx_list_t* copy=NULL;
321 const bctbx_list_t* iter;
322 for(iter=list;iter!=NULL;iter=bctbx_list_next(iter)){
323 copy=bctbx_list_append(copy,copyfunc(iter->data));
324 }
325 return copy;
326 }
327
bctbx_list_copy_reverse_with_data(const bctbx_list_t * list,bctbx_list_copy_func copyfunc)328 bctbx_list_t* bctbx_list_copy_reverse_with_data(const bctbx_list_t* list, bctbx_list_copy_func copyfunc){
329 bctbx_list_t* copy=NULL;
330 const bctbx_list_t* iter;
331 for(iter=list;iter!=NULL;iter=bctbx_list_next(iter)){
332 copy=bctbx_list_prepend(copy,copyfunc(iter->data));
333 }
334 return copy;
335 }
336