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__SLIST_H 27 #define __ARES__SLIST_H 28 29 30 /*! \addtogroup ares_slist SkipList Data Structure 31 * 32 * This data structure is known as a Skip List, which in essence is a sorted 33 * linked list with multiple levels of linkage to gain some algorithmic 34 * advantages. The usage symantecs are almost identical to what you'd expect 35 * with a linked list. 36 * 37 * Average time complexity: 38 * - Insert: O(log n) 39 * - Search: O(log n) 40 * - Delete: O(1) -- delete assumes you hold a node pointer 41 * 42 * It should be noted, however, that "effort" involved with an insert or 43 * remove operation is higher than a normal linked list. For very small 44 * lists this may be less efficient, but for any list with a moderate number 45 * of entries this will prove much more efficient. 46 * 47 * This data structure is often compared with a Binary Search Tree in 48 * functionality and usage. 49 * 50 * @{ 51 */ 52 struct ares_slist; 53 54 /*! SkipList Object, opaque */ 55 typedef struct ares_slist ares_slist_t; 56 57 struct ares_slist_node; 58 59 /*! SkipList Node Object, opaque */ 60 typedef struct ares_slist_node ares_slist_node_t; 61 62 /*! SkipList Node Value destructor callback 63 * 64 * \param[in] data User-defined data to destroy 65 */ 66 typedef void (*ares_slist_destructor_t)(void *data); 67 68 /*! SkipList comparison function 69 * 70 * \param[in] data1 First user-defined data object 71 * \param[in] data2 Second user-defined data object 72 * \return < 0 if data1 < data1, > 0 if data1 > data2, 0 if data1 == data2 73 */ 74 typedef int (*ares_slist_cmp_t)(const void *data1, const void *data2); 75 76 /*! Create SkipList 77 * 78 * \param[in] rand_state Initialized ares random state. 79 * \param[in] cmp SkipList comparison function 80 * \param[in] destruct SkipList Node Value Destructor. Optional, use NULL. 81 * \return Initialized SkipList Object or NULL on misuse or ENOMEM 82 */ 83 ares_slist_t *ares_slist_create(ares_rand_state *rand_state, 84 ares_slist_cmp_t cmp, 85 ares_slist_destructor_t destruct); 86 87 /*! Replace SkipList Node Value Destructor 88 * 89 * \param[in] list Initialized SkipList Object 90 * \param[in] destruct Replacement destructor. May be NULL. 91 */ 92 void ares_slist_replace_destructor(ares_slist_t *list, 93 ares_slist_destructor_t destruct); 94 95 /*! Insert Value into SkipList 96 * 97 * \param[in] list Initialized SkipList Object 98 * \param[in] val Node Value. Must not be NULL. Function takes ownership 99 * and will have destructor called. 100 * \return SkipList Node Object or NULL on misuse or ENOMEM 101 */ 102 ares_slist_node_t *ares_slist_insert(ares_slist_t *list, void *val); 103 104 /*! Fetch first node in SkipList 105 * 106 * \param[in] list Initialized SkipList Object 107 * \return SkipList Node Object or NULL if none 108 */ 109 ares_slist_node_t *ares_slist_node_first(const ares_slist_t *list); 110 111 /*! Fetch last node in SkipList 112 * 113 * \param[in] list Initialized SkipList Object 114 * \return SkipList Node Object or NULL if none 115 */ 116 ares_slist_node_t *ares_slist_node_last(const ares_slist_t *list); 117 118 /*! Fetch next node in SkipList 119 * 120 * \param[in] node SkipList Node Object 121 * \return SkipList Node Object or NULL if none 122 */ 123 ares_slist_node_t *ares_slist_node_next(const ares_slist_node_t *node); 124 125 /*! Fetch previous node in SkipList 126 * 127 * \param[in] node SkipList Node Object 128 * \return SkipList Node Object or NULL if none 129 */ 130 ares_slist_node_t *ares_slist_node_prev(const ares_slist_node_t *node); 131 132 /*! Fetch SkipList Node Object by Value 133 * 134 * \param[in] list Initialized SkipList Object 135 * \param[in] val Object to use for comparison 136 * \return SkipList Node Object or NULL if not found 137 */ 138 ares_slist_node_t *ares_slist_node_find(const ares_slist_t *list, 139 const void *val); 140 141 142 /*! Fetch Node Value 143 * 144 * \param[in] node SkipList Node Object 145 * \return user defined node value 146 */ 147 void *ares_slist_node_val(ares_slist_node_t *node); 148 149 /*! Fetch number of entries in SkipList Object 150 * 151 * \param[in] list Initialized SkipList Object 152 * \return number of entries 153 */ 154 size_t ares_slist_len(const ares_slist_t *list); 155 156 /*! Fetch SkipList Object from SkipList Node 157 * 158 * \param[in] node SkipList Node Object 159 * \return SkipList Object 160 */ 161 ares_slist_t *ares_slist_node_parent(ares_slist_node_t *node); 162 163 /*! Fetch first Node Value in SkipList 164 * 165 * \param[in] list Initialized SkipList Object 166 * \return user defined node value or NULL if none 167 */ 168 void *ares_slist_first_val(const ares_slist_t *list); 169 170 /*! Fetch last Node Value in SkipList 171 * 172 * \param[in] list Initialized SkipList Object 173 * \return user defined node value or NULL if none 174 */ 175 void *ares_slist_last_val(const ares_slist_t *list); 176 177 /*! Take back ownership of Node Value in SkipList, remove from SkipList. 178 * 179 * \param[in] node SkipList Node Object 180 * \return user defined node value 181 */ 182 void *ares_slist_node_claim(ares_slist_node_t *node); 183 184 /*! The internals of the node have changed, thus its position in the sorted 185 * list is no longer valid. This function will remove it and re-add it to 186 * the proper position without needing to perform any memory allocations 187 * and thus cannot fail. 188 * 189 * \param[in] node SkipList Node Object 190 */ 191 void ares_slist_node_reinsert(ares_slist_node_t *node); 192 193 /*! Remove Node from SkipList, calling destructor for Node Value. 194 * 195 * \param[in] node SkipList Node Object 196 */ 197 void ares_slist_node_destroy(ares_slist_node_t *node); 198 199 /*! Destroy SkipList Object. If there are any nodes, they will be destroyed. 200 * 201 * \param[in] list Initialized SkipList Object 202 */ 203 void ares_slist_destroy(ares_slist_t *list); 204 205 /*! @} */ 206 207 #endif /* __ARES__SLIST_H */ 208