c-preprocessor/hashmap.c

/* SPDX-License-Identifier: BSD-2 */

#include <hashmap.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

#define MAP_INIT_SIZE 1024

struct hashmap_elem {
	char *key;
	int in_use;
	char *val;
};

struct hashmap_map {
	int max_size;
	int curr_size;
	struct hashmap_elem *data;
};

void *hashmap_new(void)
{
	struct hashmap_map *m;

	m = calloc(1, sizeof(struct hashmap_map));
	if (!m)
		goto err;

	m->data = calloc(MAP_INIT_SIZE, sizeof(struct hashmap_elem));
	if (!m->data)
		goto err;

	m->max_size = MAP_INIT_SIZE;
	m->curr_size = 0;

	return m;

err:
	hashmap_free(m);
	return NULL;
}

unsigned int _hash_key(struct hashmap_map *m, char *key)
{
	unsigned int hash = 5381;
	int c;

	while ((c = *key++))
		hash = ((hash << 5) + hash) + c;

	return hash % m->max_size;
}

int _get_next_avail_pos(struct hashmap_map *m, char *key)
{
	int pos;
	int i;

	if (m->curr_size == m->max_size)
		return MAP_FULL;

	pos = _hash_key(m, key);
	i = 0;

	while (i < m->max_size) {
		if (!m->data[pos].in_use)
			return pos;

		if (!strncmp(m->data[pos].key, key, strlen(key))
			&& m->data[pos].in_use)
			return MAP_ALREADY_USED;

		pos = (pos + 1) % m->max_size;
		i++;
	}

	return MAP_FULL;
}

int _rehash(struct hashmap_map *m)
{
	int i;
	int old_size;
	int status;
	struct hashmap_elem *curr;
	struct hashmap_elem *temp;

	temp = calloc(2 * m->max_size, sizeof(struct hashmap_elem));
	if (!temp)
		return MAP_OMEM;

	curr = m->data;
	m->data = temp;

	old_size = m->max_size;
	m->max_size *= 2;
	m->curr_size = 0;

	for (i = 0; i < old_size; i++) {
		status = hashmap_put(m, curr[i].key, curr[i].val);
		if (status != MAP_OK)
			return status;
	}

	free(curr);

	return MAP_OK;
}

int hashmap_put(void *map, char *key, char *value)
{
	int pos;
	struct hashmap_map *m;

	if (!map || !key || !value)
		return MAP_BAD_ARGS;

	m = (struct hashmap_map *) map;
	pos = _get_next_avail_pos(m, key);

	if (pos == MAP_ALREADY_USED)
		return pos;

	while (pos == MAP_FULL) {
		if (_rehash(m) == MAP_OMEM)
			return MAP_OMEM;
		pos = _get_next_avail_pos(m, key);
	}

	m->data[pos].key = key;
	m->data[pos].in_use = 1;
	m->data[pos].val = value;

	m->curr_size++;

	return MAP_OK;
}

int _is_desired_pos(struct hashmap_map *m, char *key, int pos)
{
	return m->data[pos].key && key
		&& !strcmp(m->data[pos].key, key) && m->data[pos].in_use;
}

int hashmap_get(void *map, char *key, char **ret_val)
{
	int pos;
	int i;
	struct hashmap_map *m;

	if (!map || !key || !ret_val)
		return MAP_BAD_ARGS;

	m = (struct hashmap_map *) map;
	pos = _hash_key(m, key);

	for (i = 0; i < m->max_size; i++) {
		if (m->data) {
			if (_is_desired_pos(m, key, pos)) {
				*ret_val = m->data[pos].val;
				return MAP_OK;
			}
		}

		pos = (pos + 1) % m->max_size;
	}

	*ret_val = NULL;
	return MAP_MISSING;
}

int hashmap_del(void *map, char *key)
{
	int pos;
	int i;
	struct hashmap_map *m;

	if (!map || !key)
		return MAP_BAD_ARGS;

	m = (struct hashmap_map *) map;
	pos = _hash_key(m, key);

	for (i = 0; i < m->max_size; i++) {
		if (m->data) {
			if (_is_desired_pos(m, key, pos)) {
				free(m->data[pos].key);
				free(m->data[pos].val);
				m->data[pos].in_use = 0;

				m->data[pos].key = NULL;
				m->data[pos].val = NULL;

				return MAP_OK;
			}
		}

		pos = (pos + 1) % m->max_size;
	}

	return MAP_MISSING;
}

void hashmap_free(void *map)
{
	struct hashmap_map *m;
	int i;

	m = (struct hashmap_map *) map;

	if (!m)
		return;

	for (i = 0; m->data && i < m->max_size; i++) {
		free(m->data[i].key);
		free(m->data[i].val);
	}

	free(m->data);
	m->data = NULL;

	free(m);
	m = NULL;
}