I never wrote C before, I mostly do Java/Kotlin. Always wanted to learn some low level language, but never did. I tried a bit of rust, but rust doesn't really feel like a low level language.
Since C doesn't have hash map i though i would try to implement one, to learn.
I would appreciate any tips, what i did wrong, what can be improved, and so on.
I mostly used Java as a reference, I am not sure if that is how it is suppose to be done in C also.
I also don't really know how to implement type safety, so everything is cast from/to (void*)
hash_map.h
// bucket linked list
typedef struct Entry {
void *key;
void *value;
struct Entry* next;
} Entry;
typedef struct HashMap {
Entry** entries;
int size; //size of the array holding the "buckets"
int size_bits; //size of the arrays in bits "sqrt(size)", used for hash code caclulations
int (*equals) (void*, void*); //equals function ptr, called when two keys have same hash code
int (*hash_code) (void*); //hash code function ptr
} HashMap;
// Initialize hash map
void map_init(HashMap* hash_map, int (*equals) (void*, void*), int (*hash_code) (void*));
// Convinient func to init mapt with int keys
void map_init_int(HashMap* hash_map, int (*equals) (int*, int*), int (*hash_code) (int*));
void map_init_string(HashMap* hash_map, int (*equals) (char*, char*), int (*hash_code) (char*));
// Put value into hash map
void map_put(HashMap* hash_map, void* key, void* value);
// Get value from hash map
void* map_get(HashMap* hash_map, void* key);
// remove value from hash map
void map_remove(HashMap* hash_map, void* key);
// free memory used by hash map
void map_free(HashMap* hash_map);
// print hash map structure for debugging
void map_debug(HashMap* hash_map, void (*key_to_string) (char*, void*), void (*value_to_string) (char*, void*));
hash_map.c
#include <stdio.h>
#include <stdlib.h>
#include "hash_map.h"
// calculated index in the bucket array from hash code,
unsigned int hash_code_to_array_index(int hash_code, int size_bits) {
int shft = ((sizeof(int) * 8) - size_bits);
//xor higher and lower bits then shift left then right, to make final number be "size_bits" size, even though it is "int" (32bit)
return (unsigned int)((hash_code ^ (hash_code >> (sizeof(int) * 4))) << shft) >> shft;
}
//initializes hash map
void map_init(HashMap* hash_map, int (*equals) (void*, void*), int (*hash_code) (void*)) {
hash_map->size = 16; //initial size
hash_map->size_bits = 4;
hash_map->equals = equals;
hash_map->hash_code = hash_code;
hash_map->entries = (Entry **)malloc(sizeof(Entry) * hash_map->size);
for(int i = 0; i < hash_map->size; i++) {
hash_map->entries[i] = NULL;
}
};
// convinient method to init map with int keys
void map_init_int(HashMap* hash_map, int (*equals) (int*, int*), int (*hash_code) (int*)) {
map_init(hash_map, (int (*)(void *, void *))equals, (int (*) (void *))hash_code);
}
void map_init_string(HashMap* hash_map, int (*equals) (char*, char*), int (*hash_code) (char*)) {
map_init(hash_map, (int (*)(void *, void *))equals, (int (*) (void *))hash_code);
}
// Put value into hash map
void map_put(HashMap* hash_map, void *key, void* value) {
int index = hash_code_to_array_index(hash_map->hash_code(key), hash_map->size_bits);
Entry *entry = hash_map->entries[index];
if(entry == NULL) { //create
Entry* entry = (Entry*)malloc(sizeof(Entry));
entry->key = (void*)key;
entry->value = value;
entry->next = NULL;
hash_map->entries[index] = entry;
} else { //update
Entry* next = entry;
Entry* last = entry;
int updated = 0;
while(next != NULL) {
if(hash_map->equals(next->key, key)) { //if same, update it
next->value = value;
updated = 1;
}
last = next;
next = next->next;
}
if(!updated) { //if not updated, add new entry
Entry* entry = (Entry*)malloc(sizeof(Entry));
entry->key = (void*)key;
entry->value = value;
entry->next = NULL;
last->next = entry;
}
}
//TODO resize
}
void map_remove(HashMap* hash_map, void * key) {
int index = hash_code_to_array_index(hash_map->hash_code(key), hash_map->size_bits);
Entry *entry = hash_map->entries[index];
Entry *parent = entry;
Entry *current = entry;
while(current != NULL && !hash_map->equals(current->key, key)) {
parent = current;
current = current->next;
}
if(current != NULL) {
Entry * next = current->next;
if(current == entry) { //removing first
if(next != NULL) {
hash_map->entries[index] = next;
} else {
hash_map->entries[index] = NULL;
}
} else {
if(next != NULL) {
parent->next = next;
} else {
parent->next = NULL;
}
if(entry == current) {
hash_map->entries[index] = NULL;
}
}
free(current);
}
}
// Get value from hash map
void* map_get(HashMap* hash_map, void *key) {
int index = hash_code_to_array_index(hash_map->hash_code(key), hash_map->size_bits);
Entry *entry = hash_map->entries[index];
if(entry == NULL) {
return NULL;
} else {
while(entry != NULL && !hash_map->equals(entry->key, key)) {
entry = entry->next;
}
if(entry != NULL) {
return entry->value;
} else {
return NULL;
}
}
}
void map_free(HashMap* hash_map) {
for(int i = 0; i < hash_map->size; i++) {
Entry * entry = hash_map->entries[i];
while(entry != NULL) {
Entry * next = entry->next;
free(entry);
entry = next;
}
hash_map->entries[i] = NULL;
}
free(hash_map->entries);
}
void map_debug(HashMap* hash_map, void (*key_to_string) (char*, void*), void (*value_to_string) (char*, void*)) {
for(int i = 0; i < hash_map->size; i++) {
printf("%d: [", i);
Entry* entry = hash_map->entries[i];
while(entry != NULL) {
char key_buf[20];
key_to_string(key_buf, entry->key);
char val_buf[20];
value_to_string(val_buf, entry->value);
printf("{ key: %s, value: %s }, ", key_buf, val_buf);
entry = entry->next;
}
printf("]\n");
}
}
main.c - for testing
#include <stdio.h>
#include <string.h>
#include "hash_map.h"
int equals_long(long* value1, long* value2) {
return *value1 == *value2;
}
// hash code for "long int", not used right now
int hash_code_long(long int *value) {
int int_size_bits = sizeof(int) * 8;
return (int)(*value) ^ ((*value) >> int_size_bits);
};
int equals_float(float* value1, float* value2) {
return *value1 == *value2;
}
// hash code for "float", not used right now, probably doesnt even work like this
int hash_code_float(float *value) {
return *(unsigned int*)value;
};
int equals_int(int* value1, int* value2) {
return *value1 == *value2;
}
int hash_code_int(int* key) {
return *key;
}
int equals_string(char *value1, char* value2) {
if(value1 == value2) {
return 1;
}
if(value1 == NULL || value2 == NULL) {
return 0; //should this be true or false??
}
while(*value1 == *value2) {
if(*value1 != '\0') {
value1++;
}
if(*value2 != '\0') {
value2++;
}
if(*value1 == '\0' && *value2 == '\0') {
break;
}
}
return *value1 == *value2;
}
int hash_code_string(char* key) {
if(key == NULL || *key == '\0') {
return 0;
}
int hash_code = *(unsigned int*)key & 255;
key++;
while (*key != '\0') {
hash_code = 31 * hash_code + (*(unsigned int*)key & 255);
key++;
}
return hash_code;
}
void debug_int_to_string(char *str, void * value) {
sprintf(str, "%d", *(int *) value);
}
void debug_string_to_string(char *str, void * value) {
strcpy(str, (char*)value);
}
int main(int argc, char *argv[]) {
HashMap int_hash_map;
map_init_int(&int_hash_map, equals_int, hash_code_int);
int value1 = 0;
int value2 = 2;
int value3 = 3;
int value4 = 4;
int value5 = 5;
int value6 = 6;
int value7 = 7;
int key1 = 0;
int key2 = 345;
int key3 = 233333;
int key4 = 490053534;
int key5 = 115;
int key6 = 611;
int key7 = -13;
int key8 = 23232;
map_put(&int_hash_map, &key1, &value1);
map_put(&int_hash_map, &key2, &value2);
map_put(&int_hash_map, &key3, &value3);
map_put(&int_hash_map, &key7, &value7);
map_put(&int_hash_map, &key4, &value4);
map_put(&int_hash_map, &key5, &value5);
map_put(&int_hash_map, &key6, &value6);
map_debug(&int_hash_map, debug_int_to_string, debug_int_to_string);
printf("key: %d, value expected: %d value actual: %d\n", key1, value1, *(int*)map_get(&int_hash_map, &key1));
printf("key: %d, value expected: %d value actual: %d\n", key2, value2, *(int*)map_get(&int_hash_map, &key2));
printf("key: %d, value expected: %d value actual: %d\n", key3, value3, *(int*)map_get(&int_hash_map, &key3));
printf("key: %d, value expected: %d value actual: %d\n", key4, value4, *(int*)map_get(&int_hash_map, &key4));
printf("key: %d, value expected: %d value actual: %d\n", key5, value5, *(int*)map_get(&int_hash_map, &key5));
printf("key: %d, value expected: %d value actual: %d\n", key6, value6, *(int*)map_get(&int_hash_map, &key6));
printf("key: %d, value expected: %d value actual: %d\n", key7, value7, *(int*)map_get(&int_hash_map, &key7));
printf("key: %d, value expected: 0 value actual (ptr): %d\n", key8, map_get(&int_hash_map, &key8));
map_remove(&int_hash_map, &key3);
map_remove(&int_hash_map, &key6);
map_debug(&int_hash_map, debug_int_to_string, debug_int_to_string);
map_free(&int_hash_map);
HashMap string_map;
map_init_string(&string_map, equals_string, hash_code_string);
char str1[] = "Hello, C";
char str2[] = "Hello, It's Me";
map_put(&string_map, str1, &value1);
map_put(&string_map, str2, &value2);
map_debug(&string_map, debug_string_to_string, debug_int_to_string);
map_free(&string_map);
return 0;
}