rendered paste body#include "libutil.h"#include "hash_table.h"#include "value.h"#include <stdlib.h>/* Create a new hash table */htable_t* new_htable(int size){ int i = 0; /* safe malloc a new array as the table */ htable_t* new_hash_table = (htable_t*) safe_malloc( sizeof(htable_t) ); new_hash_table->buckets = size; new_hash_table->items = 0; new_hash_table->size = 0; new_hash_table->array = (value_t**) safe_malloc( sizeof(value_t*) * new_hash_table->buckets ); for (i=0; i<new_hash_table->buckets; i++) { new_hash_table->array[i] = NULL; } return new_hash_table;}/* Cleanup the hash table */void destroy_htable(htable_t* hash){ int i = 0; for (i=0; i<hash->buckets; i++) { if (hash->array[i] != NULL) { free(hash->array[i]->word); free(hash->array[i]); } }/* TODO Remove free(hash->array);*/ free(hash);}/* Find term in the hash table */value_t* htable_find_term(htable_t* hash,char* token){ int hash_id = 0; hash_id = hash_str( token, hash->buckets ); while ( hash->array[hash_id] != NULL && strcmp( hash->array[hash_id]->word, token ) != 0 ) { /* linear probe */ ++hash_id; hash_id = hash_id % hash->buckets; } if ( hash->array[hash_id] == NULL ) { /* return the found entry */ return NULL; } else { return hash->array[hash_id]; }}/* Find an id in the hash table */value_t* htable_find_id(htable_t* hash,unsigned int id){ int hash_id = hash_uint( id, hash->buckets ); while ( hash->array[hash_id] != NULL && hash->array[hash_id]->id != id ) { /* linear probe */ ++hash_id; hash_id = hash_id % hash->buckets; } if ( hash->array[hash_id] == NULL ) { /* return the found entry */ return NULL; } else { return hash->array[hash_id]; }}/* Add a new term to the hash table * this is for the forward transformation*/void htable_add_term(htable_t* hash,value_t* new){ int hash_id = 0; if ( new == NULL ) printf("ERROR, new == NULL\n"); /* Rehash when load factor is 50%*/ float load = (float) ((float) hash->items / (float) hash->buckets); if ( load > MAX_LOAD_FACTOR ) { htable_rehash_term(hash); } hash_id = hash_str( new->word, hash->buckets ); while (hash->array[hash_id] != NULL) { /* Linear probing */ ++hash_id; hash_id = hash_id % hash->buckets; } if ( hash->array[hash_id] == NULL ) { hash->array[hash_id] = new; hash->items++; } else { fprintf(stderr, "There is a problem!\n"); }}/* Add an id to the hash table * This is for the reverse transformation*/void htable_add_id(htable_t* hash,value_t* new){ int hash_id = 0; if ( new == NULL ) printf("ERROR, new == NULL\n"); /* Rehash when load factor is 50%*/ float load = (float) ((float) hash->items / (float) hash->buckets); if ( load > MAX_LOAD_FACTOR ) { htable_rehash_id(hash); } hash_id = hash_uint( new->id, hash->buckets ); while (hash->array[hash_id] != NULL) { /* Linear probing */ ++hash_id; hash_id = hash_id % hash->buckets; } if ( hash->array[hash_id] == NULL ) { hash->array[hash_id] = new; hash->items++; } else { fprintf(stderr, "There is a problem!\n"); }}void htable_rehash_id(htable_t* hash){ htable_t* new_ht; int size, i; /* Increase the size of the table */ size = hash->items * 4; new_ht = new_htable(size); for (i=0; i<hash->buckets; i++) { if ( hash->array[i] != NULL ) { htable_add_id(new_ht, hash->array[i]); } } hash->buckets = size; free(hash->array); hash->array = new_ht->array; /* TODO: Potential leaks here */ free(new_ht);}void htable_rehash_term(htable_t* hash){ htable_t* new_ht; int size, i; /* Increase the size of the table */ size = hash->items * 4; new_ht = new_htable(size); for (i=0; i<hash->buckets; i++) { if ( hash->array[i] != NULL ) { htable_add_term(new_ht, hash->array[i]); } } hash->buckets = size; free(hash->array); hash->array = new_ht->array; /* TODO: Potential leaks here */ free(new_ht);}value_t** remap_freq_htable(htable_t* htable){ /* First sort table */ insertion_sort( htable->array, htable->buckets, &cntcmphash ); htable->buckets = htable->items; /* Remap the ids */ int i = 0; for (i=0; i<htable->buckets; i++) { if (htable->array[i] != NULL) { htable->array[i]->id = i; } } value_t** narray = (value_t**) safe_malloc( sizeof(value_t**) * htable->items ); i = 0; while ( htable->array[i] != NULL ) { narray[i] = htable->array[i]; i++; } free(htable->array); htable->array = narray; return htable->array;}void dump_htable(htable_t* htable) { int i; int count = 0; for (i=0; i<htable->buckets; ++i) { /* Debug */ if ( htable->array[i] != NULL ) { count++; } } int v = 0; for (v=0; v<10; v++) { fprintf(stderr, "ID:%d - %d : \"%s\"\n", htable->array[v]->id, htable->array[v]->count, htable->array[v]->word); } fprintf(stderr, "count: %d\n", count);}/* Paul Hsieh's string hashing function modified to suit my needs. * NEVER try to write your own hash function unless you have a * few years to waste ... * http://www.azillionmonkeys.com/qed/hash.html */size_thash_str (char *buf, size_t max){ size_t tmp, result; int rem; size_t len = strlen (buf); result = len; if ((len <= 0) || (buf == NULL)) return 0; rem = len & 3; len >>= 2; /* Main loop */ for (; len > 0; len--) { result += get16bits (buf); tmp = (get16bits (buf + 2) << 11) ^ result; result = ( result << 16 ) ^ tmp; buf += 2 * sizeof (unsigned short); result += result >> 11; } /* Handle end cases */ switch (rem) { case 3: result += get16bits (buf); result ^= result << 16; result ^= buf[sizeof (unsigned short)] << 18; result += result >> 11; break; case 2: result += get16bits ( buf ); result ^= result << 11; result += result >> 17; break; case 1: result += *buf; result ^= result << 10; result += result >> 1; } /* Force "avalanching" of final 127 bits */ result ^= result << 3; result += result >> 5; result ^= result << 4; result += result >> 17; result ^= result << 25; result += result >> 6; return ((result) % (max - 1));}/* Thanks to:** http://www.concentric.net/~Ttwang/tech/inthash.htm */static size_tint_hash (unsigned int key){ key += ~(key << 15); key ^= (key >> 10); key += (key << 3); key ^= (key >> 6); key += ~(key << 11); key ^= (key >> 16); return (key);}/* A simple throttled integer hashing function. Works pretty * well AFAIKT */size_thash_uint (unsigned int buf, size_t max){ return (int_hash (buf) % (max - 1));}