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 and doubly-linked lists. 9 */ 10 11 #ifndef FWK_LIST_H 12 #define FWK_LIST_H 13 14 #include <fwk_dlist.h> 15 #include <fwk_slist.h> 16 17 #include <stddef.h> 18 #include <stdint.h> 19 20 /*! 21 * \addtogroup GroupLibFramework Framework 22 * \{ 23 */ 24 25 /*! 26 * \addtogroup GroupLinkedList Linked Lists 27 * \{ 28 */ 29 30 /*! 31 * \brief Get the container in which a linked list node is stored. 32 * 33 * \param node Pointer to the linked list node to get the container of. 34 * \param type Type of the container. 35 * \param member Name of the linked list node member. 36 * 37 * \return Pointer to the container. 38 */ 39 #define FWK_LIST_GET(node, type, member) \ 40 ((type *)(((uintptr_t)node) - offsetof(type, member))) 41 42 /*! 43 * \brief Initialize a linked list. 44 * 45 * \param[out] list List to initialize. Must not be \c NULL. 46 * 47 * \return None. 48 */ 49 #define fwk_list_init(list) \ 50 _Generic((list), \ 51 struct fwk_slist * : __fwk_slist_init, \ 52 struct fwk_dlist * : __fwk_slist_init \ 53 )((struct fwk_slist *)list) 54 55 /*! 56 * \brief Retrieve the node at the head of a linked list. 57 * 58 * \param list Pointer to the list to retrieve the head of. Must not be \c NULL. 59 * 60 * \retval NULL The list is empty. 61 * \return Pointer to the node at the head of the linked list. 62 */ 63 #define fwk_list_head(list) \ 64 ((void *)_Generic((list), \ 65 const struct fwk_slist * : __fwk_slist_head, \ 66 const struct fwk_dlist * : __fwk_slist_head, \ 67 struct fwk_slist * : __fwk_slist_head, \ 68 struct fwk_dlist * : __fwk_slist_head \ 69 )((const struct fwk_slist *)list)) 70 71 /*! 72 * \brief Test whether a linked list is empty or not. 73 * 74 * \param list Pointer to the list to test. Must not be \c NULL. 75 * 76 * \retval true The linked list is empty. 77 * \retval false The linked list is not empty. 78 */ 79 #define fwk_list_is_empty(list) \ 80 _Generic((list), \ 81 const struct fwk_slist * : __fwk_slist_is_empty, \ 82 const struct fwk_dlist * : __fwk_slist_is_empty, \ 83 struct fwk_slist * : __fwk_slist_is_empty, \ 84 struct fwk_dlist * : __fwk_slist_is_empty \ 85 )((const struct fwk_slist *)list) 86 87 /*! 88 * \brief Add a new node to the head of a linked list. 89 * 90 * \param list Pointer to the list to add to. Must not be \c NULL. 91 * \param new Pointer to the node to add. Must not be \c NULL. In debug mode, 92 * the node links must be \c NULL as they are checked to ensure the node is 93 * not already in use. 94 * 95 * \return None. 96 */ 97 #define fwk_list_push_head(list, new) \ 98 _Generic((list), \ 99 struct fwk_slist * : __fwk_slist_push_head, \ 100 struct fwk_dlist * : __fwk_dlist_push_head \ 101 )(list, new) 102 103 /*! 104 * \brief Add a new node to the end of a linked list. 105 * 106 * \param list Pointer to the list to add to. Must not be \c NULL. 107 * \param new Pointer to the node to add. Must not be \c NULL. In debug mode, 108 * the node links must be \c NULL as they are checked to ensure the node is 109 * not already in use. 110 * 111 * \return None. 112 */ 113 #define fwk_list_push_tail(list, new) \ 114 _Generic((list), \ 115 struct fwk_slist * : __fwk_slist_push_tail, \ 116 struct fwk_dlist * : __fwk_dlist_push_tail \ 117 )(list, new) 118 119 /*! 120 * \brief Remove and return the head node from a linked list. 121 * 122 * \param list Pointer to the list to remove from. Must not be \c NULL. 123 * 124 * \retval NULL The list was empty. 125 * \return The linked list node that was removed. In debug mode, the node links 126 * are set to \c NULL to ensure the node no longer references the list it 127 * has been removed from. 128 */ 129 #define fwk_list_pop_head(list) \ 130 _Generic((list), \ 131 struct fwk_slist * : __fwk_slist_pop_head, \ 132 struct fwk_dlist * : __fwk_dlist_pop_head \ 133 )(list) 134 135 /*! 136 * \brief Get the next node of a linked list. 137 * 138 * \param list Pointer to the list to get the node from. Must not be \c NULL. 139 * \param node Pointer to the node to get the next one from. Must not be \c 140 * NULL. 141 * 142 * \retval NULL 'node' was the last node of the list. 143 * \return The pointer to the next node. 144 */ 145 #define fwk_list_next(list, node) \ 146 ((void *) _Generic((list), \ 147 const struct fwk_slist * : __fwk_slist_next, \ 148 const struct fwk_dlist * : __fwk_slist_next, \ 149 struct fwk_slist * : __fwk_slist_next, \ 150 struct fwk_dlist * : __fwk_slist_next \ 151 )((const struct fwk_slist *)list, (const struct fwk_slist_node *)node)) 152 153 /*! 154 * \brief Remove a node from a linked list. 155 * 156 * \details In debug mode, the node being removed has its links set to \c NULL 157 * to ensure the node no longer references the list it has been removed 158 * from. 159 * 160 * \param list Pointer to the list to remove the node from. Must not be \c NULL. 161 * \param node Pointer to the node to remove. Must not be \c NULL. The node must 162 * be in the list. 163 * 164 * \return None. 165 */ 166 #define fwk_list_remove(list, node) \ 167 _Generic((list), \ 168 struct fwk_slist * : __fwk_slist_remove, \ 169 struct fwk_dlist * : __fwk_dlist_remove \ 170 )(list, node) 171 172 /*! 173 * \brief Insert a node into a linked list. 174 * 175 * \param list Pointer to the list. Must not be \c NULL. 176 * \param new Pointer to the node to insert. Must not be \c NULL. In debug mode, 177 * the node links must be \c NULL as they are checked to ensure the node is 178 * not already in use. 179 * \param node Pointer to the node that \p new will be inserted before. If this 180 * is \c NULL then the new node will be inserted at the tail of the list. 181 * 182 * \return None. 183 */ 184 #define fwk_list_insert(list, new, node) \ 185 _Generic((list), \ 186 struct fwk_dlist * : __fwk_dlist_insert \ 187 )(list, new, node) 188 189 /*! 190 * \brief Check if a node is in a list. 191 * 192 * \param list Pointer to the list. Must not be \c NULL. 193 * \param node Pointer to the node. Must not be \c NULL. 194 * 195 * \retval true \p node is in \p list. 196 * \retval false \p node is not in \p list. 197 */ 198 #define fwk_list_contains(list, node) \ 199 _Generic((list), \ 200 const struct fwk_slist * : __fwk_slist_contains, \ 201 const struct fwk_dlist * : __fwk_slist_contains, \ 202 struct fwk_slist * : __fwk_slist_contains, \ 203 struct fwk_dlist * : __fwk_slist_contains \ 204 )((const struct fwk_slist *)list, (const struct fwk_slist_node *)node) 205 206 /*! 207 * \brief Iterate over all nodes in a list. 208 * 209 * \param list Pointer to the list. Must not be \c NULL. 210 * \param node Pointer to the node. Must not be \c NULL. 211 * \param type Type of the container structure that contains fwk_slist node. 212 * \param member The name of the node element in the struct. 213 * \param elem Pointer to the struct object to use inside the loop 214 */ 215 #define FWK_LIST_FOR_EACH(list, node, type, member, elem) \ 216 for (node = fwk_list_head(list), \ 217 elem = FWK_LIST_GET(node, type, member); \ 218 node != NULL; \ 219 node = fwk_list_next(list, node), \ 220 elem = FWK_LIST_GET(node, type, member)) 221 222 /*! 223 * \} 224 */ 225 226 /*! 227 * \} 228 */ 229 230 #endif /* FWK_LIST_H */ 231