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