[转]libhash中的哈希函数

/*
*AustralianPublicLicenceB(OZPLB)
*
*Version1-0
*
*Copyright(c)2004NationalICTAustralia
*
*Allrightsreserved.
*
*Developedby:Embedded,Real-timeandOperatingSystemsProgram(ERTOS)
*NationalICTAustralia
* http://www.ertos.nicta.com.au
*/

#ifndef_HASH_H
#define _HASH_H

#include < stdint.h >

struct hashtable{
struct hashentry ** table;
unsigned int size;
struct hashentry * spares;
};

struct hashentry{
struct hashentry * next;
uintptr_tkey;
void * value;
};

struct hashtable * hash_init(unsigned int size);
void hash_free( struct hashtable * tablestruct);
uintptr_thash_hash(uintptr_tkey);
void * hash_lookup( struct hashtable * tablestruct,uintptr_tkey);
int hash_insert( struct hashtable * tablestruct,uintptr_tkey, void * value);
void hash_remove( struct hashtable * tablestruct,uintptr_tkey);

#endif /*!_HASH_H*/

#include < stdint.h >
#include < stdlib.h >
#include < assert.h >

#include " hash.h "

struct hashtable *
hash_init(unsigned int size)
{
struct hashtable * tablestruct;
int counter;

/* Ourhashfunctiononlyworkswithpower-of-2bucketsizesforspeed. */
assert((size & (size - 1 )) == 0 );

tablestruct = malloc( sizeof ( struct hashtable));assert(tablestruct);
if ( ! tablestruct){
return NULL;
}
tablestruct -> table = malloc(size * sizeof ( struct hashentry * ));
if ( ! tablestruct -> table){
return NULL;
}
for (counter = 0 ;counter < size;counter ++ ){
tablestruct -> table[counter] = NULL;
}
assert(tablestruct -> table);
tablestruct -> size = size;
tablestruct -> spares = NULL;

return tablestruct;
}

/* Ref http://www.concentric.net/ ~Ttwang/tech/inthash.htm */
uintptr_t
hash_hash(uintptr_tkey)
{
#if (UINTPTR_MAX==UINT32_MAX)
key += ~ (key << 15 );
key ^= (key >> 10 );
key += (key << 3 );
key ^= (key >> 6 );
key += ~ (key << 11 );
key ^= (key >> 16 );
#elif (UINTPTR_MAX==UINT64_MAX)
key += ~ (key << 32 );
key ^= (key >> 22 );
key += ~ (key << 13 );
key ^= (key >> 8 );
key += (key << 3 );
key ^= (key >> 15 );
key += ~ (key << 27 );
key ^= (key >> 31 );
#else
#error unsupportedwordsize
#endif
// printf("newkeyis%d ",key);
return key;
}

void *
hash_lookup( struct hashtable * tablestruct,uintptr_tkey)
{
uintptr_thash;
struct hashentry * entry;

hash = hash_hash(key) & (tablestruct -> size - 1 );
for (entry = tablestruct -> table[hash];entry != NULL;entry = entry -> next){
if (entry -> key == key){
return entry -> value;
}
}
return NULL;
}

/* Addthekeytothehashtable.Assumesthekeyisnotalreadypresent. */
int
hash_insert( struct hashtable * tablestruct,uintptr_tkey, void * value)
{
uintptr_thash;
struct hashentry * entry;

hash = hash_hash(key) & (tablestruct -> size - 1 );
// printf("bucketis%d ",hash);

entry = malloc( sizeof ( struct hashentry));
if ( ! entry){
return - 1 ;
}
entry -> key = key;
entry -> value = value;
entry -> next = tablestruct -> table[hash];

tablestruct -> table[hash] = entry;
return 0 ;
}

/* Removesthekeyfromthehashtable.Doesnotsignalanerrorifthekey
*wasnotpresent. */
void
hash_remove( struct hashtable * tablestruct,uintptr_tkey)
{
uintptr_thash;
struct hashentry * entry, * tmpentry;

hash = hash_hash(key) & (tablestruct -> size - 1 );
entry = tablestruct -> table[hash];
/* Ifthisisthefirstentrythenitneedsspecialhandling. */
if (entry && entry -> key == key){
tmpentry = entry -> next;
free(entry);
tablestruct -> table[hash] = tmpentry;
} else {
while (entry){
if (entry -> next && entry -> next -> key == key){
tmpentry = entry -> next;
entry -> next = entry -> next -> next;
free(tmpentry);
break ;
}
entry = entry -> next;
}
}
}

#include < stdint.h >
#include < stdlib.h >

#include " hash.h "

void
hash_free( struct hashtable * tablestruct)
{
int counter;
struct hashentry * entry, * prev;

/* Needtofreebucketsandtablestructandeveryitemineverychain */
for (counter = 0 ;counter < tablestruct -> size;counter ++ ){
entry = tablestruct -> table[counter];
while (entry){
prev = entry;
entry = entry -> next;
free(prev);
}
}
free(tablestruct -> table);
free(tablestruct);
}