#ifndef HASH_H
#define HASH_H
#include<stdio.h>
typedef struct hash_t* HASH;
typedef unsigned int (*hash_func)(const char* key, int mod);
enum val_type { H_NIL, H_INT, H_CHAR, H_LONG, H_DOUBLE, H_PTR };
typedef struct val_t {
enum val_type type;
union {
int n;
char ch;
long l;
double d;
void* pt;
} val;
} val_t;
HASH hash_create();
void hash_delete(HASH hash);
HASH hash_set(HASH me, const char* key, val_t val);
HASH hash_set_i(HASH me, const char* key, int val);
HASH hash_set_c(HASH me, const char* key, char val);
HASH hash_set_l(HASH me, const char* key, long val);
HASH hash_set_d(HASH me, const char* key, double val);
HASH hash_set_p(HASH me, const char* key, void* val);
val_t hash_get(HASH me, const char* key);
int hash_get_i(HASH me, const char* key);
char hash_get_c(HASH me, const char* key);
long hash_get_l(HASH me, const char* key);
double hash_get_d(HASH me, const char* key);
void* hash_get_p(HASH me, const char* key);
HASH hash_rehash(HASH me);
HASH hash_change_func(HASH me, hash_func func);
int hash_is_nil(val_t v);
void hash_print_status(FILE* fp, HASH me);
#endif /* HASH_H */
#include<stdio.h>
#include<limits.h>
#include<assert.h>
#include<sys/time.h>
#define NUM (1000 * 20)
unsigned int horner_rule(const char* key, int mod){
unsigned char val;
if(!key){ return 0; }
if(*key == '\0'){ return 0; }
val = (unsigned char)(*key) % mod;
return ( val + horner_rule(key+1, mod) * ((977) % mod)) % mod;
}
unsigned int fucked_hash(const char* key, int mod){
unsigned char val;
if(!key){ return 0; }
if(*key == '\0'){ return 0; }
val = (unsigned char)(*key) % mod;
return ( val + fucked_hash(key+1, mod) ) % mod;
}
double interval(struct timeval* start, struct timeval* end){
double st = (double)start->tv_sec + (double)start->tv_usec * 1e-6;
double en = (double)end->tv_sec + (double)end->tv_usec * 1e-6;
return en-st;
}
void benchmark(const char* message, hash_func func){
struct timeval start, end;
gettimeofday(&start, NULL);
{
int i;
char key[64];
HASH h = hash_create();
hash_change_func(h, func);
for( i=0; i<NUM; i++ ){
sprintf(key, "key%d", i);
hash_set_i(h, key, i);
assert(i == hash_get_i(h, key));
}
hash_delete(h);
}
gettimeofday(&end, NULL);
fprintf(stderr, "%s took:[%lf]\n", message, interval(&start, &end));
}
int main(){
benchmark("fucked_hash", fucked_hash);
benchmark("horner_rule", horner_rule);
return 0;
}
#include<stdlib.h>
#include<string.h>
#include<limits.h>
#define eq(lhs, rhs) ( strcmp( (lhs), (rhs) ) == 0 )
#define free(pt) if(pt) free(pt)
#ifndef NON_PRIME
static long primes[] = {
8 + 3,
16 + 3,
32 + 5,
64 + 3,
128 + 3,
256 + 27,
512 + 9,
1024 + 9,
2048 + 5,
4096 + 3,
8192 + 27,
16384 + 43,
32768 + 3,
65536 + 45,
131072 + 29,
262144 + 3,
524288 + 21,
1048576 + 7,
2097152 + 17,
4194304 + 15,
8388608 + 9,
16777216 + 43,
33554432 + 35,
67108864 + 15,
134217728 + 29,
268435456 + 3,
536870912 + 11,
1073741824 + 85,
0
};
#else
static long primes[] = {
8 ,
16 ,
32 ,
64 ,
128 ,
256 ,
512 ,
1024 ,
2048 ,
4096 ,
8192 ,
16384 ,
32768 ,
65536 ,
131072 ,
262144 ,
524288 ,
1048576 ,
2097152 ,
4194304 ,
8388608 ,
16777216 ,
33554432 ,
67108864 ,
134217728 ,
268435456 ,
536870912 ,
1073741824 ,
0
};
#endif /* NON_PRIME */
typedef struct hash_entry_t {
char* key;
val_t val;
struct hash_entry_t* next;
} hash_entry_t;
typedef struct hash_t {
long num_slot;
long num_elem;
hash_func hash;
hash_entry_t** slot;
} hash_t;
static val_t hash_nil();
static hash_entry_t** hash_slot_create(long num);
static void hash_slot_delete(hash_entry_t** h);
static void hash_all_entry_delete(hash_entry_t** slot, int num);
static hash_entry_t* hash_entry_create(const char* key, val_t val);
static void hash_entry_delete(hash_entry_t* slot);
static void hash_put_entry(HASH me, hash_entry_t* entry);
static void hash_put_synonym(hash_entry_t* dest, hash_entry_t* entry);
static val_t hash_get_synonym(hash_entry_t* dest, const char* key);
static long hash_get_new_size(long num_elem);
static unsigned int default_hash(const char* key, int mod);
static unsigned int default_hash(const char* key, int mod){
unsigned char val;
if(!key){ return 0; }
if(*key == '\0'){ return 0; }
val = (unsigned char)(*key) % mod;
return ( val + default_hash(key+1, mod) * ((UCHAR_MAX+1) % mod)) % mod;
}
HASH hash_create(){
HASH ret = (HASH)malloc(sizeof(hash_t));
if(!ret){
return NULL;
}
ret->num_slot = 11;
ret->num_elem = 0;
ret->hash = default_hash;
ret->slot = hash_slot_create(ret->num_slot);
if(!ret->slot){
hash_delete(ret);
return NULL;
}
return ret;
}
void hash_delete(HASH h){
if(!h){ return; }
if(h->slot){
hash_all_entry_delete(h->slot, h->num_slot);
hash_slot_delete(h->slot);
}
free(h);
}
HASH hash_set(HASH me, const char* key, val_t val){
if( !me ){ return NULL; }
if( (double)me->num_elem / (double)me->num_slot > 0.5 ){
hash_rehash(me);
}
hash_put_entry(me, hash_entry_create(key, val));
me->num_elem++;
return me;
}
HASH hash_change_func(HASH me, hash_func func){
if( !me || !func ){ return NULL; }
me->hash = func;
return hash_rehash(me);
}
val_t hash_get(HASH me, const char* key){
unsigned int pos;
if( !me ){ return hash_nil(); }
pos = me->hash(key, me->num_slot);
return hash_get_synonym(me->slot[pos], key);
}
long hash_get_new_size(long num_elem){
long target = num_elem * 4;
long* pt;
for( pt = primes; *pt; ++pt ){
if( *pt > target ){
return *pt;
}
}
return -1;
}
HASH hash_rehash(HASH me){
int i;
hash_t tmp = { 0, 0, NULL, NULL };
if(!me){ return NULL; }
fprintf(stderr, " before:\n");
hash_print_status(stderr, me);
tmp.hash = me->hash;
tmp.num_slot = hash_get_new_size(me->num_elem);
if( tmp.num_slot < 0 ){ return NULL; }
tmp.slot = hash_slot_create(tmp.num_slot);
if(!tmp.slot){ return NULL; }
for( i=0; i < me->num_slot; i++ ){
hash_entry_t* e;
for( e = me->slot[i]; e; e = e->next ){
hash_set(&tmp, e->key, e->val);
}
}
hash_all_entry_delete(me->slot, me->num_slot);
hash_slot_delete(me->slot);
me->num_slot = tmp.num_slot;
me->num_elem = tmp.num_elem;
me->slot = tmp.slot;
fprintf(stderr, " after:\n");
hash_print_status(stderr, me);
return me;
}
void hash_print_status(FILE* fp, HASH me){
int i;
int synonym = 0;
int max_depth = 0;
for( i=0; i < me->num_slot; i++ ){
hash_entry_t* e = me->slot[i];
if(e){
int depth = 0;
e = e->next;
while( e ){
synonym++;
depth++;
e = e->next;
}
max_depth = (depth>max_depth) ? depth : max_depth;
}
}
fprintf(fp, " [%ld]slots [%ld]elements [%d]synonyms [%d]max depth\n", me->num_slot, me->num_elem, synonym, max_depth);
}
int hash_get_enough_size(int num){
int ret = 1;
while(ret<num)
ret *= 2;
return ret;
}
hash_entry_t** hash_slot_create(long num){
int enough = hash_get_enough_size(num);
hash_entry_t** ret = (hash_entry_t**)malloc(sizeof(hash_entry_t*) * enough);
if(!ret){
return NULL;
}
{ /* init slots */
int i;
for( i=0; i<num; i++ ){
ret[i] = NULL;
}
}
return ret;
}
void hash_slot_delete(hash_entry_t** p){
if(p){
free(p);
}
}
hash_entry_t* hash_entry_create(const char* key, val_t val){
hash_entry_t* ret = (hash_entry_t*)malloc(sizeof(hash_entry_t));
if(!ret){
return NULL;
}
ret->next = NULL;
ret->key = strdup(key);
if(!ret->key){
hash_entry_delete(ret);
return NULL;
}
ret->val = val;
return ret;
}
void hash_all_entry_delete(hash_entry_t** slot, int num){
if(!slot || num < 0){ return; }
{
int i;
for( i=0; i<num; i++ ){
hash_entry_delete(slot[i]);
}
}
}
void hash_entry_delete(hash_entry_t* entry){
hash_entry_t* next;
if(!entry){ return; }
next = entry->next;
free(entry->key);
free(entry);
hash_entry_delete(next);
}
void hash_put_entry(HASH me, hash_entry_t* entry){
unsigned int pos;
if( !me || !me->slot || !entry ){ return; }
pos = me->hash(entry->key, me->num_slot);
if(me->slot[pos]){
hash_put_synonym(me->slot[pos], entry);
} else {
me->slot[pos] = entry;
}
}
void hash_put_synonym(hash_entry_t* dest, hash_entry_t* entry){
if( !dest || !entry ){ return; }
if( eq(dest->key, entry->key) ){
dest->val = entry->val;
hash_entry_delete(entry);
}else if( !dest->next ){
dest->next = entry;
}else{
hash_put_synonym(dest->next, entry);
}
}
val_t hash_get_synonym(hash_entry_t* dest, const char* key){
if( eq(dest->key, key) ){
return dest->val;
}
return ( dest->next ) ? hash_get_synonym(dest->next, key) : hash_nil();
}
val_t hash_nil() {
val_t ret;
ret.type = H_NIL;
ret.val.n = 0;
return ret;
}
int hash_is_nil(val_t v){
return v.type == H_NIL;
}
HASH hash_set_i(HASH me, const char* key, int val) { val_t v; v.type = H_INT; v.val.n = val; return hash_set(me, key, v); }
HASH hash_set_c(HASH me, const char* key, char val) { val_t v; v.type = H_CHAR; v.val.ch = val; return hash_set(me, key, v); }
HASH hash_set_l(HASH me, const char* key, long val) { val_t v; v.type = H_LONG; v.val.l = val; return hash_set(me, key, v); }
HASH hash_set_d(HASH me, const char* key, double val){ val_t v; v.type = H_DOUBLE; v.val.d = val; return hash_set(me, key, v); }
HASH hash_set_p(HASH me, const char* key, void* val) { val_t v; v.type = H_PTR; v.val.pt = val; return hash_set(me, key, v); }
int hash_get_i(HASH me, const char* key){ val_t v = hash_get(me, key); return v.val.n; }
char hash_get_c(HASH me, const char* key){ val_t v = hash_get(me, key); return v.val.ch; }
long hash_get_l(HASH me, const char* key){ val_t v = hash_get(me, key); return v.val.l; }
double hash_get_d(HASH me, const char* key){ val_t v = hash_get(me, key); return v.val.d; }
void* hash_get_p(HASH me, const char* key){ val_t v = hash_get(me, key); return v.val.pt; }