1 /*
2 * Arm SCP/MCP Software
3 * Copyright (c) 2015-2021, Arm Limited and Contributors. All rights reserved.
4 *
5 * SPDX-License-Identifier: BSD-3-Clause
6 *
7 * Description:
8 * Intrusive circular doubly-linked list.
9 */
10
11 #include <fwk_assert.h>
12 #include <fwk_dlist.h>
13 #include <fwk_slist.h>
14
15 #include <stddef.h>
16
__fwk_dlist_push_head(struct fwk_dlist * list,struct fwk_dlist_node * new)17 void __fwk_dlist_push_head(
18 struct fwk_dlist *list,
19 struct fwk_dlist_node *new)
20 {
21 fwk_assert(list != NULL);
22 fwk_assert(new != NULL);
23 fwk_check(new->prev == NULL);
24
25 new->prev = (struct fwk_dlist_node *)list;
26 list->head->prev = new;
27
28 __fwk_slist_push_head(
29 (struct fwk_slist *)list,
30 (struct fwk_slist_node *)new);
31 }
32
__fwk_dlist_push_tail(struct fwk_dlist * list,struct fwk_dlist_node * new)33 void __fwk_dlist_push_tail(
34 struct fwk_dlist *list,
35 struct fwk_dlist_node *new)
36 {
37 fwk_assert(list != NULL);
38 fwk_assert(new != NULL);
39 fwk_check(new->prev == NULL);
40
41 new->prev = list->tail;
42
43 __fwk_slist_push_tail(
44 (struct fwk_slist *)list,
45 (struct fwk_slist_node *)new);
46 }
47
__fwk_dlist_pop_head(struct fwk_dlist * list)48 struct fwk_dlist_node *__fwk_dlist_pop_head(struct fwk_dlist *list)
49 {
50 struct fwk_dlist_node *popped;
51
52 fwk_assert(list != NULL);
53
54 popped = (struct fwk_dlist_node *)__fwk_slist_pop_head(
55 (struct fwk_slist *)list);
56
57 list->head->prev = (struct fwk_dlist_node *)list;
58
59 if (popped != NULL) {
60 popped->prev = NULL;
61 }
62
63 return popped;
64 }
65
__fwk_dlist_remove(struct fwk_dlist * list,struct fwk_dlist_node * node)66 void __fwk_dlist_remove(
67 struct fwk_dlist *list,
68 struct fwk_dlist_node *node)
69 {
70 fwk_assert(list != NULL);
71 fwk_assert(node != NULL);
72 fwk_assert(node != (struct fwk_dlist_node *)list);
73 fwk_assert(node->prev != NULL);
74 fwk_assert(node->next != NULL);
75
76 assert(__fwk_slist_contains(
77 (struct fwk_slist *)list,
78 (struct fwk_slist_node *)node));
79
80 node->prev->next = node->next;
81 node->next->prev = node->prev;
82
83 node->prev = NULL;
84 node->next = NULL;
85 }
86
__fwk_dlist_insert(struct fwk_dlist * list,struct fwk_dlist_node * restrict new,struct fwk_dlist_node * restrict node)87 void __fwk_dlist_insert(
88 struct fwk_dlist *list,
89 struct fwk_dlist_node *restrict new,
90 struct fwk_dlist_node *restrict node)
91 {
92 fwk_assert(list != NULL);
93 fwk_assert(new != NULL);
94 fwk_assert(new != node);
95 fwk_check(new->next == NULL);
96 fwk_check(new->prev == NULL);
97
98 if (node == NULL) {
99 __fwk_dlist_push_tail(list, new);
100
101 return;
102 }
103
104 fwk_assert(node->prev != NULL);
105 fwk_assert(node->next != NULL);
106
107 assert(__fwk_slist_contains(
108 (struct fwk_slist *)list,
109 (struct fwk_slist_node *)node));
110
111 node->prev->next = new;
112 new->prev = node->prev;
113 new->next = node;
114 node->prev = new;
115 }
116
117 static_assert(offsetof(struct fwk_dlist, head) ==
118 offsetof(struct fwk_slist, head),
119 "fwk_dlist::head not aligned with fwk_slist::head");
120
121 static_assert(offsetof(struct fwk_dlist, tail) ==
122 offsetof(struct fwk_slist, tail),
123 "fwk_dlist::tail not aligned with fwk_slist::tail");
124
125 static_assert(offsetof(struct fwk_dlist, head) ==
126 offsetof(struct fwk_slist_node, next),
127 "fwk_dlist::head not aligned with fwk_slist_node::next");
128
129 static_assert(offsetof(struct fwk_dlist, head) ==
130 offsetof(struct fwk_dlist_node, next),
131 "fwk_dlist::head not aligned with fwk_dlist_node::next");
132
133 static_assert(offsetof(struct fwk_dlist, tail) ==
134 offsetof(struct fwk_dlist_node, prev),
135 "fwk_dlist::tail not aligned with fwk_dlist_node::prev");
136