1 /* 2 * Copyright (c) 2022 Meta 3 * 4 * SPDX-License-Identifier: Apache-2.0 5 */ 6 7 /** 8 * @file 9 * @ingroup hashmap_implementations 10 * @brief Open-Addressing / Linear Probe Hashmap Implementation 11 * 12 * @note Enable with @kconfig{CONFIG_SYS_HASH_MAP_OA_LP} 13 */ 14 15 #ifndef ZEPHYR_INCLUDE_SYS_HASH_MAP_OA_LP_H_ 16 #define ZEPHYR_INCLUDE_SYS_HASH_MAP_OA_LP_H_ 17 18 #include <stddef.h> 19 20 #include <zephyr/sys/hash_function.h> 21 #include <zephyr/sys/hash_map_api.h> 22 23 #ifdef __cplusplus 24 extern "C" { 25 #endif 26 27 struct sys_hashmap_oa_lp_data { 28 void *buckets; 29 size_t n_buckets; 30 size_t size; 31 size_t n_tombstones; 32 }; 33 34 /** 35 * @brief Declare a Open Addressing Linear Probe Hashmap (advanced) 36 * 37 * Declare a Open Addressing Linear Probe Hashmap with control over advanced parameters. 38 * 39 * @note The allocator @p _alloc is used for allocating internal Hashmap 40 * entries and does not interact with any user-provided keys or values. 41 * 42 * @param _name Name of the Hashmap. 43 * @param _hash_func Hash function pointer of type @ref sys_hash_func32_t. 44 * @param _alloc_func Allocator function pointer of type @ref sys_hashmap_allocator_t. 45 * @param ... Variant-specific details for @ref sys_hashmap_config. 46 */ 47 #define SYS_HASHMAP_OA_LP_DEFINE_ADVANCED(_name, _hash_func, _alloc_func, ...) \ 48 SYS_HASHMAP_DEFINE_ADVANCED(_name, &sys_hashmap_oa_lp_api, sys_hashmap_config, \ 49 sys_hashmap_oa_lp_data, _hash_func, _alloc_func, __VA_ARGS__) 50 51 /** 52 * @brief Declare a Open Addressing Linear Probe Hashmap (advanced) 53 * 54 * Declare a Open Addressing Linear Probe Hashmap with control over advanced parameters. 55 * 56 * @note The allocator @p _alloc is used for allocating internal Hashmap 57 * entries and does not interact with any user-provided keys or values. 58 * 59 * @param _name Name of the Hashmap. 60 * @param _hash_func Hash function pointer of type @ref sys_hash_func32_t. 61 * @param _alloc_func Allocator function pointer of type @ref sys_hashmap_allocator_t. 62 * @param ... Details for @ref sys_hashmap_config. 63 */ 64 #define SYS_HASHMAP_OA_LP_DEFINE_STATIC_ADVANCED(_name, _hash_func, _alloc_func, ...) \ 65 SYS_HASHMAP_DEFINE_STATIC_ADVANCED(_name, &sys_hashmap_oa_lp_api, sys_hashmap_config, \ 66 sys_hashmap_oa_lp_data, _hash_func, _alloc_func, \ 67 __VA_ARGS__) 68 69 /** 70 * @brief Declare a Open Addressing Linear Probe Hashmap statically 71 * 72 * Declare a Open Addressing Linear Probe Hashmap statically with default parameters. 73 * 74 * @param _name Name of the Hashmap. 75 */ 76 #define SYS_HASHMAP_OA_LP_DEFINE_STATIC(_name) \ 77 SYS_HASHMAP_OA_LP_DEFINE_STATIC_ADVANCED( \ 78 _name, sys_hash32, SYS_HASHMAP_DEFAULT_ALLOCATOR, \ 79 SYS_HASHMAP_CONFIG(SIZE_MAX, SYS_HASHMAP_DEFAULT_LOAD_FACTOR)) 80 81 /** 82 * @brief Declare a Open Addressing Linear Probe Hashmap 83 * 84 * Declare a Open Addressing Linear Probe Hashmap with default parameters. 85 * 86 * @param _name Name of the Hashmap. 87 */ 88 #define SYS_HASHMAP_OA_LP_DEFINE(_name) \ 89 SYS_HASHMAP_OA_LP_DEFINE_ADVANCED( \ 90 _name, sys_hash32, SYS_HASHMAP_DEFAULT_ALLOCATOR, \ 91 SYS_HASHMAP_CONFIG(SIZE_MAX, SYS_HASHMAP_DEFAULT_LOAD_FACTOR)) 92 93 #ifdef CONFIG_SYS_HASH_MAP_CHOICE_OA_LP 94 #define SYS_HASHMAP_DEFAULT_DEFINE(_name) SYS_HASHMAP_OA_LP_DEFINE(_name) 95 #define SYS_HASHMAP_DEFAULT_DEFINE_STATIC(_name) SYS_HASHMAP_OA_LP_DEFINE_STATIC(_name) 96 #define SYS_HASHMAP_DEFAULT_DEFINE_ADVANCED(_name, _hash_func, _alloc_func, ...) \ 97 SYS_HASHMAP_OA_LP_DEFINE_ADVANCED(_name, _hash_func, _alloc_func, __VA_ARGS__) 98 #define SYS_HASHMAP_DEFAULT_DEFINE_STATIC_ADVANCED(_name, _hash_func, _alloc_func, ...) \ 99 SYS_HASHMAP_OA_LP_DEFINE_STATIC_ADVANCED(_name, _hash_func, _alloc_func, __VA_ARGS__) 100 #endif 101 102 extern const struct sys_hashmap_api sys_hashmap_oa_lp_api; 103 104 #ifdef __cplusplus 105 } 106 #endif 107 108 #endif /* ZEPHYR_INCLUDE_SYS_HASH_MAP_OA_LP_H_ */ 109
