/*
 * hashmap.c
 * Copyright (c) 2009 Vedant Kumar
 * 
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 * 
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 * THE SOFTWARE.
 */
#include <stdio.h>
#include <string.h>
#include "hashmap_public.h"

struct key_val_map {
    key k;
    val v;
};

struct hashmap {
    key_val_map *map;
    uint32_t size;
    uint32_t capacity;
    uint32_t (*hash_fn)(key);
    bool (*eq_fn)(key, key);
#ifdef HMAP_DESTRUCTORS
    void (*del_fn)(val);
#endif
#ifdef HMAP_THREAD_SAFE
    sem_t lock;
#endif
};

// hashmaps need a hash function, an equality function, and a destructor
hashmap* mk_hmap(uint32_t (*hash_fn)(key),
		 bool (*eq_fn)(key, key)
#ifdef HMAP_DESTRUCTORS
		 , void (*del_fn)(val)
#endif
		 ) {
    
    hashmap* hmap = (hashmap*) malloc(sizeof(hashmap));
    hmap->map = (key_val_map*) malloc(sizeof(key_val_map) * HMAP_PRESET_SIZE);
    bzero(hmap->map, sizeof(key_val_map) * HMAP_PRESET_SIZE); 
    hmap->size = 0;
    hmap->capacity = HMAP_PRESET_SIZE;
    hmap->hash_fn = hash_fn;
    hmap->eq_fn = eq_fn;
#ifdef HMAP_DESTRUCTORS
    hmap->del_fn = del_fn;
#endif
#ifdef HMAP_THREAD_SAFE
    sem_init(&hmap->lock, 0, 1);
#endif
    return hmap;
}

void free_hmap(hashmap* hmap) {
#ifdef HMAP_THREAD_SAFE
    sem_wait(&hmap->lock);
#endif

#ifdef HMAP_DESTRUCTORS
    static uint32_t it;
    for (it=0; it < hmap->size; ++it) {
	if (hmap->map[it].v != NULL) {
	    hmap->del_fn(hmap->map[it].v);
	}
    }
#endif

    free(hmap->map);
	
#ifdef HMAP_THREAD_SAFE
    sem_post(&hmap->lock);
#endif

    free(hmap);
}

static void __oa_hmap_add(key_val_map* map, uint32_t size, 
			 uint32_t (*hash_fn)(key),
			 key in, val out) {
    static uint32_t hash;
    hash = hash_fn(in) % size;
	
    uint32_t count = 0; 
    while (map[hash].k != NULL) {
	hash = (hash + 1) % size;
	count++; 
	if (count > size) { 
	    fprintf(stdout, "Hashmap has no free entries \n"); 
	    exit(0);
	}
    }
	
    map[hash].k = in;
    map[hash].v = out;
	
}

bool __hmap_add(hashmap* hmap, key in, val out) {
#ifdef HMAP_THREAD_SAFE
    sem_wait(&hmap->lock);
#endif

    // performace degrades after a certain load
    if (((float) hmap->size) / hmap->capacity > 0.70) {
	key_val_map* temp = (key_val_map*) malloc(sizeof(key_val_map) * hmap->capacity * HMAP_GROWTH_RATE);
	if (temp != NULL) {
	    //hmap->capacity *= HMAP_GROWTH_RATE;
	} else {
#ifdef HMAP_THREAD_SAFE
	    sem_post(&hmap->lock);
#endif
	    // we're out of memory
	    return false;
	}
	
	// init new hashmap
	bzero(temp, sizeof(key_val_map) * hmap->capacity * HMAP_GROWTH_RATE);

	// re-posn all elements
	static uint32_t it;
	for (it=0; it < hmap->capacity; ++it) {
	    if (hmap->map[it].k != NULL) {
		__oa_hmap_add(temp, hmap->capacity * HMAP_GROWTH_RATE, hmap->hash_fn, hmap->map[it].k, hmap->map[it].v);
	    }
	}
		
	// swap out the old map with the new one
	free(hmap->map);
	hmap->map = temp;
	hmap->capacity *= HMAP_GROWTH_RATE;
    }
	
    __oa_hmap_add(hmap->map, hmap->capacity, hmap->hash_fn, in, out);
    hmap->size += 1;

#ifdef HMAP_THREAD_SAFE
    sem_post(&hmap->lock);
#endif
    return true;
}

val __hmap_get(hashmap* hmap, key in) {
#ifdef HMAP_THREAD_SAFE
    sem_wait(&hmap->lock);
#endif

    static uint32_t hash;
    hash = hmap->hash_fn(in) % hmap->capacity;
    
    while (hmap->map[hash].k != NULL) {
	if (hmap->eq_fn(in, hmap->map[hash].k)) {
#ifdef HMAP_THREAD_SAFE
	    sem_post(&hmap->lock);
#endif			
	    return hmap->map[hash].v;
	}
		
	hash = (hash + 1) % hmap->capacity;
    }

	
#ifdef HMAP_THREAD_SAFE
    sem_post(&hmap->lock);
#endif
	
    return NULL;
}

#ifdef HMAP_MAKE_HASHFN
// Robert Jenkins' 32 bit integer hash function
uint32_t int_hash_fn(key in) {
    static uint32_t a;
    a = *((uint32_t*) in);
	
    a = (a+0x7ed55d16) + (a<<12);
    a = (a^0xc761c23c) ^ (a>>19);
    a = (a+0x165667b1) + (a<<5);
    a = (a+0xd3a2646c) ^ (a<<9);
    a = (a+0xfd7046c5) + (a<<3);
    a = (a^0xb55a4f09) ^ (a>>16);
	
    return a;
}

bool int_eq_fn(key a, key b) {
    return *((uint32_t*) a) == *((uint32_t*) b) ? true : false;
}

#endif