1/*
2 * Copyright 2017, Data61
3 * Commonwealth Scientific and Industrial Research Organisation (CSIRO)
4 * ABN 41 687 119 230.
5 *
6 * This software may be distributed and modified according to the terms of
7 * the BSD 2-Clause license. Note that NO WARRANTY is provided.
8 * See "LICENSE_BSD2.txt" for details.
9 *
10 * @TAG(DATA61_BSD)
11 */
12
13#include <assert.h>
14#include <stdbool.h>
15#include <stdlib.h>
16#include <utils/list.h>
17
18typedef struct list_node node_t;
19
20int list_init(list_t *l)
21{
22    assert(l != NULL);
23    l->head = NULL;
24    return 0;
25}
26
27static node_t *make_node(void *data)
28{
29    node_t *n = malloc(sizeof(*n));
30    if (n != NULL) {
31        n->data = data;
32        n->next = NULL;
33    }
34    return n;
35}
36
37int list_prepend(list_t *l, void *data)
38{
39    node_t *n = make_node(data);
40    if (n == NULL) {
41        return -1;
42    }
43    return list_prepend_node(l, n);
44}
45
46int list_append(list_t *l, void *data)
47{
48    node_t *n = make_node(data);
49    if (n == NULL) {
50        return -1;
51    }
52    return list_append_node(l, n);
53}
54
55bool list_is_empty(list_t *l)
56{
57    assert(l != NULL);
58    return l->head == NULL;
59}
60
61bool list_exists(list_t *l, void *data, int(*cmp)(void *, void *))
62{
63    assert(l != NULL);
64    for (node_t *n = l->head; n != NULL; n = n->next) {
65        if (!cmp(n->data, data)) {
66            return true;
67        }
68    }
69    return false;
70}
71
72int list_length(list_t *l)
73{
74    assert(l != NULL);
75    int i = 0;
76    for (node_t *n = l->head; n != NULL; n = n->next) {
77        i++;
78    }
79    return i;
80}
81
82int list_index(list_t *l, void *data, int(*cmp)(void *, void *))
83{
84    assert(l != NULL);
85    int i = 0;
86    for (node_t *n = l->head; n != NULL; n = n->next, i++) {
87        if (!cmp(n->data, data)) {
88            return i;
89        }
90    }
91    return -1;
92}
93
94int list_foreach(list_t *l, int(*action)(void *, void *), void *token)
95{
96    assert(l != NULL);
97    for (node_t *n = l->head; n != NULL; n = n->next) {
98        int res = action(n->data, token);
99        if (res != 0) {
100            return res;
101        }
102    }
103    return 0;
104}
105
106static int remove(list_t *l, void *data, int (*cmp)(void *, void *),
107                  bool should_free)
108{
109    assert(l != NULL);
110    for (node_t *prev = NULL, *n = l->head; n != NULL; prev = n, n = n->next) {
111        if (!cmp(n->data, data)) {
112            if (prev == NULL) {
113                /* Removing the list head. */
114                l->head = n->next;
115            } else {
116                prev->next = n->next;
117            }
118            if (should_free) {
119                free(n);
120            }
121            return 0;
122        }
123    }
124    return -1;
125}
126
127int list_remove(list_t *l, void *data, int(*cmp)(void *, void *))
128{
129    return remove(l, data, cmp, true);
130}
131
132int list_remove_all(list_t *l)
133{
134    assert(l != NULL);
135    for (node_t *n = l->head; n != NULL;) {
136        node_t *temp = n->next;
137        free(n);
138        n = temp;
139    }
140    l->head = NULL;
141    return 0;
142}
143
144int list_destroy(list_t *l)
145{
146    /* Nothing required. */
147    return 0;
148}
149
150int list_prepend_node(list_t *l, node_t *node)
151{
152    assert(l != NULL);
153    assert(node != NULL);
154    node->next = l->head;
155    l->head = node;
156    return 0;
157}
158
159int list_append_node(list_t *l, node_t *node)
160{
161    assert(l != NULL);
162    assert(node != NULL);
163    node->next = NULL;
164    if (l->head == NULL) {
165        l->head = node;
166    } else {
167        node_t *end;
168        for (end = l->head; end->next != NULL; end = end->next);
169        end->next = node;
170    }
171    return 0;
172}
173
174int list_remove_node(list_t *l, void *data, int(*cmp)(void *, void *))
175{
176    return remove(l, data, cmp, false);
177}
178
179int list_remove_all_nodes(list_t *l)
180{
181    assert(l != NULL);
182    l->head = NULL;
183    return 0;
184}
185