1 /*
2 * Copyright (c) 2019 The Linux Foundation. All rights reserved.
3 *
4 * Permission to use, copy, modify, and/or distribute this software for
5 * any purpose with or without fee is hereby granted, provided that the
6 * above copyright notice and this permission notice appear in all
7 * copies.
8 *
9 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL
10 * WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED
11 * WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE
12 * AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL
13 * DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR
14 * PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
15 * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
16 * PERFORMANCE OF THIS SOFTWARE.
17 */
18
19 /**
20 * DOC: qdf_slist.h
21 *
22 * A minimal, singly linked list implementation, with push front, pop front, and
23 * remove capabilities. These are all O(1) operations.
24 *
25 * In order to remove an item, a pointer to the previous item must be known.
26 * Thus, removing an item is most efficient when combined with
27 * qdf_slist_for_each_del(). For cases where you need efficient removal of an
28 * arbitrary list node without iteration, consider using the doubly linked list
29 * qdf_list instead.
30 */
31
32 #ifndef __QDF_SLIST_H
33 #define __QDF_SLIST_H
34
35 #include "qdf_trace.h"
36 #include "qdf_util.h"
37
38 #define __qdf_slist_poison ((void *)0xdeaddeaddeaddeadull)
39
40 /**
41 * struct qdf_slist - a singly linked list
42 * @head: pointer to the head of the list
43 */
44 struct qdf_slist {
45 struct qdf_slist_node *head;
46 };
47
48 /**
49 * struct qdf_slist_node - a singly linked list node
50 * @next: pointer to the next node in the list, NULL if there is none
51 */
52 struct qdf_slist_node {
53 struct qdf_slist_node *next;
54 };
55
56 #define __qdf_slist_item(node, cursor, node_field) ({ \
57 struct qdf_slist_node *__n = (node); \
58 (__n ? qdf_container_of(__n, typeof(*(cursor)), node_field) : NULL); })
59
60 #define __qdf_slist_next_item(slist, cursor, node_field) \
61 __qdf_slist_item(cursor ? (cursor)->node_field.next : \
62 (slist)->head, cursor, node_field)
63
64 /**
65 * qdf_slist_for_each - iterate over all of the items in @slist
66 * @slist: pointer to the qdf_slist to iterate over
67 * @cursor: cursor pointer of the list's item type, populated for each item
68 * @node_field: name of the qdf_slist_node field in the item's type
69 */
70 #define qdf_slist_for_each(slist, cursor, node_field) \
71 for (cursor = __qdf_slist_item((slist)->head, cursor, node_field); \
72 cursor; \
73 cursor = __qdf_slist_item((cursor)->node_field.next, \
74 cursor, node_field))
75
76 /**
77 * qdf_slist_for_each_del - iterate over all of the items in @slist,
78 * allowing for the safe deletion of nodes during iteration
79 * @slist: pointer to the qdf_slist to iterate over
80 * @prev: cursor pointer, populated with the previous item
81 * @cursor: cursor pointer of the list's item type, populated for each item
82 * @node_field: name of the qdf_slist_node field in the item's type
83 */
84 #define qdf_slist_for_each_del(slist, prev, cursor, node_field) \
85 for (prev = NULL, \
86 cursor = __qdf_slist_item((slist)->head, cursor, node_field); \
87 cursor; \
88 prev = __qdf_slist_next_item(slist, prev, node_field) == \
89 cursor ? cursor : prev, \
90 cursor = __qdf_slist_next_item(slist, prev, node_field))
91
92 /**
93 * qdf_slist_init() - initialize a qdf_slist
94 * @slist: the list to initialize
95 *
96 * Return: None
97 */
qdf_slist_init(struct qdf_slist * slist)98 static inline void qdf_slist_init(struct qdf_slist *slist)
99 {
100 slist->head = NULL;
101 }
102
103 /**
104 * qdf_slist_deinit() - deinitialize a qdf_slist
105 * @slist: the list to deinitialize
106 *
107 * Return: None
108 */
qdf_slist_deinit(struct qdf_slist * slist)109 static inline void qdf_slist_deinit(struct qdf_slist *slist)
110 {
111 QDF_BUG(!slist->head);
112 slist->head = __qdf_slist_poison;
113 }
114
115 /**
116 * qdf_slist_empty() - check if a qdf_slist is empty
117 * @slist: the list to check
118 *
119 * Return: true if @slist contains zero items
120 */
qdf_slist_empty(struct qdf_slist * slist)121 static inline bool qdf_slist_empty(struct qdf_slist *slist)
122 {
123 return !slist->head;
124 }
125
126 /**
127 * qdf_slist_push() - push an item into the front of a qdf_slist
128 * @slist: the list to push into
129 * @cursor: the item to push
130 * @node_field: name of the qdf_slist_node field in the item's type
131 *
132 * Return: None
133 */
134 #define qdf_slist_push(slist, cursor, node_field) \
135 __qdf_slist_push(slist, &(cursor)->node_field)
136
137 static inline void
__qdf_slist_push(struct qdf_slist * slist,struct qdf_slist_node * node)138 __qdf_slist_push(struct qdf_slist *slist, struct qdf_slist_node *node)
139 {
140 node->next = slist->head;
141 slist->head = node;
142 }
143
144 /**
145 * qdf_slist_pop() - pop an item from the front of a qdf_slist
146 * @slist: the list to pop from
147 * @cursor: cursor pointer of the list's item type, not populated
148 * @node_field: name of the qdf_slist_node field in the item's type
149 *
150 * Return: pointer to the popped item, NULL if @slist was empty
151 */
152 #define qdf_slist_pop(slist, cursor, node_field) \
153 __qdf_slist_item(__qdf_slist_pop(slist), cursor, node_field)
154
__qdf_slist_pop(struct qdf_slist * slist)155 static inline struct qdf_slist_node *__qdf_slist_pop(struct qdf_slist *slist)
156 {
157 struct qdf_slist_node *node = slist->head;
158
159 if (!node)
160 return NULL;
161
162 slist->head = node->next;
163 node->next = __qdf_slist_poison;
164
165 return node;
166 }
167
168 /**
169 * qdf_slist_remove() - remove an item from a qdf_slist
170 * @slist: the list to remove from
171 * @prev: pointer to the item previous to the item to remove, NULL removes head
172 * @node_field: name of the qdf_slist_node field in the item's type
173 *
174 * Return: pointer to the removed item, NULL if none was removed
175 */
176 #define qdf_slist_remove(slist, prev, node_field) \
177 __qdf_slist_item(__qdf_slist_remove(slist, \
178 prev ? &(prev)->node_field : NULL), prev, node_field)
179
180 static inline struct qdf_slist_node *
__qdf_slist_remove(struct qdf_slist * slist,struct qdf_slist_node * prev)181 __qdf_slist_remove(struct qdf_slist *slist, struct qdf_slist_node *prev)
182 {
183 struct qdf_slist_node *node;
184
185 if (!prev)
186 return __qdf_slist_pop(slist);
187
188 if (!prev->next)
189 return NULL;
190
191 node = prev->next;
192 prev->next = node->next;
193 node->next = __qdf_slist_poison;
194
195 return node;
196 }
197
198 #endif /* __QDF_SLIST_H */
199
200