source: proiecte/PDAD/trunk/nodeslocation/mpi/hashmap.c @ 154

/*
 * 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