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