init

Just some C wares; hmap, list, optional, unit tests.

1 files changed, 238 insertions, 0 deletions

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