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
23AWS_EXTERN_C_BEGIN
24
25/**
26 * Set node's next and prev pointers to NULL.
27 */
28AWS_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 */
42AWS_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 */
50AWS_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 */
66AWS_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 */
75AWS_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 */
91AWS_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 */
118AWS_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 */
131AWS_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 */
142AWS_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 */
155AWS_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 */
167AWS_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 */
178AWS_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 */
190AWS_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 */
202AWS_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 */
220AWS_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 */
251AWS_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 */
270AWS_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 */
282AWS_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 */
293AWS_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 */
306AWS_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 */
319AWS_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 */
330AWS_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 */
343AWS_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
353AWS_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
382AWS_EXTERN_C_END
383
384#endif /* AWS_COMMON_LINKED_LIST_INL */
385