ox

hmap.c (4112B)

---

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

#include "hmap.h"

#define INITIAL_BUCKETS 8
#define LOAD_FACTOR 0.75

static void hmap_grow(HashMap* map);

// Simple string hash function (djb2)
static unsigned long
hash(const char* str)
{
	unsigned long h = 5381;
	unsigned char c;
	while ((c = (unsigned char)*str++))
		h = ((h << 5) + h) + c;
	return h;
}

HashMap*
hmap_create(size_t value_size)
{
	HashMap* map = calloc(1, sizeof(HashMap));
	if (map == NULL) { fprintf(stderr, "hmap_create: map: could not alloc\n"); }
	map->bucket_count = INITIAL_BUCKETS;
	map->size = 0;
	map->value_size = value_size;
	map->buckets = calloc(map->bucket_count, sizeof(HashNode*));
	if (map->buckets == NULL) {
		fprintf(stderr, "hmap_create: bucket: could not alloc\n");
		exit(1);
	}
	return map;
}

void
hmap_put(HashMap* map, const char* key, const void* value)
{
	if ((float)(map->size + 1) / map->bucket_count > LOAD_FACTOR) { hmap_grow(map); }
	unsigned long h = hash(key) % map->bucket_count;
	HashNode* node = map->buckets[h];
	while (node) {
		if (strcmp(node->key, key) == 0) {
			memcpy(node->value, value, map->value_size);
			return;
		}
		node = node->next;
	}
	HashNode* new_node = calloc(1, sizeof(HashNode));
	if (new_node == NULL) {
		fprintf(stderr, "hmap_put: new_node: could not alloc\n");
		exit(1);
	}
	new_node->key = strdup(key);
	new_node->value = calloc(1, map->value_size);
	if (new_node == NULL) {
		fprintf(stderr, "hmap_put: new_node->value: could not alloc\n");
		exit(1);
	}
	memcpy(new_node->value, value, map->value_size);
	new_node->next = map->buckets[h];
	map->buckets[h] = new_node;
	map->size++;
}

bool
hmap_get(HashMap* map, const char* key, void* out)
{
	unsigned long h = hash(key) % map->bucket_count;
	HashNode* node = map->buckets[h];
	while (node) {
		if (strcmp(node->key, key) == 0) {
			memcpy(out, node->value, map->value_size);
			return true;
		}
		node = node->next;
	}
	return false;
}

bool
hmap_remove(HashMap* map, const char* key)
{
	unsigned long h = hash(key) % map->bucket_count;
	HashNode* node = map->buckets[h];
	HashNode* prev = NULL;
	while (node) {
		if (strcmp(node->key, key) == 0) {
			if (prev) {
				prev->next = node->next;
			} else {
				map->buckets[h] = node->next;
			}
			free(node->key);
			free(node->value);
			free(node);
			map->size--;
			return true;
		}
		prev = node;
		node = node->next;
	}
	return false;
}

static void
hmap_grow(HashMap* map)
{
	size_t new_bucket_count = map->bucket_count * 2;
	HashNode** new_buckets = calloc(new_bucket_count, sizeof(HashNode*));
	if (new_buckets == NULL) {
		fprintf(stderr, "hmap_grow: could not alloc\n");
		exit(1);
	}
	for (size_t i = 0; i < map->bucket_count; i++) {
		HashNode* node = map->buckets[i];
		while (node) {
			HashNode* next = node->next;
			unsigned long h = hash(node->key) % new_bucket_count;
			node->next = new_buckets[h];
			new_buckets[h] = node;
			node = next;
		}
	}
	free(map->buckets);
	map->buckets = new_buckets;
	map->bucket_count = new_bucket_count;
}

void
hmap_free(HashMap* map)
{
	for (size_t i = 0; i < map->bucket_count; i++) {
		HashNode* node = map->buckets[i];
		while (node) {
			HashNode* next = node->next;
			free(node->key);
			free(node->value);
			free(node);
			node = next;
		}
	}
	free(map->buckets);
	free(map);
}

// Example usage for struct T
// struct T {
//     int id;
//     char name[32];
// };

// int main() {
//     HashMap* map = hmap_create(sizeof(struct T));
//     struct T t1 = {1, "Alice"};
//     struct T t2 = {2, "Bob"};
//     struct T t3 = {3, "Carol"};

//     hmap_put(map, "alice", &t1);
//     hmap_put(map, "bob", &t2);
//     hmap_put(map, "carol", &t3);

//     struct T out;
//     if (hmap_get(map, "bob", &out)) {
//         printf("bob: id=%d, name=%s\n", out.id, out.name);
//     }
//     if (hmap_get(map, "alice", &out)) {
//         printf("alice: id=%d, name=%s\n", out.id, out.name);
//     }
//     if (hmap_get(map, "dave", &out)) {
//         printf("dave: id=%d, name=%s\n", out.id, out.name);
//     } else {
//         printf("dave not found\n");
//     }
//     hmap_free(map);
//     return 0;
// }