Created
September 27, 2024 20:32
-
-
Save nickel-dev/6235f3f88214c51929a90542d4f83091 to your computer and use it in GitHub Desktop.
Linear search Hashmap using linked lists in C, is uses my base layer.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
intern u64 | |
hash_str(const char* str) { | |
u64 hash = 14695981039346656037ULL; // FNV offset basis | |
i32 c; | |
while ((c = *str++)) { | |
hash ^= (u64)c; | |
hash *= 1099511628211ULL; // FNV prime | |
} | |
return hash; | |
} | |
// Macros | |
#define __HASH_NEW_CONTAINER(T) \ | |
struct __Hash_##T##_Container {\ | |
u64 key;\ | |
T data;\ | |
struct __Hash_##T##_Container* next;\ | |
}; | |
#define __HASH_GET_FUNC(T, n) \ | |
intern T hash_get_##n(const char* key) {\ | |
u64 hash = hash_str(key);\ | |
struct __Hash_##T##_Container* curr = &__##n##_bucket_root;\ | |
while(curr != NULL){\ | |
if(hash == curr->key)\ | |
return curr->data;\ | |
curr = curr->next;\ | |
}\ | |
return (T){0};\ | |
} | |
#define __HASH_INSERT_FUNC(T, n) \ | |
intern void hash_insert_##n(const char* key, T data) {\ | |
u64 hash = hash_str(key);\ | |
struct __Hash_##T##_Container* curr = &__##n##_bucket_root;\ | |
while (curr != NULL) {\ | |
if (curr->key == hash) {\ | |
curr->data = data;\ | |
return;\ | |
}\ | |
if (curr->next == NULL) {\ | |
curr->next = (struct __Hash_##T##_Container*)malloc(sizeof(struct __Hash_##T##_Container));\ | |
curr = curr->next;\ | |
curr->key = hash;\ | |
curr->data = data;\ | |
curr->next = NULL;\ | |
return;\ | |
}\ | |
curr = curr->next;\ | |
}\ | |
} | |
#define __HASH_DELETE_FUNC(T, n) \ | |
intern void hash_delete_##n(const char* key) {\ | |
u64 hash = hash_str(key);\ | |
struct __Hash_##T##_Container* curr = &__##n##_bucket_root;\ | |
struct __Hash_##T##_Container* last = NULL;\ | |
while (curr != NULL) {\ | |
if (curr->key == hash) {\ | |
if (last != NULL)\ | |
last->next = curr->next;\ | |
free((void*)curr);\ | |
return;\ | |
}\ | |
last = curr;\ | |
curr = curr->next;\ | |
}\ | |
} | |
#define HASHMAP(T, name) \ | |
__HASH_NEW_CONTAINER(T)\ | |
global struct __Hash_##T##_Container __##name##_bucket_root = {0, 0, NULL};\ | |
__HASH_GET_FUNC(T, name)\ | |
__HASH_INSERT_FUNC(T, name)\ | |
__HASH_DELETE_FUNC(T, name) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment