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 13AWS_EXTERN_C_BEGIN 14 15/** 16 * Set node's next and prev pointers to NULL. 17 */ 18AWS_STATIC_IMPL void aws_linked_list_node_reset(struct aws_linked_list_node *node) { 19 AWS_PRECONDITION(node != NULL); 20 AWS_ZERO_STRUCT(*node); 21 AWS_POSTCONDITION(AWS_IS_ZEROED(*node)); 22} 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 */ 32AWS_STATIC_IMPL bool aws_linked_list_empty(const struct aws_linked_list *list) { 33 AWS_PRECONDITION(list); 34 return list->head.next == &list->tail; 35} 36 37/** 38 * Checks that a linked list is valid. 39 */ 40AWS_STATIC_IMPL bool aws_linked_list_is_valid(const struct aws_linked_list *list) { 41 if (list && list->head.next && list->head.prev == NULL && list->tail.prev && list->tail.next == NULL) { 42#if (AWS_DEEP_CHECKS == 1) 43 return aws_linked_list_is_valid_deep(list); 44#else 45 return true; 46#endif 47 } 48 return false; 49} 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 */ 56AWS_STATIC_IMPL bool aws_linked_list_node_next_is_valid(const struct aws_linked_list_node *node) { 57 return node && node->next && node->next->prev == node; 58} 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 */ 65AWS_STATIC_IMPL bool aws_linked_list_node_prev_is_valid(const struct aws_linked_list_node *node) { 66 return node && node->prev && node->prev->next == node; 67} 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 */ 81AWS_STATIC_IMPL bool aws_linked_list_is_valid_deep(const struct aws_linked_list *list) { 82 if (!list) { 83 return false; 84 } 85 /* This could go into an infinite loop for a circular list */ 86 const struct aws_linked_list_node *temp = &list->head; 87 /* Head must reach tail by following next pointers */ 88 bool head_reaches_tail = false; 89 /* By satisfying the above and that edges are bidirectional, we 90 * also guarantee that tail reaches head by following prev 91 * pointers */ 92 while (temp) { 93 if (temp == &list->tail) { 94 head_reaches_tail = true; 95 break; 96 } else if (!aws_linked_list_node_next_is_valid(temp)) { 97 /* Next and prev pointers should connect the same nodes */ 98 return false; 99 } 100 temp = temp->next; 101 } 102 return head_reaches_tail; 103} 104 105/** 106 * Initializes the list. List will be empty after this call. 107 */ 108AWS_STATIC_IMPL void aws_linked_list_init(struct aws_linked_list *list) { 109 AWS_PRECONDITION(list); 110 list->head.next = &list->tail; 111 list->head.prev = NULL; 112 list->tail.prev = &list->head; 113 list->tail.next = NULL; 114 AWS_POSTCONDITION(aws_linked_list_is_valid(list)); 115 AWS_POSTCONDITION(aws_linked_list_empty(list)); 116} 117 118/** 119 * Returns an iteration pointer for the first element in the list. 120 */ 121AWS_STATIC_IMPL struct aws_linked_list_node *aws_linked_list_begin(const struct aws_linked_list *list) { 122 AWS_PRECONDITION(aws_linked_list_is_valid(list)); 123 struct aws_linked_list_node *rval = list->head.next; 124 AWS_POSTCONDITION(aws_linked_list_is_valid(list)); 125 AWS_POSTCONDITION(rval == list->head.next); 126 return rval; 127} 128 129/** 130 * Returns an iteration pointer for one past the last element in the list. 131 */ 132AWS_STATIC_IMPL const struct aws_linked_list_node *aws_linked_list_end(const struct aws_linked_list *list) { 133 AWS_PRECONDITION(aws_linked_list_is_valid(list)); 134 const struct aws_linked_list_node *rval = &list->tail; 135 AWS_POSTCONDITION(aws_linked_list_is_valid(list)); 136 AWS_POSTCONDITION(rval == &list->tail); 137 return rval; 138} 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 */ 145AWS_STATIC_IMPL struct aws_linked_list_node *aws_linked_list_rbegin(const struct aws_linked_list *list) { 146 AWS_PRECONDITION(aws_linked_list_is_valid(list)); 147 struct aws_linked_list_node *rval = list->tail.prev; 148 AWS_POSTCONDITION(aws_linked_list_is_valid(list)); 149 AWS_POSTCONDITION(rval == list->tail.prev); 150 return rval; 151} 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 */ 157AWS_STATIC_IMPL const struct aws_linked_list_node *aws_linked_list_rend(const struct aws_linked_list *list) { 158 AWS_PRECONDITION(aws_linked_list_is_valid(list)); 159 const struct aws_linked_list_node *rval = &list->head; 160 AWS_POSTCONDITION(aws_linked_list_is_valid(list)); 161 AWS_POSTCONDITION(rval == &list->head); 162 return rval; 163} 164 165/** 166 * Returns the next element in the list. 167 */ 168AWS_STATIC_IMPL struct aws_linked_list_node *aws_linked_list_next(const struct aws_linked_list_node *node) { 169 AWS_PRECONDITION(aws_linked_list_node_next_is_valid(node)); 170 struct aws_linked_list_node *rval = node->next; 171 AWS_POSTCONDITION(aws_linked_list_node_next_is_valid(node)); 172 AWS_POSTCONDITION(aws_linked_list_node_prev_is_valid(rval)); 173 AWS_POSTCONDITION(rval == node->next); 174 return rval; 175} 176 177/** 178 * Returns the previous element in the list. 179 */ 180AWS_STATIC_IMPL struct aws_linked_list_node *aws_linked_list_prev(const struct aws_linked_list_node *node) { 181 AWS_PRECONDITION(aws_linked_list_node_prev_is_valid(node)); 182 struct aws_linked_list_node *rval = node->prev; 183 AWS_POSTCONDITION(aws_linked_list_node_prev_is_valid(node)); 184 AWS_POSTCONDITION(aws_linked_list_node_next_is_valid(rval)); 185 AWS_POSTCONDITION(rval == node->prev); 186 return rval; 187} 188 189/** 190 * Inserts to_add immediately after after. 191 */ 192AWS_STATIC_IMPL void aws_linked_list_insert_after( 193 struct aws_linked_list_node *after, 194 struct aws_linked_list_node *to_add) { 195 AWS_PRECONDITION(aws_linked_list_node_next_is_valid(after)); 196 AWS_PRECONDITION(to_add != NULL); 197 to_add->prev = after; 198 to_add->next = after->next; 199 after->next->prev = to_add; 200 after->next = to_add; 201 AWS_POSTCONDITION(aws_linked_list_node_next_is_valid(after)); 202 AWS_POSTCONDITION(aws_linked_list_node_prev_is_valid(to_add)); 203 AWS_POSTCONDITION(aws_linked_list_node_next_is_valid(to_add)); 204 AWS_POSTCONDITION(after->next == to_add); 205} 206 207/** 208 * Swaps the order two nodes in the linked list. 209 */ 210AWS_STATIC_IMPL void aws_linked_list_swap_nodes(struct aws_linked_list_node *a, struct aws_linked_list_node *b) { 211 AWS_PRECONDITION(aws_linked_list_node_prev_is_valid(a)); 212 AWS_PRECONDITION(aws_linked_list_node_next_is_valid(a)); 213 AWS_PRECONDITION(aws_linked_list_node_prev_is_valid(b)); 214 AWS_PRECONDITION(aws_linked_list_node_next_is_valid(b)); 215 216 if (a == b) { 217 return; 218 } 219 220 /* snapshot b's value to avoid clobbering its next/prev pointers if a/b are adjacent */ 221 struct aws_linked_list_node tmp = *b; 222 a->prev->next = b; 223 a->next->prev = b; 224 225 tmp.prev->next = a; 226 tmp.next->prev = a; 227 228 tmp = *a; 229 *a = *b; 230 *b = tmp; 231 232 AWS_POSTCONDITION(aws_linked_list_node_prev_is_valid(a)); 233 AWS_POSTCONDITION(aws_linked_list_node_next_is_valid(a)); 234 AWS_POSTCONDITION(aws_linked_list_node_prev_is_valid(b)); 235 AWS_POSTCONDITION(aws_linked_list_node_next_is_valid(b)); 236} 237 238/** 239 * Inserts to_add immediately before before. 240 */ 241AWS_STATIC_IMPL void aws_linked_list_insert_before( 242 struct aws_linked_list_node *before, 243 struct aws_linked_list_node *to_add) { 244 AWS_PRECONDITION(aws_linked_list_node_prev_is_valid(before)); 245 AWS_PRECONDITION(to_add != NULL); 246 to_add->next = before; 247 to_add->prev = before->prev; 248 before->prev->next = to_add; 249 before->prev = to_add; 250 AWS_POSTCONDITION(aws_linked_list_node_prev_is_valid(before)); 251 AWS_POSTCONDITION(aws_linked_list_node_prev_is_valid(to_add)); 252 AWS_POSTCONDITION(aws_linked_list_node_next_is_valid(to_add)); 253 AWS_POSTCONDITION(before->prev == to_add); 254} 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 */ 260AWS_STATIC_IMPL void aws_linked_list_remove(struct aws_linked_list_node *node) { 261 AWS_PRECONDITION(aws_linked_list_node_prev_is_valid(node)); 262 AWS_PRECONDITION(aws_linked_list_node_next_is_valid(node)); 263 node->prev->next = node->next; 264 node->next->prev = node->prev; 265 aws_linked_list_node_reset(node); 266 AWS_POSTCONDITION(node->next == NULL && node->prev == NULL); 267} 268 269/** 270 * Append new_node. 271 */ 272AWS_STATIC_IMPL void aws_linked_list_push_back(struct aws_linked_list *list, struct aws_linked_list_node *node) { 273 AWS_PRECONDITION(aws_linked_list_is_valid(list)); 274 AWS_PRECONDITION(node != NULL); 275 aws_linked_list_insert_before(&list->tail, node); 276 AWS_POSTCONDITION(aws_linked_list_is_valid(list)); 277 AWS_POSTCONDITION(list->tail.prev == node, "[node] is the new last element of [list]"); 278} 279 280/** 281 * Returns the element in the back of the list. 282 */ 283AWS_STATIC_IMPL struct aws_linked_list_node *aws_linked_list_back(const struct aws_linked_list *list) { 284 AWS_PRECONDITION(aws_linked_list_is_valid(list)); 285 AWS_PRECONDITION(!aws_linked_list_empty(list)); 286 struct aws_linked_list_node *rval = list->tail.prev; 287 AWS_POSTCONDITION(aws_linked_list_is_valid(list)); 288 AWS_POSTCONDITION(aws_linked_list_node_prev_is_valid(rval)); 289 AWS_POSTCONDITION(aws_linked_list_node_next_is_valid(rval)); 290 return rval; 291} 292 293/** 294 * Returns the element in the back of the list and removes it 295 */ 296AWS_STATIC_IMPL struct aws_linked_list_node *aws_linked_list_pop_back(struct aws_linked_list *list) { 297 AWS_PRECONDITION(!aws_linked_list_empty(list)); 298 AWS_PRECONDITION(aws_linked_list_is_valid(list)); 299 struct aws_linked_list_node *back = aws_linked_list_back(list); 300 aws_linked_list_remove(back); 301 AWS_POSTCONDITION(back->next == NULL && back->prev == NULL); 302 AWS_POSTCONDITION(aws_linked_list_is_valid(list)); 303 return back; 304} 305 306/** 307 * Prepend new_node. 308 */ 309AWS_STATIC_IMPL void aws_linked_list_push_front(struct aws_linked_list *list, struct aws_linked_list_node *node) { 310 AWS_PRECONDITION(aws_linked_list_is_valid(list)); 311 AWS_PRECONDITION(node != NULL); 312 aws_linked_list_insert_before(list->head.next, node); 313 AWS_POSTCONDITION(aws_linked_list_is_valid(list)); 314 AWS_POSTCONDITION(list->head.next == node, "[node] is the new first element of [list]"); 315} 316 317/** 318 * Returns the element in the front of the list. 319 */ 320AWS_STATIC_IMPL struct aws_linked_list_node *aws_linked_list_front(const struct aws_linked_list *list) { 321 AWS_PRECONDITION(aws_linked_list_is_valid(list)); 322 AWS_PRECONDITION(!aws_linked_list_empty(list)); 323 struct aws_linked_list_node *rval = list->head.next; 324 AWS_POSTCONDITION(aws_linked_list_is_valid(list)); 325 AWS_POSTCONDITION(aws_linked_list_node_prev_is_valid(rval)); 326 AWS_POSTCONDITION(aws_linked_list_node_next_is_valid(rval)); 327 return rval; 328} 329 330/** 331 * Returns the element in the front of the list and removes it 332 */ 333AWS_STATIC_IMPL struct aws_linked_list_node *aws_linked_list_pop_front(struct aws_linked_list *list) { 334 AWS_PRECONDITION(!aws_linked_list_empty(list)); 335 AWS_PRECONDITION(aws_linked_list_is_valid(list)); 336 struct aws_linked_list_node *front = aws_linked_list_front(list); 337 aws_linked_list_remove(front); 338 AWS_POSTCONDITION(front->next == NULL && front->prev == NULL); 339 AWS_POSTCONDITION(aws_linked_list_is_valid(list)); 340 return front; 341} 342 343AWS_STATIC_IMPL void aws_linked_list_swap_contents( 344 struct aws_linked_list *AWS_RESTRICT a, 345 struct aws_linked_list *AWS_RESTRICT b) { 346 347 AWS_PRECONDITION(aws_linked_list_is_valid(a)); 348 AWS_PRECONDITION(aws_linked_list_is_valid(b)); 349 AWS_PRECONDITION(a != b); 350 struct aws_linked_list_node *a_first = a->head.next; 351 struct aws_linked_list_node *a_last = a->tail.prev; 352 353 /* Move B's contents into A */ 354 if (aws_linked_list_empty(b)) { 355 aws_linked_list_init(a); 356 } else { 357 a->head.next = b->head.next; 358 a->head.next->prev = &a->head; 359 a->tail.prev = b->tail.prev; 360 a->tail.prev->next = &a->tail; 361 } 362 363 /* Move A's old contents into B */ 364 if (a_first == &a->tail) { 365 aws_linked_list_init(b); 366 } else { 367 b->head.next = a_first; 368 b->head.next->prev = &b->head; 369 b->tail.prev = a_last; 370 b->tail.prev->next = &b->tail; 371 } 372 AWS_POSTCONDITION(aws_linked_list_is_valid(a)); 373 AWS_POSTCONDITION(aws_linked_list_is_valid(b)); 374} 375 376AWS_STATIC_IMPL void aws_linked_list_move_all_back( 377 struct aws_linked_list *AWS_RESTRICT dst, 378 struct aws_linked_list *AWS_RESTRICT src) { 379 380 AWS_PRECONDITION(aws_linked_list_is_valid(src)); 381 AWS_PRECONDITION(aws_linked_list_is_valid(dst)); 382 AWS_PRECONDITION(dst != src); 383 384 if (!aws_linked_list_empty(src)) { 385 /* splice src nodes into dst, between the back and tail nodes */ 386 struct aws_linked_list_node *dst_back = dst->tail.prev; 387 struct aws_linked_list_node *src_front = src->head.next; 388 struct aws_linked_list_node *src_back = src->tail.prev; 389 390 dst_back->next = src_front; 391 src_front->prev = dst_back; 392 393 dst->tail.prev = src_back; 394 src_back->next = &dst->tail; 395 396 /* reset src */ 397 src->head.next = &src->tail; 398 src->tail.prev = &src->head; 399 } 400 401 AWS_POSTCONDITION(aws_linked_list_is_valid(src)); 402 AWS_POSTCONDITION(aws_linked_list_is_valid(dst)); 403} 404 405AWS_STATIC_IMPL void aws_linked_list_move_all_front( 406 struct aws_linked_list *AWS_RESTRICT dst, 407 struct aws_linked_list *AWS_RESTRICT src) { 408 409 AWS_PRECONDITION(aws_linked_list_is_valid(src)); 410 AWS_PRECONDITION(aws_linked_list_is_valid(dst)); 411 AWS_PRECONDITION(dst != src); 412 413 if (!aws_linked_list_empty(src)) { 414 /* splice src nodes into dst, between the head and front nodes */ 415 struct aws_linked_list_node *dst_front = dst->head.next; 416 struct aws_linked_list_node *src_front = src->head.next; 417 struct aws_linked_list_node *src_back = src->tail.prev; 418 419 dst->head.next = src_front; 420 src_front->prev = &dst->head; 421 422 src_back->next = dst_front; 423 dst_front->prev = src_back; 424 425 /* reset src */ 426 src->head.next = &src->tail; 427 src->tail.prev = &src->head; 428 } 429 430 AWS_POSTCONDITION(aws_linked_list_is_valid(src)); 431 AWS_POSTCONDITION(aws_linked_list_is_valid(dst)); 432} 433 434AWS_EXTERN_C_END 435 436#endif /* AWS_COMMON_LINKED_LIST_INL */ 437