1 | #ifndef AWS_COMMON_LINKED_LIST_INL |
2 | #define AWS_COMMON_LINKED_LIST_INL |
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 | #include <aws/common/linked_list.h> |
21 | #include <stddef.h> |
22 | |
23 | AWS_EXTERN_C_BEGIN |
24 | |
25 | /** |
26 | * Set node's next and prev pointers to NULL. |
27 | */ |
28 | AWS_STATIC_IMPL void aws_linked_list_node_reset(struct aws_linked_list_node *node) { |
29 | AWS_PRECONDITION(node != NULL); |
30 | AWS_ZERO_STRUCT(*node); |
31 | AWS_POSTCONDITION(AWS_IS_ZEROED(*node)); |
32 | } |
33 | |
34 | /** |
35 | * These functions need to be defined first as they are used in pre |
36 | * and post conditions. |
37 | */ |
38 | |
39 | /** |
40 | * Tests if the list is empty. |
41 | */ |
42 | AWS_STATIC_IMPL bool aws_linked_list_empty(const struct aws_linked_list *list) { |
43 | AWS_PRECONDITION(list); |
44 | return list->head.next == &list->tail; |
45 | } |
46 | |
47 | /** |
48 | * Checks that a linked list is valid. |
49 | */ |
50 | AWS_STATIC_IMPL bool aws_linked_list_is_valid(const struct aws_linked_list *list) { |
51 | if (list && list->head.next && list->head.prev == NULL && list->tail.prev && list->tail.next == NULL) { |
52 | #if (AWS_DEEP_CHECKS == 1) |
53 | return aws_linked_list_is_valid_deep(list); |
54 | #else |
55 | return true; |
56 | #endif |
57 | } |
58 | return false; |
59 | } |
60 | |
61 | /** |
62 | * Checks that the prev of the next pointer of a node points to the |
63 | * node. As this checks whether the [next] connection of a node is |
64 | * bidirectional, it returns false if used for the list tail. |
65 | */ |
66 | AWS_STATIC_IMPL bool aws_linked_list_node_next_is_valid(const struct aws_linked_list_node *node) { |
67 | return node && node->next && node->next->prev == node; |
68 | } |
69 | |
70 | /** |
71 | * Checks that the next of the prev pointer of a node points to the |
72 | * node. Similarly to the above, this returns false if used for the |
73 | * head of a list. |
74 | */ |
75 | AWS_STATIC_IMPL bool aws_linked_list_node_prev_is_valid(const struct aws_linked_list_node *node) { |
76 | return node && node->prev && node->prev->next == node; |
77 | } |
78 | |
79 | /** |
80 | * Checks that a linked list satisfies double linked list connectivity |
81 | * constraints. This check is O(n) as it traverses the whole linked |
82 | * list to ensure that tail is reachable from head (and vice versa) |
83 | * and that every connection is bidirectional. |
84 | * |
85 | * Note: This check *cannot* go into an infinite loop, because we |
86 | * ensure that the connection to the next node is |
87 | * bidirectional. Therefore, if a node's [a] a.next is a previous node |
88 | * [b] in the list, b.prev != &a and so this check would fail, thus |
89 | * terminating the loop. |
90 | */ |
91 | AWS_STATIC_IMPL bool aws_linked_list_is_valid_deep(const struct aws_linked_list *list) { |
92 | if (!list) { |
93 | return false; |
94 | } |
95 | /* This could go into an infinite loop for a circular list */ |
96 | const struct aws_linked_list_node *temp = &list->head; |
97 | /* Head must reach tail by following next pointers */ |
98 | bool head_reaches_tail = false; |
99 | /* By satisfying the above and that edges are bidirectional, we |
100 | * also guarantee that tail reaches head by following prev |
101 | * pointers */ |
102 | while (temp) { |
103 | if (temp == &list->tail) { |
104 | head_reaches_tail = true; |
105 | break; |
106 | } else if (!aws_linked_list_node_next_is_valid(temp)) { |
107 | /* Next and prev pointers should connect the same nodes */ |
108 | return false; |
109 | } |
110 | temp = temp->next; |
111 | } |
112 | return head_reaches_tail; |
113 | } |
114 | |
115 | /** |
116 | * Initializes the list. List will be empty after this call. |
117 | */ |
118 | AWS_STATIC_IMPL void aws_linked_list_init(struct aws_linked_list *list) { |
119 | AWS_PRECONDITION(list); |
120 | list->head.next = &list->tail; |
121 | list->head.prev = NULL; |
122 | list->tail.prev = &list->head; |
123 | list->tail.next = NULL; |
124 | AWS_POSTCONDITION(aws_linked_list_is_valid(list)); |
125 | AWS_POSTCONDITION(aws_linked_list_empty(list)); |
126 | } |
127 | |
128 | /** |
129 | * Returns an iteration pointer for the first element in the list. |
130 | */ |
131 | AWS_STATIC_IMPL struct aws_linked_list_node *aws_linked_list_begin(const struct aws_linked_list *list) { |
132 | AWS_PRECONDITION(aws_linked_list_is_valid(list)); |
133 | struct aws_linked_list_node *rval = list->head.next; |
134 | AWS_POSTCONDITION(aws_linked_list_is_valid(list)); |
135 | AWS_POSTCONDITION(rval == list->head.next); |
136 | return rval; |
137 | } |
138 | |
139 | /** |
140 | * Returns an iteration pointer for one past the last element in the list. |
141 | */ |
142 | AWS_STATIC_IMPL const struct aws_linked_list_node *aws_linked_list_end(const struct aws_linked_list *list) { |
143 | AWS_PRECONDITION(aws_linked_list_is_valid(list)); |
144 | const struct aws_linked_list_node *rval = &list->tail; |
145 | AWS_POSTCONDITION(aws_linked_list_is_valid(list)); |
146 | AWS_POSTCONDITION(rval == &list->tail); |
147 | return rval; |
148 | } |
149 | |
150 | /** |
151 | * Returns a pointer for the last element in the list. |
152 | * Used to begin iterating the list in reverse. Ex: |
153 | * for (i = aws_linked_list_rbegin(list); i != aws_linked_list_rend(list); i = aws_linked_list_prev(i)) {...} |
154 | */ |
155 | AWS_STATIC_IMPL struct aws_linked_list_node *aws_linked_list_rbegin(const struct aws_linked_list *list) { |
156 | AWS_PRECONDITION(aws_linked_list_is_valid(list)); |
157 | struct aws_linked_list_node *rval = list->tail.prev; |
158 | AWS_POSTCONDITION(aws_linked_list_is_valid(list)); |
159 | AWS_POSTCONDITION(rval == list->tail.prev); |
160 | return rval; |
161 | } |
162 | |
163 | /** |
164 | * Returns the pointer to one before the first element in the list. |
165 | * Used to end iterating the list in reverse. |
166 | */ |
167 | AWS_STATIC_IMPL const struct aws_linked_list_node *aws_linked_list_rend(const struct aws_linked_list *list) { |
168 | AWS_PRECONDITION(aws_linked_list_is_valid(list)); |
169 | const struct aws_linked_list_node *rval = &list->head; |
170 | AWS_POSTCONDITION(aws_linked_list_is_valid(list)); |
171 | AWS_POSTCONDITION(rval == &list->head); |
172 | return rval; |
173 | } |
174 | |
175 | /** |
176 | * Returns the next element in the list. |
177 | */ |
178 | AWS_STATIC_IMPL struct aws_linked_list_node *aws_linked_list_next(const struct aws_linked_list_node *node) { |
179 | AWS_PRECONDITION(aws_linked_list_node_next_is_valid(node)); |
180 | struct aws_linked_list_node *rval = node->next; |
181 | AWS_POSTCONDITION(aws_linked_list_node_next_is_valid(node)); |
182 | AWS_POSTCONDITION(aws_linked_list_node_prev_is_valid(rval)); |
183 | AWS_POSTCONDITION(rval == node->next); |
184 | return rval; |
185 | } |
186 | |
187 | /** |
188 | * Returns the previous element in the list. |
189 | */ |
190 | AWS_STATIC_IMPL struct aws_linked_list_node *aws_linked_list_prev(const struct aws_linked_list_node *node) { |
191 | AWS_PRECONDITION(aws_linked_list_node_prev_is_valid(node)); |
192 | struct aws_linked_list_node *rval = node->prev; |
193 | AWS_POSTCONDITION(aws_linked_list_node_prev_is_valid(node)); |
194 | AWS_POSTCONDITION(aws_linked_list_node_next_is_valid(rval)); |
195 | AWS_POSTCONDITION(rval == node->prev); |
196 | return rval; |
197 | } |
198 | |
199 | /** |
200 | * Inserts to_add immediately after after. |
201 | */ |
202 | AWS_STATIC_IMPL void aws_linked_list_insert_after( |
203 | struct aws_linked_list_node *after, |
204 | struct aws_linked_list_node *to_add) { |
205 | AWS_PRECONDITION(aws_linked_list_node_next_is_valid(after)); |
206 | AWS_PRECONDITION(to_add != NULL); |
207 | to_add->prev = after; |
208 | to_add->next = after->next; |
209 | after->next->prev = to_add; |
210 | after->next = to_add; |
211 | AWS_POSTCONDITION(aws_linked_list_node_next_is_valid(after)); |
212 | AWS_POSTCONDITION(aws_linked_list_node_prev_is_valid(to_add)); |
213 | AWS_POSTCONDITION(aws_linked_list_node_next_is_valid(to_add)); |
214 | AWS_POSTCONDITION(after->next == to_add); |
215 | } |
216 | |
217 | /** |
218 | * Swaps the order two nodes in the linked list. |
219 | */ |
220 | AWS_STATIC_IMPL void aws_linked_list_swap_nodes(struct aws_linked_list_node *a, struct aws_linked_list_node *b) { |
221 | AWS_PRECONDITION(aws_linked_list_node_prev_is_valid(a)); |
222 | AWS_PRECONDITION(aws_linked_list_node_next_is_valid(a)); |
223 | AWS_PRECONDITION(aws_linked_list_node_prev_is_valid(b)); |
224 | AWS_PRECONDITION(aws_linked_list_node_next_is_valid(b)); |
225 | |
226 | if (a == b) { |
227 | return; |
228 | } |
229 | |
230 | /* snapshot b's value to avoid clobbering its next/prev pointers if a/b are adjacent */ |
231 | struct aws_linked_list_node tmp = *b; |
232 | a->prev->next = b; |
233 | a->next->prev = b; |
234 | |
235 | tmp.prev->next = a; |
236 | tmp.next->prev = a; |
237 | |
238 | tmp = *a; |
239 | *a = *b; |
240 | *b = tmp; |
241 | |
242 | AWS_POSTCONDITION(aws_linked_list_node_prev_is_valid(a)); |
243 | AWS_POSTCONDITION(aws_linked_list_node_next_is_valid(a)); |
244 | AWS_POSTCONDITION(aws_linked_list_node_prev_is_valid(b)); |
245 | AWS_POSTCONDITION(aws_linked_list_node_next_is_valid(b)); |
246 | } |
247 | |
248 | /** |
249 | * Inserts to_add immediately before before. |
250 | */ |
251 | AWS_STATIC_IMPL void aws_linked_list_insert_before( |
252 | struct aws_linked_list_node *before, |
253 | struct aws_linked_list_node *to_add) { |
254 | AWS_PRECONDITION(aws_linked_list_node_prev_is_valid(before)); |
255 | AWS_PRECONDITION(to_add != NULL); |
256 | to_add->next = before; |
257 | to_add->prev = before->prev; |
258 | before->prev->next = to_add; |
259 | before->prev = to_add; |
260 | AWS_POSTCONDITION(aws_linked_list_node_prev_is_valid(before)); |
261 | AWS_POSTCONDITION(aws_linked_list_node_prev_is_valid(to_add)); |
262 | AWS_POSTCONDITION(aws_linked_list_node_next_is_valid(to_add)); |
263 | AWS_POSTCONDITION(before->prev == to_add); |
264 | } |
265 | |
266 | /** |
267 | * Removes the specified node from the list (prev/next point to each other) and |
268 | * returns the next node in the list. |
269 | */ |
270 | AWS_STATIC_IMPL void aws_linked_list_remove(struct aws_linked_list_node *node) { |
271 | AWS_PRECONDITION(aws_linked_list_node_prev_is_valid(node)); |
272 | AWS_PRECONDITION(aws_linked_list_node_next_is_valid(node)); |
273 | node->prev->next = node->next; |
274 | node->next->prev = node->prev; |
275 | aws_linked_list_node_reset(node); |
276 | AWS_POSTCONDITION(node->next == NULL && node->prev == NULL); |
277 | } |
278 | |
279 | /** |
280 | * Append new_node. |
281 | */ |
282 | AWS_STATIC_IMPL void aws_linked_list_push_back(struct aws_linked_list *list, struct aws_linked_list_node *node) { |
283 | AWS_PRECONDITION(aws_linked_list_is_valid(list)); |
284 | AWS_PRECONDITION(node != NULL); |
285 | aws_linked_list_insert_before(&list->tail, node); |
286 | AWS_POSTCONDITION(aws_linked_list_is_valid(list)); |
287 | AWS_POSTCONDITION(list->tail.prev == node, "[node] is the new last element of [list]" ); |
288 | } |
289 | |
290 | /** |
291 | * Returns the element in the back of the list. |
292 | */ |
293 | AWS_STATIC_IMPL struct aws_linked_list_node *aws_linked_list_back(const struct aws_linked_list *list) { |
294 | AWS_PRECONDITION(aws_linked_list_is_valid(list)); |
295 | AWS_PRECONDITION(!aws_linked_list_empty(list)); |
296 | struct aws_linked_list_node *rval = list->tail.prev; |
297 | AWS_POSTCONDITION(aws_linked_list_is_valid(list)); |
298 | AWS_POSTCONDITION(aws_linked_list_node_prev_is_valid(rval)); |
299 | AWS_POSTCONDITION(aws_linked_list_node_next_is_valid(rval)); |
300 | return rval; |
301 | } |
302 | |
303 | /** |
304 | * Returns the element in the back of the list and removes it |
305 | */ |
306 | AWS_STATIC_IMPL struct aws_linked_list_node *aws_linked_list_pop_back(struct aws_linked_list *list) { |
307 | AWS_PRECONDITION(!aws_linked_list_empty(list)); |
308 | AWS_PRECONDITION(aws_linked_list_is_valid(list)); |
309 | struct aws_linked_list_node *back = aws_linked_list_back(list); |
310 | aws_linked_list_remove(back); |
311 | AWS_POSTCONDITION(back->next == NULL && back->prev == NULL); |
312 | AWS_POSTCONDITION(aws_linked_list_is_valid(list)); |
313 | return back; |
314 | } |
315 | |
316 | /** |
317 | * Prepend new_node. |
318 | */ |
319 | AWS_STATIC_IMPL void aws_linked_list_push_front(struct aws_linked_list *list, struct aws_linked_list_node *node) { |
320 | AWS_PRECONDITION(aws_linked_list_is_valid(list)); |
321 | AWS_PRECONDITION(node != NULL); |
322 | aws_linked_list_insert_before(list->head.next, node); |
323 | AWS_POSTCONDITION(aws_linked_list_is_valid(list)); |
324 | AWS_POSTCONDITION(list->head.next == node, "[node] is the new first element of [list]" ); |
325 | } |
326 | |
327 | /** |
328 | * Returns the element in the front of the list. |
329 | */ |
330 | AWS_STATIC_IMPL struct aws_linked_list_node *aws_linked_list_front(const struct aws_linked_list *list) { |
331 | AWS_PRECONDITION(aws_linked_list_is_valid(list)); |
332 | AWS_PRECONDITION(!aws_linked_list_empty(list)); |
333 | struct aws_linked_list_node *rval = list->head.next; |
334 | AWS_POSTCONDITION(aws_linked_list_is_valid(list)); |
335 | AWS_POSTCONDITION(aws_linked_list_node_prev_is_valid(rval)); |
336 | AWS_POSTCONDITION(aws_linked_list_node_next_is_valid(rval)); |
337 | return rval; |
338 | } |
339 | |
340 | /** |
341 | * Returns the element in the front of the list and removes it |
342 | */ |
343 | AWS_STATIC_IMPL struct aws_linked_list_node *aws_linked_list_pop_front(struct aws_linked_list *list) { |
344 | AWS_PRECONDITION(!aws_linked_list_empty(list)); |
345 | AWS_PRECONDITION(aws_linked_list_is_valid(list)); |
346 | struct aws_linked_list_node *front = aws_linked_list_front(list); |
347 | aws_linked_list_remove(front); |
348 | AWS_POSTCONDITION(front->next == NULL && front->prev == NULL); |
349 | AWS_POSTCONDITION(aws_linked_list_is_valid(list)); |
350 | return front; |
351 | } |
352 | |
353 | AWS_STATIC_IMPL void aws_linked_list_swap_contents(struct aws_linked_list *a, struct aws_linked_list *b) { |
354 | AWS_PRECONDITION(aws_linked_list_is_valid(a)); |
355 | AWS_PRECONDITION(aws_linked_list_is_valid(b)); |
356 | struct aws_linked_list_node *a_first = a->head.next; |
357 | struct aws_linked_list_node *a_last = a->tail.prev; |
358 | |
359 | /* Move B's contents into A */ |
360 | if (aws_linked_list_empty(b)) { |
361 | aws_linked_list_init(a); |
362 | } else { |
363 | a->head.next = b->head.next; |
364 | a->head.next->prev = &a->head; |
365 | a->tail.prev = b->tail.prev; |
366 | a->tail.prev->next = &a->tail; |
367 | } |
368 | |
369 | /* Move A's old contents into B */ |
370 | if (a_first == &a->tail) { |
371 | aws_linked_list_init(b); |
372 | } else { |
373 | b->head.next = a_first; |
374 | b->head.next->prev = &b->head; |
375 | b->tail.prev = a_last; |
376 | b->tail.prev->next = &b->tail; |
377 | } |
378 | AWS_POSTCONDITION(aws_linked_list_is_valid(a)); |
379 | AWS_POSTCONDITION(aws_linked_list_is_valid(b)); |
380 | } |
381 | |
382 | AWS_EXTERN_C_END |
383 | |
384 | #endif /* AWS_COMMON_LINKED_LIST_INL */ |
385 | |