From 192dd9d656742b1931ae44f05e1604ff18d64d3b Mon Sep 17 00:00:00 2001 From: Cara Salter Date: Thu, 23 Mar 2023 15:30:21 -0400 Subject: Work on game.h --- src/game.h | 21 ++++-- src/hash.c | 243 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ src/hash.h | 36 +++++++++ 3 files changed, 292 insertions(+), 8 deletions(-) create mode 100644 src/hash.c create mode 100644 src/hash.h diff --git a/src/game.h b/src/game.h index 2fe6d3d..a092508 100644 --- a/src/game.h +++ b/src/game.h @@ -16,21 +16,26 @@ * ===================================================================================== */ +#include +#include "login.h" #ifndef _GAME_H #define _GAME_H -enum RequestType { - Msg, +typedef enum RequestType { MoveTo, - Attack -}; + Attack, +} RequestType; -typedef struct { - enum RequestType type; - char* args[]; +typedef struct Request{ + RequestType type; + struct Request* nxt; } Request; -int submit_request(Request req); +typedef struct { + pthread_mutex_t lock; + Request* queue_start; +} Game; +void init_game(); #endif diff --git a/src/hash.c b/src/hash.c new file mode 100644 index 0000000..edb3139 --- /dev/null +++ b/src/hash.c @@ -0,0 +1,243 @@ +/* + * ===================================================================================== + * + * Filename: hash.c + * + * Description: Implementation of a basic hashmap + * + * Version: 1.0 + * Created: 12/09/2022 07:24:38 PM + * Revision: none + * Compiler: gcc + * + * Author: YOUR NAME (), * Organization: + * + * ===================================================================================== + */ +#include +#include +#include "hash.h" +#include "clog.h" + + +/*----------------------------------------------------------------------------- + * We're defining the structs inside the .c file because really no one should be + * messing around with the internals except through the exported functions + *-----------------------------------------------------------------------------*/ + +typedef struct _map_element { + int key; + int is_used; + any_type value; +} map_element; + +typedef struct _map { + int max_size; + int cur_size; + map_element* data; +} map; + + +/* + * === FUNCTION ====================================================================== + * Name: map_init + * Description: Initializes a new hashmap + * ===================================================================================== + */ +hash_map map_init () { + map* m = (map*) malloc(sizeof(map)); + + m->data = (map_element*) calloc(512, sizeof(map_element)); + + m->max_size = 512; + m->cur_size = 0; + return m; +} /* ----- end of function map_init ----- */ + + +/* + * === FUNCTION ====================================================================== + * Name: hash_int + * Description: + * ===================================================================================== + */ +unsigned int hash_int (map* ma, unsigned int key) { + + /*----------------------------------------------------------------------------- + * This is a pretty basic hashing function, basically we're still using + * modulo but in such a way that collisions are less likely than if we just + * used it raw. + * + * The advantage of this is that it doesn't matter the max size of the + * hashmap, it doesn't have to be sufficiently removed from a power of 2 + * + * See: Hashing by Multiplication here: https://en.wikipedia.org/wiki/Hash_table#Hash_function + *-----------------------------------------------------------------------------*/ + return fmodf(floor(ma->max_size * (key * fmodf(0.3, 1.0))), ma->max_size); +} /* ----- end of function hash_int ----- */ + + +/* + * === FUNCTION ====================================================================== + * Name: hash_get_idx + * Description: + * ===================================================================================== + */ +int hash_get_idx (hash_map* m, int key) { + int c; + map* ma = (map*) m; + + if (ma->cur_size == ma->max_size) { + // Hash map is full, we need to exit now + return -2; + } + + c = hash_int(ma, key); /* This is the theoretically ideal hash index */ + + /*----------------------------------------------------------------------------- + * Pretty basic collision resolution. Needs to be able to resolve them + *-----------------------------------------------------------------------------*/ + + for(int i = 0; i < ma->max_size; i++) { + if (ma->data[c].is_used == 0) { + /*----------------------------------------------------------------------------- + * This index isn't being used, we can return it + *-----------------------------------------------------------------------------*/ + return c; + } + + if (ma->data[c].key == key && ma->data[c].is_used == 1) { + + /*----------------------------------------------------------------------------- + * This index is being used, but by this key, so we can return it + *-----------------------------------------------------------------------------*/ + return c; + } + + + /*----------------------------------------------------------------------------- + * This index is being used but not by this key. Increment the index + * modulo the map size and try again + *-----------------------------------------------------------------------------*/ + c = (c + 1) % ma->max_size; + } + return -2; +} /* ----- end of function hash_get_idx ----- */ + + +/* + * === FUNCTION ====================================================================== + * Name: map_resize + * Description: + * ===================================================================================== + */ +int map_resize(hash_map in) { + int i; + int old_size; + map_element* cur; + + /* New elements! */ + map *m = (map*) in; + map_element* tmp = (map_element*) calloc(2 * m->max_size, sizeof(map_element)); + if (!tmp) return 4; /* We're out of memory! */ + + cur = m->data; + m->data = tmp; + + old_size = m->max_size; + m->max_size = 2 * old_size; + m->cur_size = 0; + + /* Rehash */ + for (i = 0; i < old_size; i++) { + int status = map_add(m, cur[i].key, cur[i].value); + if (status != 0) { + return status; + } + } + + free(cur); + return 0; +} /* ----- end of function map_resize ----- */ + +/* + * === FUNCTION ====================================================================== + * Name: map_add + * Description: + * ===================================================================================== + */ +int map_add(hash_map m, int key, any_type val) { + map* ma = (map*) m; + + int h = hash_get_idx(m, key); + + while (h == -2) { + if (map_resize(m) == 4) { + return 4; + } + h = hash_get_idx(m, key); + } + + ma->data[h].value = val; + ma->data[h].key = key; + ma->data[h].is_used = 1; + return 0; +} /* ----- end of function map_add ----- */ + + +/* + * === FUNCTION ====================================================================== + * Name: map_get + * Description: + * ===================================================================================== + */ +int map_get (hash_map m, int key, any_type* val) { + map* ma = (map*) m; + + int h = hash_get_idx(m, key); + + if (ma->data[h].is_used == 1 && ma->data[h].key == key) { + *val = ma->data[h].value; + return 0; + } + return -3; +} /* ----- end of function map_get ----- */ + + +/* + * === FUNCTION ====================================================================== + * Name: map_del + * Description: + * ===================================================================================== + */ +int map_del (hash_map m, int key) { + map* ma = (map*) m; + + int h = hash_get_idx(m, key); + + if (ma->data[h].is_used == 1 && ma->data[h].key == key) { + ma->data[h].is_used = 0; + ma->data[h].key = 0; + } + + return 0; +} /* ----- end of function map_del ----- */ + +/* + *map_free cleans up the memory used by a hashmap + */ +void map_free(hash_map m) { + map* ma = (map*) m; + + free(ma->data); + free(ma); +} + +/* + *map_len returns the current length of the hashmap + */ +int map_len(hash_map m) { + map* ma = (map*) m; + + return ma->cur_size; +} diff --git a/src/hash.h b/src/hash.h new file mode 100644 index 0000000..3806799 --- /dev/null +++ b/src/hash.h @@ -0,0 +1,36 @@ +/* + * ===================================================================================== + * + * Filename: hash.h + * + * Description: Prototypes and structs for the hashmap implementation + * + * Version: 1.0 + * Created: 12/09/2022 07:35:39 PM + * Revision: none + * Compiler: gcc + * + * Author: Cara Salter (muirrum), cara@devcara.com + * Organization: + * + * ===================================================================================== + */ + +#include +#include + +typedef void* any_type; + +typedef any_type hash_map; + +hash_map map_init(); + +int map_add(hash_map m, int key, any_type value); + +int map_get(hash_map m, int key, any_type* value); + +int map_del(hash_map m, int key); + +void map_free(hash_map m); + +int map_len(hash_map m); -- cgit v1.2.3