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