From 89fe36162221ab36c5f2dfec1446dc406c68272b Mon Sep 17 00:00:00 2001 From: Johnny Richard Date: Wed, 17 May 2023 18:06:12 +0200 Subject: util: Create hashmap data structure with FNV-1a 32-bit hashing This path implements a hashmap data structure using the FNV-1a hashing function of 32 bits. However, there are a few limitations to consider: a) The table does not automatically expand when it becomes too large. b) The capacity of the hashmap must be a power of 2 to optimize performance, as we utilize bitwise shifting instead of modulus calculations. c) Currently, there are no functions available to destroy hashmap entries. Collisions are handled using a linked list, which is not the most optimal solution in terms of performance. However, it serves our current needs adequately. Signed-off-by: Johnny Richard --- src/hashmap.h | 75 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 75 insertions(+) create mode 100644 src/hashmap.h (limited to 'src/hashmap.h') diff --git a/src/hashmap.h b/src/hashmap.h new file mode 100644 index 0000000..6256548 --- /dev/null +++ b/src/hashmap.h @@ -0,0 +1,75 @@ +/* + * Copyright (C) 2023 Johnny Richard + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see . + */ +#ifndef HASHMAP_H +#define HASHMAP_H + +#include +#include +#include + +#define HASHMAP_INITIAL_CAPACITY 32 + +#define U32_FNV1A_PRIME 0x01000193 +#define U32_FNV1A_OFFSET_BASIS 0x811c9dc5 + +typedef struct hashmap_t hashmap_t; +typedef struct hashmap_bucket_t hashmap_bucket_t; +typedef struct hashmap_entry_t hashmap_entry_t; + +typedef struct hashmap_t +{ + hashmap_entry_t *entries; + uint32_t capacity; +} hashmap_t; + +typedef struct hashmap_entry_t +{ + char *key; + void *value; + uint32_t hash; + hashmap_entry_t *next; +} hashmap_entry_t; + +/** + * @brief: Create a new hashmap with HASHMAP_INITIAL_CAPACITY + */ +hashmap_t * +hashmap_new(void); + +/** + * @brief: Store a new entry into the hashmap. + * + * @param key: + * The function copies the key in order to have his own key. + * @param value: + * Value of the hashmap entry, the hashmap doesn't have the ownership. + * @return boolean + * true if the object has been added to the hashmap otherwise false. + */ +bool +hashmap_put(hashmap_t *map, char *key, void *value); + +void * +hashmap_get(hashmap_t *map, char *key); + +/** + * @brief: Destroy the hashmap and entries. (including keys) + */ +void +hashmap_destroy(hashmap_t *map); + +#endif /* HASHMAP_H */ -- cgit v1.2.3