diff options
| -rw-r--r-- | .gitignore | 3 | ||||
| -rw-r--r-- | LICENSE | 14 | ||||
| -rw-r--r-- | Makefile | 16 | ||||
| -rw-r--r-- | examples/Makefile | 2 | ||||
| -rw-r--r-- | examples/gehashmap.c | 42 | ||||
| -rw-r--r-- | man/Lb-desc.tmac | 5 | ||||
| -rw-r--r-- | src/gehashmap.h | 290 |
7 files changed, 372 insertions, 0 deletions
diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..1844d93 --- /dev/null +++ b/.gitignore @@ -0,0 +1,3 @@ +examples/* +!examples/Makefile +!examples/*.c @@ -0,0 +1,14 @@ +BSD Zero Clause License + +Copyright (c) 2022 Thomas Voss + +Permission to use, copy, modify, and/or distribute this software for any +purpose with or without fee is hereby granted. + +THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH +REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY +AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, +INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM +LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR +OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR +PERFORMANCE OF THIS SOFTWARE. diff --git a/Makefile b/Makefile new file mode 100644 index 0000000..b89064d --- /dev/null +++ b/Makefile @@ -0,0 +1,16 @@ +.POSIX: + +PREFIX = /usr/local +DPREFIX = ${DESTDIR}${PREFIX} +MANDIR = ${DPREFIX}/share/man + +GDIR = /usr/share/groff/site-tmac +DGDIR = ${DESTDIR}${GDIR} + +install: + mkdir -p ${DPREFIX}/include ${DGDIR} + cp src/gehashmap.h ${DPREFIX}/include + #cp man/*.3 ${MANDIR}/man3 + #cp man/*.3head ${MANDIR}/man3head + #sed '/^\.ds doc-str-Lb-liblux/d' ${GDIR}/mdoc.local >${DGDIR}/mdoc.local + #grep -v '^\.\\"' man/Lb-desc.tmac >>${DGDIR}/mdoc.local diff --git a/examples/Makefile b/examples/Makefile new file mode 100644 index 0000000..0d87a45 --- /dev/null +++ b/examples/Makefile @@ -0,0 +1,2 @@ +all: + cc -Og -g -ggdb gehashmap.c -o gehashmap diff --git a/examples/gehashmap.c b/examples/gehashmap.c new file mode 100644 index 0000000..f216d00 --- /dev/null +++ b/examples/gehashmap.c @@ -0,0 +1,42 @@ +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +size_t hash(char *); + +#define GEHASHMAP_NAME funmap +#define GEHASHMAP_KEY_T char * +#define GEHASHMAP_VAL_T int +#define GEHASHMAP_CMP_FUNC (int (*)(char *, char *)) strcmp +#define GEHASHMAP_FREE_FUNC (void (*)(char *)) free +#define GEHASHMAP_HASH_FUNC hash +#include <gehashmap.h> + +size_t +hash(char *s) +{ + char c; + size_t x = 5381; + + while (c = *s++) + x = ((x << 5) + x) + c; + + return x; +} + +int +main(void) +{ + int n; + funmap_t *map; + + funmap_new(map = malloc(sizeof(funmap_t))); + funmap_put(map, strdup("Thomas Voß"), 5); + funmap_put(map, strdup("THOMAS VOẞ"), 6); + funmap_put(map, strdup("Thomas Voss"), 7); + funmap_get(map, "Thomas Voß", &n); printf("Thomas Voß -> ‚%d‘\n", n); + funmap_get(map, "THOMAS VOẞ", &n); printf("THOMAS VOẞ -> ‚%d‘\n", n); + funmap_get(map, "Thomas Voss", &n); printf("Thomas Voss -> ‚%d‘\n", n); + funmap_free(map); + free(map); +} diff --git a/man/Lb-desc.tmac b/man/Lb-desc.tmac new file mode 100644 index 0000000..5393d37 --- /dev/null +++ b/man/Lb-desc.tmac @@ -0,0 +1,5 @@ +.\" This is the description that is printed when the .Lb macro is invoked with +.\" “liblux” as an argument. The general format for the output of the .Lb macro +.\" is: +.\" ‹Description› (‹Library Name›, ‹Linker Flag›) +.ds doc-str-Lb-libge Generic Data Structures Library (libge, \-lge) diff --git a/src/gehashmap.h b/src/gehashmap.h new file mode 100644 index 0000000..1f7048c --- /dev/null +++ b/src/gehashmap.h @@ -0,0 +1,290 @@ +/* Include guard */ + +#ifndef GEHASHMAP_H +#define GEHASHMAP_H + +#include <stdbool.h> +#include <stdlib.h> + +/* GEHASHMAP_INITIAL_SIZE is the initial capacity in items that a newly created + * hashmap can hold. GEHASHMAP_LOAD_FACTOR is the % of the hashmap that can be + * filled before we resize it to hold more items. + */ +#define GEHASHMAP_INITIAL_SIZE 16 +#define GEHASHMAP_LOAD_FACTOR 0.75 + +/* As a result of preprocessor _stuff_, we need 2 macros to properly concatinate + * things as we would expect. GEHASHMAP_CONCAT() is what we use when we want to + * concatinate things, so GEHASHMAP_CONCAT(GEHASHMAP_INITIAL_SIZE, f) would give + * us “16f”. GEHASHMAP_FUNC_NAME() gives us function names, so + * GEHASHMAP_FUNC_NAME(put) gives us the name of the function to put new items + * into the current hashmap. + */ +#define GEHASHMAP_CONCAT_HELPER(x, y) x ## y +#define GEHASHMAP_CONCAT(x, y) GEHASHMAP_CONCAT_HELPER(x, y) +#define GEHASHMAP_FUNC_NAME(x) GEHASHMAP_CONCAT(GEHASHMAP_NAME, _ ## x) + +#endif /* !GEHASHMAP_H */ + + + +/* The type of the hashmap keys */ +#ifndef GEHASHMAP_KEY_T + #error "Type for the hashmap key was not set" +#endif + +/* The type of the hashmap values */ +#ifndef GEHASHMAP_VAL_T + #error "Type for the hashmap value was not set" +#endif + +/* The name of the hashmap. If set to “foo” then the resulting hashmap type + * name would be “foo_t” and the get function would be called “foo_get()”. + */ +#ifndef GEHASHMAP_NAME + #error "Name for the hashmap type was not set" +#endif + +/* The key comparison function. This function should have the following + * signature: + * + * int function_name(GEHASHMAP_KEY_T, GEHASHMAP_KEY_T); + * + * If the two keys are the same, this function should return 0. This is to stay + * compatible with the strcmp() function. + */ +#ifndef GEHASHMAP_CMP_FUNC + #error "Comparison function for the hashmap key was not set" +#endif + +/* The key hashing function. This function should have the following signature: + * + * size_t function_name(GEHASHMAP_KEY_T); + * + * This function should return a hash of the given key. It is used for indexing + * the hashmap. + */ +#ifndef GEHASHMAP_HASH_FUNC + #error "Hashing function for the hashmap key was not set" +#endif + +/* The key freeing function. This function should have the following signature: + * + * void function_name(GEHASHMAP_KEY_T); + * + * This function should free the given key, just like the free() function. This + * is used when destroying a hashmap. If you use a hashmap key that doesn’t + * need freeing (like integers) you probably just want to make this a function + * that does nothing. + */ +#ifndef GEHASHMAP_FREE_FUNC + #error "Freeing function for the hashmap key was not set" +#endif + +/* GEHASHMAP_ENTRY_T is the type representing entries in the hashmap while + * GEHASHMAP_T is the type representing the hashmap itself. If GEHASHMAP_NAME + * is set to “foo” then GEHASHMAP_ENTRY_T will be “struct foo_entry” and + * GEHASHMAP_T will be “foo_t”. + */ +#define GEHASHMAP_ENTRY_T GEHASHMAP_CONCAT(struct GEHASHMAP_NAME, _entry) +#define GEHASHMAP_T GEHASHMAP_CONCAT(GEHASHMAP_NAME, _t) + +/* A hashmap entry */ +GEHASHMAP_ENTRY_T { + GEHASHMAP_KEY_T key; /* This entries key */ + GEHASHMAP_VAL_T val; /* This entries value */ + GEHASHMAP_ENTRY_T *next; /* Pointer to the next entry */ +}; + +/* The hashmap */ +typedef struct { + size_t size; /* The number of elements */ + size_t capacity; /* The capacity of the hashmap */ + GEHASHMAP_ENTRY_T **entries; /* A 2D array of hashmap entries */ +} GEHASHMAP_T; + +int (*gehashmap_cmp_func)(GEHASHMAP_KEY_T, + GEHASHMAP_KEY_T) = GEHASHMAP_CMP_FUNC; +void (*gehashmap_free_func)(GEHASHMAP_KEY_T) = GEHASHMAP_FREE_FUNC; +size_t (*gehashmap_hash_func)(GEHASHMAP_KEY_T) = GEHASHMAP_HASH_FUNC; + +/* Function to initialize a new hashmap. Allocation of the hashmap is left up + * to the library user. On error -1 is returned, otherwise 0 is returned. + */ +int +GEHASHMAP_FUNC_NAME(new)(GEHASHMAP_T *map) +{ + *map = (GEHASHMAP_T) { + .size = 0, + .capacity = GEHASHMAP_INITIAL_SIZE, + .entries = calloc(GEHASHMAP_INITIAL_SIZE, + sizeof(GEHASHMAP_ENTRY_T *)) + }; + return map->entries == NULL ? -1 : 0; +} + +/* Function to destroy a hashmap */ +void +GEHASHMAP_FUNC_NAME(free)(GEHASHMAP_T *map) +{ + for (size_t i = 0; i < map->capacity; i++) { + GEHASHMAP_ENTRY_T *entry = map->entries[i]; + while (entry != NULL) { + GEHASHMAP_ENTRY_T *next = entry->next; + gehashmap_free_func(entry->key); + free(entry); + entry = next; + } + } + free(map->entries); +} + +/* Function to resize a hashmap. This function should not really be touched by + * the library user basically ever. On error -1 is returned, otherwise 0 is + * returned. + */ +int +GEHASHMAP_FUNC_NAME(resize)(GEHASHMAP_T *map, size_t new_capacity) +{ + GEHASHMAP_ENTRY_T **new_entries = calloc(new_capacity, + sizeof(GEHASHMAP_ENTRY_T *)); + if (new_entries == NULL) + return -1; + + for (size_t i = 0; i < map->capacity; i++) { + GEHASHMAP_ENTRY_T *entry = map->entries[i]; + while (entry != NULL) { + GEHASHMAP_ENTRY_T *next = entry->next; + size_t hash = gehashmap_hash_func(entry->key) + % new_capacity; + entry->next = new_entries[hash]; + new_entries[hash] = entry; + entry = next; + } + } + + free(map->entries); + map->entries = new_entries; + map->capacity = new_capacity; + + return 0; +} + +/* Function to put a key/value pair into a hashmap. The key is put into the + * hashmap as is, so the user may need to allocate the key themselves if a stack + * allocated key is not appropriate. On error -1 is returned, otherwise 0 is + * returned. + */ +int +GEHASHMAP_FUNC_NAME(put)(GEHASHMAP_T *map, GEHASHMAP_KEY_T key, + GEHASHMAP_VAL_T val) +{ + size_t hash; + GEHASHMAP_ENTRY_T *entry; + + if (map->size + 1 > map->capacity * GEHASHMAP_LOAD_FACTOR) { + if (GEHASHMAP_FUNC_NAME(resize)(map, map->capacity * 2) == -1) + return -1; + } + + hash = gehashmap_hash_func(key) % map->capacity; + entry = map->entries[hash]; + while (entry != NULL) { + if (gehashmap_cmp_func(entry->key, key) == 0) { + entry->val = val; + return 0; + } + entry = entry->next; + } + + if ((entry = malloc(sizeof(GEHASHMAP_ENTRY_T))) == NULL) + return -1; + + entry->key = key; + entry->val = val; + entry->next = map->entries[hash]; + map->entries[hash] = entry; + map->size++; + + return 0; +} + +/* Function to get an element from the hashmap. If “val” is NULL then no value + * will be retrieved. If an element with the given key is found in the hashmap + * the function returns true, otherwise false is returned. + */ +bool +GEHASHMAP_FUNC_NAME(get)(GEHASHMAP_T *map, GEHASHMAP_KEY_T key, + GEHASHMAP_VAL_T *val) +{ + size_t hash = gehashmap_hash_func(key) % map->capacity; + GEHASHMAP_ENTRY_T *entry = map->entries[hash]; + + while (entry != NULL) { + if (gehashmap_cmp_func(entry->key, key) == 0) { + if (val != NULL) + *val = entry->val; + return true; + } + entry = entry->next; + } + + return false; +} + +/* Function to check if an element with a given key is contained within a + * hashmap. This is just a more readable wrapper around the get() function that + * passes NULL as the last argument. + */ +static inline bool +GEHASHMAP_FUNC_NAME(has)(GEHASHMAP_T *map, GEHASHMAP_KEY_T key) +{ + return GEHASHMAP_FUNC_NAME(get)(map, key, NULL); +} + +/* Function to remove an element with a given key from a hashmap. If the value + * was dynamically allocated it will not be freed. The key will be freed + * however as per gehashmap_free_func(). On error -1 is returned, otherwise 0 + * is returned. + */ +int +GEHASHMAP_FUNC_NAME(remove)(GEHASHMAP_T *map, GEHASHMAP_KEY_T key) +{ + size_t hash = gehashmap_hash_func(key) % map->capacity; + GEHASHMAP_ENTRY_T *entry; + + if ((entry = map->entries[hash]) == NULL) + return -1; + + if (gehashmap_cmp_func(entry->key, key) == 0) { + map->entries[hash] = entry->next; + gehashmap_free_func(entry->key); + free(entry); + map->size--; + return 0; + } + + while (entry->next != NULL) { + if (gehashmap_cmp_func(entry->next->key, key) == 0) { + GEHASHMAP_ENTRY_T *next = entry->next; + entry->next = next->next; + gehashmap_free_func(next->key); + free(next); + map->size--; + return 0; + } + entry = entry->next; + } + + return -1; +} + +/* Undefine everything */ +#undef GEHASHMAP_KEY_T +#undef GEHASHMAP_VAL_T +#undef GEHASHMAP_NAME +#undef GEHASHMAP_CMP_FUNC +#undef GEHASHMAP_HASH_FUNC +#undef GEHASHMAP_FREE_FUNC +#undef GEHASHMAP_ENTRY_T +#undef GEHASHMAP_T |