1 /******************************************************************************
2  *
3  *  Copyright 2016 Google, Inc.
4  *
5  *  Licensed under the Apache License, Version 2.0 (the "License");
6  *  you may not use this file except in compliance with the License.
7  *  You may obtain a copy of the License at:
8  *
9  *  http://www.apache.org/licenses/LICENSE-2.0
10  *
11  *  Unless required by applicable law or agreed to in writing, software
12  *  distributed under the License is distributed on an "AS IS" BASIS,
13  *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14  *  See the License for the specific language governing permissions and
15  *  limitations under the License.
16  *
17  ******************************************************************************/
18 
19 #pragma once
20 
21 #include <stdbool.h>
22 #include <stdlib.h>
23 
24 struct list_node_t;
25 typedef struct list_node_t list_node_t;
26 
27 struct list_t;
28 typedef struct list_t list_t;
29 
30 typedef void (*list_free_cb)(void* data);
31 
32 // Iterator callback prototype used for |list_foreach|.
33 // |data| represents the list item currently being iterated, |context| is a
34 // user defined value passed into |list_foreach|.
35 // Callback must return true to continue iterating or false to stop iterating.
36 typedef bool (*list_iter_cb)(void* data, void* context);
37 
38 // Returns a new, empty list. Returns NULL if not enough memory could be
39 // allocated for the list structure. The returned list must be freed with
40 // |list_free|. The |callback| specifies a function to be called whenever a
41 // list element is removed from the list. It can be used to release resources
42 // held by the list element, e.g. memory or file descriptor. |callback| may
43 // be NULL if no cleanup is necessary on element removal.
44 list_t* list_new(list_free_cb callback);
45 
46 // Frees the list. This function accepts NULL as an argument, in which case it
47 // behaves like a no-op.
48 void list_free(list_t* list);
49 
50 // Returns true if |list| is empty (has no elements), false otherwise.
51 // |list| may not be NULL.
52 bool list_is_empty(const list_t* list);
53 
54 // Returns true if the list contains |data|, false otherwise.
55 // |list| may not be NULL.
56 bool list_contains(const list_t* list, const void* data);
57 
58 // Returns the length of the |list|. |list| may not be NULL.
59 size_t list_length(const list_t* list);
60 
61 // Returns the first element in the list without removing it. |list| may not
62 // be NULL or empty.
63 void* list_front(const list_t* list);
64 
65 // Returns the last element in the list without removing it. |list| may not
66 // be NULL or empty.
67 void* list_back(const list_t* list);
68 
69 // Returns the last node in the list without removing it. |list| may not
70 // be NULL or empty.
71 list_node_t* list_back_node(const list_t* list);
72 
73 // Inserts |data| after |prev_node| in |list|. |data|, |list|, and |prev_node|
74 // may not be NULL. This function does not make a copy of |data| so the pointer
75 // must remain valid at least until the element is removed from the list or the
76 // list is freed. Returns true if |data| could be inserted, false otherwise
77 // (e.g. out of memory).
78 bool list_insert_after(list_t* list, list_node_t* prev_node, void* data);
79 
80 // Inserts |data| at the beginning of |list|. Neither |data| nor |list| may be
81 // NULL.
82 // This function does not make a copy of |data| so the pointer must remain valid
83 // at least until the element is removed from the list or the list is freed.
84 // Returns true if |data| could be inserted, false otherwise (e.g. out of
85 // memory).
86 bool list_prepend(list_t* list, void* data);
87 
88 // Inserts |data| at the end of |list|. Neither |data| nor |list| may be NULL.
89 // This function does not make a copy of |data| so the pointer must remain valid
90 // at least until the element is removed from the list or the list is freed.
91 // Returns true if |data| could be inserted, false otherwise (e.g. out of
92 // memory).
93 bool list_append(list_t* list, void* data);
94 
95 // Removes |data| from the list. Neither |list| nor |data| may be NULL. If
96 // |data|
97 // is inserted multiple times in the list, this function will only remove the
98 // first instance. If a free function was specified in |list_new|, it will be
99 // called back with |data|. This function returns true if |data| was found in
100 // the list and removed, false otherwise.
101 bool list_remove(list_t* list, void* data);
102 
103 // Removes all elements in the list. Calling this function will return the list
104 // to the
105 // same state it was in after |list_new|. |list| may not be NULL.
106 void list_clear(list_t* list);
107 
108 // Iterates through the |list| and calls |callback| for each data element.
109 // Iteration continues until |callback| returns false. The function returns the
110 // pointer to last processed element, or NULL if the list is empty, or all calls
111 // to |callback| returned true. |context| is passed to |callback| on each
112 // iteration.
113 // If the list is empty, |callback| will never be called. It is safe to mutate
114 // the list inside the callback. If an element is added before the node being
115 // visited, there will be no callback for the newly-inserted node. Neither
116 // |list| nor |callback| may be NULL.
117 list_node_t* list_foreach(const list_t* list, list_iter_cb callback,
118                           void* context);
119 
120 // Returns an iterator to the first element in |list|. |list| may not be NULL.
121 // The returned iterator is valid as long as it does not equal the value
122 // returned by |list_end|.
123 list_node_t* list_begin(const list_t* list);
124 
125 // Returns an iterator that points past the end of the list. In other words,
126 // this function returns the value of an invalid iterator for the given list.
127 // When an iterator has the same value as what's returned by this function, you
128 // may no longer call |list_next| with the iterator. |list| may not be NULL.
129 list_node_t* list_end(const list_t* list);
130 
131 // Given a valid iterator |node|, this function returns the next value for the
132 // iterator. If the returned value equals the value returned by |list_end|, the
133 // iterator has reached the end of the list and may no longer be used for any
134 // purpose.
135 list_node_t* list_next(const list_node_t* node);
136 
137 // Returns the value stored at the location pointed to by the iterator |node|.
138 // |node| must not equal the value returned by |list_end|.
139 void* list_node(const list_node_t* node);
140