1 // © 2021 Qualcomm Innovation Center, Inc. All rights reserved.
2 //
3 // SPDX-License-Identifier: BSD-3-Clause
4
5 #include <assert.h>
6 #include <hyptypes.h>
7
8 #include <list.h>
9
10 void
list_init(list_t * list)11 list_init(list_t *list)
12 {
13 assert(list != NULL);
14
15 list_node_t *head = &list->head;
16
17 atomic_store_relaxed(&head->next, head);
18 head->prev = head;
19 }
20
21 bool
list_is_empty(list_t * list)22 list_is_empty(list_t *list)
23 {
24 assert(list != NULL);
25
26 return (atomic_load_relaxed(&list->head.next) == &list->head);
27 }
28
29 list_node_t *
list_get_head(list_t * list)30 list_get_head(list_t *list)
31 {
32 assert(list != NULL);
33
34 list_node_t *node = atomic_load_relaxed(&list->head.next);
35
36 return (node != &list->head) ? node : NULL;
37 }
38
39 static inline void
list_insert_at_head_explicit(list_t * list,list_node_t * node,memory_order order)40 list_insert_at_head_explicit(list_t *list, list_node_t *node,
41 memory_order order)
42 {
43 assert(list != NULL);
44 assert(node != NULL);
45
46 list_node_t *prev = &list->head;
47 list_node_t *next = atomic_load_relaxed(&prev->next);
48
49 node->prev = prev;
50 atomic_store_relaxed(&node->next, next);
51
52 atomic_store_explicit(&prev->next, node, order);
53 next->prev = node;
54 }
55
56 void
list_insert_at_head(list_t * list,list_node_t * node)57 list_insert_at_head(list_t *list, list_node_t *node)
58 {
59 list_insert_at_head_explicit(list, node, memory_order_relaxed);
60 }
61
62 static inline void
list_insert_at_tail_explicit(list_t * list,list_node_t * node,memory_order order)63 list_insert_at_tail_explicit(list_t *list, list_node_t *node,
64 memory_order order)
65 {
66 assert(list != NULL);
67 assert(node != NULL);
68
69 list_node_t *next = &list->head;
70 list_node_t *prev = next->prev;
71
72 node->prev = prev;
73 atomic_store_relaxed(&node->next, next);
74
75 atomic_store_explicit(&prev->next, node, order);
76 next->prev = node;
77 }
78
79 void
list_insert_at_tail(list_t * list,list_node_t * node)80 list_insert_at_tail(list_t *list, list_node_t *node)
81 {
82 list_insert_at_tail_explicit(list, node, memory_order_relaxed);
83 }
84
85 void
list_insert_at_tail_release(list_t * list,list_node_t * node)86 list_insert_at_tail_release(list_t *list, list_node_t *node)
87 {
88 list_insert_at_tail_explicit(list, node, memory_order_release);
89 }
90
91 static inline bool
list_insert_in_order_explicit(list_t * list,list_node_t * node,bool (* compare_fn)(list_node_t * a,list_node_t * b),memory_order order)92 list_insert_in_order_explicit(list_t *list, list_node_t *node,
93 bool (*compare_fn)(list_node_t *a,
94 list_node_t *b),
95 memory_order order)
96 {
97 assert(list != NULL);
98 assert(node != NULL);
99
100 bool new_head = false;
101 list_node_t *head = &list->head;
102
103 list_node_t *prev = head;
104 list_node_t *next = atomic_load_relaxed(&head->next);
105
106 while (next != head) {
107 if (compare_fn(node, next)) {
108 break;
109 }
110
111 prev = next;
112 next = atomic_load_relaxed(&prev->next);
113 }
114
115 if (prev == head) {
116 new_head = true;
117 }
118
119 node->prev = prev;
120 atomic_store_relaxed(&node->next, next);
121
122 atomic_store_explicit(&prev->next, node, order);
123 next->prev = node;
124
125 return new_head;
126 }
127
128 bool
list_insert_in_order(list_t * list,list_node_t * node,bool (* compare_fn)(list_node_t * a,list_node_t * b))129 list_insert_in_order(list_t *list, list_node_t *node,
130 bool (*compare_fn)(list_node_t *a, list_node_t *b))
131 {
132 return list_insert_in_order_explicit(list, node, compare_fn,
133 memory_order_relaxed);
134 }
135
136 static inline void
list_insert_after_node_explicit(list_t * list,list_node_t * prev,list_node_t * node,memory_order order)137 list_insert_after_node_explicit(list_t *list, list_node_t *prev,
138 list_node_t *node, memory_order order)
139 {
140 assert(node != NULL);
141 assert(prev != NULL);
142
143 (void)list;
144
145 list_node_t *next = atomic_load_relaxed(&prev->next);
146
147 node->prev = prev;
148 atomic_store_relaxed(&node->next, next);
149
150 atomic_store_explicit(&prev->next, node, order);
151 next->prev = node;
152 }
153
154 void
list_insert_after_node(list_t * list,list_node_t * prev,list_node_t * node)155 list_insert_after_node(list_t *list, list_node_t *prev, list_node_t *node)
156 {
157 list_insert_after_node_explicit(list, prev, node, memory_order_relaxed);
158 }
159
160 bool
list_delete_node(list_t * list,list_node_t * node)161 list_delete_node(list_t *list, list_node_t *node)
162 {
163 assert(list != NULL);
164 assert(node != NULL);
165
166 bool new_head = false;
167
168 if ((atomic_load_relaxed(&node->next) == NULL) ||
169 (node->prev == NULL)) {
170 goto out;
171 }
172
173 list_node_t *head = &list->head;
174 list_node_t *next = atomic_load_relaxed(&node->next);
175 list_node_t *prev = node->prev;
176
177 atomic_store_relaxed(&prev->next, next);
178 next->prev = prev;
179
180 if ((prev == head) && (next != head)) {
181 new_head = true;
182 }
183
184 // Note: we do not zero the node's pointers here, because there might
185 // be a list_foreach_container_consume() that still holds a pointer to
186 // the node.
187 out:
188 return new_head;
189 }
190