#include "libutil.h"#include "hash_table.h"#include "value.h"#include <stdlib.h>/* Create a new hash table */htable_t* new_htable(int size){ printf ("TODO - New hash table!\n"); 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 = DEF_HTABLE_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){ printf ("TODO - Destroy table!\n"); int i = 0; for (i=0; i<hash->size; i++) { if (hash->array[i] != NULL) { free(hash->array[i]->word); free(hash->array[i]->freq); free(hash->array[i]); } } free(hash->array); free(hash);}/* Find term in the hash table */value_t* htable_find_term(htable_t* hash,char* token){ unsigned int hash_id = hash_str( token, MAX_WORD_LEN ); if ( hash->array[hash_id] != NULL && strcmp( hash->array[hash_id]->word, token ) != 0 ) { /* linear probe */ hash_id = ++hash_id % hash->buckets; printf("Probing, "); } else { /* return the found entry */ value_t* tmp = hash->array[hash_id]; return hash->array[hash_id]; }}/* Find an id in the hash table */value_t* htable_find_id(htable_t* hash,unsigned int 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){ if ( new == NULL ) printf("ERROR, new == NULL\n"); /* Rehash when load factor is 50%*/ if ( (float)((float)hash->items / (float)hash->buckets) > MAX_LOAD_FACTOR ) { htable_rehash_term(hash); printf ("...Load over 50% rehashing...\n"); } int hash_id = hash_str( new->word, MAX_WORD_LEN ); while (hash->array[hash_id] != NULL) { /* Linear probing */ 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){ printf ("TODO - Add ID!\n");}void htable_rehash_id(htable_t* hash){ printf ("TODO - Rehash ID!\n");}void htable_rehash_term(htable_t* hash){ printf ("TODO - Rehash Term!\n");}value_t** remap_freq_htable(htable_t* htable){ printf ("TODO - Remap freq table!\n"); value_t* tmp = htable->array; return tmp;}void dump_htable(htable_t* htable) { fprintf(stderr, "Dumping Hash Table...\n"); int i; for (i=0; i<htable->buckets; ++i) { /* Debug */ if ( htable->array[i] == NULL ) fprintf(stderr, "Array is NULL!\n"); if ( htable->array[i]->word != NULL ) fprintf(stderr, "%s, ", htable->array[i]->word); fprintf(stderr, "%d, ", htable->array[i]->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));}