include/zephyr/sys/hash_map.h

/*
 * Copyright (c) 2022 Meta
 *
 * SPDX-License-Identifier: Apache-2.0
 */

/**
 * @file
 * @brief Hashmap (Hash Table) API
 *
 * Hashmaps (a.k.a Hash Tables) sacrifice space for speed. All operations
 * on a Hashmap (insert, delete, search) are O(1) complexity (on average).
 */

#ifndef ZEPHYR_INCLUDE_SYS_HASH_MAP_H_
#define ZEPHYR_INCLUDE_SYS_HASH_MAP_H_

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

#include <zephyr/kernel.h>
#include <zephyr/sys/hash_map_api.h>
#include <zephyr/sys/hash_map_cxx.h>
#include <zephyr/sys/hash_map_oa_lp.h>
#include <zephyr/sys/hash_map_sc.h>

#ifdef __cplusplus
extern "C" {
#endif

/**
 * @ingroup hashmap_apis
 * @{
 */

/**
 * @brief Declare a Hashmap (advanced)
 *
 * Declare a Hashmap with control over advanced parameters.
 *
 * @note The allocator @p _alloc is used for allocating internal Hashmap
 * entries and does not interact with any user-provided keys or values.
 *
 * @param _name Name of the Hashmap.
 * @param _api API pointer of type @ref sys_hashmap_api.
 * @param _config_type Variant of @ref sys_hashmap_config.
 * @param _data_type Variant of @ref sys_hashmap_data.
 * @param _hash_func Hash function pointer of type @ref sys_hash_func32_t.
 * @param _alloc_func Allocator function pointer of type @ref sys_hashmap_allocator_t.
 * @param ... Variant-specific details for @p _config_type.
 */
#define SYS_HASHMAP_DEFINE_ADVANCED(_name, _api, _config_type, _data_type, _hash_func,             \
				    _alloc_func, ...)                                              \
	const struct _config_type _name##_config = __VA_ARGS__;                                    \
	struct _data_type _name##_data;                                                            \
	struct sys_hashmap _name = {                                                               \
		.api = (const struct sys_hashmap_api *)(_api),                                     \
		.config = (const struct sys_hashmap_config *)&_name##_config,                      \
		.data = (struct sys_hashmap_data *)&_name##_data,                                  \
		.hash_func = (_hash_func),                                                         \
		.alloc_func = (_alloc_func),                                                       \
	}

/**
 * @brief Declare a Hashmap (advanced)
 *
 * Declare a Hashmap with control over advanced parameters.
 *
 * @note The allocator @p _alloc is used for allocating internal Hashmap
 * entries and does not interact with any user-provided keys or values.
 *
 * @param _name Name of the Hashmap.
 * @param _api API pointer of type @ref sys_hashmap_api.
 * @param _config_type Variant of @ref sys_hashmap_config.
 * @param _data_type Variant of @ref sys_hashmap_data.
 * @param _hash_func Hash function pointer of type @ref sys_hash_func32_t.
 * @param _alloc_func Allocator function pointer of type @ref sys_hashmap_allocator_t.
 * @param ... Variant-specific details for @p _config_type.
 */
#define SYS_HASHMAP_DEFINE_STATIC_ADVANCED(_name, _api, _config_type, _data_type, _hash_func,      \
					   _alloc_func, ...)                                       \
	static const struct _config_type _name##_config = __VA_ARGS__;                             \
	static struct _data_type _name##_data;                                                     \
	static struct sys_hashmap _name = {                                                        \
		.api = (const struct sys_hashmap_api *)(_api),                                     \
		.config = (const struct sys_hashmap_config *)&_name##_config,                      \
		.data = (struct sys_hashmap_data *)&_name##_data,                                  \
		.hash_func = (_hash_func),                                                         \
		.alloc_func = (_alloc_func),                                                       \
	}

/**
 * @brief Declare a Hashmap
 *
 * Declare a Hashmap with default parameters.
 *
 * @param _name Name of the Hashmap.
 */
#define SYS_HASHMAP_DEFINE(_name) SYS_HASHMAP_DEFAULT_DEFINE(_name)

/**
 * @brief Declare a Hashmap statically
 *
 * Declare a Hashmap statically with default parameters.
 *
 * @param _name Name of the Hashmap.
 */
#define SYS_HASHMAP_DEFINE_STATIC(_name) SYS_HASHMAP_DEFAULT_DEFINE_STATIC(_name)

/*
 * A safe wrapper for realloc(), invariant of which libc provides it.
 */
static inline void *sys_hashmap_default_allocator(void *ptr, size_t size)
{
	if (size == 0) {
		free(ptr);
		return NULL;
	}

	return realloc(ptr, size);
}

#define SYS_HASHMAP_DEFAULT_ALLOCATOR sys_hashmap_default_allocator

/** @brief The default Hashmap load factor (in hundredths) */
#define SYS_HASHMAP_DEFAULT_LOAD_FACTOR 75

/** @brief Generic Hashmap */
struct sys_hashmap {
	const struct sys_hashmap_api *api;
	const struct sys_hashmap_config *config;
	struct sys_hashmap_data *data;
	sys_hash_func32_t hash_func;
	sys_hashmap_allocator_t alloc_func;
};

/**
 * @brief Iterate over all values contained in a @ref sys_hashmap
 *
 * @param map Hashmap to iterate over
 * @param cb Callback to call for each entry
 * @param cookie User-specified variable
 */
static inline void sys_hashmap_foreach(const struct sys_hashmap *map, sys_hashmap_callback_t cb,
				       void *cookie)
{
	struct sys_hashmap_iterator it = {0};

	for (map->api->iter(map, &it); sys_hashmap_iterator_has_next(&it);) {
		it.next(&it);
		cb(it.key, it.value, cookie);
	}
}

/**
 * @brief Clear all entries contained in a @ref sys_hashmap
 *
 * @note If the values in a particular Hashmap are
 *
 * @param map Hashmap to clear
 * @param cb Callback to call for each entry
 * @param cookie User-specified variable
 */
static inline void sys_hashmap_clear(struct sys_hashmap *map, sys_hashmap_callback_t cb,
				     void *cookie)
{
	map->api->clear(map, cb, cookie);
}

/**
 * @brief Insert a new entry into a @ref sys_hashmap
 *
 * Insert a new @p key - @p value pair into @p map.
 *
 * @param map Hashmap to insert into
 * @param key Key to associate with @p value
 * @param value Value to associate with @p key
 * @param old_value Location to store the value previously associated with @p key or `NULL`
 * @retval 0 if @p value was inserted for an existing key, in which case @p old_value will contain
 * the previous value
 * @retval 1 if a new entry was inserted for the @p key - @p value pair
 * @retval -ENOMEM if memory allocation failed
 * @retval -ENOSPC if the size limit has been reached
 */
static inline int sys_hashmap_insert(struct sys_hashmap *map, uint64_t key, uint64_t value,
				     uint64_t *old_value)
{
	return map->api->insert(map, key, value, old_value);
}

/**
 * @brief Remove an entry from a @ref sys_hashmap
 *
 * Erase the entry associated with key @p key, if one exists.
 *
 * @param map Hashmap to remove from
 * @param key Key to remove from @p map
 * @param value Location to store a potential value associated with @p key or `NULL`
 *
 * @retval true if @p map was modified as a result of this operation.
 * @retval false if @p map does not contain a value associated with @p key.
 */
static inline bool sys_hashmap_remove(struct sys_hashmap *map, uint64_t key, uint64_t *value)
{
	return map->api->remove(map, key, value);
}

/**
 * @brief Get a value from a @ref sys_hashmap
 *
 * Look-up the @ref uint64_t associated with @p key, if one exists.
 *
 * @param map Hashmap to search through
 * @param key Key with which to search @p map
 * @param value Location to store a potential value associated with @p key or `NULL`
 *
 * @retval true if @p map contains a value associated with @p key.
 * @retval false if @p map does not contain a value associated with @p key.
 */
static inline bool sys_hashmap_get(const struct sys_hashmap *map, uint64_t key, uint64_t *value)
{
	return map->api->get(map, key, value);
}

/**
 * @brief Check if @p map contains a value associated with @p key
 *
 * @param map Hashmap to search through
 * @param key Key with which to search @p map
 *
 * @retval true if @p map contains a value associated with @p key.
 * @retval false if @p map does not contain a value associated with @p key.
 */
static inline bool sys_hashmap_contains_key(const struct sys_hashmap *map, uint64_t key)
{
	return sys_hashmap_get(map, key, NULL);
}

/**
 * @brief Query the number of entries contained within @p map
 *
 * @param map Hashmap to search through
 *
 * @return the number of entries contained within @p map.
 */
static inline size_t sys_hashmap_size(const struct sys_hashmap *map)
{
	return map->data->size;
}

/**
 * @brief Check if @p map is empty
 *
 * @param map Hashmap to query
 *
 * @retval true if @p map is empty.
 * @retval false if @p map is not empty.
 */
static inline bool sys_hashmap_is_empty(const struct sys_hashmap *map)
{
	return map->data->size == 0;
}

/**
 * @brief Query the load factor of @p map
 *
 * @note To convert the load factor to a floating-point value use
 * `sys_hash_load_factor(map) / 100.0f`.
 *
 * @param map Hashmap to query
 *
 * @return Load factor of @p map expressed in hundredths.
 */
static inline uint8_t sys_hashmap_load_factor(const struct sys_hashmap *map)
{
	if (map->data->n_buckets == 0) {
		return 0;
	}

	return (map->data->size * 100) / map->data->n_buckets;
}

/**
 * @brief Query the number of buckets used in @p map
 *
 * @param map Hashmap to query
 * @return Number of buckets used in @p map
 */
static inline size_t sys_hashmap_num_buckets(const struct sys_hashmap *map)
{
	return map->data->n_buckets;
}

/**
 * @brief Decide whether the Hashmap should be resized
 *
 * This is a simple opportunistic method that implementations
 * can choose to use. It will grow and shrink the Hashmap by a factor
 * of 2 when insertion / removal would exceed / fall into the specified
 * load factor.
 *
 * @note Users should call this prior to inserting a new key-value pair and after removing a
 * key-value pair.
 *
 * @note The number of reserved entries is implementation-defined, but it is only considered
 * as part of the load factor when growing the hash table.
 *
 * @param map Hashmap to examine
 * @param grow true if an entry is to be added. false if an entry has been removed
 * @param num_reserved the number of reserved entries
 * @param[out] new_num_buckets variable Hashmap size
 * @return true if the Hashmap should be rehashed
 * @return false if the Hashmap should not be rehashed
 */
static inline bool sys_hashmap_should_rehash(const struct sys_hashmap *map, bool grow,
					     size_t num_reserved, size_t *new_num_buckets)
{
	size_t size;
	bool should_grow;
	size_t n_buckets;
	bool should_shrink;
	const bool shrink = !grow;
	struct sys_hashmap_oa_lp_data *const data = (struct sys_hashmap_oa_lp_data *)map->data;
	const struct sys_hashmap_config *const config = map->config;

	/* All branchless calculations, so very cache-friendly */

	/* calculate new size */
	size = data->size;
	size += grow;
	/* maximum size imposed by the implementation */
	__ASSERT_NO_MSG(size < SIZE_MAX / 100);

	/* calculate new number of buckets */
	n_buckets = data->n_buckets;
	/* initial number of buckets */
	n_buckets += grow * (size == 1) * config->initial_n_buckets;
	/* grow at a rate of 2x */
	n_buckets <<= grow * (size != 1);
	/* shrink at a rate of 2x */
	n_buckets >>= shrink;

	/* shrink to zero if empty */
	n_buckets *= (size != 0);

	__ASSERT_NO_MSG(new_num_buckets != NULL);
	__ASSERT_NO_MSG(new_num_buckets != &data->n_buckets);
	*new_num_buckets = n_buckets;

	should_grow =
		grow && (data->n_buckets == 0 ||
			 (size + num_reserved) * 100 / data->n_buckets > map->config->load_factor);
	should_shrink =
		shrink && (n_buckets == 0 || (size * 100) / n_buckets <= map->config->load_factor);

	return should_grow || should_shrink;
}

/** @} */

#ifdef __cplusplus
}
#endif

#endif /* ZEPHYR_INCLUDE_SYS_HASH_MAP_H_ */