Work on game.h

1 files changed, 243 insertions, 0 deletions

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 <stdlib.h>
+#include <math.h>
+#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;
+}