t len)
{
unsigned int i;
unsigned long crc32val = 0;
for (i = 0; i < len; i ++) {
crc32val = crc32_tab[(crc32val ^ s[i]) & 0xff] ^ (crc32val >> 8);
}
return crc32val;
}
/**
* Hashing function for a string
*/
static unsigned int _find_hash_index(hashmap_map_t * m, char* keystring){
unsigned long key = crc32((unsigned char*)(keystring), strlen(keystring));
/* Robert Jenkins' 32 bit Mix Function */
key += (key << 12);
key ^= (key >> 22);
key += (key << 4);
key ^= (key >> 9);
key += (key << 10);
key ^= (key >> 2);
key += (key << 7);
key ^= (key >> 12);
/* Knuth's Multiplicative Method */
key = (key >> 3) * 2654435761;
return key % m->table_size;
}
/**
* Return the integer of the location in data to store the point to the item,
* or HMAP_E_OVERFLOW.
*/
static int _hashmap_hash(hmap_t in, char* key){
int curr;
int i;
hashmap_elem_t *elem;
hashmap_map_t *m = (hashmap_map_t *) in;
/* If full, return immediately */
if (m->size >= (m->table_size/2)) {
return HMAP_E_OVERFLOW;
}
/* Find the best index */
curr = _find_hash_index(m, key);
/* Linear probing */
for (i = 0; i< HMAP_CHAIN_LENGTH; i++) {
elem = m->elems + curr;
if(elem->used == unused_0) {
return curr;
}
if(elem->used == used_1 && (!strcmp(elem->key, key))) {
return curr;
}
curr = (curr + 1) % m->table_size;
}
return HMAP_E_OVERFLOW;
}
/**
* Doubles the size of the hashmap, and rehashes all the elements
*/
static int _hashmap_rehash(hmap_t in){
int i;
int old_size;
hashmap_elem_t *curr;
hashmap_elem_t *elem;
/* Setup the new elements */
hashmap_map_t *m = (hashmap_map_t *) in;
hashmap_elem_t *temp = (hashmap_elem_t *) calloc(2 * m->table_size, sizeof(hashmap_elem_t));
if (!temp) {
return HMAP_E_OUTMEM;
}
/* Update the array */
curr = m->elems;
m->elems = temp;
/* Update the size */
old_size = m->table_size;
m->table_size = 2 * m->table_size;
m->size = 0;
/* Rehash the elements */
for (i = 0; i < old_size; i++){
int status;
elem = curr + i;
if (elem->used == unused_0) {
continue;
}
status = hashmap_put(m, elem->key, elem->data);
if (status != HMAP_S_OK) {
return status;
}
}
free(curr);
return HMAP_S_OK;
}
/**
* Create an empty hashmap
*/
hmap_t hashmap_create() {
hashmap_map_t* m = (hashmap_map_t*) malloc(sizeof(hashmap_map_t));
if (!m) {
exit(HMAP_E_OUTMEM);
}
m->elems = (hashmap_elem_t*) calloc(HMAP_INITIAL_SIZE, sizeof(hashmap_elem_t));
if (!m->elems) {
free(m);
exit(HMAP_E_OUTMEM);
}
m->table_size = HMAP_INITIAL_SIZE;
m->size = 0;
return m;
}
/**
* Add a pair of key-value to the hashmap
*/
int hashmap_put(hmap_t in, char* key, void_ptr value){
int index;
hashmap_map_t *m;
hashmap_elem_t *elem;
m = (hashmap_map_t *) in;
/* Find a place to put our value */
index = _hashmap_hash(in, key);
while (index == HMAP_E_OVERFLOW) {
if (_hashmap_rehash(in) == HMAP_E_OUTMEM) {
return HMAP_E_OUTMEM;
}
index = _hashmap_hash(in, key);
}
/* Set the elems */
elem = m->elems + index;
elem->data = value;
elem->key = key; /* only set to a reference */
elem->used = used_1;
m->size++;
return HMAP_S_OK;
}
/**
* Get your pointer out of the hashmap with a key
*/
int hashmap_get(hmap_t in, char* key, void_ptr *value){
int curr;
int i;
hashmap_map_t *m;
hashmap_elem_t *elem;
m = (hashmap_map_t *) in;
/* Find element location */
curr = _find_hash_index(m, key);
/* Linear probing, i |