diff options
author | robot-contrib <robot-contrib@yandex-team.com> | 2024-10-17 11:21:35 +0300 |
---|---|---|
committer | robot-contrib <robot-contrib@yandex-team.com> | 2024-10-17 11:35:23 +0300 |
commit | 3682ce7f2626a0e22e9cf839b808faed3c5d70d6 (patch) | |
tree | f7d409766375889badc8397a73ec0571a74b5ee8 /contrib/libs/c-ares/src/lib/dsa | |
parent | 09691831380ca7c15cfed3445465e27837c4130d (diff) | |
download | ydb-3682ce7f2626a0e22e9cf839b808faed3c5d70d6.tar.gz |
Update contrib/libs/c-ares to 1.34.2
commit_hash:abd65f143c484666e1545e6bbfb9d947df95ecd6
Diffstat (limited to 'contrib/libs/c-ares/src/lib/dsa')
-rw-r--r-- | contrib/libs/c-ares/src/lib/dsa/ares__array.h | 223 | ||||
-rw-r--r-- | contrib/libs/c-ares/src/lib/dsa/ares__htable_asvp.h | 130 | ||||
-rw-r--r-- | contrib/libs/c-ares/src/lib/dsa/ares__htable_strvp.h | 118 | ||||
-rw-r--r-- | contrib/libs/c-ares/src/lib/dsa/ares__htable_szvp.h | 117 | ||||
-rw-r--r-- | contrib/libs/c-ares/src/lib/dsa/ares__htable_vpvp.h | 128 | ||||
-rw-r--r-- | contrib/libs/c-ares/src/lib/dsa/ares__llist.h | 235 | ||||
-rw-r--r-- | contrib/libs/c-ares/src/lib/dsa/ares_array.c (renamed from contrib/libs/c-ares/src/lib/dsa/ares__array.c) | 156 | ||||
-rw-r--r-- | contrib/libs/c-ares/src/lib/dsa/ares_htable.c (renamed from contrib/libs/c-ares/src/lib/dsa/ares__htable.c) | 179 | ||||
-rw-r--r-- | contrib/libs/c-ares/src/lib/dsa/ares_htable.h (renamed from contrib/libs/c-ares/src/lib/dsa/ares__htable.h) | 46 | ||||
-rw-r--r-- | contrib/libs/c-ares/src/lib/dsa/ares_htable_asvp.c (renamed from contrib/libs/c-ares/src/lib/dsa/ares__htable_asvp.c) | 80 | ||||
-rw-r--r-- | contrib/libs/c-ares/src/lib/dsa/ares_htable_dict.c | 228 | ||||
-rw-r--r-- | contrib/libs/c-ares/src/lib/dsa/ares_htable_strvp.c (renamed from contrib/libs/c-ares/src/lib/dsa/ares__htable_strvp.c) | 104 | ||||
-rw-r--r-- | contrib/libs/c-ares/src/lib/dsa/ares_htable_szvp.c (renamed from contrib/libs/c-ares/src/lib/dsa/ares__htable_szvp.c) | 69 | ||||
-rw-r--r-- | contrib/libs/c-ares/src/lib/dsa/ares_htable_vpstr.c | 186 | ||||
-rw-r--r-- | contrib/libs/c-ares/src/lib/dsa/ares_htable_vpvp.c (renamed from contrib/libs/c-ares/src/lib/dsa/ares__htable_vpvp.c) | 75 | ||||
-rw-r--r-- | contrib/libs/c-ares/src/lib/dsa/ares_llist.c (renamed from contrib/libs/c-ares/src/lib/dsa/ares__llist.c) | 150 | ||||
-rw-r--r-- | contrib/libs/c-ares/src/lib/dsa/ares_slist.c (renamed from contrib/libs/c-ares/src/lib/dsa/ares__slist.c) | 146 | ||||
-rw-r--r-- | contrib/libs/c-ares/src/lib/dsa/ares_slist.h (renamed from contrib/libs/c-ares/src/lib/dsa/ares__slist.h) | 55 |
18 files changed, 965 insertions, 1460 deletions
diff --git a/contrib/libs/c-ares/src/lib/dsa/ares__array.h b/contrib/libs/c-ares/src/lib/dsa/ares__array.h deleted file mode 100644 index 6fa1c0e15e..0000000000 --- a/contrib/libs/c-ares/src/lib/dsa/ares__array.h +++ /dev/null @@ -1,223 +0,0 @@ -/* MIT License - * - * Copyright (c) 2024 Brad House - * - * Permission is hereby granted, free of charge, to any person obtaining a copy - * of this software and associated documentation files (the "Software"), to deal - * in the Software without restriction, including without limitation the rights - * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell - * copies of the Software, and to permit persons to whom the Software is - * furnished to do so, subject to the following conditions: - * - * The above copyright notice and this permission notice (including the next - * paragraph) shall be included in all copies or substantial portions of the - * Software. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR - * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, - * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE - * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER - * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, - * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE - * SOFTWARE. - * - * SPDX-License-Identifier: MIT - */ -#ifndef __ARES__ARRAY_H -#define __ARES__ARRAY_H - -/*! \addtogroup ares__array Array Data Structure - * - * This is an array with helpers. It is meant to have as little overhead - * as possible over direct array management by applications but to provide - * safety and some optimization features. It can also return the array in - * native form once all manipulation has been performed. - * - * @{ - */ - -struct ares__array; - -/*! Opaque data structure for array */ -typedef struct ares__array ares__array_t; - -/*! Callback to free user-defined member data - * - * \param[in] data pointer to member of array to be destroyed. The pointer - * itself must not be destroyed, just the data it contains. - */ -typedef void (*ares__array_destructor_t)(void *data); - -/*! Callback to compare two array elements used for sorting - * - * \param[in] data1 array member 1 - * \param[in] data2 array member 2 - * \return < 0 if data1 < data2, > 0 if data1 > data2, 0 if data1 == data2 - */ -typedef int (*ares__array_cmp_t)(const void *data1, const void *data2); - -/*! Create an array object - * - * NOTE: members of the array are typically going to be an going to be a - * struct with compiler/ABI specific padding to ensure proper alignment. - * Care needs to be taken if using primitive types, especially floating - * point numbers which size may not indicate the required alignment. - * For example, a double may be 80 bits (10 bytes), but required - * alignment of 16 bytes. In such a case, a member_size of 16 would be - * required to be used. - * - * \param[in] destruct Optional. Destructor to call on a removed member - * \param[in] member_size Size of array member, usually determined using - * sizeof() for the member such as a struct. - * - * \return array object or NULL on out of memory - */ -ares__array_t *ares__array_create(size_t member_size, - ares__array_destructor_t destruct); - - -/*! Request the array be at least the requested size. Useful if the desired - * array size is known prior to populating the array to prevent reallocations. - * - * \param[in] arr Initialized array object. - * \param[in] size Minimum number of members - * \return ARES_SUCCESS on success, ARES_EFORMERR on misuse, - * ARES_ENOMEM on out of memory */ -ares_status_t ares__array_set_size(ares__array_t *arr, size_t size); - -/*! Sort the array using the given comparison function. This is not - * persistent, any future elements inserted will not maintain this sort. - * - * \param[in] arr Initialized array object. - * \param[in] cb Sort callback - * \return ARES_SUCCESS on success - */ -ares_status_t ares__array_sort(ares__array_t *arr, ares__array_cmp_t cmp); - -/*! Destroy an array object. If a destructor is set, will be called on each - * member of the array. - * - * \param[in] arr Initialized array object. - */ -void ares__array_destroy(ares__array_t *arr); - -/*! Retrieve the array in the native format. This will also destroy the - * container. It is the responsibility of the caller to free the returned - * pointer and also any data within each array element. - * - * \param[in] arr Initialized array object - * \param[out] num_members the number of members in the returned array - * \return pointer to native array on success, NULL on failure. - */ -void *ares__array_finish(ares__array_t *arr, size_t *num_members); - -/*! Retrieve the number of members in the array - * - * \param[in] arr Initialized array object. - * \return numbrer of members - */ -size_t ares__array_len(const ares__array_t *arr); - -/*! Insert a new array member at the given index - * - * \param[out] elem_ptr Optional. Pointer to the returned array element. - * \param[in] arr Initialized array object. - * \param[in] idx Index in array to place new element, will shift any - * elements down that exist after this point. - * \return ARES_SUCCESS on success, ARES_EFORMERR on bad index, - * ARES_ENOMEM on out of memory. - */ -ares_status_t ares__array_insert_at(void **elem_ptr, ares__array_t *arr, - size_t idx); - -/*! Insert a new array member at the end of the array - * - * \param[out] elem_ptr Optional. Pointer to the returned array element. - * \param[in] arr Initialized array object. - * \return ARES_SUCCESS on success, ARES_ENOMEM on out of memory. - */ -ares_status_t ares__array_insert_last(void **elem_ptr, ares__array_t *arr); - -/*! Insert a new array member at the beginning of the array - * - * \param[out] elem_ptr Optional. Pointer to the returned array element. - * \param[in] arr Initialized array object. - * \return ARES_SUCCESS on success, ARES_ENOMEM on out of memory. - */ -ares_status_t ares__array_insert_first(void **elem_ptr, ares__array_t *arr); - -/*! Fetch a pointer to the given element in the array - * \param[in] array Initialized array object - * \param[in] idx Index to fetch - * \return pointer on success, NULL on failure */ -void *ares__array_at(ares__array_t *arr, size_t idx); - -/*! Fetch a pointer to the first element in the array - * \param[in] array Initialized array object - * \return pointer on success, NULL on failure */ -void *ares__array_first(ares__array_t *arr); - -/*! Fetch a pointer to the last element in the array - * \param[in] array Initialized array object - * \return pointer on success, NULL on failure */ -void *ares__array_last(ares__array_t *arr); - -/*! Fetch a constant pointer to the given element in the array - * \param[in] array Initialized array object - * \param[in] idx Index to fetch - * \return pointer on success, NULL on failure */ -const void *ares__array_at_const(const ares__array_t *arr, size_t idx); - -/*! Fetch a constant pointer to the first element in the array - * \param[in] array Initialized array object - * \return pointer on success, NULL on failure */ -const void *ares__array_first_const(const ares__array_t *arr); - -/*! Fetch a constant pointer to the last element in the array - * \param[in] array Initialized array object - * \return pointer on success, NULL on failure */ -const void *ares__array_last_const(const ares__array_t *arr); - -/*! Claim the data from the specified array index, copying it to the buffer - * provided by the caller. The index specified in the array will then be - * removed (without calling any possible destructor) - * - * \param[in,out] dest Optional. Buffer to hold array member. Pass NULL - * if not needed. This could leak memory if array - * member needs destructor if not provided. - * \param[in] dest_size Size of buffer provided, used as a sanity check. - * Must match member_size provided to - * ares__array_create() if dest_size specified. - * \param[in] arr Initialized array object - * \param[in] idx Index to claim - * \return ARES_SUCCESS on success, ARES_EFORMERR on usage failure. - */ -ares_status_t ares__array_claim_at(void *dest, size_t dest_size, - ares__array_t *arr, size_t idx); - -/*! Remove the member at the specified array index. The destructor will be - * called. - * - * \param[in] arr Initialized array object - * \param[in] idx Index to remove - * \return ARES_SUCCESS if removed, ARES_EFORMERR on invalid use - */ -ares_status_t ares__array_remove_at(ares__array_t *arr, size_t idx); - -/*! Remove the first member of the array. - * - * \param[in] arr Initialized array object - * \return ARES_SUCCESS if removed, ARES_EFORMERR on invalid use - */ -ares_status_t ares__array_remove_first(ares__array_t *arr); - -/*! Remove the last member of the array. - * - * \param[in] arr Initialized array object - * \return ARES_SUCCESS if removed, ARES_EFORMERR on invalid use - */ -ares_status_t ares__array_remove_last(ares__array_t *arr); - -/*! @} */ - -#endif /* __ARES__ARRAY_H */ diff --git a/contrib/libs/c-ares/src/lib/dsa/ares__htable_asvp.h b/contrib/libs/c-ares/src/lib/dsa/ares__htable_asvp.h deleted file mode 100644 index 49a766d023..0000000000 --- a/contrib/libs/c-ares/src/lib/dsa/ares__htable_asvp.h +++ /dev/null @@ -1,130 +0,0 @@ -/* MIT License - * - * Copyright (c) 2023 Brad House - * - * Permission is hereby granted, free of charge, to any person obtaining a copy - * of this software and associated documentation files (the "Software"), to deal - * in the Software without restriction, including without limitation the rights - * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell - * copies of the Software, and to permit persons to whom the Software is - * furnished to do so, subject to the following conditions: - * - * The above copyright notice and this permission notice (including the next - * paragraph) shall be included in all copies or substantial portions of the - * Software. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR - * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, - * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE - * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER - * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, - * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE - * SOFTWARE. - * - * SPDX-License-Identifier: MIT - */ -#ifndef __ARES__HTABLE_ASVP_H -#define __ARES__HTABLE_ASVP_H - -/*! \addtogroup ares__htable_asvp HashTable with ares_socket_t Key and - * void pointer Value - * - * This data structure wraps the base ares__htable data structure in order to - * split the key and value data types as ares_socket_t and void pointer, - * respectively. - * - * Average time complexity: - * - Insert: O(1) - * - Search: O(1) - * - Delete: O(1) - * - * @{ - */ - -struct ares__htable_asvp; - -/*! Opaque data type for ares_socket_t key, void pointer hash table - * implementation */ -typedef struct ares__htable_asvp ares__htable_asvp_t; - -/*! Callback to free value stored in hashtable - * - * \param[in] val user-supplied value - */ -typedef void (*ares__htable_asvp_val_free_t)(void *val); - -/*! Destroy hashtable - * - * \param[in] htable Initialized hashtable - */ -void ares__htable_asvp_destroy(ares__htable_asvp_t *htable); - -/*! Create size_t key, void pointer value hash table - * - * \param[in] val_free Optional. Call back to free user-supplied value. If - * NULL it is expected the caller will clean up any user - * supplied values. - */ -ares__htable_asvp_t * - ares__htable_asvp_create(ares__htable_asvp_val_free_t val_free); - -/*! Retrieve an array of keys from the hashtable. - * - * \param[in] htable Initialized hashtable - * \param[out] num Count of returned keys - * \return Array of keys in the hashtable. Must be free'd with ares_free(). - */ -ares_socket_t *ares__htable_asvp_keys(const ares__htable_asvp_t *htable, - size_t *num); - - -/*! Insert key/value into hash table - * - * \param[in] htable Initialized hash table - * \param[in] key key to associate with value - * \param[in] val value to store (takes ownership). May be NULL. - * \return ARES_TRUE on success, ARES_FALSE on out of memory or misuse - */ -ares_bool_t ares__htable_asvp_insert(ares__htable_asvp_t *htable, - ares_socket_t key, void *val); - -/*! Retrieve value from hashtable based on key - * - * \param[in] htable Initialized hash table - * \param[in] key key to use to search - * \param[out] val Optional. Pointer to store value. - * \return ARES_TRUE on success, ARES_FALSE on failure - */ -ares_bool_t ares__htable_asvp_get(const ares__htable_asvp_t *htable, - ares_socket_t key, void **val); - -/*! Retrieve value from hashtable directly as return value. Caveat to this - * function over ares__htable_asvp_get() is that if a NULL value is stored - * you cannot determine if the key is not found or the value is NULL. - * - * \param[in] htable Initialized hash table - * \param[in] key key to use to search - * \return value associated with key in hashtable or NULL - */ -void *ares__htable_asvp_get_direct(const ares__htable_asvp_t *htable, - ares_socket_t key); - -/*! Remove a value from the hashtable by key - * - * \param[in] htable Initialized hash table - * \param[in] key key to use to search - * \return ARES_TRUE if found, ARES_FALSE if not found - */ -ares_bool_t ares__htable_asvp_remove(ares__htable_asvp_t *htable, - ares_socket_t key); - -/*! Retrieve the number of keys stored in the hash table - * - * \param[in] htable Initialized hash table - * \return count - */ -size_t ares__htable_asvp_num_keys(const ares__htable_asvp_t *htable); - -/*! @} */ - -#endif /* __ARES__HTABLE_ASVP_H */ diff --git a/contrib/libs/c-ares/src/lib/dsa/ares__htable_strvp.h b/contrib/libs/c-ares/src/lib/dsa/ares__htable_strvp.h deleted file mode 100644 index 878c71869a..0000000000 --- a/contrib/libs/c-ares/src/lib/dsa/ares__htable_strvp.h +++ /dev/null @@ -1,118 +0,0 @@ -/* MIT License - * - * Copyright (c) 2023 Brad House - * - * Permission is hereby granted, free of charge, to any person obtaining a copy - * of this software and associated documentation files (the "Software"), to deal - * in the Software without restriction, including without limitation the rights - * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell - * copies of the Software, and to permit persons to whom the Software is - * furnished to do so, subject to the following conditions: - * - * The above copyright notice and this permission notice (including the next - * paragraph) shall be included in all copies or substantial portions of the - * Software. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR - * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, - * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE - * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER - * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, - * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE - * SOFTWARE. - * - * SPDX-License-Identifier: MIT - */ -#ifndef __ARES__HTABLE_STRVP_H -#define __ARES__HTABLE_STRVP_H - -/*! \addtogroup ares__htable_strvp HashTable with string Key and void pointer - * Value - * - * This data structure wraps the base ares__htable data structure in order to - * split the key and value data types as string and void pointer, respectively. - * - * Average time complexity: - * - Insert: O(1) - * - Search: O(1) - * - Delete: O(1) - * - * @{ - */ - -struct ares__htable_strvp; - -/*! Opaque data type for size_t key, void pointer hash table implementation */ -typedef struct ares__htable_strvp ares__htable_strvp_t; - -/*! Callback to free value stored in hashtable - * - * \param[in] val user-supplied value - */ -typedef void (*ares__htable_strvp_val_free_t)(void *val); - -/*! Destroy hashtable - * - * \param[in] htable Initialized hashtable - */ -void ares__htable_strvp_destroy(ares__htable_strvp_t *htable); - -/*! Create string, void pointer value hash table - * - * \param[in] val_free Optional. Call back to free user-supplied value. If - * NULL it is expected the caller will clean up any user - * supplied values. - */ -ares__htable_strvp_t * - ares__htable_strvp_create(ares__htable_strvp_val_free_t val_free); - -/*! Insert key/value into hash table - * - * \param[in] htable Initialized hash table - * \param[in] key key to associate with value - * \param[in] val value to store (takes ownership). May be NULL. - * \return ARES_TRUE on success, ARES_FALSE on failure or out of memory - */ -ares_bool_t ares__htable_strvp_insert(ares__htable_strvp_t *htable, - const char *key, void *val); - -/*! Retrieve value from hashtable based on key - * - * \param[in] htable Initialized hash table - * \param[in] key key to use to search - * \param[out] val Optional. Pointer to store value. - * \return ARES_TRUE on success, ARES_FALSE on failure - */ -ares_bool_t ares__htable_strvp_get(const ares__htable_strvp_t *htable, - const char *key, void **val); - -/*! Retrieve value from hashtable directly as return value. Caveat to this - * function over ares__htable_strvp_get() is that if a NULL value is stored - * you cannot determine if the key is not found or the value is NULL. - * - * \param[in] htable Initialized hash table - * \param[in] key key to use to search - * \return value associated with key in hashtable or NULL - */ -void *ares__htable_strvp_get_direct(const ares__htable_strvp_t *htable, - const char *key); - -/*! Remove a value from the hashtable by key - * - * \param[in] htable Initialized hash table - * \param[in] key key to use to search - * \return ARES_TRUE if found, ARES_FALSE if not - */ -ares_bool_t ares__htable_strvp_remove(ares__htable_strvp_t *htable, - const char *key); - -/*! Retrieve the number of keys stored in the hash table - * - * \param[in] htable Initialized hash table - * \return count - */ -size_t ares__htable_strvp_num_keys(const ares__htable_strvp_t *htable); - -/*! @} */ - -#endif /* __ARES__HTABLE_STRVP_H */ diff --git a/contrib/libs/c-ares/src/lib/dsa/ares__htable_szvp.h b/contrib/libs/c-ares/src/lib/dsa/ares__htable_szvp.h deleted file mode 100644 index 62b1776be9..0000000000 --- a/contrib/libs/c-ares/src/lib/dsa/ares__htable_szvp.h +++ /dev/null @@ -1,117 +0,0 @@ -/* MIT License - * - * Copyright (c) 2023 Brad House - * - * Permission is hereby granted, free of charge, to any person obtaining a copy - * of this software and associated documentation files (the "Software"), to deal - * in the Software without restriction, including without limitation the rights - * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell - * copies of the Software, and to permit persons to whom the Software is - * furnished to do so, subject to the following conditions: - * - * The above copyright notice and this permission notice (including the next - * paragraph) shall be included in all copies or substantial portions of the - * Software. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR - * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, - * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE - * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER - * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, - * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE - * SOFTWARE. - * - * SPDX-License-Identifier: MIT - */ -#ifndef __ARES__HTABLE_STVP_H -#define __ARES__HTABLE_STVP_H - -/*! \addtogroup ares__htable_szvp HashTable with size_t Key and void pointer - * Value - * - * This data structure wraps the base ares__htable data structure in order to - * split the key and value data types as size_t and void pointer, respectively. - * - * Average time complexity: - * - Insert: O(1) - * - Search: O(1) - * - Delete: O(1) - * - * @{ - */ - -struct ares__htable_szvp; - -/*! Opaque data type for size_t key, void pointer hash table implementation */ -typedef struct ares__htable_szvp ares__htable_szvp_t; - -/*! Callback to free value stored in hashtable - * - * \param[in] val user-supplied value - */ -typedef void (*ares__htable_szvp_val_free_t)(void *val); - -/*! Destroy hashtable - * - * \param[in] htable Initialized hashtable - */ -void ares__htable_szvp_destroy(ares__htable_szvp_t *htable); - -/*! Create size_t key, void pointer value hash table - * - * \param[in] val_free Optional. Call back to free user-supplied value. If - * NULL it is expected the caller will clean up any user - * supplied values. - */ -ares__htable_szvp_t * - ares__htable_szvp_create(ares__htable_szvp_val_free_t val_free); - -/*! Insert key/value into hash table - * - * \param[in] htable Initialized hash table - * \param[in] key key to associate with value - * \param[in] val value to store (takes ownership). May be NULL. - * \return ARES_TRUE on success, ARES_FALSE on failure or out of memory - */ -ares_bool_t ares__htable_szvp_insert(ares__htable_szvp_t *htable, size_t key, - void *val); - -/*! Retrieve value from hashtable based on key - * - * \param[in] htable Initialized hash table - * \param[in] key key to use to search - * \param[out] val Optional. Pointer to store value. - * \return ARES_TRUE on success, ARES_FALSE on failure - */ -ares_bool_t ares__htable_szvp_get(const ares__htable_szvp_t *htable, size_t key, - void **val); - -/*! Retrieve value from hashtable directly as return value. Caveat to this - * function over ares__htable_szvp_get() is that if a NULL value is stored - * you cannot determine if the key is not found or the value is NULL. - * - * \param[in] htable Initialized hash table - * \param[in] key key to use to search - * \return value associated with key in hashtable or NULL - */ -void *ares__htable_szvp_get_direct(const ares__htable_szvp_t *htable, - size_t key); - -/*! Remove a value from the hashtable by key - * - * \param[in] htable Initialized hash table - * \param[in] key key to use to search - * \return ARES_TRUE if found, ARES_FALSE if not - */ -ares_bool_t ares__htable_szvp_remove(ares__htable_szvp_t *htable, size_t key); - -/*! Retrieve the number of keys stored in the hash table - * - * \param[in] htable Initialized hash table - * \return count - */ -size_t ares__htable_szvp_num_keys(const ares__htable_szvp_t *htable); - -/*! @} */ - -#endif /* __ARES__HTABLE_STVP_H */ diff --git a/contrib/libs/c-ares/src/lib/dsa/ares__htable_vpvp.h b/contrib/libs/c-ares/src/lib/dsa/ares__htable_vpvp.h deleted file mode 100644 index 1e0c750d86..0000000000 --- a/contrib/libs/c-ares/src/lib/dsa/ares__htable_vpvp.h +++ /dev/null @@ -1,128 +0,0 @@ -/* MIT License - * - * Copyright (c) 2024 Brad House - * - * Permission is hereby granted, free of charge, to any person obtaining a copy - * of this software and associated documentation files (the "Software"), to deal - * in the Software without restriction, including without limitation the rights - * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell - * copies of the Software, and to permit persons to whom the Software is - * furnished to do so, subject to the following conditions: - * - * The above copyright notice and this permission notice (including the next - * paragraph) shall be included in all copies or substantial portions of the - * Software. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR - * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, - * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE - * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER - * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, - * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE - * SOFTWARE. - * - * SPDX-License-Identifier: MIT - */ -#ifndef __ARES__HTABLE_VPVP_H -#define __ARES__HTABLE_VPVP_H - -/*! \addtogroup ares__htable_vpvp HashTable with void pointer Key and void - * pointer Value - * - * This data structure wraps the base ares__htable data structure in order to - * split the key and value data types as size_t and void pointer, respectively. - * - * Average time complexity: - * - Insert: O(1) - * - Search: O(1) - * - Delete: O(1) - * - * @{ - */ - -struct ares__htable_vpvp; - -/*! Opaque data type for size_t key, void pointer hash table implementation */ -typedef struct ares__htable_vpvp ares__htable_vpvp_t; - -/*! Callback to free key stored in hashtable - * - * \param[in] key user-supplied key - */ -typedef void (*ares__htable_vpvp_key_free_t)(void *key); - -/*! Callback to free value stored in hashtable - * - * \param[in] val user-supplied value - */ -typedef void (*ares__htable_vpvp_val_free_t)(void *val); - -/*! Destroy hashtable - * - * \param[in] htable Initialized hashtable - */ -void ares__htable_vpvp_destroy(ares__htable_vpvp_t *htable); - -/*! Create size_t key, void pointer value hash table - * - * \param[in] key_free Optional. Call back to free user-supplied key. If - * NULL it is expected the caller will clean up any user - * supplied keys. - * \param[in] val_free Optional. Call back to free user-supplied value. If - * NULL it is expected the caller will clean up any user - * supplied values. - */ -ares__htable_vpvp_t * - ares__htable_vpvp_create(ares__htable_vpvp_key_free_t key_free, - ares__htable_vpvp_val_free_t val_free); - -/*! Insert key/value into hash table - * - * \param[in] htable Initialized hash table - * \param[in] key key to associate with value - * \param[in] val value to store (takes ownership). May be NULL. - * \return ARES_TRUE on success, ARES_FALSE on failure or out of memory - */ -ares_bool_t ares__htable_vpvp_insert(ares__htable_vpvp_t *htable, void *key, - void *val); - -/*! Retrieve value from hashtable based on key - * - * \param[in] htable Initialized hash table - * \param[in] key key to use to search - * \param[out] val Optional. Pointer to store value. - * \return ARES_TRUE on success, ARES_FALSE on failure - */ -ares_bool_t ares__htable_vpvp_get(const ares__htable_vpvp_t *htable, - const void *key, void **val); - -/*! Retrieve value from hashtable directly as return value. Caveat to this - * function over ares__htable_vpvp_get() is that if a NULL value is stored - * you cannot determine if the key is not found or the value is NULL. - * - * \param[in] htable Initialized hash table - * \param[in] key key to use to search - * \return value associated with key in hashtable or NULL - */ -void *ares__htable_vpvp_get_direct(const ares__htable_vpvp_t *htable, - const void *key); - -/*! Remove a value from the hashtable by key - * - * \param[in] htable Initialized hash table - * \param[in] key key to use to search - * \return ARES_TRUE if found, ARES_FALSE if not - */ -ares_bool_t ares__htable_vpvp_remove(ares__htable_vpvp_t *htable, - const void *key); - -/*! Retrieve the number of keys stored in the hash table - * - * \param[in] htable Initialized hash table - * \return count - */ -size_t ares__htable_vpvp_num_keys(const ares__htable_vpvp_t *htable); - -/*! @} */ - -#endif /* __ARES__HTABLE_VPVP_H */ diff --git a/contrib/libs/c-ares/src/lib/dsa/ares__llist.h b/contrib/libs/c-ares/src/lib/dsa/ares__llist.h deleted file mode 100644 index 213f54134b..0000000000 --- a/contrib/libs/c-ares/src/lib/dsa/ares__llist.h +++ /dev/null @@ -1,235 +0,0 @@ -/* MIT License - * - * Copyright (c) 2023 Brad House - * - * Permission is hereby granted, free of charge, to any person obtaining a copy - * of this software and associated documentation files (the "Software"), to deal - * in the Software without restriction, including without limitation the rights - * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell - * copies of the Software, and to permit persons to whom the Software is - * furnished to do so, subject to the following conditions: - * - * The above copyright notice and this permission notice (including the next - * paragraph) shall be included in all copies or substantial portions of the - * Software. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR - * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, - * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE - * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER - * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, - * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE - * SOFTWARE. - * - * SPDX-License-Identifier: MIT - */ -#ifndef __ARES__LLIST_H -#define __ARES__LLIST_H - -/*! \addtogroup ares__llist LinkedList Data Structure - * - * This is a doubly-linked list data structure. - * - * Average time complexity: - * - Insert: O(1) -- head or tail - * - Search: O(n) - * - Delete: O(1) -- delete assumes you hold a node pointer - * - * @{ - */ - -struct ares__llist; - -/*! Opaque data structure for linked list */ -typedef struct ares__llist ares__llist_t; - -struct ares__llist_node; - -/*! Opaque data structure for a node in a linked list */ -typedef struct ares__llist_node ares__llist_node_t; - -/*! Callback to free user-defined node data - * - * \param[in] data user supplied data - */ -typedef void (*ares__llist_destructor_t)(void *data); - -/*! Create a linked list object - * - * \param[in] destruct Optional. Destructor to call on all removed nodes - * \return linked list object or NULL on out of memory - */ -ares__llist_t *ares__llist_create(ares__llist_destructor_t destruct); - -/*! Replace destructor for linked list nodes. Typically this is used - * when wanting to disable the destructor by using NULL. - * - * \param[in] list Initialized linked list object - * \param[in] destruct replacement destructor, NULL is allowed - */ -void ares__llist_replace_destructor(ares__llist_t *list, - ares__llist_destructor_t destruct); - -/*! Insert value as the first node in the linked list - * - * \param[in] list Initialized linked list object - * \param[in] val user-supplied value. - * \return node object referencing place in list, or null if out of memory or - * misuse - */ -ares__llist_node_t *ares__llist_insert_first(ares__llist_t *list, void *val); - -/*! Insert value as the last node in the linked list - * - * \param[in] list Initialized linked list object - * \param[in] val user-supplied value. - * \return node object referencing place in list, or null if out of memory or - * misuse - */ -ares__llist_node_t *ares__llist_insert_last(ares__llist_t *list, void *val); - -/*! Insert value before specified node in the linked list - * - * \param[in] node node referenced to insert before - * \param[in] val user-supplied value. - * \return node object referencing place in list, or null if out of memory or - * misuse - */ -ares__llist_node_t *ares__llist_insert_before(ares__llist_node_t *node, - void *val); - -/*! Insert value after specified node in the linked list - * - * \param[in] node node referenced to insert after - * \param[in] val user-supplied value. - * \return node object referencing place in list, or null if out of memory or - * misuse - */ -ares__llist_node_t *ares__llist_insert_after(ares__llist_node_t *node, - void *val); - -/*! Obtain first node in list - * - * \param[in] list Initialized list object - * \return first node in list or NULL if none - */ -ares__llist_node_t *ares__llist_node_first(ares__llist_t *list); - -/*! Obtain last node in list - * - * \param[in] list Initialized list object - * \return last node in list or NULL if none - */ -ares__llist_node_t *ares__llist_node_last(ares__llist_t *list); - -/*! Obtain a node based on its index. This is an O(n) operation. - * - * \param[in] list Initialized list object - * \param[in] idx Index of node to retrieve - * \return node at index or NULL if invalid index - */ -ares__llist_node_t *ares__llist_node_idx(ares__llist_t *list, size_t idx); - -/*! Obtain next node in respect to specified node - * - * \param[in] node Node referenced - * \return node or NULL if none - */ -ares__llist_node_t *ares__llist_node_next(ares__llist_node_t *node); - -/*! Obtain previous node in respect to specified node - * - * \param[in] node Node referenced - * \return node or NULL if none - */ -ares__llist_node_t *ares__llist_node_prev(ares__llist_node_t *node); - - -/*! Obtain value from node - * - * \param[in] node Node referenced - * \return user provided value from node - */ -void *ares__llist_node_val(ares__llist_node_t *node); - -/*! Obtain the number of entries in the list - * - * \param[in] list Initialized list object - * \return count - */ -size_t ares__llist_len(const ares__llist_t *list); - -/*! Clear all entries in the list, but don't destroy the list object. - * - * \param[in] list Initialized list object - */ -void ares__llist_clear(ares__llist_t *list); - -/*! Obtain list object from referenced node - * - * \param[in] node Node referenced - * \return list object node belongs to - */ -ares__llist_t *ares__llist_node_parent(ares__llist_node_t *node); - -/*! Obtain the first user-supplied value in the list - * - * \param[in] list Initialized list object - * \return first user supplied value or NULL if none - */ -void *ares__llist_first_val(ares__llist_t *list); - -/*! Obtain the last user-supplied value in the list - * - * \param[in] list Initialized list object - * \return last user supplied value or NULL if none - */ -void *ares__llist_last_val(ares__llist_t *list); - -/*! Take ownership of user-supplied value in list without calling destructor. - * Will unchain entry from list. - * - * \param[in] node Node referenced - * \return user supplied value - */ -void *ares__llist_node_claim(ares__llist_node_t *node); - -/*! Replace user-supplied value for node - * - * \param[in] node Node referenced - * \param[in] val new user-supplied value - */ -void ares__llist_node_replace(ares__llist_node_t *node, void *val); - -/*! Destroy the node, removing it from the list and calling destructor. - * - * \param[in] node Node referenced - */ -void ares__llist_node_destroy(ares__llist_node_t *node); - -/*! Destroy the list object and all nodes in the list. - * - * \param[in] list Initialized list object - */ -void ares__llist_destroy(ares__llist_t *list); - -/*! Detach node from the current list and re-attach it to the new list as the - * last entry. - * - * \param[in] node node to move - * \param[in] new_parent new list - */ -void ares__llist_node_move_parent_last(ares__llist_node_t *node, - ares__llist_t *new_parent); - -/*! Detach node from the current list and re-attach it to the new list as the - * first entry. - * - * \param[in] node node to move - * \param[in] new_parent new list - */ -void ares__llist_node_move_parent_first(ares__llist_node_t *node, - ares__llist_t *new_parent); -/*! @} */ - -#endif /* __ARES__LLIST_H */ diff --git a/contrib/libs/c-ares/src/lib/dsa/ares__array.c b/contrib/libs/c-ares/src/lib/dsa/ares_array.c index 0c724248bf..c421d5c5f6 100644 --- a/contrib/libs/c-ares/src/lib/dsa/ares__array.c +++ b/contrib/libs/c-ares/src/lib/dsa/ares_array.c @@ -24,23 +24,23 @@ * SPDX-License-Identifier: MIT */ #include "ares_private.h" -#include "ares__array.h" +#include "ares_array.h" #define ARES__ARRAY_MIN 4 -struct ares__array { - ares__array_destructor_t destruct; - void *arr; - size_t member_size; - size_t cnt; - size_t offset; - size_t alloc_cnt; +struct ares_array { + ares_array_destructor_t destruct; + void *arr; + size_t member_size; + size_t cnt; + size_t offset; + size_t alloc_cnt; }; -ares__array_t *ares__array_create(size_t member_size, - ares__array_destructor_t destruct) +ares_array_t *ares_array_create(size_t member_size, + ares_array_destructor_t destruct) { - ares__array_t *arr; + ares_array_t *arr; if (member_size == 0) { return NULL; @@ -56,7 +56,7 @@ ares__array_t *ares__array_create(size_t member_size, return arr; } -size_t ares__array_len(const ares__array_t *arr) +size_t ares_array_len(const ares_array_t *arr) { if (arr == NULL) { return 0; @@ -64,7 +64,7 @@ size_t ares__array_len(const ares__array_t *arr) return arr->cnt; } -void *ares__array_at(ares__array_t *arr, size_t idx) +void *ares_array_at(ares_array_t *arr, size_t idx) { if (arr == NULL || idx >= arr->cnt) { return NULL; @@ -72,7 +72,7 @@ void *ares__array_at(ares__array_t *arr, size_t idx) return (unsigned char *)arr->arr + ((idx + arr->offset) * arr->member_size); } -const void *ares__array_at_const(const ares__array_t *arr, size_t idx) +const void *ares_array_at_const(const ares_array_t *arr, size_t idx) { if (arr == NULL || idx >= arr->cnt) { return NULL; @@ -80,7 +80,7 @@ const void *ares__array_at_const(const ares__array_t *arr, size_t idx) return (unsigned char *)arr->arr + ((idx + arr->offset) * arr->member_size); } -ares_status_t ares__array_sort(ares__array_t *arr, ares__array_cmp_t cmp) +ares_status_t ares_array_sort(ares_array_t *arr, ares_array_cmp_t cmp) { if (arr == NULL || cmp == NULL) { return ARES_EFORMERR; @@ -96,7 +96,7 @@ ares_status_t ares__array_sort(ares__array_t *arr, ares__array_cmp_t cmp) return ARES_SUCCESS; } -void ares__array_destroy(ares__array_t *arr) +void ares_array_destroy(ares_array_t *arr) { size_t i; @@ -106,7 +106,7 @@ void ares__array_destroy(ares__array_t *arr) if (arr->destruct != NULL) { for (i = 0; i < arr->cnt; i++) { - arr->destruct(ares__array_at(arr, i)); + arr->destruct(ares_array_at(arr, i)); } } @@ -116,8 +116,8 @@ void ares__array_destroy(ares__array_t *arr) /* NOTE: this function operates on actual indexes, NOT indexes using the * arr->offset */ -static ares_status_t ares__array_move(ares__array_t *arr, size_t dest_idx, - size_t src_idx) +static ares_status_t ares_array_move(ares_array_t *arr, size_t dest_idx, + size_t src_idx) { void *dest_ptr; const void *src_ptr; @@ -140,18 +140,14 @@ static ares_status_t ares__array_move(ares__array_t *arr, size_t dest_idx, if (dest_idx > src_idx && arr->cnt + (dest_idx - src_idx) > arr->alloc_cnt) { return ARES_EFORMERR; } - if (dest_idx < src_idx) { - nmembers = arr->cnt - dest_idx; - } else { - nmembers = arr->cnt - src_idx; - } + nmembers = arr->cnt - (src_idx - arr->offset); memmove(dest_ptr, src_ptr, nmembers * arr->member_size); return ARES_SUCCESS; } -void *ares__array_finish(ares__array_t *arr, size_t *num_members) +void *ares_array_finish(ares_array_t *arr, size_t *num_members) { void *ptr; @@ -161,7 +157,7 @@ void *ares__array_finish(ares__array_t *arr, size_t *num_members) /* Make sure we move data to beginning of allocation */ if (arr->offset != 0) { - if (ares__array_move(arr, 0, arr->offset) != ARES_SUCCESS) { + if (ares_array_move(arr, 0, arr->offset) != ARES_SUCCESS) { return NULL; } arr->offset = 0; @@ -173,7 +169,7 @@ void *ares__array_finish(ares__array_t *arr, size_t *num_members) return ptr; } -ares_status_t ares__array_set_size(ares__array_t *arr, size_t size) +ares_status_t ares_array_set_size(ares_array_t *arr, size_t size) { void *temp; @@ -182,7 +178,7 @@ ares_status_t ares__array_set_size(ares__array_t *arr, size_t size) } /* Always operate on powers of 2 */ - size = ares__round_up_pow2(size); + size = ares_round_up_pow2(size); if (size < ARES__ARRAY_MIN) { size = ARES__ARRAY_MIN; @@ -203,8 +199,8 @@ ares_status_t ares__array_set_size(ares__array_t *arr, size_t size) return ARES_SUCCESS; } -ares_status_t ares__array_insert_at(void **elem_ptr, ares__array_t *arr, - size_t idx) +ares_status_t ares_array_insert_at(void **elem_ptr, ares_array_t *arr, + size_t idx) { void *ptr; ares_status_t status; @@ -219,14 +215,14 @@ ares_status_t ares__array_insert_at(void **elem_ptr, ares__array_t *arr, } /* Allocate more if needed */ - status = ares__array_set_size(arr, arr->cnt + 1); + status = ares_array_set_size(arr, arr->cnt + 1); if (status != ARES_SUCCESS) { return status; } /* Shift if we have memory but not enough room at the end */ if (arr->cnt + 1 + arr->offset > arr->alloc_cnt) { - status = ares__array_move(arr, 0, arr->offset); + status = ares_array_move(arr, 0, arr->offset); if (status != ARES_SUCCESS) { return status; } @@ -236,7 +232,7 @@ ares_status_t ares__array_insert_at(void **elem_ptr, ares__array_t *arr, /* If we're inserting anywhere other than the end, we need to move some * elements out of the way */ if (idx != arr->cnt) { - status = ares__array_move(arr, idx + arr->offset + 1, idx + arr->offset); + status = ares_array_move(arr, idx + arr->offset + 1, idx + arr->offset); if (status != ARES_SUCCESS) { return status; } @@ -255,46 +251,88 @@ ares_status_t ares__array_insert_at(void **elem_ptr, ares__array_t *arr, return ARES_SUCCESS; } -ares_status_t ares__array_insert_last(void **elem_ptr, ares__array_t *arr) +ares_status_t ares_array_insert_last(void **elem_ptr, ares_array_t *arr) +{ + return ares_array_insert_at(elem_ptr, arr, ares_array_len(arr)); +} + +ares_status_t ares_array_insert_first(void **elem_ptr, ares_array_t *arr) +{ + return ares_array_insert_at(elem_ptr, arr, 0); +} + +ares_status_t ares_array_insertdata_at(ares_array_t *arr, size_t idx, + const void *data_ptr) +{ + ares_status_t status; + void *ptr = NULL; + + status = ares_array_insert_at(&ptr, arr, idx); + if (status != ARES_SUCCESS) { + return status; + } + memcpy(ptr, data_ptr, arr->member_size); + return ARES_SUCCESS; +} + +ares_status_t ares_array_insertdata_last(ares_array_t *arr, + const void *data_ptr) { - return ares__array_insert_at(elem_ptr, arr, ares__array_len(arr)); + ares_status_t status; + void *ptr = NULL; + + status = ares_array_insert_last(&ptr, arr); + if (status != ARES_SUCCESS) { + return status; + } + memcpy(ptr, data_ptr, arr->member_size); + return ARES_SUCCESS; } -ares_status_t ares__array_insert_first(void **elem_ptr, ares__array_t *arr) +ares_status_t ares_array_insertdata_first(ares_array_t *arr, + const void *data_ptr) { - return ares__array_insert_at(elem_ptr, arr, 0); + ares_status_t status; + void *ptr = NULL; + + status = ares_array_insert_last(&ptr, arr); + if (status != ARES_SUCCESS) { + return status; + } + memcpy(ptr, data_ptr, arr->member_size); + return ARES_SUCCESS; } -void *ares__array_first(ares__array_t *arr) +void *ares_array_first(ares_array_t *arr) { - return ares__array_at(arr, 0); + return ares_array_at(arr, 0); } -void *ares__array_last(ares__array_t *arr) +void *ares_array_last(ares_array_t *arr) { - size_t cnt = ares__array_len(arr); + size_t cnt = ares_array_len(arr); if (cnt == 0) { return NULL; } - return ares__array_at(arr, cnt - 1); + return ares_array_at(arr, cnt - 1); } -const void *ares__array_first_const(const ares__array_t *arr) +const void *ares_array_first_const(const ares_array_t *arr) { - return ares__array_at_const(arr, 0); + return ares_array_at_const(arr, 0); } -const void *ares__array_last_const(const ares__array_t *arr) +const void *ares_array_last_const(const ares_array_t *arr) { - size_t cnt = ares__array_len(arr); + size_t cnt = ares_array_len(arr); if (cnt == 0) { return NULL; } - return ares__array_at_const(arr, cnt - 1); + return ares_array_at_const(arr, cnt - 1); } -ares_status_t ares__array_claim_at(void *dest, size_t dest_size, - ares__array_t *arr, size_t idx) +ares_status_t ares_array_claim_at(void *dest, size_t dest_size, + ares_array_t *arr, size_t idx) { ares_status_t status; @@ -307,7 +345,7 @@ ares_status_t ares__array_claim_at(void *dest, size_t dest_size, } if (dest) { - memcpy(dest, ares__array_at(arr, idx), arr->member_size); + memcpy(dest, ares_array_at(arr, idx), arr->member_size); } if (idx == 0) { @@ -317,7 +355,7 @@ ares_status_t ares__array_claim_at(void *dest, size_t dest_size, } else if (idx != arr->cnt - 1) { /* Must shift entire array if removing an element from the middle. Does * nothing if removing last element other than decrement count. */ - status = ares__array_move(arr, idx + arr->offset, idx + arr->offset + 1); + status = ares_array_move(arr, idx + arr->offset, idx + arr->offset + 1); if (status != ARES_SUCCESS) { return status; } @@ -327,9 +365,9 @@ ares_status_t ares__array_claim_at(void *dest, size_t dest_size, return ARES_SUCCESS; } -ares_status_t ares__array_remove_at(ares__array_t *arr, size_t idx) +ares_status_t ares_array_remove_at(ares_array_t *arr, size_t idx) { - void *ptr = ares__array_at(arr, idx); + void *ptr = ares_array_at(arr, idx); if (arr == NULL || ptr == NULL) { return ARES_EFORMERR; } @@ -338,19 +376,19 @@ ares_status_t ares__array_remove_at(ares__array_t *arr, size_t idx) arr->destruct(ptr); } - return ares__array_claim_at(NULL, 0, arr, idx); + return ares_array_claim_at(NULL, 0, arr, idx); } -ares_status_t ares__array_remove_first(ares__array_t *arr) +ares_status_t ares_array_remove_first(ares_array_t *arr) { - return ares__array_remove_at(arr, 0); + return ares_array_remove_at(arr, 0); } -ares_status_t ares__array_remove_last(ares__array_t *arr) +ares_status_t ares_array_remove_last(ares_array_t *arr) { - size_t cnt = ares__array_len(arr); + size_t cnt = ares_array_len(arr); if (cnt == 0) { return ARES_EFORMERR; } - return ares__array_remove_at(arr, cnt - 1); + return ares_array_remove_at(arr, cnt - 1); } diff --git a/contrib/libs/c-ares/src/lib/dsa/ares__htable.c b/contrib/libs/c-ares/src/lib/dsa/ares_htable.c index 9049b3246b..f76b67cae9 100644 --- a/contrib/libs/c-ares/src/lib/dsa/ares__htable.c +++ b/contrib/libs/c-ares/src/lib/dsa/ares_htable.c @@ -24,33 +24,37 @@ * SPDX-License-Identifier: MIT */ #include "ares_private.h" -#include "ares__llist.h" -#include "ares__htable.h" +#include "ares_llist.h" +#include "ares_htable.h" #define ARES__HTABLE_MAX_BUCKETS (1U << 24) #define ARES__HTABLE_MIN_BUCKETS (1U << 4) #define ARES__HTABLE_EXPAND_PERCENT 75 -struct ares__htable { - ares__htable_hashfunc_t hash; - ares__htable_bucket_key_t bucket_key; - ares__htable_bucket_free_t bucket_free; - ares__htable_key_eq_t key_eq; - unsigned int seed; - unsigned int size; - size_t num_keys; - size_t num_collisions; - /* NOTE: if we converted buckets into ares__slist_t we could guarantee on +struct ares_htable { + ares_htable_hashfunc_t hash; + ares_htable_bucket_key_t bucket_key; + ares_htable_bucket_free_t bucket_free; + ares_htable_key_eq_t key_eq; + unsigned int seed; + unsigned int size; + size_t num_keys; + size_t num_collisions; + /* NOTE: if we converted buckets into ares_slist_t we could guarantee on * hash collisions we would have O(log n) worst case insert and search * performance. (We'd also need to make key_eq into a key_cmp to * support sort). That said, risk with a random hash seed is near zero, - * and ares__slist_t is heavier weight, so I think using ares__llist_t + * and ares_slist_t is heavier weight, so I think using ares_llist_t * is an overall win. */ - ares__llist_t **buckets; + ares_llist_t **buckets; }; -static unsigned int ares__htable_generate_seed(ares__htable_t *htable) +static unsigned int ares_htable_generate_seed(ares_htable_t *htable) { +#ifdef FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION + /* Seed needs to be static for fuzzing */ + return 0; +#else unsigned int seed = 0; time_t t = time(NULL); @@ -61,11 +65,12 @@ static unsigned int ares__htable_generate_seed(ares__htable_t *htable) seed |= (unsigned int)((size_t)&seed & 0xFFFFFFFF); seed |= (unsigned int)(((ares_uint64_t)t) & 0xFFFFFFFF); return seed; +#endif } -static void ares__htable_buckets_destroy(ares__llist_t **buckets, - unsigned int size, - ares_bool_t destroy_vals) +static void ares_htable_buckets_destroy(ares_llist_t **buckets, + unsigned int size, + ares_bool_t destroy_vals) { unsigned int i; @@ -79,30 +84,30 @@ static void ares__htable_buckets_destroy(ares__llist_t **buckets, } if (!destroy_vals) { - ares__llist_replace_destructor(buckets[i], NULL); + ares_llist_replace_destructor(buckets[i], NULL); } - ares__llist_destroy(buckets[i]); + ares_llist_destroy(buckets[i]); } ares_free(buckets); } -void ares__htable_destroy(ares__htable_t *htable) +void ares_htable_destroy(ares_htable_t *htable) { if (htable == NULL) { return; } - ares__htable_buckets_destroy(htable->buckets, htable->size, ARES_TRUE); + ares_htable_buckets_destroy(htable->buckets, htable->size, ARES_TRUE); ares_free(htable); } -ares__htable_t *ares__htable_create(ares__htable_hashfunc_t hash_func, - ares__htable_bucket_key_t bucket_key, - ares__htable_bucket_free_t bucket_free, - ares__htable_key_eq_t key_eq) +ares_htable_t *ares_htable_create(ares_htable_hashfunc_t hash_func, + ares_htable_bucket_key_t bucket_key, + ares_htable_bucket_free_t bucket_free, + ares_htable_key_eq_t key_eq) { - ares__htable_t *htable = NULL; + ares_htable_t *htable = NULL; if (hash_func == NULL || bucket_key == NULL || bucket_free == NULL || key_eq == NULL) { @@ -118,7 +123,7 @@ ares__htable_t *ares__htable_create(ares__htable_hashfunc_t hash_func, htable->bucket_key = bucket_key; htable->bucket_free = bucket_free; htable->key_eq = key_eq; - htable->seed = ares__htable_generate_seed(htable); + htable->seed = ares_htable_generate_seed(htable); htable->size = ARES__HTABLE_MIN_BUCKETS; htable->buckets = ares_malloc_zero(sizeof(*htable->buckets) * htable->size); @@ -129,11 +134,11 @@ ares__htable_t *ares__htable_create(ares__htable_hashfunc_t hash_func, return htable; fail: - ares__htable_destroy(htable); + ares_htable_destroy(htable); return NULL; } -const void **ares__htable_all_buckets(const ares__htable_t *htable, size_t *num) +const void **ares_htable_all_buckets(const ares_htable_t *htable, size_t *num) { const void **out = NULL; size_t cnt = 0; @@ -151,10 +156,10 @@ const void **ares__htable_all_buckets(const ares__htable_t *htable, size_t *num) } for (i = 0; i < htable->size; i++) { - ares__llist_node_t *node; - for (node = ares__llist_node_first(htable->buckets[i]); node != NULL; - node = ares__llist_node_next(node)) { - out[cnt++] = ares__llist_node_val(node); + ares_llist_node_t *node; + for (node = ares_llist_node_first(htable->buckets[i]); node != NULL; + node = ares_llist_node_next(node)) { + out[cnt++] = ares_llist_node_val(node); } } @@ -169,14 +174,14 @@ const void **ares__htable_all_buckets(const ares__htable_t *htable, size_t *num) * efficient */ #define HASH_IDX(h, key) h->hash(key, h->seed) & (h->size - 1) -static ares__llist_node_t *ares__htable_find(const ares__htable_t *htable, - unsigned int idx, const void *key) +static ares_llist_node_t *ares_htable_find(const ares_htable_t *htable, + unsigned int idx, const void *key) { - ares__llist_node_t *node = NULL; + ares_llist_node_t *node = NULL; - for (node = ares__llist_node_first(htable->buckets[idx]); node != NULL; - node = ares__llist_node_next(node)) { - if (htable->key_eq(key, htable->bucket_key(ares__llist_node_val(node)))) { + for (node = ares_llist_node_first(htable->buckets[idx]); node != NULL; + node = ares_llist_node_next(node)) { + if (htable->key_eq(key, htable->bucket_key(ares_llist_node_val(node)))) { break; } } @@ -184,14 +189,14 @@ static ares__llist_node_t *ares__htable_find(const ares__htable_t *htable, return node; } -static ares_bool_t ares__htable_expand(ares__htable_t *htable) +static ares_bool_t ares_htable_expand(ares_htable_t *htable) { - ares__llist_t **buckets = NULL; - unsigned int old_size = htable->size; - size_t i; - ares__llist_t **prealloc_llist = NULL; - size_t prealloc_llist_len = 0; - ares_bool_t rv = ARES_FALSE; + ares_llist_t **buckets = NULL; + unsigned int old_size = htable->size; + size_t i; + ares_llist_t **prealloc_llist = NULL; + size_t prealloc_llist_len = 0; + ares_bool_t rv = ARES_FALSE; /* Not a failure, just won't expand */ if (old_size == ARES__HTABLE_MAX_BUCKETS) { @@ -219,7 +224,7 @@ static ares_bool_t ares__htable_expand(ares__htable_t *htable) } } for (i = 0; i < prealloc_llist_len; i++) { - prealloc_llist[i] = ares__llist_create(htable->bucket_free); + prealloc_llist[i] = ares_llist_create(htable->bucket_free); if (prealloc_llist[i] == NULL) { goto done; } @@ -228,7 +233,7 @@ static ares_bool_t ares__htable_expand(ares__htable_t *htable) /* Iterate across all buckets and move the entries to the new buckets */ htable->num_collisions = 0; for (i = 0; i < old_size; i++) { - ares__llist_node_t *node; + ares_llist_node_t *node; /* Nothing in this bucket */ if (htable->buckets[i] == NULL) { @@ -238,8 +243,8 @@ static ares_bool_t ares__htable_expand(ares__htable_t *htable) /* Fast path optimization (most likely case), there is likely only a single * entry in both the source and destination, check for this to confirm and * if so, just move the bucket over */ - if (ares__llist_len(htable->buckets[i]) == 1) { - const void *val = ares__llist_first_val(htable->buckets[i]); + if (ares_llist_len(htable->buckets[i]) == 1) { + const void *val = ares_llist_first_val(htable->buckets[i]); size_t idx = HASH_IDX(htable, htable->bucket_key(val)); if (buckets[idx] == NULL) { @@ -251,13 +256,13 @@ static ares_bool_t ares__htable_expand(ares__htable_t *htable) } /* Slow path, collisions */ - while ((node = ares__llist_node_first(htable->buckets[i])) != NULL) { - const void *val = ares__llist_node_val(node); + while ((node = ares_llist_node_first(htable->buckets[i])) != NULL) { + const void *val = ares_llist_node_val(node); size_t idx = HASH_IDX(htable, htable->bucket_key(val)); /* Try fast path again as maybe we popped one collision off and the * next we can reuse the llist parent */ - if (buckets[idx] == NULL && ares__llist_len(htable->buckets[i]) == 1) { + if (buckets[idx] == NULL && ares_llist_len(htable->buckets[i]) == 1) { /* Swap! */ buckets[idx] = htable->buckets[i]; htable->buckets[i] = NULL; @@ -277,12 +282,12 @@ static ares_bool_t ares__htable_expand(ares__htable_t *htable) htable->num_collisions++; } - ares__llist_node_move_parent_first(node, buckets[idx]); + ares_llist_node_mvparent_first(node, buckets[idx]); } /* Abandoned bucket, destroy */ if (htable->buckets[i] != NULL) { - ares__llist_destroy(htable->buckets[i]); + ares_llist_destroy(htable->buckets[i]); htable->buckets[i] = NULL; } } @@ -297,8 +302,8 @@ static ares_bool_t ares__htable_expand(ares__htable_t *htable) done: ares_free(buckets); /* destroy any unused preallocated buckets */ - ares__htable_buckets_destroy(prealloc_llist, (unsigned int)prealloc_llist_len, - ARES_FALSE); + ares_htable_buckets_destroy(prealloc_llist, (unsigned int)prealloc_llist_len, + ARES_FALSE); /* On failure, we need to restore the htable size */ if (rv != ARES_TRUE) { @@ -308,11 +313,11 @@ done: return rv; } -ares_bool_t ares__htable_insert(ares__htable_t *htable, void *bucket) +ares_bool_t ares_htable_insert(ares_htable_t *htable, void *bucket) { - unsigned int idx = 0; - ares__llist_node_t *node = NULL; - const void *key = NULL; + unsigned int idx = 0; + ares_llist_node_t *node = NULL; + const void *key = NULL; if (htable == NULL || bucket == NULL) { return ARES_FALSE; @@ -323,9 +328,9 @@ ares_bool_t ares__htable_insert(ares__htable_t *htable, void *bucket) idx = HASH_IDX(htable, key); /* See if we have a matching bucket already, if so, replace it */ - node = ares__htable_find(htable, idx, key); + node = ares_htable_find(htable, idx, key); if (node != NULL) { - ares__llist_node_replace(node, bucket); + ares_llist_node_replace(node, bucket); return ARES_TRUE; } @@ -333,7 +338,7 @@ ares_bool_t ares__htable_insert(ares__htable_t *htable, void *bucket) * increased beyond our threshold */ if (htable->num_keys + 1 > (htable->size * ARES__HTABLE_EXPAND_PERCENT) / 100) { - if (!ares__htable_expand(htable)) { + if (!ares_htable_expand(htable)) { return ARES_FALSE; /* LCOV_EXCL_LINE */ } /* If we expanded, need to calculate a new index */ @@ -342,19 +347,19 @@ ares_bool_t ares__htable_insert(ares__htable_t *htable, void *bucket) /* We lazily allocate the linked list */ if (htable->buckets[idx] == NULL) { - htable->buckets[idx] = ares__llist_create(htable->bucket_free); + htable->buckets[idx] = ares_llist_create(htable->bucket_free); if (htable->buckets[idx] == NULL) { return ARES_FALSE; } } - node = ares__llist_insert_first(htable->buckets[idx], bucket); + node = ares_llist_insert_first(htable->buckets[idx], bucket); if (node == NULL) { return ARES_FALSE; } /* Track collisions for rehash stability */ - if (ares__llist_len(htable->buckets[idx]) > 1) { + if (ares_llist_len(htable->buckets[idx]) > 1) { htable->num_collisions++; } @@ -363,7 +368,7 @@ ares_bool_t ares__htable_insert(ares__htable_t *htable, void *bucket) return ARES_TRUE; } -void *ares__htable_get(const ares__htable_t *htable, const void *key) +void *ares_htable_get(const ares_htable_t *htable, const void *key) { unsigned int idx; @@ -373,20 +378,20 @@ void *ares__htable_get(const ares__htable_t *htable, const void *key) idx = HASH_IDX(htable, key); - return ares__llist_node_val(ares__htable_find(htable, idx, key)); + return ares_llist_node_val(ares_htable_find(htable, idx, key)); } -ares_bool_t ares__htable_remove(ares__htable_t *htable, const void *key) +ares_bool_t ares_htable_remove(ares_htable_t *htable, const void *key) { - ares__llist_node_t *node; - unsigned int idx; + ares_llist_node_t *node; + unsigned int idx; if (htable == NULL || key == NULL) { return ARES_FALSE; } idx = HASH_IDX(htable, key); - node = ares__htable_find(htable, idx, key); + node = ares_htable_find(htable, idx, key); if (node == NULL) { return ARES_FALSE; } @@ -394,15 +399,15 @@ ares_bool_t ares__htable_remove(ares__htable_t *htable, const void *key) htable->num_keys--; /* Reduce collisions */ - if (ares__llist_len(ares__llist_node_parent(node)) > 1) { + if (ares_llist_len(ares_llist_node_parent(node)) > 1) { htable->num_collisions--; } - ares__llist_node_destroy(node); + ares_llist_node_destroy(node); return ARES_TRUE; } -size_t ares__htable_num_keys(const ares__htable_t *htable) +size_t ares_htable_num_keys(const ares_htable_t *htable) { if (htable == NULL) { return 0; @@ -410,16 +415,15 @@ size_t ares__htable_num_keys(const ares__htable_t *htable) return htable->num_keys; } -unsigned int ares__htable_hash_FNV1a(const unsigned char *key, size_t key_len, - unsigned int seed) +unsigned int ares_htable_hash_FNV1a(const unsigned char *key, size_t key_len, + unsigned int seed) { - /* recommended seed is 2166136261U, but we don't want collisions */ - unsigned int hv = seed; + unsigned int hv = seed ^ 2166136261U; size_t i; for (i = 0; i < key_len; i++) { hv ^= (unsigned int)key[i]; - /* hv *= 0x01000193 */ + /* hv *= 16777619 (0x01000193) */ hv += (hv << 1) + (hv << 4) + (hv << 7) + (hv << 8) + (hv << 24); } @@ -427,16 +431,15 @@ unsigned int ares__htable_hash_FNV1a(const unsigned char *key, size_t key_len, } /* Case insensitive version, meant for ASCII strings */ -unsigned int ares__htable_hash_FNV1a_casecmp(const unsigned char *key, - size_t key_len, unsigned int seed) +unsigned int ares_htable_hash_FNV1a_casecmp(const unsigned char *key, + size_t key_len, unsigned int seed) { - /* recommended seed is 2166136261U, but we don't want collisions */ - unsigned int hv = seed; + unsigned int hv = seed ^ 2166136261U; size_t i; for (i = 0; i < key_len; i++) { - hv ^= (unsigned int)ares__tolower(key[i]); - /* hv *= 0x01000193 */ + hv ^= (unsigned int)ares_tolower(key[i]); + /* hv *= 16777619 (0x01000193) */ hv += (hv << 1) + (hv << 4) + (hv << 7) + (hv << 8) + (hv << 24); } diff --git a/contrib/libs/c-ares/src/lib/dsa/ares__htable.h b/contrib/libs/c-ares/src/lib/dsa/ares_htable.h index d09c865977..5700286eb0 100644 --- a/contrib/libs/c-ares/src/lib/dsa/ares__htable.h +++ b/contrib/libs/c-ares/src/lib/dsa/ares_htable.h @@ -27,7 +27,7 @@ #define __ARES__HTABLE_H -/*! \addtogroup ares__htable Base HashTable Data Structure +/*! \addtogroup ares_htable Base HashTable Data Structure * * This is a basic hashtable data structure that is meant to be wrapped * by a higher level implementation. This data structure is designed to @@ -45,10 +45,10 @@ * @{ */ -struct ares__htable; +struct ares_htable; /*! Opaque data type for generic hash table implementation */ -typedef struct ares__htable ares__htable_t; +typedef struct ares_htable ares_htable_t; /*! Callback for generating a hash of the key. * @@ -58,21 +58,21 @@ typedef struct ares__htable ares__htable_t; * but otherwise will not change between calls. * \return hash */ -typedef unsigned int (*ares__htable_hashfunc_t)(const void *key, - unsigned int seed); +typedef unsigned int (*ares_htable_hashfunc_t)(const void *key, + unsigned int seed); /*! Callback to free the bucket * * \param[in] bucket user provided bucket */ -typedef void (*ares__htable_bucket_free_t)(void *bucket); +typedef void (*ares_htable_bucket_free_t)(void *bucket); /*! Callback to extract the key from the user-provided bucket * * \param[in] bucket user provided bucket * \return pointer to key held in bucket */ -typedef const void *(*ares__htable_bucket_key_t)(const void *bucket); +typedef const void *(*ares_htable_bucket_key_t)(const void *bucket); /*! Callback to compare two keys for equality * @@ -80,15 +80,14 @@ typedef const void *(*ares__htable_bucket_key_t)(const void *bucket); * \param[in] key2 second key * \return ARES_TRUE if equal, ARES_FALSE if not */ -typedef ares_bool_t (*ares__htable_key_eq_t)(const void *key1, - const void *key2); +typedef ares_bool_t (*ares_htable_key_eq_t)(const void *key1, const void *key2); /*! Destroy the initialized hashtable * * \param[in] htable initialized hashtable */ -void ares__htable_destroy(ares__htable_t *htable); +void ares_htable_destroy(ares_htable_t *htable); /*! Create a new hashtable * @@ -98,17 +97,17 @@ void ares__htable_destroy(ares__htable_t *htable); * \param[in] key_eq Required. Callback to check for key equality. * \return initialized hashtable. NULL if out of memory or misuse. */ -ares__htable_t *ares__htable_create(ares__htable_hashfunc_t hash_func, - ares__htable_bucket_key_t bucket_key, - ares__htable_bucket_free_t bucket_free, - ares__htable_key_eq_t key_eq); +ares_htable_t *ares_htable_create(ares_htable_hashfunc_t hash_func, + ares_htable_bucket_key_t bucket_key, + ares_htable_bucket_free_t bucket_free, + ares_htable_key_eq_t key_eq); /*! Count of keys from initialized hashtable * * \param[in] htable Initialized hashtable. * \return count of keys */ -size_t ares__htable_num_keys(const ares__htable_t *htable); +size_t ares_htable_num_keys(const ares_htable_t *htable); /*! Retrieve an array of buckets from the hashtable. This is mainly used as * a helper for retrieving an array of keys. @@ -120,8 +119,7 @@ size_t ares__htable_num_keys(const ares__htable_t *htable); * will be a dangling pointer. It is expected wrappers will make * such values safe by duplicating them. */ -const void **ares__htable_all_buckets(const ares__htable_t *htable, - size_t *num); +const void **ares_htable_all_buckets(const ares_htable_t *htable, size_t *num); /*! Insert bucket into hashtable * @@ -130,7 +128,7 @@ const void **ares__htable_all_buckets(const ares__htable_t *htable, * allowed to be NULL. * \return ARES_TRUE on success, ARES_FALSE if out of memory */ -ares_bool_t ares__htable_insert(ares__htable_t *htable, void *bucket); +ares_bool_t ares_htable_insert(ares_htable_t *htable, void *bucket); /*! Retrieve bucket from hashtable based on key. * @@ -138,7 +136,7 @@ ares_bool_t ares__htable_insert(ares__htable_t *htable, void *bucket); * \param[in] key Pointer to key to use for comparison. * \return matching bucket, or NULL if not found. */ -void *ares__htable_get(const ares__htable_t *htable, const void *key); +void *ares_htable_get(const ares_htable_t *htable, const void *key); /*! Remove bucket from hashtable by key * @@ -146,7 +144,7 @@ void *ares__htable_get(const ares__htable_t *htable, const void *key); * \param[in] key Pointer to key to use for comparison * \return ARES_TRUE if found, ARES_FALSE if not found */ -ares_bool_t ares__htable_remove(ares__htable_t *htable, const void *key); +ares_bool_t ares_htable_remove(ares_htable_t *htable, const void *key); /*! FNV1a hash algorithm. Can be used as underlying primitive for building * a wrapper hashtable. @@ -156,8 +154,8 @@ ares_bool_t ares__htable_remove(ares__htable_t *htable, const void *key); * \param[in] seed Seed for generating hash * \return hash value */ -unsigned int ares__htable_hash_FNV1a(const unsigned char *key, size_t key_len, - unsigned int seed); +unsigned int ares_htable_hash_FNV1a(const unsigned char *key, size_t key_len, + unsigned int seed); /*! FNV1a hash algorithm, but converts all characters to lowercase before * hashing to make the hash case-insensitive. Can be used as underlying @@ -168,8 +166,8 @@ unsigned int ares__htable_hash_FNV1a(const unsigned char *key, size_t key_len, * \param[in] seed Seed for generating hash * \return hash value */ -unsigned int ares__htable_hash_FNV1a_casecmp(const unsigned char *key, - size_t key_len, unsigned int seed); +unsigned int ares_htable_hash_FNV1a_casecmp(const unsigned char *key, + size_t key_len, unsigned int seed); /*! @} */ diff --git a/contrib/libs/c-ares/src/lib/dsa/ares__htable_asvp.c b/contrib/libs/c-ares/src/lib/dsa/ares_htable_asvp.c index 4b9267ff6c..32f4d2c994 100644 --- a/contrib/libs/c-ares/src/lib/dsa/ares__htable_asvp.c +++ b/contrib/libs/c-ares/src/lib/dsa/ares_htable_asvp.c @@ -24,46 +24,45 @@ * SPDX-License-Identifier: MIT */ #include "ares_private.h" -#include "ares__htable.h" -#include "ares__htable_asvp.h" +#include "ares_htable.h" +#include "ares_htable_asvp.h" -struct ares__htable_asvp { - ares__htable_asvp_val_free_t free_val; - ares__htable_t *hash; +struct ares_htable_asvp { + ares_htable_asvp_val_free_t free_val; + ares_htable_t *hash; }; typedef struct { - ares_socket_t key; - void *val; - ares__htable_asvp_t *parent; -} ares__htable_asvp_bucket_t; + ares_socket_t key; + void *val; + ares_htable_asvp_t *parent; +} ares_htable_asvp_bucket_t; -void ares__htable_asvp_destroy(ares__htable_asvp_t *htable) +void ares_htable_asvp_destroy(ares_htable_asvp_t *htable) { if (htable == NULL) { return; } - ares__htable_destroy(htable->hash); + ares_htable_destroy(htable->hash); ares_free(htable); } static unsigned int hash_func(const void *key, unsigned int seed) { const ares_socket_t *arg = key; - return ares__htable_hash_FNV1a((const unsigned char *)arg, sizeof(*arg), - seed); + return ares_htable_hash_FNV1a((const unsigned char *)arg, sizeof(*arg), seed); } static const void *bucket_key(const void *bucket) { - const ares__htable_asvp_bucket_t *arg = bucket; + const ares_htable_asvp_bucket_t *arg = bucket; return &arg->key; } static void bucket_free(void *bucket) { - ares__htable_asvp_bucket_t *arg = bucket; + ares_htable_asvp_bucket_t *arg = bucket; if (arg->parent->free_val) { arg->parent->free_val(arg->val); @@ -84,16 +83,15 @@ static ares_bool_t key_eq(const void *key1, const void *key2) return ARES_FALSE; } -ares__htable_asvp_t * - ares__htable_asvp_create(ares__htable_asvp_val_free_t val_free) +ares_htable_asvp_t * + ares_htable_asvp_create(ares_htable_asvp_val_free_t val_free) { - ares__htable_asvp_t *htable = ares_malloc(sizeof(*htable)); + ares_htable_asvp_t *htable = ares_malloc(sizeof(*htable)); if (htable == NULL) { goto fail; } - htable->hash = - ares__htable_create(hash_func, bucket_key, bucket_free, key_eq); + htable->hash = ares_htable_create(hash_func, bucket_key, bucket_free, key_eq); if (htable->hash == NULL) { goto fail; } @@ -104,14 +102,14 @@ ares__htable_asvp_t * fail: if (htable) { - ares__htable_destroy(htable->hash); + ares_htable_destroy(htable->hash); ares_free(htable); } return NULL; } -ares_socket_t *ares__htable_asvp_keys(const ares__htable_asvp_t *htable, - size_t *num) +ares_socket_t *ares_htable_asvp_keys(const ares_htable_asvp_t *htable, + size_t *num) { const void **buckets = NULL; size_t cnt = 0; @@ -124,7 +122,7 @@ ares_socket_t *ares__htable_asvp_keys(const ares__htable_asvp_t *htable, *num = 0; - buckets = ares__htable_all_buckets(htable->hash, &cnt); + buckets = ares_htable_all_buckets(htable->hash, &cnt); if (buckets == NULL || cnt == 0) { return NULL; } @@ -136,7 +134,7 @@ ares_socket_t *ares__htable_asvp_keys(const ares__htable_asvp_t *htable, } for (i = 0; i < cnt; i++) { - out[i] = ((const ares__htable_asvp_bucket_t *)buckets[i])->key; + out[i] = ((const ares_htable_asvp_bucket_t *)buckets[i])->key; } ares_free(buckets); @@ -144,10 +142,10 @@ ares_socket_t *ares__htable_asvp_keys(const ares__htable_asvp_t *htable, return out; } -ares_bool_t ares__htable_asvp_insert(ares__htable_asvp_t *htable, - ares_socket_t key, void *val) +ares_bool_t ares_htable_asvp_insert(ares_htable_asvp_t *htable, + ares_socket_t key, void *val) { - ares__htable_asvp_bucket_t *bucket = NULL; + ares_htable_asvp_bucket_t *bucket = NULL; if (htable == NULL) { goto fail; @@ -162,7 +160,7 @@ ares_bool_t ares__htable_asvp_insert(ares__htable_asvp_t *htable, bucket->key = key; bucket->val = val; - if (!ares__htable_insert(htable->hash, bucket)) { + if (!ares_htable_insert(htable->hash, bucket)) { goto fail; /* LCOV_EXCL_LINE: OutOfMemory */ } @@ -175,10 +173,10 @@ fail: return ARES_FALSE; } -ares_bool_t ares__htable_asvp_get(const ares__htable_asvp_t *htable, - ares_socket_t key, void **val) +ares_bool_t ares_htable_asvp_get(const ares_htable_asvp_t *htable, + ares_socket_t key, void **val) { - ares__htable_asvp_bucket_t *bucket = NULL; + ares_htable_asvp_bucket_t *bucket = NULL; if (val) { *val = NULL; @@ -188,7 +186,7 @@ ares_bool_t ares__htable_asvp_get(const ares__htable_asvp_t *htable, return ARES_FALSE; } - bucket = ares__htable_get(htable->hash, &key); + bucket = ares_htable_get(htable->hash, &key); if (bucket == NULL) { return ARES_FALSE; } @@ -199,28 +197,28 @@ ares_bool_t ares__htable_asvp_get(const ares__htable_asvp_t *htable, return ARES_TRUE; } -void *ares__htable_asvp_get_direct(const ares__htable_asvp_t *htable, - ares_socket_t key) +void *ares_htable_asvp_get_direct(const ares_htable_asvp_t *htable, + ares_socket_t key) { void *val = NULL; - ares__htable_asvp_get(htable, key, &val); + ares_htable_asvp_get(htable, key, &val); return val; } -ares_bool_t ares__htable_asvp_remove(ares__htable_asvp_t *htable, - ares_socket_t key) +ares_bool_t ares_htable_asvp_remove(ares_htable_asvp_t *htable, + ares_socket_t key) { if (htable == NULL) { return ARES_FALSE; } - return ares__htable_remove(htable->hash, &key); + return ares_htable_remove(htable->hash, &key); } -size_t ares__htable_asvp_num_keys(const ares__htable_asvp_t *htable) +size_t ares_htable_asvp_num_keys(const ares_htable_asvp_t *htable) { if (htable == NULL) { return 0; } - return ares__htable_num_keys(htable->hash); + return ares_htable_num_keys(htable->hash); } diff --git a/contrib/libs/c-ares/src/lib/dsa/ares_htable_dict.c b/contrib/libs/c-ares/src/lib/dsa/ares_htable_dict.c new file mode 100644 index 0000000000..93d7a20137 --- /dev/null +++ b/contrib/libs/c-ares/src/lib/dsa/ares_htable_dict.c @@ -0,0 +1,228 @@ +/* MIT License + * + * Copyright (c) 2024 Brad House + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice (including the next + * paragraph) shall be included in all copies or substantial portions of the + * Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + * + * SPDX-License-Identifier: MIT + */ +#include "ares_private.h" +#include "ares_htable.h" +#include "ares_htable_dict.h" + +struct ares_htable_dict { + ares_htable_t *hash; +}; + +typedef struct { + char *key; + char *val; + ares_htable_dict_t *parent; +} ares_htable_dict_bucket_t; + +void ares_htable_dict_destroy(ares_htable_dict_t *htable) +{ + if (htable == NULL) { + return; /* LCOV_EXCL_LINE: DefensiveCoding */ + } + + ares_htable_destroy(htable->hash); + ares_free(htable); +} + +static unsigned int hash_func(const void *key, unsigned int seed) +{ + return ares_htable_hash_FNV1a_casecmp(key, ares_strlen(key), seed); +} + +static const void *bucket_key(const void *bucket) +{ + const ares_htable_dict_bucket_t *arg = bucket; + return arg->key; +} + +static void bucket_free(void *bucket) +{ + ares_htable_dict_bucket_t *arg = bucket; + + ares_free(arg->key); + ares_free(arg->val); + + ares_free(arg); +} + +static ares_bool_t key_eq(const void *key1, const void *key2) +{ + return ares_strcaseeq(key1, key2); +} + +ares_htable_dict_t *ares_htable_dict_create(void) +{ + ares_htable_dict_t *htable = ares_malloc(sizeof(*htable)); + if (htable == NULL) { + goto fail; /* LCOV_EXCL_LINE: OutOfMemory */ + } + + htable->hash = ares_htable_create(hash_func, bucket_key, bucket_free, key_eq); + if (htable->hash == NULL) { + goto fail; /* LCOV_EXCL_LINE: OutOfMemory */ + } + + return htable; + +/* LCOV_EXCL_START: OutOfMemory */ +fail: + if (htable) { + ares_htable_destroy(htable->hash); + ares_free(htable); + } + return NULL; + /* LCOV_EXCL_STOP */ +} + +ares_bool_t ares_htable_dict_insert(ares_htable_dict_t *htable, const char *key, + const char *val) +{ + ares_htable_dict_bucket_t *bucket = NULL; + + if (htable == NULL || ares_strlen(key) == 0) { + goto fail; + } + + bucket = ares_malloc_zero(sizeof(*bucket)); + if (bucket == NULL) { + goto fail; + } + + bucket->parent = htable; + bucket->key = ares_strdup(key); + if (bucket->key == NULL) { + goto fail; + } + + if (val != NULL) { + bucket->val = ares_strdup(val); + if (bucket->val == NULL) { + goto fail; + } + } + + if (!ares_htable_insert(htable->hash, bucket)) { + goto fail; + } + + return ARES_TRUE; + +fail: + if (bucket) { + ares_free(bucket->val); + ares_free(bucket); + } + return ARES_FALSE; +} + +ares_bool_t ares_htable_dict_get(const ares_htable_dict_t *htable, + const char *key, const char **val) +{ + const ares_htable_dict_bucket_t *bucket = NULL; + + if (val) { + *val = NULL; + } + + if (htable == NULL) { + return ARES_FALSE; + } + + bucket = ares_htable_get(htable->hash, key); + if (bucket == NULL) { + return ARES_FALSE; + } + + if (val) { + *val = bucket->val; + } + return ARES_TRUE; +} + +const char *ares_htable_dict_get_direct(const ares_htable_dict_t *htable, + const char *key) +{ + const char *val = NULL; + ares_htable_dict_get(htable, key, &val); + return val; +} + +ares_bool_t ares_htable_dict_remove(ares_htable_dict_t *htable, const char *key) +{ + if (htable == NULL) { + return ARES_FALSE; + } + + return ares_htable_remove(htable->hash, key); +} + +size_t ares_htable_dict_num_keys(const ares_htable_dict_t *htable) +{ + if (htable == NULL) { + return 0; + } + return ares_htable_num_keys(htable->hash); +} + +char **ares_htable_dict_keys(const ares_htable_dict_t *htable, size_t *num) +{ + const void **buckets = NULL; + size_t cnt = 0; + char **out = NULL; + size_t i; + + if (htable == NULL || num == NULL) { + return NULL; /* LCOV_EXCL_LINE: DefensiveCoding */ + } + + *num = 0; + + buckets = ares_htable_all_buckets(htable->hash, &cnt); + if (buckets == NULL || cnt == 0) { + return NULL; + } + + out = ares_malloc_zero(sizeof(*out) * cnt); + if (out == NULL) { + goto fail; /* LCOV_EXCL_LINE: OutOfMemory */ + } + + for (i = 0; i < cnt; i++) { + out[i] = ares_strdup(((const ares_htable_dict_bucket_t *)buckets[i])->key); + if (out[i] == NULL) { + goto fail; + } + } + + ares_free(buckets); + *num = cnt; + return out; + +fail: + *num = 0; + ares_free_array(out, cnt, ares_free); + return NULL; +} diff --git a/contrib/libs/c-ares/src/lib/dsa/ares__htable_strvp.c b/contrib/libs/c-ares/src/lib/dsa/ares_htable_strvp.c index d73a1928a7..daca117e80 100644 --- a/contrib/libs/c-ares/src/lib/dsa/ares__htable_strvp.c +++ b/contrib/libs/c-ares/src/lib/dsa/ares_htable_strvp.c @@ -24,46 +24,46 @@ * SPDX-License-Identifier: MIT */ #include "ares_private.h" -#include "ares__htable.h" -#include "ares__htable_strvp.h" +#include "ares_htable.h" +#include "ares_htable_strvp.h" -struct ares__htable_strvp { - ares__htable_strvp_val_free_t free_val; - ares__htable_t *hash; +struct ares_htable_strvp { + ares_htable_strvp_val_free_t free_val; + ares_htable_t *hash; }; typedef struct { - char *key; - void *val; - ares__htable_strvp_t *parent; -} ares__htable_strvp_bucket_t; + char *key; + void *val; + ares_htable_strvp_t *parent; +} ares_htable_strvp_bucket_t; -void ares__htable_strvp_destroy(ares__htable_strvp_t *htable) +void ares_htable_strvp_destroy(ares_htable_strvp_t *htable) { if (htable == NULL) { return; } - ares__htable_destroy(htable->hash); + ares_htable_destroy(htable->hash); ares_free(htable); } static unsigned int hash_func(const void *key, unsigned int seed) { const char *arg = key; - return ares__htable_hash_FNV1a_casecmp((const unsigned char *)arg, - ares_strlen(arg), seed); + return ares_htable_hash_FNV1a_casecmp((const unsigned char *)arg, + ares_strlen(arg), seed); } static const void *bucket_key(const void *bucket) { - const ares__htable_strvp_bucket_t *arg = bucket; + const ares_htable_strvp_bucket_t *arg = bucket; return arg->key; } static void bucket_free(void *bucket) { - ares__htable_strvp_bucket_t *arg = bucket; + ares_htable_strvp_bucket_t *arg = bucket; if (arg->parent->free_val) { arg->parent->free_val(arg->val); @@ -74,26 +74,18 @@ static void bucket_free(void *bucket) static ares_bool_t key_eq(const void *key1, const void *key2) { - const char *k1 = key1; - const char *k2 = key2; - - if (strcasecmp(k1, k2) == 0) { - return ARES_TRUE; - } - - return ARES_FALSE; + return ares_strcaseeq(key1, key2); } -ares__htable_strvp_t * - ares__htable_strvp_create(ares__htable_strvp_val_free_t val_free) +ares_htable_strvp_t * + ares_htable_strvp_create(ares_htable_strvp_val_free_t val_free) { - ares__htable_strvp_t *htable = ares_malloc(sizeof(*htable)); + ares_htable_strvp_t *htable = ares_malloc(sizeof(*htable)); if (htable == NULL) { goto fail; } - htable->hash = - ares__htable_create(hash_func, bucket_key, bucket_free, key_eq); + htable->hash = ares_htable_create(hash_func, bucket_key, bucket_free, key_eq); if (htable->hash == NULL) { goto fail; } @@ -104,16 +96,16 @@ ares__htable_strvp_t * fail: if (htable) { - ares__htable_destroy(htable->hash); + ares_htable_destroy(htable->hash); ares_free(htable); } return NULL; } -ares_bool_t ares__htable_strvp_insert(ares__htable_strvp_t *htable, - const char *key, void *val) +ares_bool_t ares_htable_strvp_insert(ares_htable_strvp_t *htable, + const char *key, void *val) { - ares__htable_strvp_bucket_t *bucket = NULL; + ares_htable_strvp_bucket_t *bucket = NULL; if (htable == NULL || key == NULL) { goto fail; @@ -131,7 +123,7 @@ ares_bool_t ares__htable_strvp_insert(ares__htable_strvp_t *htable, } bucket->val = val; - if (!ares__htable_insert(htable->hash, bucket)) { + if (!ares_htable_insert(htable->hash, bucket)) { goto fail; } @@ -145,10 +137,10 @@ fail: return ARES_FALSE; } -ares_bool_t ares__htable_strvp_get(const ares__htable_strvp_t *htable, - const char *key, void **val) +ares_bool_t ares_htable_strvp_get(const ares_htable_strvp_t *htable, + const char *key, void **val) { - ares__htable_strvp_bucket_t *bucket = NULL; + ares_htable_strvp_bucket_t *bucket = NULL; if (val) { *val = NULL; @@ -158,7 +150,7 @@ ares_bool_t ares__htable_strvp_get(const ares__htable_strvp_t *htable, return ARES_FALSE; } - bucket = ares__htable_get(htable->hash, key); + bucket = ares_htable_get(htable->hash, key); if (bucket == NULL) { return ARES_FALSE; } @@ -169,28 +161,50 @@ ares_bool_t ares__htable_strvp_get(const ares__htable_strvp_t *htable, return ARES_TRUE; } -void *ares__htable_strvp_get_direct(const ares__htable_strvp_t *htable, - const char *key) +void *ares_htable_strvp_get_direct(const ares_htable_strvp_t *htable, + const char *key) { void *val = NULL; - ares__htable_strvp_get(htable, key, &val); + ares_htable_strvp_get(htable, key, &val); return val; } -ares_bool_t ares__htable_strvp_remove(ares__htable_strvp_t *htable, - const char *key) +ares_bool_t ares_htable_strvp_remove(ares_htable_strvp_t *htable, + const char *key) { if (htable == NULL) { return ARES_FALSE; } - return ares__htable_remove(htable->hash, key); + return ares_htable_remove(htable->hash, key); +} + +void *ares_htable_strvp_claim(ares_htable_strvp_t *htable, const char *key) +{ + ares_htable_strvp_bucket_t *bucket = NULL; + void *val; + + if (htable == NULL || key == NULL) { + return NULL; + } + + bucket = ares_htable_get(htable->hash, key); + if (bucket == NULL) { + return NULL; + } + + /* Unassociate value from bucket */ + val = bucket->val; + bucket->val = NULL; + + ares_htable_strvp_remove(htable, key); + return val; } -size_t ares__htable_strvp_num_keys(const ares__htable_strvp_t *htable) +size_t ares_htable_strvp_num_keys(const ares_htable_strvp_t *htable) { if (htable == NULL) { return 0; } - return ares__htable_num_keys(htable->hash); + return ares_htable_num_keys(htable->hash); } diff --git a/contrib/libs/c-ares/src/lib/dsa/ares__htable_szvp.c b/contrib/libs/c-ares/src/lib/dsa/ares_htable_szvp.c index b3e88d8b9a..fdaae0a571 100644 --- a/contrib/libs/c-ares/src/lib/dsa/ares__htable_szvp.c +++ b/contrib/libs/c-ares/src/lib/dsa/ares_htable_szvp.c @@ -24,46 +24,45 @@ * SPDX-License-Identifier: MIT */ #include "ares_private.h" -#include "ares__htable.h" -#include "ares__htable_szvp.h" +#include "ares_htable.h" +#include "ares_htable_szvp.h" -struct ares__htable_szvp { - ares__htable_szvp_val_free_t free_val; - ares__htable_t *hash; +struct ares_htable_szvp { + ares_htable_szvp_val_free_t free_val; + ares_htable_t *hash; }; typedef struct { - size_t key; - void *val; - ares__htable_szvp_t *parent; -} ares__htable_szvp_bucket_t; + size_t key; + void *val; + ares_htable_szvp_t *parent; +} ares_htable_szvp_bucket_t; -void ares__htable_szvp_destroy(ares__htable_szvp_t *htable) +void ares_htable_szvp_destroy(ares_htable_szvp_t *htable) { if (htable == NULL) { return; } - ares__htable_destroy(htable->hash); + ares_htable_destroy(htable->hash); ares_free(htable); } static unsigned int hash_func(const void *key, unsigned int seed) { const size_t *arg = key; - return ares__htable_hash_FNV1a((const unsigned char *)arg, sizeof(*arg), - seed); + return ares_htable_hash_FNV1a((const unsigned char *)arg, sizeof(*arg), seed); } static const void *bucket_key(const void *bucket) { - const ares__htable_szvp_bucket_t *arg = bucket; + const ares_htable_szvp_bucket_t *arg = bucket; return &arg->key; } static void bucket_free(void *bucket) { - ares__htable_szvp_bucket_t *arg = bucket; + ares_htable_szvp_bucket_t *arg = bucket; if (arg->parent->free_val) { arg->parent->free_val(arg->val); @@ -84,16 +83,15 @@ static ares_bool_t key_eq(const void *key1, const void *key2) return ARES_FALSE; } -ares__htable_szvp_t * - ares__htable_szvp_create(ares__htable_szvp_val_free_t val_free) +ares_htable_szvp_t * + ares_htable_szvp_create(ares_htable_szvp_val_free_t val_free) { - ares__htable_szvp_t *htable = ares_malloc(sizeof(*htable)); + ares_htable_szvp_t *htable = ares_malloc(sizeof(*htable)); if (htable == NULL) { goto fail; } - htable->hash = - ares__htable_create(hash_func, bucket_key, bucket_free, key_eq); + htable->hash = ares_htable_create(hash_func, bucket_key, bucket_free, key_eq); if (htable->hash == NULL) { goto fail; } @@ -104,16 +102,16 @@ ares__htable_szvp_t * fail: if (htable) { - ares__htable_destroy(htable->hash); + ares_htable_destroy(htable->hash); ares_free(htable); } return NULL; } -ares_bool_t ares__htable_szvp_insert(ares__htable_szvp_t *htable, size_t key, - void *val) +ares_bool_t ares_htable_szvp_insert(ares_htable_szvp_t *htable, size_t key, + void *val) { - ares__htable_szvp_bucket_t *bucket = NULL; + ares_htable_szvp_bucket_t *bucket = NULL; if (htable == NULL) { goto fail; @@ -128,7 +126,7 @@ ares_bool_t ares__htable_szvp_insert(ares__htable_szvp_t *htable, size_t key, bucket->key = key; bucket->val = val; - if (!ares__htable_insert(htable->hash, bucket)) { + if (!ares_htable_insert(htable->hash, bucket)) { goto fail; /* LCOV_EXCL_LINE: OutOfMemory */ } @@ -141,10 +139,10 @@ fail: return ARES_FALSE; } -ares_bool_t ares__htable_szvp_get(const ares__htable_szvp_t *htable, size_t key, - void **val) +ares_bool_t ares_htable_szvp_get(const ares_htable_szvp_t *htable, size_t key, + void **val) { - ares__htable_szvp_bucket_t *bucket = NULL; + ares_htable_szvp_bucket_t *bucket = NULL; if (val) { *val = NULL; @@ -154,7 +152,7 @@ ares_bool_t ares__htable_szvp_get(const ares__htable_szvp_t *htable, size_t key, return ARES_FALSE; } - bucket = ares__htable_get(htable->hash, &key); + bucket = ares_htable_get(htable->hash, &key); if (bucket == NULL) { return ARES_FALSE; } @@ -165,27 +163,26 @@ ares_bool_t ares__htable_szvp_get(const ares__htable_szvp_t *htable, size_t key, return ARES_TRUE; } -void *ares__htable_szvp_get_direct(const ares__htable_szvp_t *htable, - size_t key) +void *ares_htable_szvp_get_direct(const ares_htable_szvp_t *htable, size_t key) { void *val = NULL; - ares__htable_szvp_get(htable, key, &val); + ares_htable_szvp_get(htable, key, &val); return val; } -ares_bool_t ares__htable_szvp_remove(ares__htable_szvp_t *htable, size_t key) +ares_bool_t ares_htable_szvp_remove(ares_htable_szvp_t *htable, size_t key) { if (htable == NULL) { return ARES_FALSE; } - return ares__htable_remove(htable->hash, &key); + return ares_htable_remove(htable->hash, &key); } -size_t ares__htable_szvp_num_keys(const ares__htable_szvp_t *htable) +size_t ares_htable_szvp_num_keys(const ares_htable_szvp_t *htable) { if (htable == NULL) { return 0; } - return ares__htable_num_keys(htable->hash); + return ares_htable_num_keys(htable->hash); } diff --git a/contrib/libs/c-ares/src/lib/dsa/ares_htable_vpstr.c b/contrib/libs/c-ares/src/lib/dsa/ares_htable_vpstr.c new file mode 100644 index 0000000000..86c881f768 --- /dev/null +++ b/contrib/libs/c-ares/src/lib/dsa/ares_htable_vpstr.c @@ -0,0 +1,186 @@ +/* MIT License + * + * Copyright (c) 2024 Brad House + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice (including the next + * paragraph) shall be included in all copies or substantial portions of the + * Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + * + * SPDX-License-Identifier: MIT + */ +#include "ares_private.h" +#include "ares_htable.h" +#include "ares_htable_vpstr.h" + +struct ares_htable_vpstr { + ares_htable_t *hash; +}; + +typedef struct { + void *key; + char *val; + ares_htable_vpstr_t *parent; +} ares_htable_vpstr_bucket_t; + +void ares_htable_vpstr_destroy(ares_htable_vpstr_t *htable) +{ + if (htable == NULL) { + return; /* LCOV_EXCL_LINE: DefensiveCoding */ + } + + ares_htable_destroy(htable->hash); + ares_free(htable); +} + +static unsigned int hash_func(const void *key, unsigned int seed) +{ + return ares_htable_hash_FNV1a((const unsigned char *)&key, sizeof(key), seed); +} + +static const void *bucket_key(const void *bucket) +{ + const ares_htable_vpstr_bucket_t *arg = bucket; + return arg->key; +} + +static void bucket_free(void *bucket) +{ + ares_htable_vpstr_bucket_t *arg = bucket; + + ares_free(arg->val); + + ares_free(arg); +} + +static ares_bool_t key_eq(const void *key1, const void *key2) +{ + if (key1 == key2) { + return ARES_TRUE; + } + + return ARES_FALSE; +} + +ares_htable_vpstr_t *ares_htable_vpstr_create(void) +{ + ares_htable_vpstr_t *htable = ares_malloc(sizeof(*htable)); + if (htable == NULL) { + goto fail; /* LCOV_EXCL_LINE: OutOfMemory */ + } + + htable->hash = ares_htable_create(hash_func, bucket_key, bucket_free, key_eq); + if (htable->hash == NULL) { + goto fail; /* LCOV_EXCL_LINE: OutOfMemory */ + } + + return htable; + +/* LCOV_EXCL_START: OutOfMemory */ +fail: + if (htable) { + ares_htable_destroy(htable->hash); + ares_free(htable); + } + return NULL; + /* LCOV_EXCL_STOP */ +} + +ares_bool_t ares_htable_vpstr_insert(ares_htable_vpstr_t *htable, void *key, + const char *val) +{ + ares_htable_vpstr_bucket_t *bucket = NULL; + + if (htable == NULL) { + goto fail; + } + + bucket = ares_malloc(sizeof(*bucket)); + if (bucket == NULL) { + goto fail; + } + + bucket->parent = htable; + bucket->key = key; + bucket->val = ares_strdup(val); + if (bucket->val == NULL) { + goto fail; + } + + if (!ares_htable_insert(htable->hash, bucket)) { + goto fail; + } + + return ARES_TRUE; + +fail: + if (bucket) { + ares_free(bucket->val); + ares_free(bucket); + } + return ARES_FALSE; +} + +ares_bool_t ares_htable_vpstr_get(const ares_htable_vpstr_t *htable, + const void *key, const char **val) +{ + const ares_htable_vpstr_bucket_t *bucket = NULL; + + if (val) { + *val = NULL; + } + + if (htable == NULL) { + return ARES_FALSE; + } + + bucket = ares_htable_get(htable->hash, key); + if (bucket == NULL) { + return ARES_FALSE; + } + + if (val) { + *val = bucket->val; + } + return ARES_TRUE; +} + +const char *ares_htable_vpstr_get_direct(const ares_htable_vpstr_t *htable, + const void *key) +{ + const char *val = NULL; + ares_htable_vpstr_get(htable, key, &val); + return val; +} + +ares_bool_t ares_htable_vpstr_remove(ares_htable_vpstr_t *htable, + const void *key) +{ + if (htable == NULL) { + return ARES_FALSE; + } + + return ares_htable_remove(htable->hash, key); +} + +size_t ares_htable_vpstr_num_keys(const ares_htable_vpstr_t *htable) +{ + if (htable == NULL) { + return 0; + } + return ares_htable_num_keys(htable->hash); +} diff --git a/contrib/libs/c-ares/src/lib/dsa/ares__htable_vpvp.c b/contrib/libs/c-ares/src/lib/dsa/ares_htable_vpvp.c index 9042c48dd7..14fd6e9da0 100644 --- a/contrib/libs/c-ares/src/lib/dsa/ares__htable_vpvp.c +++ b/contrib/libs/c-ares/src/lib/dsa/ares_htable_vpvp.c @@ -24,46 +24,45 @@ * SPDX-License-Identifier: MIT */ #include "ares_private.h" -#include "ares__htable.h" -#include "ares__htable_vpvp.h" +#include "ares_htable.h" +#include "ares_htable_vpvp.h" -struct ares__htable_vpvp { - ares__htable_vpvp_key_free_t free_key; - ares__htable_vpvp_val_free_t free_val; - ares__htable_t *hash; +struct ares_htable_vpvp { + ares_htable_vpvp_key_free_t free_key; + ares_htable_vpvp_val_free_t free_val; + ares_htable_t *hash; }; typedef struct { - void *key; - void *val; - ares__htable_vpvp_t *parent; -} ares__htable_vpvp_bucket_t; + void *key; + void *val; + ares_htable_vpvp_t *parent; +} ares_htable_vpvp_bucket_t; -void ares__htable_vpvp_destroy(ares__htable_vpvp_t *htable) +void ares_htable_vpvp_destroy(ares_htable_vpvp_t *htable) { if (htable == NULL) { return; /* LCOV_EXCL_LINE: DefensiveCoding */ } - ares__htable_destroy(htable->hash); + ares_htable_destroy(htable->hash); ares_free(htable); } static unsigned int hash_func(const void *key, unsigned int seed) { - return ares__htable_hash_FNV1a((const unsigned char *)&key, sizeof(key), - seed); + return ares_htable_hash_FNV1a((const unsigned char *)&key, sizeof(key), seed); } static const void *bucket_key(const void *bucket) { - const ares__htable_vpvp_bucket_t *arg = bucket; + const ares_htable_vpvp_bucket_t *arg = bucket; return arg->key; } static void bucket_free(void *bucket) { - ares__htable_vpvp_bucket_t *arg = bucket; + ares_htable_vpvp_bucket_t *arg = bucket; if (arg->parent->free_key) { arg->parent->free_key(arg->key); @@ -85,17 +84,16 @@ static ares_bool_t key_eq(const void *key1, const void *key2) return ARES_FALSE; } -ares__htable_vpvp_t * - ares__htable_vpvp_create(ares__htable_vpvp_key_free_t key_free, - ares__htable_vpvp_val_free_t val_free) +ares_htable_vpvp_t * + ares_htable_vpvp_create(ares_htable_vpvp_key_free_t key_free, + ares_htable_vpvp_val_free_t val_free) { - ares__htable_vpvp_t *htable = ares_malloc(sizeof(*htable)); + ares_htable_vpvp_t *htable = ares_malloc(sizeof(*htable)); if (htable == NULL) { goto fail; /* LCOV_EXCL_LINE: OutOfMemory */ } - htable->hash = - ares__htable_create(hash_func, bucket_key, bucket_free, key_eq); + htable->hash = ares_htable_create(hash_func, bucket_key, bucket_free, key_eq); if (htable->hash == NULL) { goto fail; /* LCOV_EXCL_LINE: OutOfMemory */ } @@ -108,17 +106,17 @@ ares__htable_vpvp_t * /* LCOV_EXCL_START: OutOfMemory */ fail: if (htable) { - ares__htable_destroy(htable->hash); + ares_htable_destroy(htable->hash); ares_free(htable); } return NULL; /* LCOV_EXCL_STOP */ } -ares_bool_t ares__htable_vpvp_insert(ares__htable_vpvp_t *htable, void *key, - void *val) +ares_bool_t ares_htable_vpvp_insert(ares_htable_vpvp_t *htable, void *key, + void *val) { - ares__htable_vpvp_bucket_t *bucket = NULL; + ares_htable_vpvp_bucket_t *bucket = NULL; if (htable == NULL) { goto fail; @@ -133,7 +131,7 @@ ares_bool_t ares__htable_vpvp_insert(ares__htable_vpvp_t *htable, void *key, bucket->key = key; bucket->val = val; - if (!ares__htable_insert(htable->hash, bucket)) { + if (!ares_htable_insert(htable->hash, bucket)) { goto fail; } @@ -146,10 +144,10 @@ fail: return ARES_FALSE; } -ares_bool_t ares__htable_vpvp_get(const ares__htable_vpvp_t *htable, - const void *key, void **val) +ares_bool_t ares_htable_vpvp_get(const ares_htable_vpvp_t *htable, + const void *key, void **val) { - ares__htable_vpvp_bucket_t *bucket = NULL; + ares_htable_vpvp_bucket_t *bucket = NULL; if (val) { *val = NULL; @@ -159,7 +157,7 @@ ares_bool_t ares__htable_vpvp_get(const ares__htable_vpvp_t *htable, return ARES_FALSE; } - bucket = ares__htable_get(htable->hash, key); + bucket = ares_htable_get(htable->hash, key); if (bucket == NULL) { return ARES_FALSE; } @@ -170,28 +168,27 @@ ares_bool_t ares__htable_vpvp_get(const ares__htable_vpvp_t *htable, return ARES_TRUE; } -void *ares__htable_vpvp_get_direct(const ares__htable_vpvp_t *htable, - const void *key) +void *ares_htable_vpvp_get_direct(const ares_htable_vpvp_t *htable, + const void *key) { void *val = NULL; - ares__htable_vpvp_get(htable, key, &val); + ares_htable_vpvp_get(htable, key, &val); return val; } -ares_bool_t ares__htable_vpvp_remove(ares__htable_vpvp_t *htable, - const void *key) +ares_bool_t ares_htable_vpvp_remove(ares_htable_vpvp_t *htable, const void *key) { if (htable == NULL) { return ARES_FALSE; } - return ares__htable_remove(htable->hash, key); + return ares_htable_remove(htable->hash, key); } -size_t ares__htable_vpvp_num_keys(const ares__htable_vpvp_t *htable) +size_t ares_htable_vpvp_num_keys(const ares_htable_vpvp_t *htable) { if (htable == NULL) { return 0; } - return ares__htable_num_keys(htable->hash); + return ares_htable_num_keys(htable->hash); } diff --git a/contrib/libs/c-ares/src/lib/dsa/ares__llist.c b/contrib/libs/c-ares/src/lib/dsa/ares_llist.c index 96936c1abe..6bd7de269a 100644 --- a/contrib/libs/c-ares/src/lib/dsa/ares__llist.c +++ b/contrib/libs/c-ares/src/lib/dsa/ares_llist.c @@ -24,25 +24,25 @@ * SPDX-License-Identifier: MIT */ #include "ares_private.h" -#include "ares__llist.h" +#include "ares_llist.h" -struct ares__llist { - ares__llist_node_t *head; - ares__llist_node_t *tail; - ares__llist_destructor_t destruct; - size_t cnt; +struct ares_llist { + ares_llist_node_t *head; + ares_llist_node_t *tail; + ares_llist_destructor_t destruct; + size_t cnt; }; -struct ares__llist_node { - void *data; - ares__llist_node_t *prev; - ares__llist_node_t *next; - ares__llist_t *parent; +struct ares_llist_node { + void *data; + ares_llist_node_t *prev; + ares_llist_node_t *next; + ares_llist_t *parent; }; -ares__llist_t *ares__llist_create(ares__llist_destructor_t destruct) +ares_llist_t *ares_llist_create(ares_llist_destructor_t destruct) { - ares__llist_t *list = ares_malloc_zero(sizeof(*list)); + ares_llist_t *list = ares_malloc_zero(sizeof(*list)); if (list == NULL) { return NULL; @@ -53,8 +53,8 @@ ares__llist_t *ares__llist_create(ares__llist_destructor_t destruct) return list; } -void ares__llist_replace_destructor(ares__llist_t *list, - ares__llist_destructor_t destruct) +void ares_llist_replace_destructor(ares_llist_t *list, + ares_llist_destructor_t destruct) { if (list == NULL) { return; @@ -67,12 +67,11 @@ typedef enum { ARES__LLIST_INSERT_HEAD, ARES__LLIST_INSERT_TAIL, ARES__LLIST_INSERT_BEFORE -} ares__llist_insert_type_t; +} ares_llist_insert_type_t; -static void ares__llist_attach_at(ares__llist_t *list, - ares__llist_insert_type_t type, - ares__llist_node_t *at, - ares__llist_node_t *node) +static void ares_llist_attach_at(ares_llist_t *list, + ares_llist_insert_type_t type, + ares_llist_node_t *at, ares_llist_node_t *node) { if (list == NULL || node == NULL) { return; /* LCOV_EXCL_LINE: DefensiveCoding */ @@ -117,12 +116,11 @@ static void ares__llist_attach_at(ares__llist_t *list, list->cnt++; } -static ares__llist_node_t *ares__llist_insert_at(ares__llist_t *list, - ares__llist_insert_type_t type, - ares__llist_node_t *at, - void *val) +static ares_llist_node_t *ares_llist_insert_at(ares_llist_t *list, + ares_llist_insert_type_t type, + ares_llist_node_t *at, void *val) { - ares__llist_node_t *node = NULL; + ares_llist_node_t *node = NULL; if (list == NULL || val == NULL) { return NULL; /* LCOV_EXCL_LINE: DefensiveCoding */ @@ -135,48 +133,46 @@ static ares__llist_node_t *ares__llist_insert_at(ares__llist_t *list, } node->data = val; - ares__llist_attach_at(list, type, at, node); + ares_llist_attach_at(list, type, at, node); return node; } -ares__llist_node_t *ares__llist_insert_first(ares__llist_t *list, void *val) +ares_llist_node_t *ares_llist_insert_first(ares_llist_t *list, void *val) { - return ares__llist_insert_at(list, ARES__LLIST_INSERT_HEAD, NULL, val); + return ares_llist_insert_at(list, ARES__LLIST_INSERT_HEAD, NULL, val); } -ares__llist_node_t *ares__llist_insert_last(ares__llist_t *list, void *val) +ares_llist_node_t *ares_llist_insert_last(ares_llist_t *list, void *val) { - return ares__llist_insert_at(list, ARES__LLIST_INSERT_TAIL, NULL, val); + return ares_llist_insert_at(list, ARES__LLIST_INSERT_TAIL, NULL, val); } -ares__llist_node_t *ares__llist_insert_before(ares__llist_node_t *node, - void *val) +ares_llist_node_t *ares_llist_insert_before(ares_llist_node_t *node, void *val) { if (node == NULL) { return NULL; } - return ares__llist_insert_at(node->parent, ARES__LLIST_INSERT_BEFORE, node, - val); + return ares_llist_insert_at(node->parent, ARES__LLIST_INSERT_BEFORE, node, + val); } -ares__llist_node_t *ares__llist_insert_after(ares__llist_node_t *node, - void *val) +ares_llist_node_t *ares_llist_insert_after(ares_llist_node_t *node, void *val) { if (node == NULL) { return NULL; } if (node->next == NULL) { - return ares__llist_insert_last(node->parent, val); + return ares_llist_insert_last(node->parent, val); } - return ares__llist_insert_at(node->parent, ARES__LLIST_INSERT_BEFORE, - node->next, val); + return ares_llist_insert_at(node->parent, ARES__LLIST_INSERT_BEFORE, + node->next, val); } -ares__llist_node_t *ares__llist_node_first(ares__llist_t *list) +ares_llist_node_t *ares_llist_node_first(ares_llist_t *list) { if (list == NULL) { return NULL; @@ -184,10 +180,10 @@ ares__llist_node_t *ares__llist_node_first(ares__llist_t *list) return list->head; } -ares__llist_node_t *ares__llist_node_idx(ares__llist_t *list, size_t idx) +ares_llist_node_t *ares_llist_node_idx(ares_llist_t *list, size_t idx) { - ares__llist_node_t *node; - size_t cnt; + ares_llist_node_t *node; + size_t cnt; if (list == NULL) { return NULL; @@ -204,7 +200,7 @@ ares__llist_node_t *ares__llist_node_idx(ares__llist_t *list, size_t idx) return node; } -ares__llist_node_t *ares__llist_node_last(ares__llist_t *list) +ares_llist_node_t *ares_llist_node_last(ares_llist_t *list) { if (list == NULL) { return NULL; @@ -212,7 +208,7 @@ ares__llist_node_t *ares__llist_node_last(ares__llist_t *list) return list->tail; } -ares__llist_node_t *ares__llist_node_next(ares__llist_node_t *node) +ares_llist_node_t *ares_llist_node_next(ares_llist_node_t *node) { if (node == NULL) { return NULL; @@ -220,7 +216,7 @@ ares__llist_node_t *ares__llist_node_next(ares__llist_node_t *node) return node->next; } -ares__llist_node_t *ares__llist_node_prev(ares__llist_node_t *node) +ares_llist_node_t *ares_llist_node_prev(ares_llist_node_t *node) { if (node == NULL) { return NULL; @@ -228,7 +224,7 @@ ares__llist_node_t *ares__llist_node_prev(ares__llist_node_t *node) return node->prev; } -void *ares__llist_node_val(ares__llist_node_t *node) +void *ares_llist_node_val(ares_llist_node_t *node) { if (node == NULL) { return NULL; @@ -237,7 +233,7 @@ void *ares__llist_node_val(ares__llist_node_t *node) return node->data; } -size_t ares__llist_len(const ares__llist_t *list) +size_t ares_llist_len(const ares_llist_t *list) { if (list == NULL) { return 0; @@ -245,7 +241,7 @@ size_t ares__llist_len(const ares__llist_t *list) return list->cnt; } -ares__llist_t *ares__llist_node_parent(ares__llist_node_t *node) +ares_llist_t *ares_llist_node_parent(ares_llist_node_t *node) { if (node == NULL) { return NULL; @@ -253,19 +249,19 @@ ares__llist_t *ares__llist_node_parent(ares__llist_node_t *node) return node->parent; } -void *ares__llist_first_val(ares__llist_t *list) +void *ares_llist_first_val(ares_llist_t *list) { - return ares__llist_node_val(ares__llist_node_first(list)); + return ares_llist_node_val(ares_llist_node_first(list)); } -void *ares__llist_last_val(ares__llist_t *list) +void *ares_llist_last_val(ares_llist_t *list) { - return ares__llist_node_val(ares__llist_node_last(list)); + return ares_llist_node_val(ares_llist_node_last(list)); } -static void ares__llist_node_detach(ares__llist_node_t *node) +static void ares_llist_node_detach(ares_llist_node_t *node) { - ares__llist_t *list; + ares_llist_t *list; if (node == NULL) { return; /* LCOV_EXCL_LINE: DefensiveCoding */ @@ -293,7 +289,7 @@ static void ares__llist_node_detach(ares__llist_node_t *node) list->cnt--; } -void *ares__llist_node_claim(ares__llist_node_t *node) +void *ares_llist_node_claim(ares_llist_node_t *node) { void *val; @@ -302,16 +298,16 @@ void *ares__llist_node_claim(ares__llist_node_t *node) } val = node->data; - ares__llist_node_detach(node); + ares_llist_node_detach(node); ares_free(node); return val; } -void ares__llist_node_destroy(ares__llist_node_t *node) +void ares_llist_node_destroy(ares_llist_node_t *node) { - ares__llist_destructor_t destruct; - void *val; + ares_llist_destructor_t destruct; + void *val; if (node == NULL) { return; @@ -319,15 +315,15 @@ void ares__llist_node_destroy(ares__llist_node_t *node) destruct = node->parent->destruct; - val = ares__llist_node_claim(node); + val = ares_llist_node_claim(node); if (val != NULL && destruct != NULL) { destruct(val); } } -void ares__llist_node_replace(ares__llist_node_t *node, void *val) +void ares_llist_node_replace(ares_llist_node_t *node, void *val) { - ares__llist_destructor_t destruct; + ares_llist_destructor_t destruct; if (node == NULL) { return; @@ -341,46 +337,46 @@ void ares__llist_node_replace(ares__llist_node_t *node, void *val) node->data = val; } -void ares__llist_clear(ares__llist_t *list) +void ares_llist_clear(ares_llist_t *list) { - ares__llist_node_t *node; + ares_llist_node_t *node; if (list == NULL) { return; } - while ((node = ares__llist_node_first(list)) != NULL) { - ares__llist_node_destroy(node); + while ((node = ares_llist_node_first(list)) != NULL) { + ares_llist_node_destroy(node); } } -void ares__llist_destroy(ares__llist_t *list) +void ares_llist_destroy(ares_llist_t *list) { if (list == NULL) { return; } - ares__llist_clear(list); + ares_llist_clear(list); ares_free(list); } -void ares__llist_node_move_parent_last(ares__llist_node_t *node, - ares__llist_t *new_parent) +void ares_llist_node_mvparent_last(ares_llist_node_t *node, + ares_llist_t *new_parent) { if (node == NULL || new_parent == NULL) { return; /* LCOV_EXCL_LINE: DefensiveCoding */ } - ares__llist_node_detach(node); - ares__llist_attach_at(new_parent, ARES__LLIST_INSERT_TAIL, NULL, node); + ares_llist_node_detach(node); + ares_llist_attach_at(new_parent, ARES__LLIST_INSERT_TAIL, NULL, node); } -void ares__llist_node_move_parent_first(ares__llist_node_t *node, - ares__llist_t *new_parent) +void ares_llist_node_mvparent_first(ares_llist_node_t *node, + ares_llist_t *new_parent) { if (node == NULL || new_parent == NULL) { return; /* LCOV_EXCL_LINE: DefensiveCoding */ } - ares__llist_node_detach(node); - ares__llist_attach_at(new_parent, ARES__LLIST_INSERT_HEAD, NULL, node); + ares_llist_node_detach(node); + ares_llist_attach_at(new_parent, ARES__LLIST_INSERT_HEAD, NULL, node); } diff --git a/contrib/libs/c-ares/src/lib/dsa/ares__slist.c b/contrib/libs/c-ares/src/lib/dsa/ares_slist.c index f0e3f8b14a..7e68347994 100644 --- a/contrib/libs/c-ares/src/lib/dsa/ares__slist.c +++ b/contrib/libs/c-ares/src/lib/dsa/ares_slist.c @@ -24,39 +24,39 @@ * SPDX-License-Identifier: MIT */ #include "ares_private.h" -#include "ares__slist.h" +#include "ares_slist.h" /* SkipList implementation */ #define ARES__SLIST_START_LEVELS 4 -struct ares__slist { - ares_rand_state *rand_state; - unsigned char rand_data[8]; - size_t rand_bits; +struct ares_slist { + ares_rand_state *rand_state; + unsigned char rand_data[8]; + size_t rand_bits; - ares__slist_node_t **head; - size_t levels; - ares__slist_node_t *tail; + ares_slist_node_t **head; + size_t levels; + ares_slist_node_t *tail; - ares__slist_cmp_t cmp; - ares__slist_destructor_t destruct; - size_t cnt; + ares_slist_cmp_t cmp; + ares_slist_destructor_t destruct; + size_t cnt; }; -struct ares__slist_node { - void *data; - ares__slist_node_t **prev; - ares__slist_node_t **next; - size_t levels; - ares__slist_t *parent; +struct ares_slist_node { + void *data; + ares_slist_node_t **prev; + ares_slist_node_t **next; + size_t levels; + ares_slist_t *parent; }; -ares__slist_t *ares__slist_create(ares_rand_state *rand_state, - ares__slist_cmp_t cmp, - ares__slist_destructor_t destruct) +ares_slist_t *ares_slist_create(ares_rand_state *rand_state, + ares_slist_cmp_t cmp, + ares_slist_destructor_t destruct) { - ares__slist_t *list; + ares_slist_t *list; if (rand_state == NULL || cmp == NULL) { return NULL; @@ -82,18 +82,17 @@ ares__slist_t *ares__slist_create(ares_rand_state *rand_state, return list; } -static ares_bool_t ares__slist_coin_flip(ares__slist_t *list) +static ares_bool_t ares_slist_coin_flip(ares_slist_t *list) { size_t total_bits = sizeof(list->rand_data) * 8; size_t bit; /* Refill random data used for coin flips. We pull this in 8 byte chunks. - * ares__rand_bytes() has some built-in caching of its own so we don't need + * ares_rand_bytes() has some built-in caching of its own so we don't need * to be excessive in caching ourselves. Prefer to require less memory per * skiplist */ if (list->rand_bits == 0) { - ares__rand_bytes(list->rand_state, list->rand_data, - sizeof(list->rand_data)); + ares_rand_bytes(list->rand_state, list->rand_data, sizeof(list->rand_data)); list->rand_bits = total_bits; } @@ -103,8 +102,8 @@ static ares_bool_t ares__slist_coin_flip(ares__slist_t *list) return (list->rand_data[bit / 8] & (1 << (bit % 8))) ? ARES_TRUE : ARES_FALSE; } -void ares__slist_replace_destructor(ares__slist_t *list, - ares__slist_destructor_t destruct) +void ares_slist_replace_destructor(ares_slist_t *list, + ares_slist_destructor_t destruct) { if (list == NULL) { return; @@ -113,14 +112,14 @@ void ares__slist_replace_destructor(ares__slist_t *list, list->destruct = destruct; } -static size_t ares__slist_max_level(const ares__slist_t *list) +static size_t ares_slist_max_level(const ares_slist_t *list) { size_t max_level = 0; if (list->cnt + 1 <= (1 << ARES__SLIST_START_LEVELS)) { max_level = ARES__SLIST_START_LEVELS; } else { - max_level = ares__log2(ares__round_up_pow2(list->cnt + 1)); + max_level = ares_log2(ares_round_up_pow2(list->cnt + 1)); } if (list->levels > max_level) { @@ -130,21 +129,21 @@ static size_t ares__slist_max_level(const ares__slist_t *list) return max_level; } -static size_t ares__slist_calc_level(ares__slist_t *list) +static size_t ares_slist_calc_level(ares_slist_t *list) { - size_t max_level = ares__slist_max_level(list); + size_t max_level = ares_slist_max_level(list); size_t level; - for (level = 1; ares__slist_coin_flip(list) && level < max_level; level++) + for (level = 1; ares_slist_coin_flip(list) && level < max_level; level++) ; return level; } -static void ares__slist_node_push(ares__slist_t *list, ares__slist_node_t *node) +static void ares_slist_node_push(ares_slist_t *list, ares_slist_node_t *node) { - size_t i; - ares__slist_node_t *left = NULL; + size_t i; + ares_slist_node_t *left = NULL; /* Scan from highest level in the slist, even if we're not using that number * of levels for this entry as this is what makes it O(log n) */ @@ -193,9 +192,9 @@ static void ares__slist_node_push(ares__slist_t *list, ares__slist_node_t *node) } } -ares__slist_node_t *ares__slist_insert(ares__slist_t *list, void *val) +ares_slist_node_t *ares_slist_insert(ares_slist_t *list, void *val) { - ares__slist_node_t *node = NULL; + ares_slist_node_t *node = NULL; if (list == NULL || val == NULL) { return NULL; @@ -211,7 +210,7 @@ ares__slist_node_t *ares__slist_insert(ares__slist_t *list, void *val) node->parent = list; /* Randomly determine the number of levels we want to use */ - node->levels = ares__slist_calc_level(list); + node->levels = ares_slist_calc_level(list); /* Allocate array of next and prev nodes for linking each level */ node->next = ares_malloc_zero(sizeof(*node->next) * node->levels); @@ -238,7 +237,7 @@ ares__slist_node_t *ares__slist_insert(ares__slist_t *list, void *val) list->levels = node->levels; } - ares__slist_node_push(list, node); + ares_slist_node_push(list, node); list->cnt++; @@ -255,10 +254,10 @@ fail: /* LCOV_EXCL_STOP */ } -static void ares__slist_node_pop(ares__slist_node_t *node) +static void ares_slist_node_pop(ares_slist_node_t *node) { - ares__slist_t *list = node->parent; - size_t i; + ares_slist_t *list = node->parent; + size_t i; /* relink each node at each level */ for (i = node->levels; i-- > 0;) { @@ -281,10 +280,10 @@ static void ares__slist_node_pop(ares__slist_node_t *node) memset(node->prev, 0, sizeof(*node->prev) * node->levels); } -void *ares__slist_node_claim(ares__slist_node_t *node) +void *ares_slist_node_claim(ares_slist_node_t *node) { - ares__slist_t *list; - void *val; + ares_slist_t *list; + void *val; if (node == NULL) { return NULL; @@ -293,7 +292,7 @@ void *ares__slist_node_claim(ares__slist_node_t *node) list = node->parent; val = node->data; - ares__slist_node_pop(node); + ares_slist_node_pop(node); ares_free(node->next); ares_free(node->prev); @@ -304,9 +303,9 @@ void *ares__slist_node_claim(ares__slist_node_t *node) return val; } -void ares__slist_node_reinsert(ares__slist_node_t *node) +void ares_slist_node_reinsert(ares_slist_node_t *node) { - ares__slist_t *list; + ares_slist_t *list; if (node == NULL) { return; @@ -314,15 +313,16 @@ void ares__slist_node_reinsert(ares__slist_node_t *node) list = node->parent; - ares__slist_node_pop(node); - ares__slist_node_push(list, node); + ares_slist_node_pop(node); + ares_slist_node_push(list, node); } -ares__slist_node_t *ares__slist_node_find(ares__slist_t *list, const void *val) +ares_slist_node_t *ares_slist_node_find(const ares_slist_t *list, + const void *val) { - size_t i; - ares__slist_node_t *node = NULL; - int rv = -1; + size_t i; + ares_slist_node_t *node = NULL; + int rv = -1; if (list == NULL || val == NULL) { return NULL; @@ -377,7 +377,7 @@ ares__slist_node_t *ares__slist_node_find(ares__slist_t *list, const void *val) return node; } -ares__slist_node_t *ares__slist_node_first(ares__slist_t *list) +ares_slist_node_t *ares_slist_node_first(const ares_slist_t *list) { if (list == NULL) { return NULL; @@ -386,7 +386,7 @@ ares__slist_node_t *ares__slist_node_first(ares__slist_t *list) return list->head[0]; } -ares__slist_node_t *ares__slist_node_last(ares__slist_t *list) +ares_slist_node_t *ares_slist_node_last(const ares_slist_t *list) { if (list == NULL) { return NULL; @@ -394,7 +394,7 @@ ares__slist_node_t *ares__slist_node_last(ares__slist_t *list) return list->tail; } -ares__slist_node_t *ares__slist_node_next(ares__slist_node_t *node) +ares_slist_node_t *ares_slist_node_next(const ares_slist_node_t *node) { if (node == NULL) { return NULL; @@ -402,7 +402,7 @@ ares__slist_node_t *ares__slist_node_next(ares__slist_node_t *node) return node->next[0]; } -ares__slist_node_t *ares__slist_node_prev(ares__slist_node_t *node) +ares_slist_node_t *ares_slist_node_prev(const ares_slist_node_t *node) { if (node == NULL) { return NULL; @@ -410,7 +410,7 @@ ares__slist_node_t *ares__slist_node_prev(ares__slist_node_t *node) return node->prev[0]; } -void *ares__slist_node_val(ares__slist_node_t *node) +void *ares_slist_node_val(ares_slist_node_t *node) { if (node == NULL) { return NULL; @@ -419,7 +419,7 @@ void *ares__slist_node_val(ares__slist_node_t *node) return node->data; } -size_t ares__slist_len(const ares__slist_t *list) +size_t ares_slist_len(const ares_slist_t *list) { if (list == NULL) { return 0; @@ -427,7 +427,7 @@ size_t ares__slist_len(const ares__slist_t *list) return list->cnt; } -ares__slist_t *ares__slist_node_parent(ares__slist_node_t *node) +ares_slist_t *ares_slist_node_parent(ares_slist_node_t *node) { if (node == NULL) { return NULL; @@ -435,43 +435,43 @@ ares__slist_t *ares__slist_node_parent(ares__slist_node_t *node) return node->parent; } -void *ares__slist_first_val(ares__slist_t *list) +void *ares_slist_first_val(const ares_slist_t *list) { - return ares__slist_node_val(ares__slist_node_first(list)); + return ares_slist_node_val(ares_slist_node_first(list)); } -void *ares__slist_last_val(ares__slist_t *list) +void *ares_slist_last_val(const ares_slist_t *list) { - return ares__slist_node_val(ares__slist_node_last(list)); + return ares_slist_node_val(ares_slist_node_last(list)); } -void ares__slist_node_destroy(ares__slist_node_t *node) +void ares_slist_node_destroy(ares_slist_node_t *node) { - ares__slist_destructor_t destruct; - void *val; + ares_slist_destructor_t destruct; + void *val; if (node == NULL) { return; } destruct = node->parent->destruct; - val = ares__slist_node_claim(node); + val = ares_slist_node_claim(node); if (val != NULL && destruct != NULL) { destruct(val); } } -void ares__slist_destroy(ares__slist_t *list) +void ares_slist_destroy(ares_slist_t *list) { - ares__slist_node_t *node; + ares_slist_node_t *node; if (list == NULL) { return; } - while ((node = ares__slist_node_first(list)) != NULL) { - ares__slist_node_destroy(node); + while ((node = ares_slist_node_first(list)) != NULL) { + ares_slist_node_destroy(node); } ares_free(list->head); diff --git a/contrib/libs/c-ares/src/lib/dsa/ares__slist.h b/contrib/libs/c-ares/src/lib/dsa/ares_slist.h index 26af88fa78..a89c2652f2 100644 --- a/contrib/libs/c-ares/src/lib/dsa/ares__slist.h +++ b/contrib/libs/c-ares/src/lib/dsa/ares_slist.h @@ -27,7 +27,7 @@ #define __ARES__SLIST_H -/*! \addtogroup ares__slist SkipList Data Structure +/*! \addtogroup ares_slist SkipList Data Structure * * This data structure is known as a Skip List, which in essence is a sorted * linked list with multiple levels of linkage to gain some algorithmic @@ -49,21 +49,21 @@ * * @{ */ -struct ares__slist; +struct ares_slist; /*! SkipList Object, opaque */ -typedef struct ares__slist ares__slist_t; +typedef struct ares_slist ares_slist_t; -struct ares__slist_node; +struct ares_slist_node; /*! SkipList Node Object, opaque */ -typedef struct ares__slist_node ares__slist_node_t; +typedef struct ares_slist_node ares_slist_node_t; /*! SkipList Node Value destructor callback * * \param[in] data User-defined data to destroy */ -typedef void (*ares__slist_destructor_t)(void *data); +typedef void (*ares_slist_destructor_t)(void *data); /*! SkipList comparison function * @@ -71,7 +71,7 @@ typedef void (*ares__slist_destructor_t)(void *data); * \param[in] data2 Second user-defined data object * \return < 0 if data1 < data1, > 0 if data1 > data2, 0 if data1 == data2 */ -typedef int (*ares__slist_cmp_t)(const void *data1, const void *data2); +typedef int (*ares_slist_cmp_t)(const void *data1, const void *data2); /*! Create SkipList * @@ -80,17 +80,17 @@ typedef int (*ares__slist_cmp_t)(const void *data1, const void *data2); * \param[in] destruct SkipList Node Value Destructor. Optional, use NULL. * \return Initialized SkipList Object or NULL on misuse or ENOMEM */ -ares__slist_t *ares__slist_create(ares_rand_state *rand_state, - ares__slist_cmp_t cmp, - ares__slist_destructor_t destruct); +ares_slist_t *ares_slist_create(ares_rand_state *rand_state, + ares_slist_cmp_t cmp, + ares_slist_destructor_t destruct); /*! Replace SkipList Node Value Destructor * * \param[in] list Initialized SkipList Object * \param[in] destruct Replacement destructor. May be NULL. */ -void ares__slist_replace_destructor(ares__slist_t *list, - ares__slist_destructor_t destruct); +void ares_slist_replace_destructor(ares_slist_t *list, + ares_slist_destructor_t destruct); /*! Insert Value into SkipList * @@ -99,35 +99,35 @@ void ares__slist_replace_destructor(ares__slist_t *list * and will have destructor called. * \return SkipList Node Object or NULL on misuse or ENOMEM */ -ares__slist_node_t *ares__slist_insert(ares__slist_t *list, void *val); +ares_slist_node_t *ares_slist_insert(ares_slist_t *list, void *val); /*! Fetch first node in SkipList * * \param[in] list Initialized SkipList Object * \return SkipList Node Object or NULL if none */ -ares__slist_node_t *ares__slist_node_first(ares__slist_t *list); +ares_slist_node_t *ares_slist_node_first(const ares_slist_t *list); /*! Fetch last node in SkipList * * \param[in] list Initialized SkipList Object * \return SkipList Node Object or NULL if none */ -ares__slist_node_t *ares__slist_node_last(ares__slist_t *list); +ares_slist_node_t *ares_slist_node_last(const ares_slist_t *list); /*! Fetch next node in SkipList * * \param[in] node SkipList Node Object * \return SkipList Node Object or NULL if none */ -ares__slist_node_t *ares__slist_node_next(ares__slist_node_t *node); +ares_slist_node_t *ares_slist_node_next(const ares_slist_node_t *node); /*! Fetch previous node in SkipList * * \param[in] node SkipList Node Object * \return SkipList Node Object or NULL if none */ -ares__slist_node_t *ares__slist_node_prev(ares__slist_node_t *node); +ares_slist_node_t *ares_slist_node_prev(const ares_slist_node_t *node); /*! Fetch SkipList Node Object by Value * @@ -135,7 +135,8 @@ ares__slist_node_t *ares__slist_node_prev(ares__slist_node_t *node); * \param[in] val Object to use for comparison * \return SkipList Node Object or NULL if not found */ -ares__slist_node_t *ares__slist_node_find(ares__slist_t *list, const void *val); +ares_slist_node_t *ares_slist_node_find(const ares_slist_t *list, + const void *val); /*! Fetch Node Value @@ -143,42 +144,42 @@ ares__slist_node_t *ares__slist_node_find(ares__slist_t *list, const void *val); * \param[in] node SkipList Node Object * \return user defined node value */ -void *ares__slist_node_val(ares__slist_node_t *node); +void *ares_slist_node_val(ares_slist_node_t *node); /*! Fetch number of entries in SkipList Object * * \param[in] list Initialized SkipList Object * \return number of entries */ -size_t ares__slist_len(const ares__slist_t *list); +size_t ares_slist_len(const ares_slist_t *list); /*! Fetch SkipList Object from SkipList Node * * \param[in] node SkipList Node Object * \return SkipList Object */ -ares__slist_t *ares__slist_node_parent(ares__slist_node_t *node); +ares_slist_t *ares_slist_node_parent(ares_slist_node_t *node); /*! Fetch first Node Value in SkipList * * \param[in] list Initialized SkipList Object * \return user defined node value or NULL if none */ -void *ares__slist_first_val(ares__slist_t *list); +void *ares_slist_first_val(const ares_slist_t *list); /*! Fetch last Node Value in SkipList * * \param[in] list Initialized SkipList Object * \return user defined node value or NULL if none */ -void *ares__slist_last_val(ares__slist_t *list); +void *ares_slist_last_val(const ares_slist_t *list); /*! Take back ownership of Node Value in SkipList, remove from SkipList. * * \param[in] node SkipList Node Object * \return user defined node value */ -void *ares__slist_node_claim(ares__slist_node_t *node); +void *ares_slist_node_claim(ares_slist_node_t *node); /*! The internals of the node have changed, thus its position in the sorted * list is no longer valid. This function will remove it and re-add it to @@ -187,19 +188,19 @@ void *ares__slist_node_claim(ares__slist_node_t *node); * * \param[in] node SkipList Node Object */ -void ares__slist_node_reinsert(ares__slist_node_t *node); +void ares_slist_node_reinsert(ares_slist_node_t *node); /*! Remove Node from SkipList, calling destructor for Node Value. * * \param[in] node SkipList Node Object */ -void ares__slist_node_destroy(ares__slist_node_t *node); +void ares_slist_node_destroy(ares_slist_node_t *node); /*! Destroy SkipList Object. If there are any nodes, they will be destroyed. * * \param[in] list Initialized SkipList Object */ -void ares__slist_destroy(ares__slist_t *list); +void ares_slist_destroy(ares_slist_t *list); /*! @} */ |