#include
#ifdef DMALLOC
#include
#else
#include
#endif
#include "hash.h"
#ifndef __USE_ISOC99
#define inline
#endif
struct hashentry
{
void *key;
void *data;
struct hashentry *next;
};
struct _hashtable
{
unsigned int (*gethash)(void *);
int (*compare)(void *, void *);
int hashsize;
int count;
struct hashentry **hashlist;
};
#define hashindex(key, tab) ((tab->gethash)(key) % (tab->hashsize -1))
/**************************************
** *
** 通过src字符串获取一个32位的key值 *
** *
**************************************/
unsigned int lh_strhash(void *src)
{
int i, l;
unsigned long ret = 0;
unsigned short *s;
char *str = (char *)src;
if(str == NULL)
{
return(0);
}
l = (int)(strlen(str) + 1) / 2;
s = (unsigned short *)str;
for(i = 0; i < l; i++)
{
ret ^= s[i] << (i & 0x0f);
}
return(ret);
}
int equal_str(void *k1, void *k2)
{
return (0 == strcmp((char *)k1, (char *)k2));
}
struct hashentry *hashentry_new(void *key, void *data)
{
struct hashentry *new = malloc(sizeof(struct hashentry));
new->key = key;
new->data = data;
new->next = NULL;
return new;
}
struct hashentry *hashentry_free(struct hashentry *h)
{
struct hashentry *next = h->next;
free(h->key);
free(h->data);
free(h);
h = NULL;
return (next);
}
void hlist_append(struct hashentry **root, void *key, void *data)
{
struct hashentry *l, *pos;
l = hashentry_new(key, data);
if(*root == NULL)
{
*root = l;
}
else
{
for(pos = *root; pos->next != NULL; pos = pos->next);
{
pos->next = l;
}
}
}
int hlist_update(struct hashentry *root, void *key, void *data, int (*compare)(void *, void *))
{
struct hashentry *pos;
for(pos = root; pos != NULL; pos = pos->next)
{
if(compare(key, pos->key))
{
free(pos->data);
pos->data = data;
free(key);
return 0;
}
}
return -1;
}
int hlist_remove(struct hashentry **root, void *key, int (*compare)(void *,void *))
{
struct hashentry *pos, *prev;
if (NULL == *root) return -1;
if (compare((*root)->key, key))
{
*root = hashentry_free(*root);
return 0;
}
prev = *root;
for (pos = prev->next; NULL != pos; pos = pos->next)
{
if (compare(pos->key, key))
{
prev->next = hashentry_free(pos);
return 0;
}
prev = pos;
}
return -1;
}
hashtable *hash_create(unsigned int (*keyfunc)(void *),
int (*comparefunc)(void *, void *),
int size)
{
int i;
int len = (int)sizeof(struct hashentry *) * size;
hashtable *tab = malloc( sizeof(hashtable) );
memset(tab, 0, sizeof(hashtable));
tab->hashlist = malloc((size_t)len);
if (tab->hashlist == NULL)
{
free(tab);
return NULL;
}
memset(tab->hashlist, 0, (size_t)len);
for (i = 0; i < size; i++)
{
tab->hashlist[i] = NULL ;
}
tab->compare = comparefunc;
tab->gethash = keyfunc;
tab->hashsize = size;
tab->count = 0;
return tab;
}
void hash_free(hashtable *tab)
{
int i;
struct hashentry *pos;
for (i = 0; i < tab->hashsize; i++)
{
for (pos = tab->hashlist[i]; NULL != pos; pos = hashentry_free(pos));
}
free(tab->hashlist);
free(tab);
tab =NULL;
}
void hash_insert(void *key, void *data, hashtable *tab)
{
unsigned int index = hashindex(key, tab);
struct hashentry *root = tab->hashlist[index];
if ( hlist_update(root, key, data, tab->compare ) != 0 ) { //(1)
hlist_append(&(tab->hashlist[index]), key, data );
tab->count++;
}
}
//(1) 查看Hash Table中是否存在键值为key的项，
//如果有则替换该键值所对应的value，
//否则调用hlist_append为key, data生成新的hashentry并插入相应的队列中。
void hash_remove(void *key, hashtable *tab)
{
unsigned int index = hashindex(key, tab);
if (hlist_remove(&(tab->hashlist[index]), key, tab->compare) == 0)
{
tab->count--;
}
}
void *hash_value(void *key, hashtable *tab)
{
struct hashentry *pos;
unsigned int index = hashindex(key, tab);
for (pos = tab->hashlist[index]; NULL != pos; pos = pos->next)
{
if (tab->compare(key, pos->key))
{
return (pos->data);
}
}
return NULL;
}
void hash_for_each_do(hashtable *tab, int(cb)(void *, void *))
{
int i = 0;
struct hashentry *pos;
for (i = 0; i < tab->hashsize; i++)
{
for (pos = tab->hashlist[i]; NULL != pos; pos = pos->next )
{
cb(pos->key, pos->data);
}
}
}
int hash_count(hashtable *tab)
{
return tab->count;
}
==================================================================
SHA-1 的描述
以下是 SHA-1 算法的伪代码：
(Initialize variables:)
a = h0 = 0x67452301
b = h1 = 0xEFCDAB89
c = h2 = 0x98BADCFE
d = h3 = 0x10325476
e = h4 = 0xC3D2E1F0
(Pre-processing:)
paddedmessage = (message) append 1
while length(paddedmessage) mod 512 <> 448:
paddedmessage = paddedmessage append 0
paddedmessage = paddedmessage append (length(message) in 64-bit format)
(Process the message in successive 512-bit chunks:)
while 512-bit chunk(s) remain(s):
break the current chunk into sixteen 32-bit words w(i), 0 <= i <= 15
(Extend the sixteen 32-bit words into eighty 32-bit words:)
for i from 16 to 79:
w(i) = (w(i-3) xor w(i-8) xor w(i-14) xor w(i-16)) leftrotate 1
(Main loop:)
for i from 0 to 79:
temp = (a leftrotate 5) + f(b,c,d) + e + k + w(i) (note: all addition is mod 2^32)
where:
(0 <= i <= 19): f(b,c,d) = (b and c) or ((not b) and d), k = 0x5A827999
(20 <= i <= 39): f(b,c,d) = (b xor c xor d), k = 0x6ED9EBA1
(40 <= i <= 59): f(b,c,d) = (b and c) or (b and d) or (c and d), k = 0x8F1BBCDC
(60 <= i <= 79): f(b,c,d) = (b xor c xor d), k = 0xCA62C1D6
e = d
d = c
c = b leftrotate 30
b = a
a = temp
h0 = h0 + a
h1 = h1 + b
h2 = h2 + c
h3 = h3 + d
h4 = h4 + e
digest = hash = h0 append h1 append h2 append h3 append h4
注意：FIPS PUB 180-1 展示的构想，用以下的公式替代可以增进效能：
(0 <= i <= 19): f(b,c,d) = (d xor (b and (c xor d)))
(40 <= i <= 59): f(b,c,d) = (b and c) or (d and (b or c)))