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
23struct aws_linked_list_node {
24 struct aws_linked_list_node *next;
25 struct aws_linked_list_node *prev;
26};
27
28struct aws_linked_list {
29 struct aws_linked_list_node head;
30 struct aws_linked_list_node tail;
31};
32
33AWS_EXTERN_C_BEGIN
34
35/**
36 * Set node's next and prev pointers to NULL.
37 */
38AWS_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 */
48AWS_STATIC_IMPL bool aws_linked_list_empty(const struct aws_linked_list *list);
49
50/**
51 * Checks that a linked list is valid.
52 */
53AWS_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 */
59AWS_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 */
66AWS_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 */
79AWS_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 */
84AWS_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 */
89AWS_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 */
94AWS_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 */
101AWS_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 */
107AWS_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 */
112AWS_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 */
117AWS_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 */
122AWS_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 */
128AWS_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 */
133AWS_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 */
141AWS_STATIC_IMPL void aws_linked_list_remove(struct aws_linked_list_node *node);
142
143/**
144 * Append new_node.
145 */
146AWS_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 */
151AWS_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 */
156AWS_STATIC_IMPL struct aws_linked_list_node *aws_linked_list_pop_back(struct aws_linked_list *list);
157
158/**
159 * Prepend new_node.
160 */
161AWS_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 */
165AWS_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 */
169AWS_STATIC_IMPL struct aws_linked_list_node *aws_linked_list_pop_front(struct aws_linked_list *list);
170
171AWS_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 */
176AWS_EXTERN_C_END
177
178#endif /* AWS_COMMON_LINKED_LIST_H */
179