ares_llist.h (8072B)
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 CARES_EXTERN 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 CARES_EXTERN void 71 ares_llist_replace_destructor(ares_llist_t *list, 72 ares_llist_destructor_t destruct); 73 74 /*! Insert value as the first node in the linked list 75 * 76 * \param[in] list Initialized linked list object 77 * \param[in] val user-supplied value. 78 * \return node object referencing place in list, or null if out of memory or 79 * misuse 80 */ 81 CARES_EXTERN ares_llist_node_t *ares_llist_insert_first(ares_llist_t *list, 82 void *val); 83 84 /*! Insert value as the last node in the linked list 85 * 86 * \param[in] list Initialized linked list object 87 * \param[in] val user-supplied value. 88 * \return node object referencing place in list, or null if out of memory or 89 * misuse 90 */ 91 CARES_EXTERN ares_llist_node_t *ares_llist_insert_last(ares_llist_t *list, 92 void *val); 93 94 /*! Insert value before specified node in the linked list 95 * 96 * \param[in] node node referenced to insert before 97 * \param[in] val user-supplied value. 98 * \return node object referencing place in list, or null if out of memory or 99 * misuse 100 */ 101 CARES_EXTERN ares_llist_node_t * 102 ares_llist_insert_before(ares_llist_node_t *node, void *val); 103 104 /*! Insert value after specified node in the linked list 105 * 106 * \param[in] node node referenced to insert after 107 * \param[in] val user-supplied value. 108 * \return node object referencing place in list, or null if out of memory or 109 * misuse 110 */ 111 CARES_EXTERN ares_llist_node_t *ares_llist_insert_after(ares_llist_node_t *node, 112 void *val); 113 114 /*! Obtain first node in list 115 * 116 * \param[in] list Initialized list object 117 * \return first node in list or NULL if none 118 */ 119 CARES_EXTERN ares_llist_node_t *ares_llist_node_first(ares_llist_t *list); 120 121 /*! Obtain last node in list 122 * 123 * \param[in] list Initialized list object 124 * \return last node in list or NULL if none 125 */ 126 CARES_EXTERN ares_llist_node_t *ares_llist_node_last(ares_llist_t *list); 127 128 /*! Obtain a node based on its index. This is an O(n) operation. 129 * 130 * \param[in] list Initialized list object 131 * \param[in] idx Index of node to retrieve 132 * \return node at index or NULL if invalid index 133 */ 134 CARES_EXTERN ares_llist_node_t *ares_llist_node_idx(ares_llist_t *list, 135 size_t idx); 136 137 /*! Obtain next node in respect to specified node 138 * 139 * \param[in] node Node referenced 140 * \return node or NULL if none 141 */ 142 CARES_EXTERN ares_llist_node_t *ares_llist_node_next(ares_llist_node_t *node); 143 144 /*! Obtain previous node in respect to specified node 145 * 146 * \param[in] node Node referenced 147 * \return node or NULL if none 148 */ 149 CARES_EXTERN ares_llist_node_t *ares_llist_node_prev(ares_llist_node_t *node); 150 151 152 /*! Obtain value from node 153 * 154 * \param[in] node Node referenced 155 * \return user provided value from node 156 */ 157 CARES_EXTERN void *ares_llist_node_val(ares_llist_node_t *node); 158 159 /*! Obtain the number of entries in the list 160 * 161 * \param[in] list Initialized list object 162 * \return count 163 */ 164 CARES_EXTERN size_t ares_llist_len(const ares_llist_t *list); 165 166 /*! Clear all entries in the list, but don't destroy the list object. 167 * 168 * \param[in] list Initialized list object 169 */ 170 CARES_EXTERN void ares_llist_clear(ares_llist_t *list); 171 172 /*! Obtain list object from referenced node 173 * 174 * \param[in] node Node referenced 175 * \return list object node belongs to 176 */ 177 CARES_EXTERN ares_llist_t *ares_llist_node_parent(ares_llist_node_t *node); 178 179 /*! Obtain the first user-supplied value in the list 180 * 181 * \param[in] list Initialized list object 182 * \return first user supplied value or NULL if none 183 */ 184 CARES_EXTERN void *ares_llist_first_val(ares_llist_t *list); 185 186 /*! Obtain the last user-supplied value in the list 187 * 188 * \param[in] list Initialized list object 189 * \return last user supplied value or NULL if none 190 */ 191 CARES_EXTERN void *ares_llist_last_val(ares_llist_t *list); 192 193 /*! Take ownership of user-supplied value in list without calling destructor. 194 * Will unchain entry from list. 195 * 196 * \param[in] node Node referenced 197 * \return user supplied value 198 */ 199 CARES_EXTERN void *ares_llist_node_claim(ares_llist_node_t *node); 200 201 /*! Replace user-supplied value for node 202 * 203 * \param[in] node Node referenced 204 * \param[in] val new user-supplied value 205 */ 206 CARES_EXTERN void ares_llist_node_replace(ares_llist_node_t *node, void *val); 207 208 /*! Destroy the node, removing it from the list and calling destructor. 209 * 210 * \param[in] node Node referenced 211 */ 212 CARES_EXTERN void ares_llist_node_destroy(ares_llist_node_t *node); 213 214 /*! Destroy the list object and all nodes in the list. 215 * 216 * \param[in] list Initialized list object 217 */ 218 CARES_EXTERN void ares_llist_destroy(ares_llist_t *list); 219 220 /*! Detach node from the current list and re-attach it to the new list as the 221 * last entry. 222 * 223 * \param[in] node node to move 224 * \param[in] new_parent new list 225 */ 226 CARES_EXTERN void ares_llist_node_mvparent_last(ares_llist_node_t *node, 227 ares_llist_t *new_parent); 228 229 /*! Detach node from the current list and re-attach it to the new list as the 230 * first entry. 231 * 232 * \param[in] node node to move 233 * \param[in] new_parent new list 234 */ 235 CARES_EXTERN void ares_llist_node_mvparent_first(ares_llist_node_t *node, 236 ares_llist_t *new_parent); 237 /*! @} */ 238 239 #endif /* __ARES__LLIST_H */