/* SPDX-License-Identifier: LGPL-2.1 */
/**
 * hmap.h - a simple generic hashmap. v2.0.0
 *
 * Copyright (c) 2022-2023 - Yaroslav de la Peña Smirnov
 *
 * Documentation
 * =============
 *
 * In order to use this hashmap, you need to incapsulate struct hmap_entry
 * inside your own structure. For example::
 *
 * 	struct my_struct {
 * 		char				*key;
 * 		uint64_t 			data;
 * 		struct hmap_entry	entry;
 * 	};
 *
 * Then you can insert any instance of such struct into the hashmap by calling
 * the corresponding method and passing it the pointer to @entry.
 *
 * For search and removal operations you just need to fill your structure with
 * your key. The hmap_cmp_fn and hmap_hash_fn functions you provided will be
 * called by hmap in order to perform the needed operations.
 *
 * When you get a hmap_entry pointer from hmap's API, you can get your
 * containing structure with the help of the hmap_item macro, for example::
 *
 * 	struct hmap_entry *e = hmap_get(map, key);
 * 	struct my_struct *my = hmap_item(e, struct my_struct, entry);
 *
 */
#ifndef HMAP_H
#define HMAP_H
#include "../utils.h"

#include <inttypes.h>
#include <stdbool.h>
#include <sys/types.h>

#ifndef HMAP_INIT_CAP
#define HMAP_INIT_CAP 64
#endif

/**
 * Structures
 * ==========
 */

/**
 * struct hmap - opaque structure for generic hashmap.
 */
struct hmap;

/**
 * struct hmap_entry - the base class for a hashmap entry.
 * @next:	linked list in case of collisions.
 * @hash:	the hash value of the entry key.
 *
 * This structure should only be manipulated using the methods below. The @hash
 * member should be filled by the hmap_hash_fn function provided to hmap_new().
 */
struct hmap_entry {
	struct hmap_entry *next;
	size_t			   hash;
};

/**
 * struct hmap_iter - iterator over hmap entries.
 * @map:	hashmap.
 * @next:	next item to be returned.
 * @cursor:	current position in buckets table.
 *
 * If you want to remove entries while iterating, be sure to change the dynamic
 * resizing setting to on = false with hmap_dynamic_get().
 */
struct hmap_iter {
	struct hmap		  *map;
	struct hmap_entry *next;
	size_t			   cursor;
};

/**
 * Typedefs
 * ========
 */

typedef bool (*hmap_cmp_fn)(const struct hmap_entry *ent,
							const struct hmap_entry *key);
typedef void (*hmap_hash_fn)(struct hmap_entry *ent);

/**
 * Methods
 * =======
 */

/**
 * hmap_new_with() - allocate new hashmap with given parameters.
 * @cmp_fn:		key comparison function.
 * @hash_fn:	key hashing function.
 * @cap:		initial hashmap capacity.
 * @dynamic:	whether the hashmap should dynamically grow/shrink based on load
 * 				factor.
 * 
 * Return:	pointer to hmap object.
 */
struct hmap *hmap_new_with(hmap_cmp_fn cmp_fn, hmap_hash_fn hash_fn, size_t cap,
						   bool dynamic);

/**
 * hmap_new - allocate new hashmap with default parameters.
 * @cmp_fn:		key comparison function.
 * @hash_fn:	key hashing function.
 * 
 * Return:	pointer to hmap object.
 */
#define hmap_new(cmp_fn, hash_fn) \
	hmap_new_with(cmp_fn, hash_fn, HMAP_INIT_CAP, true)

/**
 * hmap_free() - free all resources used by @map.
 * @map:	hashmap.
 *
 * This function does not release or free any resources associated with any
 * entries stored in the hashmap. It is the responsibility of the caller to free
 * any such resources.
 */
void hmap_free(struct hmap *map);

/**
 * hmap_item - get the pointer to the containing structure for this entry.
 * @entry:	struct hmap_entry pointer.
 * @type:	containing struct.
 * @member:	the member in the struct that holds hmap_entry.
 */
#define hmap_item(entry, type, member) container_of(entry, type, member)

/**
 * hmap_add() - add entry to @map.
 * @map:	hashmap.
 * @ent:	entry to add.
 *
 * If there's already an entry with the same key, it wil still add it and hold
 * both.
 */
void hmap_add(struct hmap *map, struct hmap_entry *ent);

/**
 * hmap_get() - get entry with @key from @map.
 * @map:	hashmap.
 * @key:	hmap_entry object that holds the key.
 *
 * In order to pass the key, you just need to fill what is needed by your
 * hashing and comparison functions; you could even use a separate structure
 * that just holds the key, if you use the appropriate logic in your functions.
 *
 * If there are entries with duplicate keys, it will get the first it finds. If
 * your want to get the next duplicate-key entry use hmap_get_next_dup().
 *
 * Return: pointer to entry; NULL if no entry with such key.
 */
struct hmap_entry *hmap_get(struct hmap *map, struct hmap_entry *key);

/**
 * hmap_get_next_dup() - get the next entry with the same key as @ent.
 * @map:	hashmap.
 * @ent:	entry with duplicate key.
 *
 * Return: pointer to entry; NULL if no more entries with same key.
 */
struct hmap_entry *hmap_get_next_dup(struct hmap *map, struct hmap_entry *ent);

/**
 * hmap_remove() - remove entry with @key from @map.
 * @map:	hashmap.
 * @key:	hmap_entry object that holds the key.
 *
 * If there are entries with duplicates keys, it will remove the first it finds.
 *
 * Return: pointer to removed entry; NULL if no entry with such key.
 */
struct hmap_entry *hmap_remove(struct hmap *map, struct hmap_entry *key);

/**
 * hmap_entry_cnt() - get the current number of entries in @map.
 * @map:	hashmap.
 *
 * Return: number of entries held by @map.
 */
size_t hmap_entry_cnt(struct hmap *map);

/**
 * hmap_dynamic_set() - enable/disable hashmap resizing.
 * @map:	hashmap.
 * @on:		whether to turn on/off.
 */
void hmap_dynamic_set(struct hmap *map, bool on);

/**
 * hmap_dynamic_get() - get current hashmap resizing setting.
 * @map:	hashmap.
 *
 * Return: current dynamic resizing setting.
 */
bool hmap_dynamic_get(struct hmap *map);

/**
 * hmap_cur_cap() - get the current capacity of @map.
 * @map:	hashmap.
 *
 * Return: current @map capacity.
 */
size_t hmap_cur_cap(struct hmap *map);

/**
 * hmap_iter_init() - initialize and reset hmap iterator.
 * @iter:	pointer to hmap_iter object.
 * @map:	hashmap to iterate over.
 */
void hmap_iter_init(struct hmap_iter *iter, struct hmap *map);

/**
 * hmap_iter_next() - get the next entry.
 * @iter:	iterator.
 *
 * Return: pointer to entry; NULL if no more entries are left.
 */
struct hmap_entry *hmap_iter_next(struct hmap_iter *iter);

/**
 * hmap_iter_foreach - loop to iterate over every entry.
 * @iter:	pointer to iterator.
 * @entry:	hmap_entry pointer to hold the next entry.
 */
#define hmap_iter_foreach(iter, entry) \
	for (entry = hmap_iter_next((iter)); entry; entry = hmap_iter_next((iter)))

#endif /* HMAP_H */