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/* Bog standard singly-linked-list implementation. */
14
15#pragma once
16
17#include <stdbool.h>
18
19/* Type of a linked-list. */
20typedef struct {
21    struct list_node *head;
22} list_t;
23
24/* Create a new linked-list. Returns 0 on success. */
25int list_init(list_t *l);
26
27/* Prepend a value to the list. In general, prefer this to appending if order
28 * of the elements is not relevant as prepending is faster. Returns 0 on
29 * success.
30 */
31int list_prepend(list_t *l, void *data);
32
33/* Append a value to the list. Returns 0 on success. */
34int list_append(list_t *l, void *data);
35
36/* Returns true if the given list contains no elements. */
37bool list_is_empty(list_t *l);
38
39/* Returns true if the given element is in the list. The third argument is a
40 * comparator to determine list element equality.
41 */
42bool list_exists(list_t *l, void *data, int(*cmp)(void *, void *));
43
44/* Returns the number of elements in the list. */
45int list_length(list_t *l);
46
47/* Returns the index of the given element in the list or -1 if the element is
48 * not found.
49 */
50int list_index(list_t *l, void *data, int(*cmp)(void *, void *));
51
52/* Call the given function on every list element. While traversing the list, if
53 * the caller's action ever returns non-zero the traversal is aborted and that
54 * value is returned. If traversal completes, this function returns 0.
55 */
56int list_foreach(list_t *l, int(*action)(void *, void *), void *token);
57
58/* Remove the given element from the list. Returns non-zero if the element is
59 * not found.
60 */
61int list_remove(list_t *l, void *data, int(*cmp)(void *, void *));
62
63/* Remove all elements from the list. Returns 0 on success. */
64int list_remove_all(list_t *l);
65
66/* Destroy the list. The caller is expected to have previously removed all
67 * elements of the list. Returns 0 on success.
68 */
69int list_destroy(list_t *l);
70
71/* Below various equivalents of operations above are provided, but that take a
72 * caller-constructed node. The purpose of these is to allow you to
73 * stack-/statically-allocate nodes when you have no dynamic memory.
74 */
75
76/* Internal structure of the node of list. */
77struct list_node {
78    void *data;
79    struct list_node *next;
80};
81
82int list_prepend_node(list_t *l, struct list_node *node);
83int list_append_node(list_t *l, struct list_node *node);
84int list_remove_node(list_t *l, void *data, int(*cmp)(void *, void *));
85int list_remove_all_nodes(list_t *l);
86