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_ */