1 #ifndef AWS_COMMON_LINKED_LIST_H 2 #define AWS_COMMON_LINKED_LIST_H 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 11 #include <stddef.h> 12 13 struct aws_linked_list_node { 14 struct aws_linked_list_node *next; 15 struct aws_linked_list_node *prev; 16 }; 17 18 struct aws_linked_list { 19 struct aws_linked_list_node head; 20 struct aws_linked_list_node tail; 21 }; 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 30 /** 31 * These functions need to be defined first as they are used in pre 32 * and post conditions. 33 */ 34 35 /** 36 * Tests if the list is empty. 37 */ 38 AWS_STATIC_IMPL bool aws_linked_list_empty(const struct aws_linked_list *list); 39 40 /** 41 * Checks that a linked list is valid. 42 */ 43 AWS_STATIC_IMPL bool aws_linked_list_is_valid(const struct aws_linked_list *list); 44 /** 45 * Checks that the prev of the next pointer of a node points to the 46 * node. As this checks whether the [next] connection of a node is 47 * bidirectional, it returns false if used for the list tail. 48 */ 49 AWS_STATIC_IMPL bool aws_linked_list_node_next_is_valid(const struct aws_linked_list_node *node); 50 51 /** 52 * Checks that the next of the prev pointer of a node points to the 53 * node. Similarly to the above, this returns false if used for the 54 * head of a list. 55 */ 56 AWS_STATIC_IMPL bool aws_linked_list_node_prev_is_valid(const struct aws_linked_list_node *node); 57 /** 58 * Checks that a linked list satisfies double linked list connectivity 59 * constraints. This check is O(n) as it traverses the whole linked 60 * list to ensure that tail is reachable from head (and vice versa) 61 * and that every connection is bidirectional. 62 * 63 * Note: This check *cannot* go into an infinite loop, because we 64 * ensure that the connection to the next node is 65 * bidirectional. Therefore, if a node's [a] a.next is a previous node 66 * [b] in the list, b.prev != &a and so this check would fail, thus 67 * terminating the loop. 68 */ 69 AWS_STATIC_IMPL bool aws_linked_list_is_valid_deep(const struct aws_linked_list *list); 70 71 /** 72 * Initializes the list. List will be empty after this call. 73 */ 74 AWS_STATIC_IMPL void aws_linked_list_init(struct aws_linked_list *list); 75 76 /** 77 * Returns an iteration pointer for the first element in the list. 78 */ 79 AWS_STATIC_IMPL struct aws_linked_list_node *aws_linked_list_begin(const struct aws_linked_list *list); 80 81 /** 82 * Returns an iteration pointer for one past the last element in the list. 83 */ 84 AWS_STATIC_IMPL const struct aws_linked_list_node *aws_linked_list_end(const struct aws_linked_list *list); 85 86 /** 87 * Returns a pointer for the last element in the list. 88 * Used to begin iterating the list in reverse. Ex: 89 * for (i = aws_linked_list_rbegin(list); i != aws_linked_list_rend(list); i = aws_linked_list_prev(i)) {...} 90 */ 91 AWS_STATIC_IMPL struct aws_linked_list_node *aws_linked_list_rbegin(const struct aws_linked_list *list); 92 93 /** 94 * Returns the pointer to one before the first element in the list. 95 * Used to end iterating the list in reverse. 96 */ 97 AWS_STATIC_IMPL const struct aws_linked_list_node *aws_linked_list_rend(const struct aws_linked_list *list); 98 99 /** 100 * Returns the next element in the list. 101 */ 102 AWS_STATIC_IMPL struct aws_linked_list_node *aws_linked_list_next(const struct aws_linked_list_node *node); 103 104 /** 105 * Returns the previous element in the list. 106 */ 107 AWS_STATIC_IMPL struct aws_linked_list_node *aws_linked_list_prev(const struct aws_linked_list_node *node); 108 109 /** 110 * Inserts to_add immediately after after. 111 */ 112 AWS_STATIC_IMPL void aws_linked_list_insert_after( 113 struct aws_linked_list_node *after, 114 struct aws_linked_list_node *to_add); 115 /** 116 * Swaps the order two nodes in the linked list. 117 */ 118 AWS_STATIC_IMPL void aws_linked_list_swap_nodes(struct aws_linked_list_node *a, struct aws_linked_list_node *b); 119 120 /** 121 * Inserts to_add immediately before before. 122 */ 123 AWS_STATIC_IMPL void aws_linked_list_insert_before( 124 struct aws_linked_list_node *before, 125 struct aws_linked_list_node *to_add); 126 127 /** 128 * Removes the specified node from the list (prev/next point to each other) and 129 * returns the next node in the list. 130 */ 131 AWS_STATIC_IMPL void aws_linked_list_remove(struct aws_linked_list_node *node); 132 133 /** 134 * Append new_node. 135 */ 136 AWS_STATIC_IMPL void aws_linked_list_push_back(struct aws_linked_list *list, struct aws_linked_list_node *node); 137 138 /** 139 * Returns the element in the back of the list. 140 */ 141 AWS_STATIC_IMPL struct aws_linked_list_node *aws_linked_list_back(const struct aws_linked_list *list); 142 143 /** 144 * Returns the element in the back of the list and removes it 145 */ 146 AWS_STATIC_IMPL struct aws_linked_list_node *aws_linked_list_pop_back(struct aws_linked_list *list); 147 148 /** 149 * Prepend new_node. 150 */ 151 AWS_STATIC_IMPL void aws_linked_list_push_front(struct aws_linked_list *list, struct aws_linked_list_node *node); 152 /** 153 * Returns the element in the front of the list. 154 */ 155 AWS_STATIC_IMPL struct aws_linked_list_node *aws_linked_list_front(const struct aws_linked_list *list); 156 /** 157 * Returns the element in the front of the list and removes it 158 */ 159 AWS_STATIC_IMPL struct aws_linked_list_node *aws_linked_list_pop_front(struct aws_linked_list *list); 160 161 AWS_STATIC_IMPL void aws_linked_list_swap_contents( 162 struct aws_linked_list *AWS_RESTRICT a, 163 struct aws_linked_list *AWS_RESTRICT b); 164 165 /** 166 * Remove all nodes from one list, and add them to the back of another. 167 * 168 * Example: if dst={1,2} and src={3,4}, they become dst={1,2,3,4} and src={} 169 */ 170 AWS_STATIC_IMPL void aws_linked_list_move_all_back( 171 struct aws_linked_list *AWS_RESTRICT dst, 172 struct aws_linked_list *AWS_RESTRICT src); 173 174 /** 175 * Remove all nodes from one list, and add them to the front of another. 176 * 177 * Example: if dst={2,1} and src={4,3}, they become dst={4,3,2,1} and src={} 178 */ 179 AWS_STATIC_IMPL void aws_linked_list_move_all_front( 180 struct aws_linked_list *AWS_RESTRICT dst, 181 struct aws_linked_list *AWS_RESTRICT src); 182 183 #ifndef AWS_NO_STATIC_IMPL 184 # include <aws/common/linked_list.inl> 185 #endif /* AWS_NO_STATIC_IMPL */ 186 AWS_EXTERN_C_END 187 188 #endif /* AWS_COMMON_LINKED_LIST_H */ 189