ox

hmap.c (4118B)

---

 #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;
 // }