Line data    Source code

       1           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           0 : struct sys_hashmap_oa_lp_data {
      28           0 :         void *buckets;
      29           0 :         size_t n_buckets;
      30           0 :         size_t size;
      31           0 :         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           1 : #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           1 : #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           1 : #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           1 : #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           0 : 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_ */