1 /* MIT License 2 * 3 * Copyright (c) 2023 Brad House 4 * 5 * Permission is hereby granted, free of charge, to any person obtaining a copy 6 * of this software and associated documentation files (the "Software"), to deal 7 * in the Software without restriction, including without limitation the rights 8 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell 9 * copies of the Software, and to permit persons to whom the Software is 10 * furnished to do so, subject to the following conditions: 11 * 12 * The above copyright notice and this permission notice (including the next 13 * paragraph) shall be included in all copies or substantial portions of the 14 * Software. 15 * 16 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 17 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 18 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 19 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 20 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 21 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE 22 * SOFTWARE. 23 * 24 * SPDX-License-Identifier: MIT 25 */ 26 #ifndef __ARES__LLIST_H 27 #define __ARES__LLIST_H 28 29 /*! \addtogroup ares__llist LinkedList Data Structure 30 * 31 * This is a doubly-linked list data structure. 32 * 33 * Average time complexity: 34 * - Insert: O(1) -- head or tail 35 * - Search: O(n) 36 * - Delete: O(1) -- delete assumes you hold a node pointer 37 * 38 * @{ 39 */ 40 41 struct ares__llist; 42 43 /*! Opaque data structure for linked list */ 44 typedef struct ares__llist ares__llist_t; 45 46 struct ares__llist_node; 47 48 /*! Opaque data structure for a node in a linked list */ 49 typedef struct ares__llist_node ares__llist_node_t; 50 51 /*! Callback to free user-defined node data 52 * 53 * \param[in] data user supplied data 54 */ 55 typedef void (*ares__llist_destructor_t)(void *data); 56 57 /*! Create a linked list object 58 * 59 * \param[in] destruct Optional. Destructor to call on all removed nodes 60 * \return linked list object or NULL on out of memory 61 */ 62 ares__llist_t *ares__llist_create(ares__llist_destructor_t destruct); 63 64 /*! Replace destructor for linked list nodes. Typically this is used 65 * when wanting to disable the destructor by using NULL. 66 * 67 * \param[in] list Initialized linked list object 68 * \param[in] destruct replacement destructor, NULL is allowed 69 */ 70 void ares__llist_replace_destructor(ares__llist_t *list, 71 ares__llist_destructor_t destruct); 72 73 /*! Insert value as the first node in the linked list 74 * 75 * \param[in] list Initialized linked list object 76 * \param[in] val user-supplied value. 77 * \return node object referencing place in list, or null if out of memory or 78 * misuse 79 */ 80 ares__llist_node_t *ares__llist_insert_first(ares__llist_t *list, void *val); 81 82 /*! Insert value as the last node in the linked list 83 * 84 * \param[in] list Initialized linked list object 85 * \param[in] val user-supplied value. 86 * \return node object referencing place in list, or null if out of memory or 87 * misuse 88 */ 89 ares__llist_node_t *ares__llist_insert_last(ares__llist_t *list, void *val); 90 91 /*! Insert value before specified node in the linked list 92 * 93 * \param[in] node node referenced to insert before 94 * \param[in] val user-supplied value. 95 * \return node object referencing place in list, or null if out of memory or 96 * misuse 97 */ 98 ares__llist_node_t *ares__llist_insert_before(ares__llist_node_t *node, 99 void *val); 100 101 /*! Insert value after specified node in the linked list 102 * 103 * \param[in] node node referenced to insert after 104 * \param[in] val user-supplied value. 105 * \return node object referencing place in list, or null if out of memory or 106 * misuse 107 */ 108 ares__llist_node_t *ares__llist_insert_after(ares__llist_node_t *node, 109 void *val); 110 111 /*! Obtain first node in list 112 * 113 * \param[in] list Initialized list object 114 * \return first node in list or NULL if none 115 */ 116 ares__llist_node_t *ares__llist_node_first(ares__llist_t *list); 117 118 /*! Obtain last node in list 119 * 120 * \param[in] list Initialized list object 121 * \return last node in list or NULL if none 122 */ 123 ares__llist_node_t *ares__llist_node_last(ares__llist_t *list); 124 125 /*! Obtain next node in respect to specified node 126 * 127 * \param[in] node Node referenced 128 * \return node or NULL if none 129 */ 130 ares__llist_node_t *ares__llist_node_next(ares__llist_node_t *node); 131 132 /*! Obtain previous node in respect to specified node 133 * 134 * \param[in] node Node referenced 135 * \return node or NULL if none 136 */ 137 ares__llist_node_t *ares__llist_node_prev(ares__llist_node_t *node); 138 139 /*! Obtain value from node 140 * 141 * \param[in] node Node referenced 142 * \return user provided value from node 143 */ 144 void *ares__llist_node_val(ares__llist_node_t *node); 145 146 /*! Obtain the number of entries in the list 147 * 148 * \param[in] list Initialized list object 149 * \return count 150 */ 151 size_t ares__llist_len(const ares__llist_t *list); 152 153 /*! Obtain list object from referenced node 154 * 155 * \param[in] node Node referenced 156 * \return list object node belongs to 157 */ 158 ares__llist_t *ares__llist_node_parent(ares__llist_node_t *node); 159 160 /*! Obtain the first user-supplied value in the list 161 * 162 * \param[in] list Initialized list object 163 * \return first user supplied value or NULL if none 164 */ 165 void *ares__llist_first_val(ares__llist_t *list); 166 167 /*! Obtain the last user-supplied value in the list 168 * 169 * \param[in] list Initialized list object 170 * \return last user supplied value or NULL if none 171 */ 172 void *ares__llist_last_val(ares__llist_t *list); 173 174 /*! Take ownership of user-supplied value in list without calling destructor. 175 * Will unchain entry from list. 176 * 177 * \param[in] node Node referenced 178 * \return user supplied value 179 */ 180 void *ares__llist_node_claim(ares__llist_node_t *node); 181 182 /*! Replace user-supplied value for node 183 * 184 * \param[in] node Node referenced 185 * \param[in] val new user-supplied value 186 */ 187 void ares__llist_node_replace(ares__llist_node_t *node, void *val); 188 189 /*! Destroy the node, removing it from the list and calling destructor. 190 * 191 * \param[in] node Node referenced 192 */ 193 void ares__llist_node_destroy(ares__llist_node_t *node); 194 195 /*! Destroy the list object and all nodes in the list. 196 * 197 * \param[in] list Initialized list object 198 */ 199 void ares__llist_destroy(ares__llist_t *list); 200 201 /*! Detach node from the current list and re-attach it to the new list as the 202 * last entry. 203 * 204 * \param[in] node node to move 205 * \param[in] parent new list 206 */ 207 void ares__llist_node_move_parent_last(ares__llist_node_t *node, 208 ares__llist_t *new_parent); 209 210 /*! Detach node from the current list and re-attach it to the new list as the 211 * first entry. 212 * 213 * \param[in] node node to move 214 * \param[in] parent new list 215 */ 216 void ares__llist_node_move_parent_first(ares__llist_node_t *node, 217 ares__llist_t *new_parent); 218 /*! @} */ 219 220 #endif /* __ARES__LLIST_H */ 221