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(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(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(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(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(ares__slist_t *list, const void *val); 139 140 141 /*! Fetch Node Value 142 * 143 * \param[in] node SkipList Node Object 144 * \return user defined node value 145 */ 146 void *ares__slist_node_val(ares__slist_node_t *node); 147 148 /*! Fetch number of entries in SkipList Object 149 * 150 * \param[in] list Initialized SkipList Object 151 * \return number of entries 152 */ 153 size_t ares__slist_len(const ares__slist_t *list); 154 155 /*! Fetch SkipList Object from SkipList Node 156 * 157 * \param[in] node SkipList Node Object 158 * \return SkipList Object 159 */ 160 ares__slist_t *ares__slist_node_parent(ares__slist_node_t *node); 161 162 /*! Fetch first Node Value in SkipList 163 * 164 * \param[in] list Initialized SkipList Object 165 * \return user defined node value or NULL if none 166 */ 167 void *ares__slist_first_val(ares__slist_t *list); 168 169 /*! Fetch last Node Value in SkipList 170 * 171 * \param[in] list Initialized SkipList Object 172 * \return user defined node value or NULL if none 173 */ 174 void *ares__slist_last_val(ares__slist_t *list); 175 176 /*! Take back ownership of Node Value in SkipList, remove from SkipList. 177 * 178 * \param[in] node SkipList Node Object 179 * \return user defined node value 180 */ 181 void *ares__slist_node_claim(ares__slist_node_t *node); 182 183 /*! The internals of the node have changed, thus its position in the sorted 184 * list is no longer valid. This function will remove it and re-add it to 185 * the proper position without needing to perform any memory allocations 186 * and thus cannot fail. 187 * 188 * \param[in] node SkipList Node Object 189 */ 190 void ares__slist_node_reinsert(ares__slist_node_t *node); 191 192 /*! Remove Node from SkipList, calling destructor for Node Value. 193 * 194 * \param[in] node SkipList Node Object 195 */ 196 void ares__slist_node_destroy(ares__slist_node_t *node); 197 198 /*! Destroy SkipList Object. If there are any nodes, they will be destroyed. 199 * 200 * \param[in] list Initialized SkipList Object 201 */ 202 void ares__slist_destroy(ares__slist_t *list); 203 204 /*! @} */ 205 206 #endif /* __ARES__SLIST_H */ 207