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