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 singly-linked list.
9 */
10
11 #include <fwk_assert.h>
12 #include <fwk_list.h>
13 #include <fwk_slist.h>
14
15 #include <stdbool.h>
16 #include <stddef.h>
17
__fwk_slist_init(struct fwk_slist * list)18 void __fwk_slist_init(struct fwk_slist *list)
19 {
20 fwk_assert(list != NULL);
21
22 list->head = (struct fwk_slist_node *)list;
23 list->tail = (struct fwk_slist_node *)list;
24 }
25
__fwk_slist_head(const struct fwk_slist * list)26 struct fwk_slist_node *__fwk_slist_head(const struct fwk_slist *list)
27 {
28 fwk_assert(list != NULL);
29
30 if (__fwk_slist_is_empty(list)) {
31 return NULL;
32 }
33
34 return list->head;
35 }
36
__fwk_slist_is_empty(const struct fwk_slist * list)37 bool __fwk_slist_is_empty(const struct fwk_slist *list)
38 {
39 bool is_empty;
40
41 fwk_assert(list != NULL);
42
43 is_empty = list->head == (struct fwk_slist_node *)list;
44
45 if (is_empty) {
46 fwk_assert(list->tail == list->head);
47 }
48
49 return is_empty;
50 }
51
__fwk_slist_push_head(struct fwk_slist * list,struct fwk_slist_node * new)52 void __fwk_slist_push_head(
53 struct fwk_slist *list,
54 struct fwk_slist_node *new)
55 {
56 fwk_assert(list != NULL);
57 fwk_assert(new != NULL);
58 fwk_check(new->next == NULL);
59
60 new->next = list->head;
61
62 list->head = new;
63 if (list->tail == (struct fwk_slist_node *)list) {
64 list->tail = new;
65 }
66 }
67
__fwk_slist_push_tail(struct fwk_slist * list,struct fwk_slist_node * new)68 void __fwk_slist_push_tail(
69 struct fwk_slist *list,
70 struct fwk_slist_node *new)
71 {
72 fwk_assert(list != NULL);
73 fwk_assert(new != NULL);
74 fwk_check(new->next == NULL);
75
76 new->next = (struct fwk_slist_node *)list;
77
78 list->tail->next = new;
79 list->tail = new;
80 }
81
__fwk_slist_pop_head(struct fwk_slist * list)82 struct fwk_slist_node *__fwk_slist_pop_head(struct fwk_slist *list)
83 {
84 struct fwk_slist_node *popped;
85
86 fwk_assert(list != NULL);
87
88 if (__fwk_slist_is_empty(list)) {
89 return NULL;
90 }
91
92 popped = list->head;
93 if (popped->next == (struct fwk_slist_node *)list) {
94 list->tail = (struct fwk_slist_node *)list;
95 }
96
97 list->head = popped->next;
98
99 popped->next = NULL;
100
101 return popped;
102 }
103
__fwk_slist_next(const struct fwk_slist * list,const struct fwk_slist_node * node)104 struct fwk_slist_node *__fwk_slist_next(
105 const struct fwk_slist *list,
106 const struct fwk_slist_node *node)
107 {
108 fwk_assert(list != NULL);
109 fwk_assert(node != NULL);
110
111 fwk_assert(__fwk_slist_contains(list, node));
112
113 return (node->next == (struct fwk_slist_node *)list) ? NULL : node->next;
114 }
115
__fwk_slist_remove(struct fwk_slist * list,struct fwk_slist_node * node)116 void __fwk_slist_remove(
117 struct fwk_slist *list,
118 struct fwk_slist_node *node)
119 {
120 fwk_assert(list != NULL);
121 fwk_assert(node != NULL);
122 fwk_assert(node->next != NULL);
123
124 struct fwk_slist_node *node_iter = (struct fwk_slist_node *)list;
125
126 while (node_iter->next != (struct fwk_slist_node *)list) {
127 if (node_iter->next == node) {
128 node_iter->next = node->next;
129
130 if (node->next == (struct fwk_slist_node *)list) {
131 list->tail = (struct fwk_slist_node *)node_iter;
132 }
133
134 node->next = NULL;
135
136 return;
137 }
138 node_iter = node_iter->next;
139 }
140
141 fwk_unexpected();
142 }
143
__fwk_slist_contains(const struct fwk_slist * list,const struct fwk_slist_node * node)144 bool __fwk_slist_contains(
145 const struct fwk_slist *list,
146 const struct fwk_slist_node *node)
147 {
148 const struct fwk_slist_node *node_iter;
149
150 fwk_assert(list != NULL);
151 fwk_assert(node != NULL);
152 fwk_assert(node->next != NULL);
153
154 node_iter = (struct fwk_slist_node *)list;
155
156 while (node_iter->next != (struct fwk_slist_node *)list) {
157 if (node_iter->next == node) {
158 return true;
159 }
160
161 node_iter = node_iter->next;
162 }
163
164 return false;
165 }
166
167 static_assert(offsetof(struct fwk_slist, head) ==
168 offsetof(struct fwk_slist_node, next),
169 "fwk_slist::head not aligned with fwk_slist_node::next");
170