path: root/hmap/hmap.c

/* SPDX-License-Identifier: MIT */
#include "hmap.h"

#include <string.h>
#include <stdlib.h>
#include <limits.h>
#ifdef HMAP_DEBUG
#include <stdio.h>
#endif

#ifndef HMAP_LOAD_FACTOR
#define HMAP_LOAD_FACTOR 80
#endif
#ifndef HMAP_GROWTH_RATE
#define HMAP_GROWTH_RATE 2
#endif

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

/**
 * struct hmap - generic hash map.
 * @buckets:	table where we store our buckets.
 * @cap:		current capacity.
 * @cnt:		how many entries we currently hold.
 * @grow_at:	load factor at which we grow. > 100 if hmap is not dynamic.
 * @shrink_at:	load factor at which we shrink.
 * @cmp:		key compare function.
 */
struct hmap {
	struct hmap_entry **buckets;

	size_t cap;
	size_t cnt;

	size_t grow_at;
	size_t shrink_at;

	hmap_cmp_fn	 cmp;
	hmap_hash_fn hash_key;

	uint8_t dynamic : 1;
};

/**
 * Internal methods
 * ================
 */

/**
 * find_hmap_bucket() - find the bucket for @key.
 * @map:	hashmap.
 * @key:	key with hash.
 *
 * Return:	pointer to bucket in buckets table.
 */
static inline struct hmap_entry **find_hmap_bucket(struct hmap		 *map,
												   struct hmap_entry *key)
{
	size_t i = key->hash % map->cap;

	return map->buckets + i;
}

/**
 * find_hmap_entry() - find entry that has @key.
 * @map:	hashmap.
 * @key:	key with hash.
 *
 * Return:	pointer where the entry is stored.
 */
static struct hmap_entry **find_hmap_entry(struct hmap		 *map,
										   struct hmap_entry *key)
{
	map->hash_key(key);

	struct hmap_entry **ptr = find_hmap_bucket(map, key);
	while (*ptr) {
		if (map->cmp(*ptr, key)) {
			return ptr;
		}
		ptr = &(*ptr)->next;
	}

	return ptr;
}

/**
 * __hmap_add() -- low level add function.
 * @map:	hashmap.
 * @ent:	entry to add.
 */
static void __hmap_add(struct hmap *map, struct hmap_entry *ent)
{
	struct hmap_entry **bucket = find_hmap_bucket(map, ent);
	if (*bucket) {
		struct hmap_entry *coll = *bucket;
		struct hmap_entry *next = coll->next;
#ifdef HMAP_DEBUG
		fprintf(stderr, "\nCOLLISION!\n");
#endif
		while (next) {
#ifdef HMAP_DEBUG
			fprintf(stderr, "\nCOLLISION!\n");
#endif
			coll = next;
			next = coll->next;
		}
		coll->next = ent;
	} else {
		*bucket = ent;
	}
}

/**
 * set_thresholds() - set growth and shrink thresholds.
 * @map:	hashmap.
 */
static inline void set_thresholds(struct hmap *map)
{
	map->grow_at = map->cap * HMAP_LOAD_FACTOR / 100;
	if (map->cap <= HMAP_INIT_CAP) {
		map->shrink_at = 0;
	} else {
		map->shrink_at = map->grow_at / HMAP_GROWTH_RATE - 2;
	}
}

/**
 * alloc_buckets() - allocate buckets table.
 * @map:	hashmap.
 */
static inline void alloc_buckets(struct hmap *map)
{
	map->buckets = calloc(map->cap, sizeof(struct hmap_entry *));
}

/**
 * maybe_realloc() - grow/shrink buckets table if needed.
 * @map:	hashmap.
 */
static void maybe_realloc(struct hmap *map)
{
	if (!map->dynamic) {
		return;
	}

	size_t oldcap = map->cap;

	if (map->cnt >= map->grow_at) {
		map->cap = map->cap * HMAP_GROWTH_RATE;
	} else if (map->cnt < map->shrink_at) {
		map->cap = map->cap / HMAP_GROWTH_RATE;
	} else {
		return;
	}

	struct hmap_entry **oldbucks = map->buckets;

	alloc_buckets(map);
	set_thresholds(map);

	for (size_t i = 0; i < oldcap; i++) {
		struct hmap_entry *next = oldbucks[i], *cur;
		while (next) {
			cur		  = next;
			next	  = cur->next;
			cur->next = NULL;
			__hmap_add(map, cur);
		}
	}

	free(oldbucks);
}

/**
 * Public methods
 * ==============
 */

struct hmap *hmap_new_with(hmap_cmp_fn cmp_fn, hmap_hash_fn hash_fn, size_t cap,
						   bool dynamic)
{
	struct hmap *map = malloc(sizeof(*map));

	map->cap	  = cap;
	map->cnt	  = 0;
	map->cmp	  = cmp_fn;
	map->hash_key = hash_fn;
	map->dynamic  = dynamic;
	alloc_buckets(map);
	if (dynamic) {
		set_thresholds(map);
	}

	return map;
}

void hmap_add(struct hmap *map, struct hmap_entry *ent)
{
	ent->next = NULL;
	map->hash_key(ent);

	map->cnt++;
	maybe_realloc(map);

	__hmap_add(map, ent);
}

struct hmap_entry *hmap_get(struct hmap *map, struct hmap_entry *key)
{
	return *find_hmap_entry(map, key);
}

struct hmap_entry *hmap_get_next_dup(struct hmap *map, struct hmap_entry *ent)
{
	struct hmap_entry *next = ent->next;
	while (next) {
		if (map->cmp(next, ent)) {
			return next;
		}
	}

	return next;
}

struct hmap_entry *hmap_remove(struct hmap *map, struct hmap_entry *key)
{
	struct hmap_entry **ptr = find_hmap_entry(map, key), *old;

	if (*ptr) {
		if (map->cmp(*ptr, key)) {
			old	 = *ptr;
			*ptr = old->next;

			map->cnt--;
			maybe_realloc(map);

			return old;
		}
	}

	return NULL;
}

size_t hmap_entry_cnt(struct hmap *map)
{
	return map->cnt;
}

size_t hmap_cur_cap(struct hmap *map)
{
	return map->cap;
}

void hmap_dynamic_set(struct hmap *map, bool on)
{
	map->dynamic = on;
}

bool hmap_dynamic_get(struct hmap *map)
{
	return map->dynamic;
}

void hmap_free(struct hmap *map)
{
	free(map->buckets);
	free(map);
}

void hmap_iter_init(struct hmap_iter *iter, struct hmap *map)
{
	iter->map	 = map;
	iter->cursor = 0;
	iter->next	 = NULL;
}

struct hmap_entry *hmap_iter_next(struct hmap_iter *iter)
{
	struct hmap_entry *cur = iter->next;

	for (;;) {
		if (cur) {
			iter->next = cur->next;
			return cur;
		}

		if (iter->cursor >= iter->map->cap) {
			return NULL;
		}

		cur = iter->map->buckets[iter->cursor++];
	}
}