From 8a9208612eec8ddae4c418485d848ecfa0613699 Mon Sep 17 00:00:00 2001 From: Anton Kling Date: Mon, 30 Oct 2023 22:12:14 +0100 Subject: Meta: Move kernel and userland to their own folders. This is to allow both the kernel and the userland to share certain header files and to make the folder structure a bit more clear. --- hashmap/hashmap.c | 212 ------------------------------------------------------ hashmap/hashmap.h | 39 ---------- 2 files changed, 251 deletions(-) delete mode 100644 hashmap/hashmap.c delete mode 100644 hashmap/hashmap.h (limited to 'hashmap') diff --git a/hashmap/hashmap.c b/hashmap/hashmap.c deleted file mode 100644 index 2eeef98..0000000 --- a/hashmap/hashmap.c +++ /dev/null @@ -1,212 +0,0 @@ -// -// Copyright (C) 2022 by Anton Kling -// -// SPDX-License-Identifier: BSD-2-Clause -// -/* - * HashMap - * ------- - * This hashmap works by creating a array of linked lists and associating - * the "key" with a specific entry in the array. This is done through a - * hash. Once the linked list is found it goes through it until it finds - * a entry that has the "key" provided. - * - * Changing the hashing function - * ----------------------------- - * The default hashing function in this library is a custom made - * one that can be found in hash.c. But it should be possible to use any - * other hashing algorithm should you want to as long as it uses these - * types: - * uint32_t hash_function(uint8_t*, size_t) - * - * The hashing algorithm can be changed via changing the "hash_function" - * pointer in the HashMap structure. - * - * Important to note that the hashing function shall not be changed - * after having added entries to the hashmap as the key to linked list - * pairing will change. - */ -#include "hashmap.h" - -#include -#include -#include -#include - -#define CONSTANT 0x031b5515 - -uint32_t mix(uint32_t x) { - x ^= CONSTANT; - x ^= (x << 13); - x ^= (x >> 7); - x ^= (x << 17); - return x; -} - -uint32_t hash(const uint8_t *data, size_t len) { - uint32_t hash = 0; - for (; len;) { - uint32_t value = 0; - uint8_t read_len = (sizeof(uint32_t) < len) ? sizeof(uint32_t) : len; - memcpy(&value, data, read_len); - hash ^= mix(value); - data += read_len; - len -= read_len; - } - return hash; -} - -char *copy_c_string(const char *str) { - char *ret_string; - size_t len = strlen(str); - ret_string = kmalloc(len + 1); - if (!ret_string) - return NULL; - memcpy(ret_string, str, len); - ret_string[len] = '\0'; - return ret_string; -} - -uint32_t limit_hash(HashMap *m, uint32_t hash) { return hash % m->size; } - -void free_linkedlist_entry(LinkedList *entry) { - if (entry->key_allocated) { - // If the key is allocated by the hashmap library then it owns the - // key and can safley discard the const qualifier and override its - // contents - kfree((char *)entry->key); - } - kfree(entry); -} - -LinkedList *get_linkedlist_entry(LinkedList *list, const char *key, - LinkedList **prev) { - if (prev) - *prev = NULL; - for (; list; list = list->next) { - const char *str1 = key; - const char *str2 = list->key; - for (; *str1 && *str2; str1++, str2++) - if (*str1 != *str2) - break; - if (*str1 == *str2) - return list; - if (prev) - prev = &list; - } - return NULL; -} - -void *get_linkedlist_value(LinkedList *list, const char *key) { - LinkedList *entry = get_linkedlist_entry(list, key, NULL); - if (!entry) - return NULL; - return entry->value; -} - -uint32_t find_index(HashMap *m, const char *key) { - return limit_hash(m, m->hash_function((uint8_t *)key, strlen(key))); -} - -int hashmap_add_entry(HashMap *m, const char *key, void *value, - void (*upon_deletion)(const char *, void *), - int do_not_allocate_key) { - // Create the entry - LinkedList *entry = kmalloc(sizeof(LinkedList)); - if (!entry) - return 0; - - entry->key_allocated = !do_not_allocate_key; - if (do_not_allocate_key) { - entry->key = key; - } else { - if (!(entry->key = copy_c_string(key))) - return 0; - } - entry->value = value; - entry->next = NULL; - entry->upon_deletion = upon_deletion; - - // Add the new entry to the list. - uint32_t index = find_index(m, key); - LinkedList **list_pointer = &m->entries[index]; - for (; *list_pointer;) - list_pointer = &(*list_pointer)->next; - - *list_pointer = entry; - m->num_entries++; - return 1; -} - -void *hashmap_get_entry(HashMap *m, const char *key) { - uint32_t index = find_index(m, key); - if (!m->entries[index]) - return NULL; - return get_linkedlist_value(m->entries[index], key); -} - -int hashmap_delete_entry(HashMap *m, const char *key) { - LinkedList *list = m->entries[find_index(m, key)]; - if (!list) - return 0; - LinkedList **prev = NULL; - LinkedList *entry = get_linkedlist_entry(list, key, prev); - if (!entry) - return 0; - if (!prev) - prev = &m->entries[find_index(m, key)]; - - if (entry->upon_deletion) - entry->upon_deletion(entry->key, entry->value); - - LinkedList *next = entry->next; - free_linkedlist_entry(entry); - if (*prev != entry) - (*prev)->next = next; - else - *prev = NULL; - - // Redo the delete process incase there are multiple - // entires that have the same key. - hashmap_delete_entry(m, key); - m->num_entries--; - return 1; -} - -void hashmap_free(HashMap *m) { - for (int i = 0; i < m->size; i++) { - if (!m->entries[i]) - continue; - LinkedList *list = m->entries[i]; - for (; list;) { - if (list->upon_deletion) - list->upon_deletion(list->key, list->value); - LinkedList *old = list; - list = list->next; - free_linkedlist_entry(old); - } - } - kfree(m->entries); - kfree(m); -} - -HashMap *hashmap_create(size_t size) { - HashMap *m = kmalloc(sizeof(HashMap)); - if (!m) - return NULL; - - m->size = size; - m->num_entries = 0; - - // Create a array of pointers to linkedlists but don't create them - // yet. - m->entries = kcalloc(size, sizeof(LinkedList **)); - if (!m->entries) - return NULL; - - for (size_t i = 0; i < m->size; i++) - m->entries[i] = NULL; - - m->hash_function = hash; - return m; -} diff --git a/hashmap/hashmap.h b/hashmap/hashmap.h deleted file mode 100644 index 40f146a..0000000 --- a/hashmap/hashmap.h +++ /dev/null @@ -1,39 +0,0 @@ -// -// Copyright (C) 2022 by Anton Kling -// -// SPDX-License-Identifier: BSD-2-Clause -// -#ifndef HASHMAP_H -#define HASHMAP_H -#include -#include - -typedef struct LinkedList { - const char *key; - int key_allocated; - void *value; - void (*upon_deletion)(const char *, void *); - struct LinkedList *next; -} LinkedList; - -typedef struct HashMap { - LinkedList **entries; - size_t size; - size_t num_entries; - uint32_t (*hash_function)(const uint8_t *data, size_t len); -} HashMap; - -HashMap *hashmap_create(size_t size); -void hashmap_free(HashMap *m); - -// hashmap_add_entry() -// ------------------- -// This function adds a entry to the hashmap. The "key" passed to the -// hashmap will be allocated by default unless (do_not_allocate_key) is -// set to 1. -int hashmap_add_entry(HashMap *m, const char *key, void *value, - void (*upon_deletion)(const char *, void *), - int do_not_allocate_key); -void *hashmap_get_entry(HashMap *m, const char *key); -int hashmap_delete_entry(HashMap *m, const char *key); -#endif -- cgit v1.2.3