/*
 * =====================================================================================
 *
 *       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;
}