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
43struct list_entry {
44    struct list_entry *m_prev;
45    struct list_entry *m_next;
46    void *m_object;
47    bool m_managed;
48};
49
50static
51atf_list_citer_t
52entry_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
60static
61atf_list_iter_t
62entry_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
70static
71struct list_entry *
72new_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
87static
88void
89delete_entry(struct list_entry *le)
90{
91    if (le->m_managed)
92        free(le->m_object);
93
94    free(le);
95}
96
97static
98struct list_entry *
99new_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
124const void *
125atf_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
132atf_list_citer_t
133atf_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
146bool
147atf_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
161void *
162atf_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
169atf_list_iter_t
170atf_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
183bool
184atf_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
198atf_error_t
199atf_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
227void
228atf_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
251atf_list_iter_t
252atf_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
258atf_list_citer_t
259atf_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
265atf_list_iter_t
266atf_list_end(atf_list_t *l)
267{
268    return entry_to_iter(l, l->m_end);
269}
270
271atf_list_citer_t
272atf_list_end_c(const atf_list_t *l)
273{
274    return entry_to_citer(l, l->m_end);
275}
276
277void *
278atf_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
296const void *
297atf_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
316size_t
317atf_list_size(const atf_list_t *l)
318{
319    return l->m_size;
320}
321
322char **
323atf_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
346out:
347    return array;
348}
349
350/*
351 * Modifiers.
352 */
353
354atf_error_t
355atf_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
373void
374atf_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