1 | #ifndef AWS_COMMON_LINKED_LIST_H |
2 | #define AWS_COMMON_LINKED_LIST_H |
3 | |
4 | /* |
5 | * Copyright 2010-2018 Amazon.com, Inc. or its affiliates. All Rights Reserved. |
6 | * |
7 | * Licensed under the Apache License, Version 2.0 (the "License"). |
8 | * You may not use this file except in compliance with the License. |
9 | * A copy of the License is located at |
10 | * |
11 | * http://aws.amazon.com/apache2.0 |
12 | * |
13 | * or in the "license" file accompanying this file. This file is distributed |
14 | * on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either |
15 | * express or implied. See the License for the specific language governing |
16 | * permissions and limitations under the License. |
17 | */ |
18 | |
19 | #include <aws/common/common.h> |
20 | |
21 | #include <stddef.h> |
22 | |
23 | struct aws_linked_list_node { |
24 | struct aws_linked_list_node *next; |
25 | struct aws_linked_list_node *prev; |
26 | }; |
27 | |
28 | struct aws_linked_list { |
29 | struct aws_linked_list_node head; |
30 | struct aws_linked_list_node tail; |
31 | }; |
32 | |
33 | AWS_EXTERN_C_BEGIN |
34 | |
35 | /** |
36 | * Set node's next and prev pointers to NULL. |
37 | */ |
38 | AWS_STATIC_IMPL void aws_linked_list_node_reset(struct aws_linked_list_node *node); |
39 | |
40 | /** |
41 | * These functions need to be defined first as they are used in pre |
42 | * and post conditions. |
43 | */ |
44 | |
45 | /** |
46 | * Tests if the list is empty. |
47 | */ |
48 | AWS_STATIC_IMPL bool aws_linked_list_empty(const struct aws_linked_list *list); |
49 | |
50 | /** |
51 | * Checks that a linked list is valid. |
52 | */ |
53 | AWS_STATIC_IMPL bool aws_linked_list_is_valid(const struct aws_linked_list *list); |
54 | /** |
55 | * Checks that the prev of the next pointer of a node points to the |
56 | * node. As this checks whether the [next] connection of a node is |
57 | * bidirectional, it returns false if used for the list tail. |
58 | */ |
59 | AWS_STATIC_IMPL bool aws_linked_list_node_next_is_valid(const struct aws_linked_list_node *node); |
60 | |
61 | /** |
62 | * Checks that the next of the prev pointer of a node points to the |
63 | * node. Similarly to the above, this returns false if used for the |
64 | * head of a list. |
65 | */ |
66 | AWS_STATIC_IMPL bool aws_linked_list_node_prev_is_valid(const struct aws_linked_list_node *node); |
67 | /** |
68 | * Checks that a linked list satisfies double linked list connectivity |
69 | * constraints. This check is O(n) as it traverses the whole linked |
70 | * list to ensure that tail is reachable from head (and vice versa) |
71 | * and that every connection is bidirectional. |
72 | * |
73 | * Note: This check *cannot* go into an infinite loop, because we |
74 | * ensure that the connection to the next node is |
75 | * bidirectional. Therefore, if a node's [a] a.next is a previous node |
76 | * [b] in the list, b.prev != &a and so this check would fail, thus |
77 | * terminating the loop. |
78 | */ |
79 | AWS_STATIC_IMPL bool aws_linked_list_is_valid_deep(const struct aws_linked_list *list); |
80 | |
81 | /** |
82 | * Initializes the list. List will be empty after this call. |
83 | */ |
84 | AWS_STATIC_IMPL void aws_linked_list_init(struct aws_linked_list *list); |
85 | |
86 | /** |
87 | * Returns an iteration pointer for the first element in the list. |
88 | */ |
89 | AWS_STATIC_IMPL struct aws_linked_list_node *aws_linked_list_begin(const struct aws_linked_list *list); |
90 | |
91 | /** |
92 | * Returns an iteration pointer for one past the last element in the list. |
93 | */ |
94 | AWS_STATIC_IMPL const struct aws_linked_list_node *aws_linked_list_end(const struct aws_linked_list *list); |
95 | |
96 | /** |
97 | * Returns a pointer for the last element in the list. |
98 | * Used to begin iterating the list in reverse. Ex: |
99 | * for (i = aws_linked_list_rbegin(list); i != aws_linked_list_rend(list); i = aws_linked_list_prev(i)) {...} |
100 | */ |
101 | AWS_STATIC_IMPL struct aws_linked_list_node *aws_linked_list_rbegin(const struct aws_linked_list *list); |
102 | |
103 | /** |
104 | * Returns the pointer to one before the first element in the list. |
105 | * Used to end iterating the list in reverse. |
106 | */ |
107 | AWS_STATIC_IMPL const struct aws_linked_list_node *aws_linked_list_rend(const struct aws_linked_list *list); |
108 | |
109 | /** |
110 | * Returns the next element in the list. |
111 | */ |
112 | AWS_STATIC_IMPL struct aws_linked_list_node *aws_linked_list_next(const struct aws_linked_list_node *node); |
113 | |
114 | /** |
115 | * Returns the previous element in the list. |
116 | */ |
117 | AWS_STATIC_IMPL struct aws_linked_list_node *aws_linked_list_prev(const struct aws_linked_list_node *node); |
118 | |
119 | /** |
120 | * Inserts to_add immediately after after. |
121 | */ |
122 | AWS_STATIC_IMPL void aws_linked_list_insert_after( |
123 | struct aws_linked_list_node *after, |
124 | struct aws_linked_list_node *to_add); |
125 | /** |
126 | * Swaps the order two nodes in the linked list. |
127 | */ |
128 | AWS_STATIC_IMPL void aws_linked_list_swap_nodes(struct aws_linked_list_node *a, struct aws_linked_list_node *b); |
129 | |
130 | /** |
131 | * Inserts to_add immediately before before. |
132 | */ |
133 | AWS_STATIC_IMPL void aws_linked_list_insert_before( |
134 | struct aws_linked_list_node *before, |
135 | struct aws_linked_list_node *to_add); |
136 | |
137 | /** |
138 | * Removes the specified node from the list (prev/next point to each other) and |
139 | * returns the next node in the list. |
140 | */ |
141 | AWS_STATIC_IMPL void aws_linked_list_remove(struct aws_linked_list_node *node); |
142 | |
143 | /** |
144 | * Append new_node. |
145 | */ |
146 | AWS_STATIC_IMPL void aws_linked_list_push_back(struct aws_linked_list *list, struct aws_linked_list_node *node); |
147 | |
148 | /** |
149 | * Returns the element in the back of the list. |
150 | */ |
151 | AWS_STATIC_IMPL struct aws_linked_list_node *aws_linked_list_back(const struct aws_linked_list *list); |
152 | |
153 | /** |
154 | * Returns the element in the back of the list and removes it |
155 | */ |
156 | AWS_STATIC_IMPL struct aws_linked_list_node *aws_linked_list_pop_back(struct aws_linked_list *list); |
157 | |
158 | /** |
159 | * Prepend new_node. |
160 | */ |
161 | AWS_STATIC_IMPL void aws_linked_list_push_front(struct aws_linked_list *list, struct aws_linked_list_node *node); |
162 | /** |
163 | * Returns the element in the front of the list. |
164 | */ |
165 | AWS_STATIC_IMPL struct aws_linked_list_node *aws_linked_list_front(const struct aws_linked_list *list); |
166 | /** |
167 | * Returns the element in the front of the list and removes it |
168 | */ |
169 | AWS_STATIC_IMPL struct aws_linked_list_node *aws_linked_list_pop_front(struct aws_linked_list *list); |
170 | |
171 | AWS_STATIC_IMPL void aws_linked_list_swap_contents(struct aws_linked_list *a, struct aws_linked_list *b); |
172 | |
173 | #ifndef AWS_NO_STATIC_IMPL |
174 | # include <aws/common/linked_list.inl> |
175 | #endif /* AWS_NO_STATIC_IMPL */ |
176 | AWS_EXTERN_C_END |
177 | |
178 | #endif /* AWS_COMMON_LINKED_LIST_H */ |
179 | |