From cb1a40859029f33184355475e51fec95afb79a73 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Yaroslav=20de=20la=20Pe=C3=B1a=20Smirnov?= Date: Sat, 22 Jul 2023 03:03:09 +0300 Subject: init Just some C wares; hmap, list, optional, unit tests. --- hmap/hmap.h | 238 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 238 insertions(+) create mode 100644 hmap/hmap.h (limited to 'hmap/hmap.h') diff --git a/hmap/hmap.h b/hmap/hmap.h new file mode 100644 index 0000000..bbd95f3 --- /dev/null +++ b/hmap/hmap.h @@ -0,0 +1,238 @@ +/* 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 +#include +#include + +#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 */ -- cgit v1.2.3