哈稀处理

#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)))