hash_map.h

Go to the documentation of this file.

/*
 * Copyright (c) 2022 Meta
 *
 * SPDX-License-Identifier: Apache-2.0
 */
 
#ifndef ZEPHYR_INCLUDE_SYS_HASH_MAP_H_
#define ZEPHYR_INCLUDE_SYS_HASH_MAP_H_
 
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdlib.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
 
#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),                                                       \
        }
 
#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),                                                       \
        }
 
#define SYS_HASHMAP_DEFINE(_name) SYS_HASHMAP_DEFAULT_DEFINE(_name)
 
#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
 
#define SYS_HASHMAP_DEFAULT_LOAD_FACTOR 75
 
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;
};
 
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);
        }
}
 
static inline void sys_hashmap_clear(struct sys_hashmap *map, sys_hashmap_callback_t cb,
                                     void *cookie)
{
        map->api->clear(map, cb, cookie);
}
 
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);
}
 
static inline bool sys_hashmap_remove(struct sys_hashmap *map, uint64_t key, uint64_t *value)
{
        return map->api->remove(map, key, value);
}
 
static inline bool sys_hashmap_get(const struct sys_hashmap *map, uint64_t key, uint64_t *value)
{
        return map->api->get(map, key, value);
}
 
static inline bool sys_hashmap_contains_key(const struct sys_hashmap *map, uint64_t key)
{
        return sys_hashmap_get(map, key, NULL);
}
 
static inline size_t sys_hashmap_size(const struct sys_hashmap *map)
{
        return map->data->size;
}
 
static inline bool sys_hashmap_is_empty(const struct sys_hashmap *map)
{
        return map->data->size == 0;
}
 
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;
}
 
static inline size_t sys_hashmap_num_buckets(const struct sys_hashmap *map)
{
        return map->data->n_buckets;
}
 
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_ */