rendered paste body#include "libutil.h"#include "hash_table.h"#include "value.h"#include <stdlib.h>htable_t* new_htable(int size){ htable_t* htable; htable = (htable_t*) safe_malloc(sizeof(htable_t)); /*useless metic*/ htable->size=0; /*max items*/ htable->buckets=size; /*currently used items*/ htable->items=0; htable->array = (value_t**) safe_malloc( sizeof(value_t*) * htable->buckets); int i=0; htable->size= sizeof(htable_t*)+ (sizeof(value_t*) * htable->buckets); for (i=0; i< htable->buckets; i++){ htable->array[i] = NULL; } return htable; }void destroy_htable(htable_t* hash){ int i; for(i=0; i<hash->buckets; i++){ if(hash->array[i]!=NULL){ free(hash->array[i]->word); } } free(hash->array); free(hash);}value_t* htable_find_term(htable_t* hash,char* token){ size_t hash_address= 0; hash_address=hash_str(token, hash->buckets); while(hash->array[hash_address]!=NULL && token != NULL && strcmp(hash->array[hash_address]->word, token) != 0){ hash_address = ++hash_address % hash->buckets; } if(hash->array[hash_address]==NULL){ return NULL; }else if(strcmp(hash->array[hash_address]->word, token) == 0){ return hash->array[hash_address]; }else{ /*should never get here!*/ printf("Error, should never get here"); getchar(); /*so puase if you do*/ return NULL; } }value_t* htable_find_id(htable_t* hash,unsigned int id){ size_t hash_address= 0; hash_address=hash_uint(id, hash->buckets); while(hash->array[hash_address]!=NULL && hash->array[hash_address]->id != id){ hash_address = ++hash_address % hash->buckets; } if(hash->array[hash_address]==NULL){ return NULL; }else if(hash->array[hash_address]->id == id){ return hash->array[hash_address]; }else{ /*should never get here!*/ printf("Error, should never get here"); getchar(); /*so puase if you do*/ return NULL; } }void htable_add_term(htable_t* hash, value_t* new){ size_t hash_address; if( (float) ( (float) hash->items / (float) hash->buckets) > MAX_LOAD_FACTOR){ htable_rehash_term(hash); } hash_address=hash_str(new->word, hash->buckets); while(hash->array[hash_address]!=NULL){ hash_address= ++hash_address % hash->buckets; } hash->array[hash_address]=new; hash->items=hash->items+1; }void htable_add_id(htable_t* hash,value_t* new){ size_t hash_address; if( (float) ( (float) hash->items / (float) hash->buckets) > MAX_LOAD_FACTOR){ htable_rehash_id(hash); } hash_address=hash_uint(new->id, hash->buckets); while(hash->array[hash_address]!=NULL){ hash_address= ++hash_address % hash->buckets; } hash->array[hash_address]=new; hash->items=hash->items+1; }void htable_rehash_id(htable_t* hash){ int size,i; size = hash->buckets*2; htable_t* newTable = new_htable(size); for(i=0;i<hash->buckets; i++){ if(hash->array[i] != NULL){ htable_add_id(newTable, hash->array[i]); } } free(hash->array); hash->array = newTable->array; hash->buckets=size; hash->size= sizeof(htable_t)+ (sizeof(value_t) * hash->buckets); for(i=0;i<hash->buckets;i++) { if(hash->array[i]==NULL){ hash->size=sizeof(hash->array[i]); } }}void htable_rehash_term(htable_t* hash){ int size,i; size = hash->buckets*2; htable_t* newTable = new_htable(size); for(i=0;i<hash->buckets; i++){ if(hash->array[i] != NULL){ htable_add_term(newTable, hash->array[i]); } } free(hash->array); hash->array = newTable->array; hash->buckets=size; hash->size= sizeof(htable_t*)+ (sizeof(value_t*) * hash->buckets);}value_t** remap_freq_htable(htable_t* htable){ insertion_sort(htable->array, htable->buckets, nullcntcmp ); int i = 0; for (i=0; i<htable->buckets; i++) { if (htable->array[i] != NULL) { htable->array[i]->id = i; } } value_t** limitedArray = (value_t**) safe_malloc(htable->items * sizeof(value_t**) ); i = 0; while ( htable->array[i] != NULL ) { limitedArray[i] = htable->array[i]; i++; } htable->buckets = htable->items; return limitedArray;}/* 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));}int unique_words_htable(htable_t *htable){ return htable->items;}