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 */ 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 */ 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 */ 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 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 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 * 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