xref: /freebsd/contrib/atf/atf-c/detail/list.c (revision 145992504973bd16cf3518af9ba5ce185fefa82a) 
1 /*
2  * Automated Testing Framework (atf)
3  *
4  * Copyright (c) 2008 The NetBSD Foundation, Inc.
5  * All rights reserved.
6  *
7  * Redistribution and use in source and binary forms, with or without
8  * modification, are permitted provided that the following conditions
9  * are met:
10  * 1. Redistributions of source code must retain the above copyright
11  *    notice, this list of conditions and the following disclaimer.
12  * 2. Redistributions in binary form must reproduce the above copyright
13  *    notice, this list of conditions and the following disclaimer in the
14  *    documentation and/or other materials provided with the distribution.
15  *
16  * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND
17  * CONTRIBUTORS ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES,
18  * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
19  * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20  * IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS BE LIABLE FOR ANY
21  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
23  * GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
24  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER
25  * IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
26  * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN
27  * IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28  */
29 
30 #include <stdlib.h>
31 #include <string.h>
32 
33 #include "atf-c/error.h"
34 #include "atf-c/utils.h"
35 
36 #include "list.h"
37 #include "sanity.h"
38 
39 /* ---------------------------------------------------------------------
40  * Auxiliary functions.
41  * --------------------------------------------------------------------- */
42 
43 struct list_entry {
44     struct list_entry *m_prev;
45     struct list_entry *m_next;
46     void *m_object;
47     bool m_managed;
48 };
49 
50 static
51 atf_list_citer_t
52 entry_to_citer(const atf_list_t *l, const struct list_entry *le)
53 {
54     atf_list_citer_t iter;
55     iter.m_list = l;
56     iter.m_entry = le;
57     return iter;
58 }
59 
60 static
61 atf_list_iter_t
62 entry_to_iter(atf_list_t *l, struct list_entry *le)
63 {
64     atf_list_iter_t iter;
65     iter.m_list = l;
66     iter.m_entry = le;
67     return iter;
68 }
69 
70 static
71 struct list_entry *
72 new_entry(void *object, bool managed)
73 {
74     struct list_entry *le;
75 
76     le = (struct list_entry *)malloc(sizeof(*le));
77     if (le != NULL) {
78         le->m_prev = le->m_next = NULL;
79         le->m_object = object;
80         le->m_managed = managed;
81     } else
82         free(object);
83 
84     return le;
85 }
86 
87 static
88 void
89 delete_entry(struct list_entry *le)
90 {
91     if (le->m_managed)
92         free(le->m_object);
93 
94     free(le);
95 }
96 
97 static
98 struct list_entry *
99 new_entry_and_link(void *object, bool managed, struct list_entry *prev,
100                    struct list_entry *next)
101 {
102     struct list_entry *le;
103 
104     le = new_entry(object, managed);
105     if (le != NULL) {
106         le->m_prev = prev;
107         le->m_next = next;
108 
109         prev->m_next = le;
110         next->m_prev = le;
111     }
112 
113     return le;
114 }
115 
116 /* ---------------------------------------------------------------------
117  * The "atf_list_citer" type.
118  * --------------------------------------------------------------------- */
119 
120 /*
121  * Getters.
122  */
123 
124 const void *
125 atf_list_citer_data(const atf_list_citer_t citer)
126 {
127     const struct list_entry *le = citer.m_entry;
128     PRE(le != NULL);
129     return le->m_object;
130 }
131 
132 atf_list_citer_t
133 atf_list_citer_next(const atf_list_citer_t citer)
134 {
135     const struct list_entry *le = citer.m_entry;
136     atf_list_citer_t newciter;
137 
138     PRE(le != NULL);
139 
140     newciter = citer;
141     newciter.m_entry = le->m_next;
142 
143     return newciter;
144 }
145 
146 bool
147 atf_equal_list_citer_list_citer(const atf_list_citer_t i1,
148                                 const atf_list_citer_t i2)
149 {
150     return i1.m_list == i2.m_list && i1.m_entry == i2.m_entry;
151 }
152 
153 /* ---------------------------------------------------------------------
154  * The "atf_list_iter" type.
155  * --------------------------------------------------------------------- */
156 
157 /*
158  * Getters.
159  */
160 
161 void *
162 atf_list_iter_data(const atf_list_iter_t iter)
163 {
164     const struct list_entry *le = iter.m_entry;
165     PRE(le != NULL);
166     return le->m_object;
167 }
168 
169 atf_list_iter_t
170 atf_list_iter_next(const atf_list_iter_t iter)
171 {
172     const struct list_entry *le = iter.m_entry;
173     atf_list_iter_t newiter;
174 
175     PRE(le != NULL);
176 
177     newiter = iter;
178     newiter.m_entry = le->m_next;
179 
180     return newiter;
181 }
182 
183 bool
184 atf_equal_list_iter_list_iter(const atf_list_iter_t i1,
185                               const atf_list_iter_t i2)
186 {
187     return i1.m_list == i2.m_list && i1.m_entry == i2.m_entry;
188 }
189 
190 /* ---------------------------------------------------------------------
191  * The "atf_list" type.
192  * --------------------------------------------------------------------- */
193 
194 /*
195  * Constructors and destructors.
196  */
197 
198 atf_error_t
199 atf_list_init(atf_list_t *l)
200 {
201     struct list_entry *lebeg, *leend;
202 
203     lebeg = new_entry(NULL, false);
204     if (lebeg == NULL) {
205         return atf_no_memory_error();
206     }
207 
208     leend = new_entry(NULL, false);
209     if (leend == NULL) {
210         free(lebeg);
211         return atf_no_memory_error();
212     }
213 
214     lebeg->m_next = leend;
215     lebeg->m_prev = NULL;
216 
217     leend->m_next = NULL;
218     leend->m_prev = lebeg;
219 
220     l->m_size = 0;
221     l->m_begin = lebeg;
222     l->m_end = leend;
223 
224     return atf_no_error();
225 }
226 
227 void
228 atf_list_fini(atf_list_t *l)
229 {
230     struct list_entry *le;
231     size_t freed;
232 
233     le = (struct list_entry *)l->m_begin;
234     freed = 0;
235     while (le != NULL) {
236         struct list_entry *lenext;
237 
238         lenext = le->m_next;
239         delete_entry(le);
240         le = lenext;
241 
242         freed++;
243     }
244     INV(freed == l->m_size + 2);
245 }
246 
247 /*
248  * Getters.
249  */
250 
251 atf_list_iter_t
252 atf_list_begin(atf_list_t *l)
253 {
254     struct list_entry *le = l->m_begin;
255     return entry_to_iter(l, le->m_next);
256 }
257 
258 atf_list_citer_t
259 atf_list_begin_c(const atf_list_t *l)
260 {
261     const struct list_entry *le = l->m_begin;
262     return entry_to_citer(l, le->m_next);
263 }
264 
265 atf_list_iter_t
266 atf_list_end(atf_list_t *l)
267 {
268     return entry_to_iter(l, l->m_end);
269 }
270 
271 atf_list_citer_t
272 atf_list_end_c(const atf_list_t *l)
273 {
274     return entry_to_citer(l, l->m_end);
275 }
276 
277 void *
278 atf_list_index(atf_list_t *list, const size_t idx)
279 {
280     atf_list_iter_t iter;
281 
282     PRE(idx < atf_list_size(list));
283 
284     iter = atf_list_begin(list);
285     {
286         size_t pos = 0;
287         while (pos < idx &&
288                !atf_equal_list_iter_list_iter((iter), atf_list_end(list))) {
289             iter = atf_list_iter_next(iter);
290             pos++;
291         }
292     }
293     return atf_list_iter_data(iter);
294 }
295 
296 const void *
297 atf_list_index_c(const atf_list_t *list, const size_t idx)
298 {
299     atf_list_citer_t iter;
300 
301     PRE(idx < atf_list_size(list));
302 
303     iter = atf_list_begin_c(list);
304     {
305         size_t pos = 0;
306         while (pos < idx &&
307                !atf_equal_list_citer_list_citer((iter),
308                                                 atf_list_end_c(list))) {
309             iter = atf_list_citer_next(iter);
310             pos++;
311         }
312     }
313     return atf_list_citer_data(iter);
314 }
315 
316 size_t
317 atf_list_size(const atf_list_t *l)
318 {
319     return l->m_size;
320 }
321 
322 char **
323 atf_list_to_charpp(const atf_list_t *l)
324 {
325     char **array;
326     atf_list_citer_t iter;
327     size_t i;
328 
329     array = malloc(sizeof(char *) * (atf_list_size(l) + 1));
330     if (array == NULL)
331         goto out;
332 
333     i = 0;
334     atf_list_for_each_c(iter, l) {
335         array[i] = strdup((const char *)atf_list_citer_data(iter));
336         if (array[i] == NULL) {
337             atf_utils_free_charpp(array);
338             array = NULL;
339             goto out;
340         }
341 
342         i++;
343     }
344     array[i] = NULL;
345 
346 out:
347     return array;
348 }
349 
350 /*
351  * Modifiers.
352  */
353 
354 atf_error_t
355 atf_list_append(atf_list_t *l, void *data, bool managed)
356 {
357     struct list_entry *le, *next, *prev;
358     atf_error_t err;
359 
360     next = (struct list_entry *)l->m_end;
361     prev = next->m_prev;
362     le = new_entry_and_link(data, managed, prev, next);
363     if (le == NULL)
364         err = atf_no_memory_error();
365     else {
366         l->m_size++;
367         err = atf_no_error();
368     }
369 
370     return err;
371 }
372 
373 void
374 atf_list_append_list(atf_list_t *l, atf_list_t *src)
375 {
376     struct list_entry *e1, *e2, *ghost1, *ghost2;
377 
378     ghost1 = (struct list_entry *)l->m_end;
379     ghost2 = (struct list_entry *)src->m_begin;
380 
381     e1 = ghost1->m_prev;
382     e2 = ghost2->m_next;
383 
384     delete_entry(ghost1);
385     delete_entry(ghost2);
386 
387     e1->m_next = e2;
388     e2->m_prev = e1;
389 
390     l->m_end = src->m_end;
391     l->m_size += src->m_size;
392 }
393