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
39struct list_entry {
40    struct list_entry *m_prev;
41    struct list_entry *m_next;
42    void *m_object;
43    bool m_managed;
44};
45
46static
47atf_list_citer_t
48entry_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
56static
57atf_list_iter_t
58entry_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
66static
67struct list_entry *
68new_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
78        free(object);
79
80    return le;
81}
82
83static
84void
85delete_entry(struct list_entry *le)
86{
87    if (le->m_managed)
88        free(le->m_object);
89
90    free(le);
91}
92
93static
94struct list_entry *
95new_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
120const void *
121atf_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
128atf_list_citer_t
129atf_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
142bool
143atf_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
157void *
158atf_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
165atf_list_iter_t
166atf_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
179bool
180atf_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
194atf_error_t
195atf_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
223void
224atf_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
247atf_list_iter_t
248atf_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
254atf_list_citer_t
255atf_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
261atf_list_iter_t
262atf_list_end(atf_list_t *l)
263{
264    return entry_to_iter(l, l->m_end);
265}
266
267atf_list_citer_t
268atf_list_end_c(const atf_list_t *l)
269{
270    return entry_to_citer(l, l->m_end);
271}
272
273void *
274atf_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
292const void *
293atf_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
312size_t
313atf_list_size(const atf_list_t *l)
314{
315    return l->m_size;
316}
317
318char **
319atf_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
342out:
343    return array;
344}
345
346/*
347 * Modifiers.
348 */
349
350atf_error_t
351atf_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
369void
370atf_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